# finite subsets proof

If $$A$$ is an infinite set then $$\mathcal{F}(A),$$ the set of finite subsets of $$A$$ has the same cardinality as $$A$$. Is the following proof of the above fact correct?

Note that $$|A_k|\leq |A^k|$$ for any $$k\geq 0,$$ where $$A_k$$ is the set of subsets of $$A$$ of cardinality $$k$$ since the map $$f : A_k\to A^k, f(\{a_1,\cdots, a_k\}) = (a_1,\cdots, a_k)$$ is injective (indeed for two different subsets, at least one element differs, so that element will be mapped to a different tuple by $$f$$). Then $$\mathcal{F}(A) = \cup_{k\geq 0} A_k$$, which is a disjoint union as $$A_i \cap A_j = \emptyset$$ for $$i\neq j$$ (the cardinality of a finite set is unique). So $$|\mathcal{F}(A)| = \sum_{k\geq 0} |A_k| \leq \sum_{k\geq 0}|A^k| = \sum_{k\geq 1}|A^k| = \sum_{k\geq 1} |A| = \aleph_0 |A|$$. Also, $$g : A\to A_1, g(a) = \{a\}$$ is clearly a bijection, so $$|A| = |A_1| \leq |\mathcal{F}(A)|$$ as $$A_1\subseteq \mathcal{F}(A)$$ and if $$B\subseteq A$$ then there is clearly an injective (identity) function from $$B$$ to $$A.$$ So $$|\mathcal{F}(A)| = |A|$$ by transitivity (for infinite sets this also applies).

## 1 Answer

Small issue: the function $$f : A_k \to A^k$$ you wrote down is not well-defined! For example, should $$f(\{2,3\}) = f(\{3,2\})$$ be $$(2,3)$$ or $$(3,2)$$? You gave no way to decide. You could try to fix this in a few ways:

1. Put a total order on $$A$$ (if you assume the axiom of choice, this is always possible), and then define $$f$$ so that it lists the elements in ascending order.
2. Put a total order on every element of $$A_k$$ (if you assume the axiom of choice, this is always possible), and then define $$f$$ so that it lists the elements in ascending order.
3. Redesign the argument: instead build a surjection $$A^k \to A_k$$.

To me, approach #3 feels most natural -- there is an "obvious map" $$(a_1, \dots, a_k) \mapsto \{a_1, \dots, a_k\}$$ that feels like it should be a surjection. The only issue is that $$\lvert \{a_1, \dots, a_k\} \rvert$$ need not equal $$k$$! So we have the wrong codomain: instead, this is a surjection $$A^k \to A_{\leq k}$$. This shows $$\lvert A_{\leq k} \rvert \leq \lvert A^k \rvert$$, and we also have $$\lvert A_k \rvert \leq \lvert A_{\leq k} \rvert$$, so transitively $$\lvert A_k \rvert \leq \lvert A^k \rvert$$.

Another small issue: you definitely showed $$\lvert \mathcal{F}(A) \rvert \leq \aleph_0 \lvert A \rvert$$, and that $$\lvert A \rvert \leq \lvert \mathcal{F}(A) \rvert$$. For your proof to be complete, you should say somewhere that $$\aleph_0 \lvert A \rvert = \lvert A \rvert$$.

Edit: as a side note, I should also mention that it's necessary to assume the axiom of choice here: choice is equivalent to the claim that $$a^2 = a$$ for all infinite cardinals $$a$$, and if we had $$\lvert A \rvert^2 > \lvert A \rvert$$ here the claim would be false.