# Non-existence of a surjection $\aleph_n \to \aleph_{n+1}$, without the axiom of choice

Firstly, let's establish what exactly I mean by these symbols. Let $\omega_0 = \{ 0, 1, 2, \ldots \}$, where $0, 1, 2, \ldots$ are the usual von Neumann representations of the natural numbers. Let $n$ be a finite natural number. For each $n$, define $\omega_{n+1} = \sup S$, where $S$ the image of the set $R$ under the function-class mapping well-orders to their von Neumann ordinal, and $R \subset \mathcal{P}(\omega_n \times \omega_n)$ is the set of all well-orders on $\omega_n$. We define $\aleph_n = \omega_n$.

Unless I'm mistaken, this establishes the existence of $\omega_n$ for all $n \in \mathbb{N}$ as sets under the axioms of ZF. It's straightforward to see that there is no injection $\omega_{n+1} \to \omega_n$, as that would establish (via pullback) that $|\omega_{n+1}| \le \aleph_n$, and this is a contradiction as $\omega_{n+1}$ is strictly greater than all ordinals in $S$. This in turn implies, by the axiom of choice, that there is no surjection $\omega_n \to \omega_{n+1}$, and the conclusion that there is no surjection $\aleph_n \to \aleph_{n+1}$ follows.

My question is: Can this be done, using my definitions above, without the axiom of choice? I'm willing to accept reasonable alternative definitions, provided that they don't render the conclusion tautological.

(This is a self-imposed extension to a homework problem: Should I tag with homework?)

-
Zhen: If there is a surjection $f:\alpha\to\beta$, where $\alpha$ is an ordinal, then there is an injection $\beta\to\alpha$: For each $\gamma\in\beta$ map $\gamma$ to the least element $\delta$ of $\alpha$ with $f(\delta)=\gamma$. No choice is used here. –  Andres Caicedo Jan 2 '11 at 17:02

You've made a very big mess, I think. The way you defined cardinal numbers is very awkward, so to say. In my eyes, anyway.

Let us review the construction of ordinals:

1. $0 = \emptyset$
2. $\alpha+1 = \alpha \cup \{\alpha\}$
3. At limit stages, $\delta = \bigcup_{\beta<\delta} \beta$

Now we define initial ordinals as ordinal numbers which cannot be bijected with any smaller ordinal. For example $\omega$ (the set of natural numbers) is such ordinal, while $\omega+1, \omega+\omega, \omega\cdot\omega$ are not initial ordinals.

Under the axiom of choice, every set is well-orderable, and therefore we can choose the initial ordinal out of each equivalence class as a representative. This is the usual notion of $\aleph$ numbers under the axiom of choice.

Without assuming choice, the cardinal system is not well-ordered and can behave very strangely.

Regardless to that, when you are only dealing with ordinals you don't need choice because there is a canonical choice function (take the minimal element). So even without the axiom of choice it is true that $\omega_\alpha$ has no bijection with $\omega_\beta$ for $\alpha\not=\beta$.

The idea behind aleph numbers, as far as I see it, is that it is a well ordering of cardinalities (not necessarily all cardinalities, though) and as such it holds just fine even when not assuming choice. However, in the case you don't have the axiom of choice to help you out, $2^{\aleph_0}$ might not be well-orderable and thus won't be represented by an ordinal, and therefore won't be represented by an $\aleph$ number, same with multiplication. It is equivalent to the axiom of choice that for every infinite set $|X| = |X\times X|$.

Just last remark, you said that the construction you gave infers the existence of $\aleph_n$ for every natural number $n$ while in fact it gives you $\aleph_\alpha$ for every ordinal $\alpha$ and not just for the natural numbers.

-
I'm confused. I don't see any difference between your definitions and mine? For what it's worth, I'm defining $\aleph_n = | \omega_n |$ and I'm fairly certain that my definition of $\omega_n$ shows that it's initial without invoking AC, so we have $\aleph_n = \omega_n$. –  Zhen Lin Jan 2 '11 at 9:42
Zhen, yours is the same really, but it felt very cluttered to me. –  Asaf Karagila Jan 2 '11 at 9:46
Ah. Well, in any case, your observation that there's a canonical choice function when sets of ordinals are involved gave me an idea on how to complete the proof. Thanks. –  Zhen Lin Jan 2 '11 at 10:07
@Cameron: Thanks. –  Asaf Karagila Apr 21 '13 at 16:40
On an unrelated note, this one of the first answers I wrote about AC, oh how little did I know back then and how clumsy was my understanding back then... sigh good times! –  Asaf Karagila Apr 21 '13 at 16:41

How are you surpassing AOC in assuming the existence of well orderings?

I'm not quite clear what your definition of \aleph_n is. Is it the nth cardinal number (is that what a Von Neumann ordinal is?)?

-
Let $r \in \mathcal{P}(\omega_n \times \omega_n)$. Then the predicate "$r$ is a well-ordering" is expressible in the language of ZF, so by the axiom of separation I can form the subset of well-orderings of $\omega_n$. $\aleph_n$ is defined as the cardinality of $\omega_n$, and I am defining the cardinality of a set to be the least ordinal which well-orders it. (I suppose this is equivalent to the axiom of choice, but it's irrelevant for alephs, I think.) –  Zhen Lin Jan 2 '11 at 8:47
This should be a comment to the question, but since the answer has no owner (Lashi Bandara has been removed), it can't be converted to a comment. –  robjohn Nov 5 '12 at 23:26
@robjohn: I feel that this thread won't be missing much by removing this altogether. –  Asaf Karagila Nov 5 '12 at 23:33
@AsafKaragila: I have no reason to doubt you, but I will defer to another mod who has more knowledge here, or to the community voting to delete. I also think Zhen Lin's response might be worth saving. –  robjohn Nov 5 '12 at 23:46