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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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