3
$\begingroup$

For the von Neumann ordinals, $\in$ is the standard well-ordering.

I would like to know the standard way to define a well-ordering $<$ for the set of Zermelo ordinals.

In particular, I would like to know, for any two distinct Zermelo ordinals $u$ and $v$, how one determines, formally1, whether $u < v$ or $v < u$.

I assume that this definition of $<$ for Zermelo ordinals will depend only on Zermelo's axioms, with the possible addition of the Axiom of Foundation. At any rate, I am interested only in such a definition. (In particular, I would like to avoid any definition that requires the existence of the set $\omega$ of finite von Neumann ordinals.2)


In case the definition of Zermelo ordinals is not sufficiently standardized, below I give the one I know.

If $w$ is any set, let $\rho(w)$ be the formula that asserts $$\varnothing \in w \;\; \wedge \;\; \forall y\in w (\{y\} \in w).$$

Zermelo's original Axiom of Infinity postulates the existence of a set $w$ such that $\rho(w)$.

Let set $z$ be the smallest set $w$ such that $\rho(w)$ holds. Formally, $$z := \bigcap \,\{w : \rho(w)\}.$$

A "Zermelo ordinal" is an element of the set $z$.


1 I use the word "formally" here to rule out the method of "counting the number of curly braces." :)

2 On p. 42 of his The Foundations of Mathematics Kenneth Kunen contrasts Zermelo's original Axiom of Infinity (Axiom des Unendlichen: $\exists w [\varnothing \in w \ \wedge \ \forall y\in w (\{y\} \in w)]$), which justifies the existence of the set of Zermelo ordinals, with the now more standard Axiom of Infinity ($\exists w [\varnothing \in w \ \wedge \ \forall y\in w (y \cup \{y\} \in w)]$), which justifies the existence of the set $\omega$ of finite von Neumman ordinals. Kunen writes (my emphasis added):

...the two Axioms of Infinity are equivalent, although one needs to use [the Axiom of] Replacement (which Zermelo did not have) to prove the equivalence...".

As an exercise, I would like to prove, using the Axiom of Replacement, that the existence of the set $z$ of Zermelo ordinals implies the existence of the set $\omega$ of finite von Neumman ordinals, but all my attempts stumble for not having a proper definition of a well-ordering for $z$.

$\endgroup$

1 Answer 1

3
$\begingroup$

First, we need to show that transitive closures (of relations) exist. This can be done using the axiom of the power set and $\Delta_0$ separation without reference to the axiom of infinity. It can also be done with full separation.

The transitive closure of $S \subseteq A^2$ is simply $\{(a, b) \in A^2 \mid \forall Q \subseteq A^2,$ if $Q$ is transitive and $S \subseteq Q$ then $(a, b) \in Q\}$. You can easily verify that the transitive closure is the smallest transitive relation containing $S$.

Then $< \subseteq z^2$ is the transitive closure of $\in_z = \{(a, b) \in z^2 \mid a \in b\}$. Since $\in_z$ is well-founded and the transitive closure of a well-founded relation is also well-founded, we see that $<$ is well-founded. The fact that $<$ is a strict total order can be shown using induction.

Edit: Here's a proof that the transitive closure of a well-founded relation is well-founded.

Consider any relation $\prec \subseteq S^2$, and let $<$ be its transitive closure. Prove that $x < y$ if and only if either $x \prec y$ or $\exists z \in S (z \prec y \land x < z)$. Dually, we see that $x < y$ if and only if either $x \prec y$ or $\exists z \in S (x \prec z \land z < y)$.

A set $Q \subseteq S$ is said to be "inductive" with respect to $\prec$ if $\forall x \in S (\{y \in S \mid y \prec x\} \subseteq Q \to x \in Q)$. Then $\prec$ is said to be a well-founded relation if for all $Q \subseteq S$ which are inductive with respect to $S$, $Q = S$. We are defining the term "well-founded" here using well-founded induction.

Now suppose that $\prec$ is well-founded. We wish to demonstrate that $<$ is also well-founded. Consider some $Q$ which is inductive with respect to $<$. Define $Q' = \{x \in S \mid \{y \in S \mid y < x\} \subseteq Q\}$. Note that $Q' \subseteq Q$.

