8
$\begingroup$

Perhaps, the class of ordinals $\Omega$ can be axiomatised up to isomorphism by claiming it to be well-ordered such that for every subset $X\subseteq \Omega$ there exists a "succesor" ordinal $\sigma$ which is the smallest ordinal larger than any element of $X$.

I dont like this axiomatization (and I am not even sure, if it works) because it already starts with the ordering. Compare that with Peano's Axioms which include only the successor function and allow to construct the ordering from it.

My question: Are there some axioms which characterize the class of ordinals "up to isomorphism" and do only rely on the "successor function" $$ \mathcal{P}(\Omega) \to \Omega \ ,\ X \mapsto \text{smallest ordinal larger than any element of}\ X $$ where $\Omega$ is the class of ordinals and $\mathcal{P}(\Omega)$ the class of all subsets. Problem: The successor function has to be axiomatized without referring to the ordering.

The idea is to think of ordinals not as the isomorphism classes of well-orderings but rather as a class that is inductively "generated" by the transfinitely iterated process of "counting the successor" of all numbers already being counted. This is the spirit of Peano's axioms, which also dont view the natural numbers as isomorphism classes of finite sets.

There seems to be a resemblance to the categorical idea of a "natural numbers object", which is a diagram $$ \{0\} \to \mathbb{N} \xrightarrow{n \to n+1} \mathbb{N} $$ being initial along all diagrams of the form $\{0\} \to X \to X$.

Maybe the class of ordinals can be described as a universal diagram of the form $$ \mathcal{P}(\Omega) \to \Omega \quad ?$$ Compare this to the fact, that for some set $X$, there is an embedding $X \to \Omega$ if and only if there is a choice function on its power set.

Edit: Here is an interesting property of the successor function which may be used for axioms: For any subset $T\subseteq \Omega$ we have $$ s(T) = s\left( \bigcup \lbrace R \in \mathcal{P}(\Omega) \mid s(R) = s(T) \rbrace \right) $$ and this construction allows for an ordinal $\sigma \in \Omega$ to implicitly use the set $\Omega_{<\sigma}$ of all smaller ordinals (which in the von Neumann model is equal to $\sigma$ itself).

Futher edit: Here is a sketch of the way I imagined ($s$ being the successor function):

  • Formulate axioms allowing for a kind of recursion theorem involving commutative diagrams. Subidea: Any well-ordered class should give rise to a similar diagram, so the theorem that any well-ordered class can be embedded into $\Omega$ is a consequence of the universality of $\Omega$'s diagram.
  • That recursion theorem should ensure that the recursive definition $$ \alpha + s(\emptyset) := \alpha, \qquad \alpha + s(B) := s( \lbrace \alpha + \beta \mid \beta \in B \rbrace )\qquad B \neq \emptyset $$ is well-defined.
  • Define $$ \alpha \le \beta \qquad :\Leftrightarrow \qquad \exists \gamma : \alpha + \gamma = \beta $$ and finally prove this relation to be a well-ordering.

Will this work?

$\endgroup$
7
  • $\begingroup$ Like Peano's successor function, the successor function $s:\mathcal{P}(\Omega) \to \Omega$ is simply required by the axioms. It does not need a definition at all, much less defined in terms of an ordering. What it needs is axioms that assure it has the required behavior. You can then define $\alpha < \beta$ to be the relation $\exists A \subset \Omega$ with $\alpha \in A$ and $s(A) = \beta$. $\endgroup$ – Paul Sinclair Aug 7 '19 at 21:35
  • $\begingroup$ By the way, you might want to look at Conway's surreal numbers - in particular, the axiomatic definition of them in terms of a left set-right set operator. If you restrict that system to only allow empty right sets, then the operator becomes exactly your ordinal successor function. $\endgroup$ – Paul Sinclair Aug 7 '19 at 21:40
  • $\begingroup$ @Paul Sinclair: My question was supposed to ask how those axioms, "assuring the required behavior of the successor function" might look like. After reading Wikipedia and nlab, It seems to me that Conway's construction does heavily rely on ordering because its axiom for equality is based on it. Do you know a more formal axiomatic approach to surreal numbers that I can look up on the Internet? $\endgroup$ – Lucina Aug 8 '19 at 11:13
  • $\begingroup$ In Conway's scheme, the order is defined inductively with the ordinals themselves. Note also that applying it to just ordinals simplifies the demands. However, for something closer to Peano, I think the main axioms you want are going to be "$\forall A\subset \Omega, s(A) \notin A$", "$s(A) = 0 \implies A = \emptyset$", and "$s(A) \in B \implies s(A\cup B) = s(B)$", and something to say that $\Omega$ is not in the domain of $s$. But I haven't thought it through to see if that is enough. $\endgroup$ – Paul Sinclair Aug 8 '19 at 16:36
  • $\begingroup$ Actually, you can define $0 = s(\emptyset)$, so that axiom isn't needed, but you are going to need some way of restricting $s$ to bounded subsets of $\Omega$ only. Maybe allow $s$ for all subsets of $\Omega$, but make the codomain of $s$ to be $\Omega \cup \{s(\Omega)\}$ $\endgroup$ – Paul Sinclair Aug 8 '19 at 16:51
