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?)
 A: 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:


*

*$0 = \emptyset$

*$\alpha+1 = \alpha \cup \{\alpha\}$

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