# The cardinality of the set of all finite subsets of an infinite set

Let $X$ be an infinite set of cardinality $|X|$, and let $S$ be the set of all finite subests of $X$. How can we show that Card($S$)$=|X|$? Can anyone help, please?

-
same question: physicsforums.com/showthread.php?t=249076 –  PEV Mar 15 '11 at 3:18

The cardinality is at least $|X|$, since $S$ contains all singletons.

Let $S_n$ be the subset of $S$ consisting of all subsets of cardinality exactly $n$. Then $S$ is the disjoint union of the $S_n$.

Now, for any positive integer $n$, the number of subsets of $X$ of cardinality $n$ is at most $|X|^n = |X|$ (equality since $|X|$ is infinite); because an $n$-tuple of elements of $X$ determines a subset of $X$ of cardinality at most $n$; and every subset with $n$ elements determines only finitely many distinct $n$-tuples of elements of $X$ (namely, $n!$). So $|S_n|\leq n!|X|^n = |X|$ for all $n$.

Therefore: \begin{align*} |X| &\leq |S| = \left|\bigcup_{n=0}^{\infty} S_n\right| = \sum_{n=0}^{\infty}|S_n|\\ &= \sum_{n=1}^{\infty}|S_n| \leq \sum_{n=1}^{\infty}|X|\\ &= \aleph_0|X| = |X|, \end{align*} with the last equality since $|X|\geq\aleph_0$.

Thus, $|X|\leq |S|\leq |X|$, so $|S|=|X|$.

-
Do I have it right that this requires some choice, as in the absence of AC, the reals could be a countable union of countable sets? –  Ross Millikan Mar 15 '11 at 4:02
@Ross: I don't think so. In the absence of AC, you do not know that a countable union of countable sets is countable (the fact that $\mathbb{R}$ may be a countable union of countable sets show shows such unions need not be countable without AC). Here, we are assuming $X$ has a cardinal, and cardinal arithmetic does not usually require AC. Though I worked with $X$, you could simply work with the corresponding cardinals, which are already well-ordered, so that should allow you to avoid AC. But if we don't assume $X$ has a cardinality, I expect $S$ does not either. –  Arturo Magidin Mar 15 '11 at 4:05
@Arturo: Thank you very much. –  yaa09d Mar 15 '11 at 4:22
In Schecter's Handbook of Analysis and its Foundations, comparability of all cardinals is equivalent to AC (pg 145) –  Ross Millikan Mar 15 '11 at 4:28
@Arturo, as far as I've seen the term cardinality means the equivalence class under the relation "there exists a bijection", while assuming AC it reduces to $\aleph$ numbers, and without AC it becomes a different beast altogether. –  Asaf Karagila Mar 15 '11 at 13:55