0
$\begingroup$

In Kenneth Kunen's The Foundations of Mathematics, the following statement is proven:

If $R$ well-orders $A$, then there is a unique $\alpha \in ON$ such that $(A;R) \cong (\alpha;\in)$.

In case there is any confusion (because I've seen that sometimes there are slight differences in convention), Kunen establishes the following definitions:

  • $R$ well-orders $A$ iff $R$ totally orders $A$ strictly and $R$ is well-founded on $A$

  • $R$ is well-founded on $A$ iff for all non-empty sets $X \subseteq A$, there is a $y \in X$ that is $R$-minimal in $X$

  • $y \in X$ is $R$-minimal in $X$ iff $\neg \exists z (z \in X \land zRy)$. Alternatively, $y \in X$ is $R$-maximal in $X$ iff $\neg \exists z (z \in X \land yRz))$

  • $R$ totally orders $A$ strictly iff $R$ is transitive and irreflexive on $A$ and satisfies trichotomy on $A$

  • Informally we define $ON = \{x: x \text{ is an ordinal} \}$, and the author has proven that $ON$ is well-ordered by $\in$

  • If $<$ and$\prec$ are relations, then their lexicographic product on $S \times T$ is the relation $\triangleleft$ on $S \times T$ defined by:

$$\langle s,t \rangle \triangleleft \langle s',t' \rangle \leftrightarrow [s < s' \lor [s=s' \land t \prec t']]$$

Finally:

  • $F$ is an isomorphism from $(A;<)$ onto $(B; \triangleleft)$ iff $F$ is a bijection $(F: A \to B$) and $\forall x,y \in A [ x < y \leftrightarrow F(x) \triangleleft F(y)]$. Then, $(A;<)$ and $(B;\triangleleft)$ are isomorphic (in symbols, $(A;<) \cong (B;\triangleleft)$ ) iff there exists an isomorphism from $(A;<)$ onto $(B;\triangleleft)$.

After proving the above statement, Kunen provides the following two definitions (which are what my question relates to):

Definition 1: If $R$ well-orders $A$ then $\text{type}(A;R)$ is the unique $\alpha \in ON$ such that $(A;R) \cong (\alpha;\in)$. We also write $\text{type}(A)$ (when $R$ is clear from context). or $\text{type}(R)$ (when $A$ is clear from context).

Definition 2: $\alpha \cdot \beta = \text{ type}(\beta \times \alpha) $ and $\alpha + \beta = \text{ type}(\{0\} \times \alpha \ \ \cup \ \ \{1\} \times \beta)$.

Kunen adds: "In both cases, we're using lexicographic order to compare ordered pairs of ordinals"


Using Kunen's definitions of ordinal multiplication and addition, I want to make sure that I am correctly understanding the major features. The two examples I would like to consider are:

  1. $\omega + 1 $ versus $1 + \omega$

  2. $\omega \cdot 2$ versus $2 \cdot \omega$ (Edit: Because this post is running long, I'll just focus on the addition)

Because of Kunen's definitions of ordinal arithmetic, a useful lemma is the following:

If $<$ and $\prec$ are well-orders of $S,T$, respectively, then their lexicographic product $\triangleleft$ on $S \times T$ is a well-order of $S \times T$.

$\color{blue}{\text{ Also, although I only did an informal proof, I am fairly certain that } \{0\} \times \alpha \ \ \cup \ \ \{1\} \times \beta}$ $\color{blue}{\text{is well-ordered, too}}.$


Consider $\omega + 1 $

$\omega$ is an ordinal and $1$ is an ordinal, which we will denote as $\{0\}$. Presumably, the implicit relation associated with these sets is $\in$. Thus:

$\omega + \{0\} = \text{type}(\{0\} \times \omega \ \cup \ \{1\} \times \{0\})=\text{type}(\{ \langle 0,0 \rangle, \langle 0,1 \rangle, \langle 0,2 \rangle,...,\langle 1,0 \rangle\})$

Importantly, note that $\langle 1,0 \rangle$ is a maximal element. Let $A$ be the set $\{ \langle 0,0 \rangle, \langle 0,1 \rangle, \langle 0,2 \rangle,...,\langle 1,0 \rangle\}$.

By the initial statement this post began with: there is a unique $\alpha \in ON$ such that $(A;\in) \cong (\alpha;\in)$

Consider $1 + \omega$

$\{0\} + \omega = \text{type}(\{0\} \times \{0\} \ \cup \ \{1\} \times \omega)=\text{type}(\{ \langle 0,0 \rangle, \langle 1,0 \rangle, \langle 1,1 \rangle \langle 1,2 \rangle, ...\}) $

Importantly, note that there is no maximal element. Let $A'$ be the set $\{ \langle 0,0 \rangle, \langle 1,0 \rangle, \langle 1,1 \rangle \langle 1,2 \rangle, ...\}$

By the initial statement this post began with: there is a unique $\alpha' \in ON$ such that $(A';\in) \cong (\alpha';\in)$

Now, the trouble I am having in both cases is determining which function I should use to describe the isomorphisms...and then, using these functions, demonstrate that $\alpha = S(\omega)$ and $\alpha'=\omega$


For $\alpha \in ON$ such that $(A;\in) \cong (\alpha;\in)$, a good candidate seems to be something along the lines of:

$$f: \begin{cases} \langle 0,n \rangle \mapsto n \\ \langle 1, 0 \rangle \mapsto \omega \end{cases}$$

However, the fact that I am mapping $\langle 1, 0 \rangle$ to $\omega$ seems arbitrary. Couldn't I have mapped it to any ordinal that lays "above" the natural numbers?

For $\alpha' \in ON$ such that $(A';\in) \cong (\alpha';\in)$, a good candidate seems to be:

$$f': \begin{cases} \langle 0,0 \rangle \mapsto 0 \\ \langle 1, n \rangle \mapsto n+1 \end{cases}$$

Once again, however, I'm not quite sure I understand why my mappings are justified. I feel like I am creating these functions rather blindly, and without the proper motivation/justification.

I apologize if this question does not make much sense (still getting used to working with ordinals).

$\endgroup$
1
  • 1
    $\begingroup$ In the case of your bijection for $\omega+1$, if you map that last element to something bigger than $\omega$, then you haven’t given a bijection to an ordinal, which is what you need. $\endgroup$ Dec 15, 2020 at 13:26

1 Answer 1

5
$\begingroup$

Ordinal addition is "stacking up orders". So $\alpha+\beta$ means that we put a copy of $\beta$ on top of a copy of $\alpha$. Now, what does it mean for $1$ and $\omega$? Well, putting a copy of $\omega$ on top of $1$ is just $\{-1\}\cup\Bbb N$, really. And quite easily, this is again isomorphic to $\Bbb N$ by the obvious function. On the other hand, $\omega+1$ means adding a copy of $1$, i.e. a point, on top of $\omega$. So $\omega+1$ is $\Bbb N$ with a "cap", a maximum. Clearly, not the same order as $\omega$.

Since you bring up order multiplication, the idea is that $\alpha\cdot\beta$ is replacing each point in $\beta$ with a copy of $\alpha$. So $\omega\cdot 2$ means consider $\{0,1\}$ and then replacing each of those with a copy of $\omega$: so we really get $\omega+\omega$ (in fact, the very same set, by definition!). On the other hand, $2\cdot\omega$ means replacing each natural number with a copy of $\{0,1\}$. But this is the same as considering $\{0,1\}$ and then $\{2,3\}$, and then $\{4,5\}$, etc. So $\{2n,2n+1\}$ is the $n$th copy. Easily, again, this is the same as $\omega$.

$\endgroup$
2
  • $\begingroup$ I appreciate the attempt at "dumbing it down" for me to offer intuition, but I fear that I do not know enough about ordinals to fully appreciate/comprehend the analogy you provided. I don't really understand the notion of putting a copy of an ordinal "on top" of another ordinal. I cannot create an appropriate image in my head that is faithfully capturing your idea. Also, what exactly do you mean by "point"? A set with a singular element? $\endgroup$
    – S.Cramer
    Dec 16, 2020 at 2:04
  • $\begingroup$ Draw it on a piece of paper. Put two forks and then three knives (left-to-right, in this case). Play with it. Things can be simple, too. And yes, a point is exactly a single element, or the ordinal $1$. $\endgroup$
    – Asaf Karagila
    Dec 16, 2020 at 2:05

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.