2
$\begingroup$

How about these axioms, with "s" and "is an ordinal" as undefined terms?

  1. If $A$ is a set of ordinals, then $s(A)$ is an ordinal.
  2. If $A$ is a set of ordinals, then $s(A) \notin A$.
  3. If $A,A',B$ are sets of ordinals, and $s(A) = s(A')$, then $s(A\cup B) = s(A'\cup B)$.
  4. If $K \ne \emptyset$ is a set of ordinals, then there exists an ordinal set $A$ with $s(A) \in K$ such that for all ordinal sets $B$ with $s(B) \in K, s(A\cup B) = s(B)$.

I've not included equality axioms because unlike the Peano axioms, these axioms require a larger theory of sets, and equality is part of that larger theory.

The ordinals do not form a set, since if $\Omega$ were the set of all ordinals, then by (1), $s(\Omega)$ is an ordinal, and so $s(\Omega) \in \Omega$, in contradiction to (2). Thus $\Omega$ can only be a class.

(4) implies that every ordinal is of the form $s(A)$ for some ordinal set $A$, since if $\alpha$ is an ordinal, then $\{\alpha\}$ is a set of ordinals. And by considering the set $\{s(A), s(B)\}$, it is easy to see that

  • if $A$ and $B$ are sets of ordinals, then either $s(A\cup B) = s(A)$ or $s(A\cup B) = s(B)$.

If $\alpha = s(A)$ and $\beta = s(B)$, define $\alpha \le \beta$ if $s(A\cup B) = s(B)$. Two applications of (3) show that it is well-defined, and the bullet point shows that for all $\alpha,\beta$ we have $\alpha \le \alpha$, $\alpha \le \beta$ and $\beta \le \alpha \implies \alpha = \beta$ and either $\alpha \le \beta$ or $\beta \le \alpha$.

Transitivity is not much harder to prove: if $\alpha \le \beta$ and $\beta \le \gamma$, with $\alpha = s(A), \beta = s(B), \gamma = s(C)$, then $s(A\cup B) = \beta$, and $s(B\cup C) = \gamma$. Also since $\beta \le \gamma, \:s((A\cup B)\cup C) = \gamma$, but then $s(A \cup (B \cup C)) = \gamma$, which means $\alpha \le \gamma$.

Therefore $\le$ is a linear order on ordinals. (4) says that $\le$ is a well-order.

$\endgroup$
14
  • $\begingroup$ Nice! I was looking for something like that. Can we simplify the rather artificial axiom (4)? Great work in showing, that your axioms imply a well-ordering! Nevertheless it seems more natural to me, to first define addition of ordinals recursively and then define the ordering like: $$ \alpha \le \beta \quad : \Leftrightarrow\quad \exists \gamma : \alpha = \beta + \gamma $$ $\endgroup$ – Lucina Aug 9 '19 at 0:24
  • $\begingroup$ I would rather like to add a transfinite induction axiom: "If $T\subseteq \Omega$ is a subclass, such that for each subset $S\subseteq T$ we have $s(S) \in T$, then already $T=\Omega$" This suffices to show that every ordinal is the successor of a set of ordinals. $\endgroup$ – Lucina Aug 9 '19 at 0:26
  • $\begingroup$ It seems to me, that your axiom (4) is a pretty sophisticated way of requiring any set of ordinals to contain a smallest element. It helps you to quickly prove your relation $\le$ to be a well-order. But I feel, that this is a clever but unneccessary shortcut. Maybe we can replace your axiom (4) by a weaker yet simpler one, therefore lengthen the existence proof for the "canonical well-order"? $\endgroup$ – Lucina Aug 9 '19 at 0:38
  • 1
    $\begingroup$ @ Vsotvep: We are so used to von Neumann's definition of ordinals that we often speak of von Neumann ordinals as THE (one and only) ordinals, where $<$ and $\in$ coincide. But to my opinion, von Neumann's definition of ordinals is just as unnatural as his definition of $\mathbb{N}$ and the ordinals should, like the natural numbers, be viewed as a class of urelements, that obeys a bunch of axioms. $\endgroup$ – Lucina Aug 9 '19 at 10:56
  • 1
    $\begingroup$ Sorry for the delay, but I had other things to do. Before I get to your question, I am wondering if you truly understand the nature of ordinals. You say that (4) seems unnatural, but in fact it is a straight-forward expression of the key concept behind them: that they are well-ordered (once $\le$ is defined, you can rephrase (4) as "every non-empty set of ordinals has a least element").The very raison d'etre of ordinals is that they are types for well-orderings. Every well-ordering corresponds to a unique ordinal, and if two orderings have the same ordinal, they are isomorphic. $\endgroup$ – Paul Sinclair Aug 12 '19 at 21:18
0
$\begingroup$

Here is one solution I came upon by myself. I am not really trusting myself if it works, so I am grateful for your feedback.

First some definitions: Suppose we have a class $X$ together with a map $r:\mathcal{P}(X) \to X$. Call a subclass $C \subseteq X$ inductive if for any subset $T\subseteq C$ there is also $s(T) \in C$. Clearly, the intersection of an arbitrary familiy of inductive subclasses is inductive. So we get a hull operator and can define $$ M(X) := \bigcap \lbrace \ \text{inductive subclasses of}\ X \rbrace$$ We also get another map $$ R : \mathcal{P}(\mathcal{P}(X)) \to \mathcal{P}(X) \ ,\quad C \mapsto \bigcup_{T \in C} (T \cup \lbrace s(T)\rbrace) $$ I define $$ I(X) := M(\mathcal{P}(X)) = \bigcap \lbrace \ \text{inductive subclasses of}\ \mathcal{P}(X) \rbrace$$ and this class will be of great importance. While the idea of $M(X)$ is to define the largest subclass of $X$ reachable by transfinite counting, the idea behind $I(X)$ is to keep track of that counting and remember the "initial sets" (therefore the letter "I") of numbers already counted. Be restricting the original map $r$ we get a diagram $$ I(X) \xrightarrow{r} X$$

Here are my "transfinite peano axioms" for the class of ordinals: The ordinals form a class $\Omega$ together with a "successor function" $s : \mathcal{P}(\Omega) \to \Omega$ such that the following holds:

  • For any subset $T \in \mathcal{P}(\Omega)$ we have $s(T) \notin T$. (This corresponds to the Peano axiom concerning $0$ not being in the image of the successor function. While that Peano axiom ensures, that $\mathbb{N}$ not only consists of one element, the transfinite equivalent here ensures, that $\Omega$ is a proper class. So both axioms are about size)
  • The restricted successor function $s : I(\Omega) \to \Omega$ is injective. (This corresponds to the Peano axiom concerning the successor function to be injective. It ensures that the process of (transfinite) counting does not end up in a circle)
  • ("transfinite induction axiom") If there is a subclass $C \subseteq \Omega$ such that for any subset $T \subseteq C$ with $T\in I(\Omega)$ there is also $s(T) \in C$, then we already have $T=\Omega$. (This corresponds to the induction axiom. It ensures that the process of (transfinite) counting exhausts the entire class).

Make sure yourself by using the transfinite induction axiom, that the restricted successor function $s:I(\Omega) \to \Omega$ is surjective, so, combined with the second axiom, bijective. Note that the von Neumann model makes this cheap, because each von Neumann ordinal is the successor of the set of its elements. For some ordinal $\sigma \in \Omega$, I will write $$ P_\sigma := s^{-1}(\sigma) $$ for the "set of predecessors" of $\sigma$. Bijectivity of $s$ means, that the induction axiom can be formulated as: "Is $T\subseteq \Omega$ a subclass, such that for any $\sigma \in \Omega$ with $P_\sigma \subseteq T$ we already have $\sigma \in T$, then $T=\Omega$."

Lemma: For any two ordinals $\sigma, \varrho \in \Omega$ with $\sigma \in P_\varrho$, we have $P_\sigma \subseteq P_\varrho$.

Proof: We do induction on $P_\varrho$ and use the inductive nature of the definition of $I(\Omega)$ so that we only have to show that the class $$ C := \lbrace T \in I(\Omega) \mid \forall \sigma \in \Omega : \sigma \in T \to P_\sigma \subseteq T \rbrace $$ is an inductive subclass of $\mathcal{P}(\Omega)$. Let $S \subseteq C$ be a subclass and $\sigma \in \Omega$ with $\sigma \in \bigcup_{T\in S} (T \cup \{s(T)\})$. So there exists some $T_0\in S$ with $\sigma \in T_0 \cup \lbrace s(T_0)\rbrace $ In case of $\sigma = s(T_0)$ we would have $P_\sigma = T_0 \subseteq \bigcup_{T\in S} (T \cup \{s(T)\})$. In case $\sigma \in T_0 \in S\subseteq C$ we would have $P_\sigma \subseteq T_0 \subseteq \bigcup_{T\in S} (T \cup \{s(T)\})$. So $C$ is indeed inductive and we get $C=I(\Omega)$.

Now comes the universal property of $\Omega$: For any class $X$ together with a map $r: \mathcal{P}(X) \to X$, there exists a unique map $f : \Omega \to X$, such that $$ f(s(T)) = r(f(T)) \qquad\qquad T \in I(\Omega) $$ which means, that the diagram

diagram

commutes. Proof:

Define a class of maps $$ M := \lbrace g : P \to X \mid P \in I(\Omega),\ \forall \sigma \in P : g(\sigma) = r(g(P_\sigma)) \rbrace $$ Note that this definition makes sense, because if $\sigma \in P \in I(\Omega)$ then, by the above lemma, there is also $P_\sigma \subseteq P$.

First proof step: For any $g,h \in M$ and $\sigma \in \text{dom}(g) \cap \text{dom}(h)$ we have $g(\sigma)=h(\sigma)$. Proof is per induction on $\sigma$. Suppose the claim being correct for all elements of $P_\sigma$. If now $\sigma \in \text{dom}(g) \cap \text{dom}(h)$ we have $P_\sigma \subseteq \text{dom}(g) \cap \text{dom}(h)$, the inductive assumption tells us $g \vert_{P_\sigma}= h \vert_{P_\sigma}$ and we get $$ g(\sigma) = r(g(P_\sigma)) = r(h(P_\sigma)) = h(\sigma) $$ Second proof step: For any $\sigma \in \Omega$, there exists a map $g \in M$ with $\sigma \in \text{dom}(g)$. Proof is again per induction on $\sigma$. Suppose the claim being true for all elements of $P_\sigma$. Because $I(\Omega)$ is inductive, we have $$ B := P_\sigma \cup \lbrace \sigma\rbrace \in I(\Omega) $$ Now define a map $ g : B \to X $ by

  • $g(b) := h(b)$ if $b \in P_\sigma$ and $h \in M$ is any function with $b \in \text{dom}(h)$. This $h$ exists per inductive assumption and the whole thing is well defined by the first step of the proof.
  • $r(g(P_\sigma))$ if $b=\sigma$.

We need to verify that $g \in M$: By definition we have $g(\sigma) = r(g(P_\sigma))$. For each $\varrho \in P_\sigma$ we have $g(\varrho) = h(\varrho) = r(h(P_\varrho)) = r(g(P_\varrho))$. So, indeed $g \in M$.

Third proof step: Define the function $f: \Omega \to X$ by setting $f(\sigma)$ to the value $g(\sigma)$ of any $g \in M$ with $\sigma \in \text{dom}(g)$. Thats it. $f$ is unique by the first proof step. QED

Now lets define addition of ordinals. Therefore let $X$ be an arbitrary class with a map $r : \mathcal{P}(X) \to X$. Define another map: $$ g : \mathcal{P}(\text{Maps}(X,X)) \to \text{Maps}(X,X) \ , \quad T \mapsto (\sigma \mapsto s(\lbrace t(\sigma) \mid t \in T \rbrace)) $$ with the exception $g(\emptyset) := \text{id}_X$. The universal property gets us a unique map $f : \Omega \to \text{Maps}(X,X)$ and we define $$x + \sigma := f(\sigma)(x) \qquad\qquad \sigma \in \Omega,\ x \in X $$ which is the element of $X$ one obtains by "iterating the function $r$ on $x$ $\sigma$ times". In the special case $X=\Omega$, we get the addition of ordinals.

Here is an incomplete idea on how to proof that any well-ordered set can be embedded to an initial segment of $\Omega$: If $X$ is a well-ordered set, we get a canonical function $$ \mathcal{P}(X) \to X \ ,\ T \mapsto \ \text{smallest element of}\ X \setminus T $$ and define $r(X)$ as some member of $X$ (its irrelevant, which one you choose). Universal property lets us get a unique map $f:\Omega \to X$. Assume that there is no $\sigma \in \Omega$ with $f(P_\sigma) =X$. Then (I wasnt yet able to show that) $f$ is injective so we can define a surjective left inverse of $f$. The axiom of replacement concludes that $\Omega$ is a set because $X$ is. But its an easy consequence of the first axiom, that $\Omega$ is a proper class.

$\endgroup$

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.