# $\aleph_1\leq A$ for an uncountable set $A$

So we have to prove (axiom of choice is given) that $\aleph_1$ which is the next aleph after $\aleph_0=\omega$ satisfies $$\aleph_1\leq A$$ given that $A$ is uncountable.

Here was my reasoning. The axiom of choice is equivalent to saying that any two cardinalities are comparable. Thus, assume that $A<\aleph_1$, by definition of the alephs, we must have that $|A|=\omega$ which means that $A$ is equinumerous with the naturals, the definition of countable. Hence, by contrapositive we are done.

Is this argument right? The professor said on the midterm we need to use transfinite recursion, but I dont see how.

-
That should be all there is to it (except that $|A|=\omega$ is not quite necessary; it could also be that $A$ is finite). Perhaps the intention of the professor's statement was that you need transfinite induction to prove that any set is equinumerous to an aleph number? –  Henning Makholm Mar 3 '12 at 2:08
It reads: Use the Transifinite Recursion Theorem and the Axiom of Choice (but none of the consequences of Choice) to show that $\aleph_1\leq_c A$ for every uncountable set $A$. –  Daniel Montealegre Mar 3 '12 at 2:13
Maybe you're meant not to use the fact that (assuming AC) any two cardinals are comparable. –  Zach N Mar 3 '12 at 2:20
But that is not a consequence, is something equivalent... Oh geez...I have a bad feeling about this. I did it on my midterm :( –  Daniel Montealegre Mar 3 '12 at 2:23
It’s equivalent, but that means that it’s also a consequence: it was proved from AC. (AC was also proved from it, but that’s beside the point.) By Axiom of Choice in the problem statement your instructor evidently meant whatever form of AC you were given as the basic axiom. –  Brian M. Scott Mar 3 '12 at 2:30

The fact any two cardinalities are comparable is probably one of the consequences of Choice that you're supposed not to use.

It looks more like the expected solution is to use transfinite induction up to $\omega_1$ to explicitly construct an injection $\omega_1\to A$.

With details depending on the exact formulation of AC and transfinite recursion you're using, it would look something like:

1. Fix a choice function $\chi: \mathscr P(A)\setminus\{\varnothing\}\to A$.
2. Define by transfinite recursion a function $f:\omega_1\to A$: $$f(\alpha) = \chi(A\setminus\{f(\beta)\mid \beta\in\alpha\})$$
3. Every $\alpha<\omega_1$ is at most countable, so $\{f(\beta)\mid\beta\in\alpha\}$ is at most countable, so $A\setminus\{f(\beta)\mid \beta\in\alpha\}$ must be nonempty, and the definition makes sense.
4. $f$ is an injection, because if $\beta<\alpha<\omega_1$ then $f(\alpha)$ has explicitly been constructed to differ from $f(\beta)$.
-
How would I do that? –  Daniel Montealegre Mar 3 '12 at 2:22
Answer extended with proof sketch (and proof sketch then simplified in a later edit). –  Henning Makholm Mar 3 '12 at 2:49
Several things aren't clear to me but perhaps it's just the notation. What is $f_0$? –  Patrick Mar 3 '12 at 3:01
Okay, I see it now. –  Patrick Mar 3 '12 at 3:07
Intuitively I see why $A\backslash \{f(\beta)|\beta\in\alpha\}$ is non-empty, because uncountable is bigger than countable, but would I need proof of it? –  Daniel Montealegre Mar 3 '12 at 3:09

Here's a proof that doesn't use the fact that (in the presence of AC) any two cardinals are comparable.

Using transfinite recursion, define a map $f\colon\omega_1\to A$ as follows. By AC, there is a choice function $C$ for the set of nonempty subsets of $A$. Put $f(0) = C(A)$. Suppose $\alpha>0$; assuming $f(\beta)$ is defined for every $\beta<\alpha$, put $f(\alpha) = C(A\smallsetminus\{f(\beta) : \beta<\alpha\})$. Then $f$ is an injection $\omega_1\to A$. $\square$

This is very similar to the proof from AC that every set can be well-ordered: at each stage the choice function $C$ provides a new value for your function $f$.

-
Where do I use the fact that $A$ is uncountable and that $\omega_1$ is the first cardinal after $\omega$? –  Daniel Montealegre Mar 3 '12 at 9:31
The set $A\smallsetminus \{f(\beta) : \beta<\alpha\}$ is only guaranteed to be nonempty when $\alpha$ is countable. So the induction only works up to $\omega_1$, the first uncountable ordinal. –  Zach N Mar 3 '12 at 14:46

Zach’s version is what you’d normally find in practice. Here, in case you need it, is a version that uses the recursion theorem (in one of its common forms) a bit more explicitly:

Let $\xi:\wp(A)\setminus\{\varnothing\}\to A$ be a choice function. Define $\psi:{^{<\omega_1}A}\to A:g\mapsto\xi(A\setminus\operatorname{ran}g)$. The recursion theorem then says that there is a function $f:\omega_1\to A$ such that for each $\alpha<\omega_1$, $f(\alpha)=\psi(f\upharpoonright\alpha)$, and it’s easy to verify by transfinite induction that $f$ is injective.

Here ${^{<\omega_1}A}$ is the set of functions from ordinals less than $\omega_1$ to $A$.

-