Exercise 6.32 (Enderton, Elements of Set Theory) (answer to same question) states:
Let $\mathsf{F}(A)$ be the set of all finite subsets of $A$. Show that if $A$ is infinite then $A \approx \mathsf{F}(A)$.
For the purposes of this exercise, I could use the approach cited. However, I want to know what is wrong with the attempt (2) I made. I will describe it informally.
- If $|A| = \aleph_0$ then the injection $f(x) = \{x\} : A \rightarrow \mathsf{F}(A)$ gives $|A| \leq |\mathsf{F}(A)|$. Conversely, the bijections $f : \omega \rightarrow A$ and $g : \bigcup_{i \in \omega} \omega^i \rightarrow \omega$ (i.e., a tupling function) can be composed to obtain an injection $f : \mathsf{F}(A) \rightarrow A$. So $|\mathsf{F}(A)| \leq |A|$. By the Schroder-Bernstein Theorem, $|A| = |\mathsf{F}(A)|$ and $A \approx \mathsf{F}(A)$.
- If not, I want to do the following: (i) define a set $H$ of bijections from subsets of $\mathsf{F}(A)$ to subsets of $A$; (ii) show that $H$ is closed under union of chains ($\bigcup B : \mathsf{F}(A) \rightarrow A$ is bijective where $B$ is a chain in $H$); (iii) employ Zorn's Lemma to obtain a maximal function $f \in H$; (iv) conclude that $\mathsf{F}(A) \approx A$. This approach would be very easy, because I could appeal to prior theorems regarding unions of functions and so on.
After step (iii), I need to show that $dom(f) = \mathsf{F}(A)$ and $ran(f) = \mathsf{F}(A)$. So I suppose not and obtain a contradiction due to $f$'s maximality in $H$. However, this is problematic. Why? Because in each attempt that I have made, I can replace the "finite powerset" operator by the powerset operator throughout and obtain a false statement. So I am missing something about $\mathsf{F}(A)$. I'm not sure what this is.
Best Answer
First of all, for the countable case, one does not need this much of a hassle, simply because there is a very nice well ordering of $Fin(\omega)$, namely:
$$\{x_1,\ldots,x_n\}\mapsto\sum_{i=1}^n 2^{x_i}$$
As for the higher cardinalities:
By induction we have $\lambda^n=\lambda$ for all $n<\omega$, and therefore $\lambda\le\lambda\cup\lambda^2\cup\ldots \le\lambda\times\lambda = \lambda$ and clearly every finite subset of $\lambda$ can be found within some $\lambda^n$.
Note, however this requires the axiom of choice, and will not work without it as not always $\lambda+\lambda=\lambda$ and let alone $\lambda\times\lambda$.