I have to prove

ZF $\vdash$ $\forall \alpha \exists \beta:\beta > \alpha$, where $\alpha, \beta-$ cardinal numbers.

I can prove it only in ZFC. Let's fix some cardinal number $\alpha$. By Cantor's theorem there is no bijection between $\alpha$ and $\mathcal{P}(\alpha)$ (set of all subsets of $\alpha$). Using axiom of choice we can transform $\mathcal{P}(\alpha)$ to a well-ordered set. Then I proved a theorem in ZF that there is an isomorphism between every well-ordered set and some ordinal. Suppose $x \sim \mathcal{P}(\alpha)$. Assume by axiom of specification $$ A = \{z \in x + 1 \mid \exists f: z \to x \land f - \text{bijection}\} $$ $A$ is non-empty and is a subset of a well-ordered set hence it has least element $\beta$. This is our cardinal number. But how to avoid axiom of choice?

  • 2
    $\begingroup$ See Hartogs number. $\endgroup$ – Brian M. Scott Apr 9 '15 at 21:33
  • $\begingroup$ Agree with Brain, the main point is to construct some "larger" well ordered set. $\endgroup$ – Salomo Apr 9 '15 at 21:34
  • $\begingroup$ @BrianM.Scott, I'm doing practically the same thing. Is there an easier proof in ZFC? $\endgroup$ – Jihad Apr 9 '15 at 21:36
  • $\begingroup$ @Jihad: What you’re doing is quite a bit different from the proof of the Hartogs theorem without $\mathsf{AC}$, though there are certainly some commonalities. With $\mathsf{AC}$ I don’t think that you can get much simpler than the argument that you already have. $\endgroup$ – Brian M. Scott Apr 9 '15 at 21:42

Assuming $\sf ZF$ we can prove Hartogs theorem. Namely, for every set $X$ there exists a set $A$ and a well-ordering of $A$ such that there is no injection from $A$ into $X$.

The proof does not use the axiom of choice. It goes by considering all the well-orders whose domain is a subset of $X$, then considering the equivalence classes under the order isomorphism relation, then noting that this gives us a well-ordered set, and we can prove it cannot be injected into $X$. Nowhere we use the axiom of choice.

Assuming $\sf ZF$ we can also prove that every well-ordered set is isomorphic to a unique von Neumann ordinal.

Here we don't use the axiom of choice as well. We use transfinite recursion, and essentially prove a particular case for the Mostowski collapse lemma (which also does not use the axiom of choice). We construct the ordinal by transfinite recursion on the given well-order. There is no need for choice here either.

Combine the two, and there you have it. Given any ordinal $\alpha$, there is some ordinal $\beta$ such that $|\alpha|<|\beta|$.


Since you seem to already have considerable information about ordinal numbers, you might use the following proof of Hartogs's theorem, which seems slightly more efficient than Asaf's because you don't need to well-order equivalence classes. Given $X$, there is a set $W$ of all well-orderings of subsets of $X$. Each such well-ordering is isomorphic to a unique ordinal. So, by the axiom of replacement, these is a set $Y$ consisting of all the ordinals that are isomorphic to members of $W$. Since there is no set containing all the ordinals, there is an ordinal $\alpha\notin Y$. This $\alpha$ cannot be mapped one-to-one into $X$, because such a map $f$ would be an isomorphism from $\alpha$ to the range of $f$ suitably well-ordered.

  • $\begingroup$ I actually thought about making that remark. It is essentially reversing the two theorems I mentioned, which can simplify the proof of Hartogs' theorem. I am, however, a fan of understanding the broader context in which we avoid replacement. $\endgroup$ – Asaf Karagila Apr 9 '15 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.