# Looking for a complete exposition of the Burali-Forti paradox

In the context of ZFC, one normally uses von Neumann's definition of the ordinals. However, originially an ordinal was just the order-type of a well-ordered set (where "order-type of A" may for example be defined to be the equivalence class of all ordered sets that are order-isomorphic to A; this definition is of course no longer allowed in ZFC, but was common in pre-ZFC naive set theory).

I am now looking for a complete exposition of Burali-Forti paradox, with the original definition of ordinal. One can in a number of papers and books find expositions similar to the following one cited from Wikipedia:

"The "order types" (ordinal numbers) themselves are well-ordered in a natural way, and this well-ordering must have an order type Ω. It is easily shown in naïve set theory (and remains true in ZFC but not in New Foundations) that the order type of all ordinal numbers less than a fixed α is α itself. So the order type of all ordinal numbers less than Ω is Ω itself. But this means that Ω, being the order type of a proper initial segment of the ordinals, is strictly less than the order type of all the ordinals, but the latter is Ω itself by definition. This is a contradiction."

To complete this exposition, we need proofs for the following two facts:

• The ordinals are well-ordered under their natural ordering.
• The order type of all ordinal numbers less than a fixed α is α itself.

The book "Grundbegriffe der Mengenlehre" by Gerhard Hessenberg (1906) (which can be read online at http://www.archive.org/stream/grundbegriffede00hessgoog#page/n79/mode/1up) presents proofs for these facts, which to me however seem invalid (I do not understand why he may conclude "und umgekehrt ist jeder Zahl ν<μ ein Abschnitt in M eindeutig zugeordnet" on page 550).

I have found a complicated proof for the first fact, which however is based on induction (over the natural numbers) and three applications of the Axiom of Choice. It seems to me that the second fact may be proven using transfinite induction (transfinite induction, it seems to me, may only be used once one has established the first fact). So in principle, I think I can complete the Burali-Forti paradox as stated above, but this completed derivation would be very lengthy and involved.

So what I am actually looking for is a more concise or less involved complete derivation of the Burali-Forti paradox. Can anyone present such a derivation here, or point me to an existing one in the literature?

-
None of these results require any form of choice. The main things you need to show are the following: if a well-ordered set X has an order-preserving injection into a well-ordered set Y, then there is a unique such injection whose image is an initial segment of Y. If X, Y are well-ordered sets, there is either an order-preserving injection from X to Y or an order-preserving injection from Y to X. To do this you need a precise form of definition by recursion. Anyway, I would expect this material to be in many standard books. –  Qiaochu Yuan Nov 25 '10 at 17:21
I do disagree with one part of Qiaochu's comment. I am pretty sure that, when I was thinking this all through a few years ago, I never did need to come up with a precise form of definition by recursion. I wrote up the initial, and hardest, steps below; I'm curious when I will need to use because it hasn't happened yet. –  David Speyer Nov 25 '10 at 18:13

So, an awkward admission. I've never actually read a basic intro to ZFC, nor taken a course on the subject. So, while I suspect this can all be found in any basic text, I don't know which one to refer you to.

But it isn't hard to do all of this by hand, just tedious. I'll get you to the point of showing that ordinals, by your definition, are totally ordered. I think that's the part which is most different from the Von Neummann ordinal case. The rest is not too much more difficult, and I assume someone will be recommending a textbook soon anyway.

We'll write $X \preceq Y$ if $X$ and $Y$ are well ordered sets and there is an order preserving bijection between $X$ and an initial segment of $Y$.

Lemma 1 If $X$ and $Y$ are well ordered sets, there is at most one order preserving injection $X \to Y$ whose image is an initial interval.

Proof: Suppose there were two, call them $\phi_1$ and $\phi_2$. Since they are not the same, there is some smallest $x \in X$ such that $\phi_1(x) \neq \phi_2(x)$ (using that $X$ is well ordered). Let $Y' = \{ \phi_1(x'): x' < x \}$. Since $\phi_1(x) \not \in Y'$, the set $Y \setminus Y'$ is not empty, let its least member be $y$. Then either $\phi_1(x)$ or $\phi_2(x)$ is not $y$; say WLOG $\phi_1(x) \neq y$. Since $\phi_1(x) \not \in Y'$, we deduce that $\phi_1(x) > y$. Now, consider any $x' \in X$. If $x' < x$, then $\phi_1(x') \in Y'$ and $\phi_1(x') \neq y$; if $x' \geq x$ then $\phi_1(x') \geq \phi_1(x) > y$. So $y$ is not in the image of $\phi_1$, but $\phi_1(x) >y$ is. This contradicts that the image of $\phi_1$ is an initial interval. QED

We'll write $X \preceq_{\phi} Y$ to mean that $\phi$ is an order preserving map $X \to Y$ whose image is an initial segment. So $X \preceq Y$ if and only if $X \preceq_{\phi} Y$ for some $\phi$.

Corollary: If $X \preceq Y$ and $Y \preceq X$ then $X$ and $Y$ are isomorphic posets.

Proof: Let $X \preceq_{\phi} Y$ and $Y \preceq_{\psi} X$. Then $X \preceq_{\psi \circ \phi} X$. But also $X \preceq_{\mathrm{Id}} X$. So $\psi \circ \phi = \mathrm{Id}$. Similarly, $\phi \circ \psi = \mathrm{Id}$. So $\phi$ and $\psi$ are mutually inverse order preserving maps. QED

Thus, we see that that the ordinals are partially ordered under $\preceq$. (Of course, expressing this concept takes us out of the language of ZFC, since it is a statement about classes.) We will next show that this partial order is total.

Prop 2 Let $X$ and $Y$ be well ordered sets. Then either $X \preceq Y$ or $Y \preceq X$.

Proof: Consider $X' := \{ x \in X : X_{\leq x} \preceq Y \}$.

Consider the follow subset of $X' \times Y$:

$$\Phi = \{ (x,y) : \ \exists x' \in X,\ x \leq x',\ \exists \phi:\ X_{\leq x'} \preceq_{\phi} Y \ \mbox{and} \ y=\phi(x) \}$$

We claim that $\Phi$ is a function. In other words, we claim that, for each $x \in X'$, there is exactly one $y$ such that $(x, y) \in \Phi$. There is at least one such $y$ because we can take $x'=x$ and, by the definition of $X'$, there will be map $\phi$ such that $X_{\leq x} \preceq_{\phi} Y$; take $y= \phi(x)$. To see that there is not more than one $y$ above $x$, suppose that there were $y_1$ and $y_2$. They would correspond to some $(x'_1, \phi_1)$, $(x'_2, \phi_2)$. (No axiom of choice here, I'm only making finitely many choices!) WLOG, say $x'_1 \leq x'_2$. Let $\phi'_2$ be the restriction of $\phi_2$ to $X_{\leq x'_1}$. Then $X_{\leq x'_1} \preceq_{\phi_1} Y$ and $X_{\leq x'_1} \preceq_{\phi'_2} Y$. So, by lemma 1, $\phi_1=\phi'_2$. Then $\phi_1(x) = \phi'_2(x)$ which is to say, $y_1=y_2$.

So, $\Phi$ is a function. It is now easy to check (details left to you) that $X' \preceq_{\Phi} Y$. If $X=X'$, we are done. If not, let $Y' = \Phi(X')$. If $Y=Y'$, then $\Phi$ is injective and surjective, so its inverse is a function and we have $Y \preceq_{\Phi^{-1}} X$. If $X \neq X'$ and $Y \neq Y'$, then let $x$ and $y$ be the minimal elements of $X \setminus X'$ and $Y \setminus Y'$ (since $X$ and $Y$ are well ordered). Define $\phi'$ on $X_{\leq x}$ to be $\phi$ on $X_{<x} = X'$ and by $\phi(x)=y$. Then $\phi$ is easily checked to be order preserving and have image an initial interval, so $X_{\leq x} \preceq Y$. This contradicts that we took $x$ not to be in $X'$, and we are done. QED

At this point, we see that equivalence classes of well-ordered sets form a total order under $\preceq$.

-
Your proof of Proposition 2 essentially repeats the formal proof of definition by recursion that I saw when this material was first presented to me. I think the proof is slightly cleaner if this principle is abstracted out and proven separately, but it doesn't make too much of a difference. –  Qiaochu Yuan Nov 25 '10 at 18:59
@David : I am not sure I understand what you mean by "Of course, expressing this concept takes us out of the language of ZFC, since it is a statement about classes." It seems obvious to me how to express this in ZFC. Perhaps I'm overlooking some subtlety? –  Andres Caicedo Nov 26 '10 at 16:48
What I was thinking was that I couldn't say "For $\mathcal{X}$ and $\mathcal{Y}$ any two equivalence classes of well ordered sets, either $X \preceq Y$ for all $X \in \mathcal{X}$ and $Y \in \mathcal{Y}$, or vice versa." Maybe I introduced more confusion than I removed, though. –  David Speyer Nov 26 '10 at 17:32

I have now found a textbook that provides a complete proof of the Burali-Forti paradox without making use of von Neumann's definition of ordinals: "Basic Set Theory" by Azriel Levy. Before providing von Neumann's definition, he works just on the assumption that some "order types" can be defined such that the order type of two well-ordered sets is identicall iff they are order-isomorphic. Based only on this assumption, and, importantly for my concern, without using the Axiom of Foundation, he shows that the class of ordinals cannot be a set.

-