I claim that $Q'$ is inductive with respect to $\prec$. For consider some arbitrary $x \in S$, and suppose $\{y \in S \mid y \prec x\} \subseteq Q'$. Now suppose we have some $y \in S$ with $y < x$. Then there are two cases. The first is that $y \prec x$; in this case, we have $y \in Q' \subseteq Q$. The second is that there is some $z \in S$ such that $z \prec x$ and $y < z$. In that case, we know that $z \in Q'$, and therefore $y \in Q$. So in either case, we know that $y \in Q$. Thus, we see that $\{y \in S \mid y < x\} \subseteq Q$. Therefore, $x \in Q'$.

Since $Q'$ is inductive with respect to $\prec$ and $\prec$ is well-founded, we have $Q' = S$. Then we have $S = Q' \subseteq Q \subseteq S$, so $Q = S$. $\square$

Now we show that any well-founded relation $\prec \subseteq S^2$ is irreflexive. Define $Q = \{x \in S \mid x \nprec x\}$; we will show that $Q$ is inductive. Now consider an arbitrary $x \in S$, and suppose $\{y \in S \mid y \prec x\} \subseteq Q$. Suppose $x \prec x$. Then $x \in Q$; that is, $x \nprec x$. This is a contradiction. Therefore, $x \nprec x$; that is, $x \in Q$. Since $Q$ is inductive, we have $Q = S$, so $S$ is irreflexive. $\square$

Let's return to our original topic, the relation $<$ on the Zermelo ordinals. We have shown that $<$ is well-founded and thus irreflexive. And of course it is transitive, being a transitive closure. All that remains is to show that $<$ is total.

We demonstrate $\forall a \in z \forall b \in z (a < b \lor a = b \lor b < a)$ by induction on $a$.

The base case is $\forall b \in z (0 < b \lor 0 = b \lor b < 0)$. We actually strengthen what must be proved to $\forall b \in z (0 < b \lor 0 = b)$; this follows immediately from induction on $b$.

For the inductive step, suppose $\forall b \in z (a < b \lor a = b \lor b < a)$. We wish to show that $\forall b \in z (Sa < b \lor Sa = b \lor b < Sa)$. Consider some $b \in z$. By the inductive hypothesis, we know that either $a < b$, $a = b$, or $b < a$. If $a = b$ or $b < a$, then clearly $b < Sa$. If $a < b$, then we have two possibilities. The first is that $a \in b$; in this case, we have $b = Sa$. The second is that there is some $c \in z$ such that $a \in c$ and $c < b$. In this case, we actually have $c = Sa$, and therefore $Sa < b$. This completes the proof. $\square$

$\endgroup$
4
  • $\begingroup$ Thanks! This way of defining transitive closure is handier for this problem than the one that Kunnen gives, because it does not require the use of $\omega$ at all. (Kunnen's is a recursive definition, and it does use $\omega$, though I suppose one could devise a similar definition that uses $z$ instead.) Unfortunately, I can't come even close to filling the missing bits in your argument, to prove that $<$, as you defined it, is well-founded on $z$ and that it is a strict total order on $z$ (other than the by-construction fact that $<$ is transitive on $z$). Can you point to a full proof? $\endgroup$
    – kjo
    May 29 at 9:27
  • 1
    $\begingroup$ @kjo I fleshed out the proof for you. You are correct that you run into a serious issue trying to define transitive closures in terms of the natural numbers if you only have $z$ and not $\omega$. You would like to define the transitive closure using finite sequences, but to discuss finite sequences, you would likely need to already have the $<$ operator in hand. $\endgroup$ May 29 at 17:03
  • $\begingroup$ Thank you! There's a lot of interesting mathematics in your post. I did not know that way of defining well-foundedness. It was not at all obvious to me that it was equivalent to the definition I knew; it was very illuminating for me to work out the proof of this equivalence. I had not realized how much ground, mostly new to me, had to be covered to address my original question... For one thing, I still feel a bit wobbly on the properties of a relation's transitive closure. I will probably be posting some follow-up questions on this subject. (More targeted, I hope!) Thanks again! $\endgroup$
    – kjo
    May 29 at 23:02
  • 1
    $\begingroup$ @kjo A good question is one that raises more good questions. My definition of well-foundedness is more common among mathematicians who work with constructive logic, where you don’t assume $\forall P(P \lor \neg P)$. The traditional version of wellfoundedness is useless in this setting, since if we have a classically well-founded $\prec$ and any $a \prec b$, the law of excluded middle holds (by considering a set of the form $\{x \mid x =b \lor (x =a \land P)\}$, whose minimal element is either $a$ (meaning $P$ holds) or $b$ (meaning $\neg P$ holds). I’m glad you found the exercise illuminating. $\endgroup$ May 29 at 23:24

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.