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

Question

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

Answer 1

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|$.

Answer 2

This is an old post, but because Arturo's otherwise good answer is a bit cavalier on choice usage and the comments don't make the exact level of choice needed entirely clear, I thought I'd explain my own approach to the question in a ZF framework.

We can establish the following with no well-orderability assumptions:

Lemma: If $X$ is a nonempty set and $X\times X\approx X$ (meaning there is a bijection from $X\times X$ to $X$), then $\bigcup_{n\in\omega}X^n\approx\omega\times X$.

Proof: Fix a bijection $f:X\times X\to X$ and $x_0\in X$. Then we can define

$$g_0:x\in X^0\mapsto x_0$$ $$g_{n+1}:x\in X^{n+1}\mapsto f(g_n(x\restriction n), x_n)$$

Then by induction we have that $g_n$ is an injection from $X^n$ to $X$, and then $$h:x\in\bigcup_{n\in\omega}X^n\mapsto \langle \operatorname{dom}x,g_{\operatorname{dom}x}(x)\rangle$$

is an injection from $\bigcup_{n\in\omega}X^n$ to $\omega\times X$. (We use that $X^n$ for different $n$ are disjoint because $x\in X^n$ implies $x:n\to X$ so that $\operatorname{dom}x=n$.) For the reverse inequality, define

$$j:n\in\omega,x\in X\mapsto(z\in n+1\mapsto x).$$

Then if $j(n,x)=j(m,y)$ we have $(z\in n+1\mapsto x)=(z\in m+1\mapsto y)$ so the domains of the functions are equal, i.e. $n+1=m+1\Rightarrow n=m$, and also $x=j(n,x)(0)=j(m,y)(0)=y$.

---

Adding an assumption of well-ordering allows us to simplify the statement to what we are after:

If $X$ is an infinite well-orderable set, then the set $[X]^{<\omega}$ of finite subsets of $X$ is equipollent to $X$.

Proof: Since singletons are in $[X]^{<\omega}$ and naturally bijective with $X$, $X\preceq[X]^{<\omega}$. For the converse, we have $X\times X\approx X$ because $X$ is infinite well-orderable, so by the lemma $$\bigcup_{n\in\omega}X^n\approx\omega\times X\preceq X\times X\approx X;$$ thus $\bigcup_{n\in\omega}X^n$ is also well-orderable, so we can reverse the surjection $f:\bigcup_{n\in\omega}X^n\to[X]^{<\omega}$ which maps each function to its range to get an injection. Thus, $X\preceq [X]^{<\omega}\preceq\bigcup_{n\in\omega}X^n\preceq X$.

Answer 3

The following arguments require the employment of the axiom of choice,
but no further elaboration is given.

Let $X$ be an infinite set and let $S$ be the set of all finite subsets of $X$.

We can write

$$\tag 1 S = \{\emptyset\} \cup \displaystyle \bigcup_{k\ge1} S_k, \quad S_k = \{A \in \mathcal P(X) \mid |A| = k\}$$

We'll show using induction that each $S_k$ is equipotent to $X$.

The singleton mapping shows that $S_1$ equipotent to $X$.

For the inductive step, assume $S_k$ is equipotent to $X$.
Since there exists an injection of $S_k$ into $S_{k+1}$, $|X| \le |S_{k+1}|$.
Moreover, there also exists a surjection of $S_k \times X$ onto $S_{k+1}$. But then by our inductive hypothesis, $|S_{k+1}| \le |X \times X|$. Since $|X \times X|= |X|$, we've shown that $S_{k+1}$ is equipotent to $X$ and we've completed the inductive step.

Since we know that the cardinality of a countable union of equinumerous infinite sets does not increase, we conclude that

$$ |S| = |X|$$

---

Note: I worked on this question wearing 'bijective blinders', but the solution might appear too close to Arturo Magidin's accepted answer to merit a posting, so I've made it Community wiki.