Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
3  
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
3  
@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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.