4
$\begingroup$

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.

  • 0
    How is it possible to use Axiom X in a proof without using any consequences of Axiom X? (At least the instructor should have written "_proper_ consequences".)2012-03-03

3 Answers 3

4

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)$.
  • 0
    @Daniel: Perhaps. But that's easy: It is clear by construction that $\{f(\beta)\mid \beta\in\alpha\}\subseteq A$ -- but if they are equal then $f$ restricted to $\alpha$ must be a _bijection_ $\alpha\to A$, and since \alpha<\omega_1 it is by definition at most countable.2012-03-03
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$.

  • 0
    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.2012-03-03
2

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