# Set of Finite Subsets of an Infinite Set (Enderton, Chapter 6.32)

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.

1. 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)$.
2. 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.

-

The maximality of $f$ isn't enough to show that the domain of the function is $F(A)$. It it enough to tell you just the fact that either the domain is $F(A)$ or the range is $A$.

This is because if you can find $x\in A$ and $y\in F(A)$ such that $y\notin dom(f)$ and $x\notin ran(f)$ then you can extend $f$ to $f\cup\{(y,x)\}$. But it may be possible that the domain of this maximal function is a proper subset of $F(A)$ while its range is $A$ and therefore it is impossible to extend this function inside $H$ since you require the functions to be $1-1$.

As Asaf points out the problem (assuming choice) is very easy. You just observe that $\kappa\times\kappa=\kappa$ for all cardinals and by using that you get that $\kappa^n=\kappa$ and $\aleph_0\times\kappa=\kappa$ which is enough to show what you want.

-
Since he is using Zorn's llama to trek up the mountain of functions, he is already using choice. So it's no big deal. Without choice I am fairly certain it is a simple exercise to generate $A$ such that $|A|\lneqq |Fin(A)|$. – Asaf Karagila May 11 '11 at 16:41
@Asaf: Indeed Zorn's lemon is equivalent to choice (and sour), I just wanted to emphasize the use of choice. And without choice you cannot even guarantee that $|[A]^2|=|A|$ (I think). – Apostolos May 11 '11 at 17:13
+1 for both comments, and for you clever use of llama, lemon (aka lemma!) – amWhy May 11 '11 at 19:47

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

-