5
$\begingroup$

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?

$\endgroup$
4
  • 5
    $\begingroup$ 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. $\endgroup$ Nov 25, 2010 at 17:21
  • $\begingroup$ 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. $\endgroup$ Nov 25, 2010 at 18:13
  • $\begingroup$ It doesn't directly answer your question, but you may be interested in Florio and Leach-Krouse's recent article in the Review of Symbolic Logic, "What Russell should have said to Burali-Forti". $\endgroup$ Feb 17, 2018 at 10:12
  • $\begingroup$ It seems that in the set theory NBG (en.wikipedia.org/wiki/…) the approach of Cantor is legal. One can consider the class $WO=\{\langle\alpha,w\rangle:\alpha$ is a von Neumann ordinal, $w$ is a well-ordered set, order isomorphic to $\alpha\}$. For each ordinal $\alpha$ the sections $WO(\alpha)=\{w:\langle\alpha,w\rangle\in WO\}$ are ordinals in the sense of Cantor. $\endgroup$ Apr 16, 2020 at 6:30

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 25, 2010 at 18:59
  • $\begingroup$ @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? $\endgroup$ Nov 26, 2010 at 16:48
  • $\begingroup$ 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. $\endgroup$ Nov 26, 2010 at 17:32
0
$\begingroup$

You might want to look at Burali-Forti as a Purely Logical Paradox (2018) by Graham Leach-Krouse:

Russell's paradox is purely logical in the following sense: a contradiction can be formally deduced from the proposition that there is a set of all non-self-membered sets, in pure first-order logic—the first-order logical form of this proposition is inconsistent. This explains why Russell's paradox is portable—why versions of the paradox arise in contexts unrelated to set theory, from propositions with the same logical form as the claim that there is a set of all non-self-membered sets.

Burali-Forti's paradox, like Russell's paradox, is portable. I offer the following explanation for this fact: Burali-Forti's paradox, like Russell's, is purely logical. Concretely, I show that if we enrich the language L of first-order logic with a well-foundedness quantifier W and adopt certain minimal inference rules for this quantifier, then a contradiction can be formally deduced from the proposition that there is a greatest ordinal.

Moreover, a proposition with the same logical form as the claim that there is a greatest ordinal can be found at the heart of several other paradoxes that resemble Burali-Forti's. The reductio of Burali-Forti can be repeated verbatim to establish the inconsistency of these other propositions. Hence, the portability of the Burali-Forti's paradox is explained in the same way as the portability of Russell's: both paradoxes involve an inconsistent logical form---Russell's involves an inconsistent form expressible in L and Burali-Forti's involves an inconsistent form expressible in L + W.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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