Let $A$ be a finite set with cardinality $\lvert A\rvert$. Then is it true that $\sum_{j\in A}1 =\lvert A\rvert$?
Asked
Active
Viewed 72 times
0
-
1What does that $\sum_{j\in A_{k}}$ even mean... – Arctic Char May 29 '21 at 18:23
-
1The title suggests that you're allowing some of the $A_i$s to be empty, but in a partition all pieces are usually required to be nonempty (see here). Note meanwhile that the only sensible value for the "empty sum" $\sum_{i\in\emptyset}1$ is $0$ (we'll want $(\sum_{i\in A}1)+(\sum_{j\in B}1)=\sum_{k\in A\cup B}1$ whenever $A\cap B=\emptyset$); similarly, the"empty product" $\prod_{i\in\emptyset}1$ should be $1$. – Noah Schweber May 29 '21 at 18:23
-
@ArcticChar I suspect that's supposed to be "$\sum_{j\in A_k}1$." – Noah Schweber May 29 '21 at 18:24
-
@ArcticChar To be understood as $\sum_{j\in A_{k}}1$. – Miski123 May 29 '21 at 18:25
-
We don’t need to know what the $A_k$ are, other than that they’re finite sets. $\sum_{j\in A} 1 = |A|$ always. – mjqxxxx May 29 '21 at 18:30
-
@NoahSchweber Makes sense, thanks! – Miski123 May 29 '21 at 18:33
-
@mjqxxxx Fixed now. :) – Miski123 May 29 '21 at 18:33
2 Answers
3
Turning my comment into an answer - surprisingly, I couldn't find a duplicate of this question on this site, although I vividly recall it being asked before:
The answer is yes. For finite $A$s this is obvious; the interesting question is what happens when $A$ is empty:
What is the value of the "empty sum" $\sum_{i\in\emptyset}1$?
The answer (ignoring a minority of authors who require the index set of a sum to be nonempty) is that the empty sum equals $0$. This is more than merely a convention - it is the only possible way to define the empty sum which is at all reasonable. Specifically, one of the key rules about summations is that $$\sum_{i\in A}f(i)+\sum_{j\in B}f(j)=\sum_{k\in A\cup B}f(k)$$ whenever $A\cap B=\emptyset$ (ignoring issues around definedness, e.g. problems with conditional convergence - if you like, require $f$ to only ever output nonnegative values). Since $\emptyset\cap B=\emptyset$ for all $B$ we'll want $$\sum_{i\in\emptyset}f(i)+x=x$$ for all $x$ and $f$, and this pins down the value of the empty sum.
Similarly, the "empty product" $\prod_{i\in\emptyset}1$ is $1$. This is an instance of a more general phenomenon: that "natural" operations often come equipped with overarching properties which yield canonical extensions to larger-than-originally-considered domains (e.g. extending the summation operation from nonempty index sets to include the empty set).
Noah Schweber
- 245,398
1
The identity $$ \sum_{j\in A} 1 =\lvert A\rvert $$ is correct since you are adding a one for every value of $j$ present in the set $A$, which in this case is equivalent to the cardinality of $A$.
Ethan Bolker
- 95,224
- 7
- 108
- 199
Aaron Hendrickson
- 6,042
-
Note however that as far as I'm aware the notation "$\sum_{j\in A}$" is nonstandard; in fact, I've never seen it used. – Noah Schweber May 29 '21 at 18:38
-
@NoahSchweber I have used this notation before without any confusion. The notation under the uppercase sigma is simply directions of what to sum over, which from the context given in the question is clear. It is very similar to the notation under an integral sign when integrating over a set too. – Aaron Hendrickson May 29 '21 at 18:46
-
Fair, I'm a bit surprised. But would you really write $\int_A$ instead of $\int_Adx$ (keeping in mind that "$dx$" should be conflatable with "$1dx$," thinking either about forms or Riemann sums)? – Noah Schweber May 29 '21 at 18:53
-
@NoahSchweber No I would definitely write $\int_A \mathrm dx$ that's why you need to include the variable of summation in this case, i.e. $\sum_{j\in A}$ instead of $\sum_{A}$. Maybe I am misunderstanding you. – Aaron Hendrickson May 29 '21 at 18:57