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:
-
$\omega + 1 $ versus $1 + \omega$
-
$\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).
Best Answer
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$.