# Section 3.2: Problem 3 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Let $\mathfrak{A}$ be a model of $\mbox{Th}\mathfrak{N}_{L}$ (or equivalently a model of $A_{L}$ ). For $a$ and $b$ in $|\mathfrak{A}|$ define the equivalence relation: Let $[a]$ be the equivalence class to which $a$ belongs. Order equivalence classes by Show that this is a well-defined ordering on the set of equivalence classes.
First, we argue that $\sim$ is an equivalence relation. The reflectiveness and symmetry of the relation follows immediately from the definition. Regarding the transitivity, we can use the axioms, in particular, S2, to see that if $b=\mathbb{S}^{n}a$ then $c=\mathbb{S}^{n+k}a$ iff $c=\mathbb{S}^{k}b$ , and $b=\mathbb{S}^{n+k}c$ iff $a=\mathbb{S}^{k}c$ , from which the transitivity of $\sim$ follows.
Now, we show that $\prec$ is well-defined. Suppose that $[a]\prec[b]$ . We need to show that if $c\sim a$ then $[c]\prec[b]$ , and if $c\sim b$ , then $[a]\prec[c]$ . If $c\sim a$ , then $c\nsim b$ ($\sim$ is an equivalence relation), and either $c<^{\mathfrak{A}}a$ or $c=a$ , in which case $c<^{\mathfrak{A}}b$ , or $c=\mathbb{S}^{n}a$ , in which case if we assume $b=c$ or $a<^{\mathfrak{A}}b<^{\mathfrak{A}}c$ , then $b=\mathbb{S}^{k}a$ for some $0 (by S2), contradicting the assumption that $a\nsim b$ . In either case, $c\nsim b$ and $c<^{\mathfrak{A}}b$ , implying $[c]\prec[b]$ . Similarly, we consider the case $c\sim b$ to show $[a]\prec[c]$ .
Finally, we ensure that the ordering properties hold for $\prec$ .
1. Trichotomy. For every $a$ and $b$ , either $a\sim b$ ($[a]=[b]$ ) or $a\nsim b$ , hence, $a\neq b$ , and either $a<^{\mathfrak{A}}b$ ($[a]\prec[b]$ ) or $b<^{\mathfrak{A}}a$ ($[b]\prec[a]$ ).
2. Antisymmetry. For every $a$ and $b$ , if $a\nsim b$ and $a<^{\mathfrak{A}}b$ ($[a]\prec[b]$ ) then not $b<^{\mathfrak{A}}a$ ($[b]\nprec[a]$ ). Alternatively, $a\sim b$ or $a\nless^{\mathfrak{A}}b$ ($[a]\nprec[b]$ ) iff $b\sim a$ ($[b]=[a]$ ) or $b\nsim a$ (hence, $b\neq a$ ) and $b<^{\mathfrak{A}}a$ ($[b]\prec[a]$ ).
3. Transitivity. For every $a$ , $b$ and $c$ , if $a\nsim b$ and $a<^{\mathfrak{A}}b$ ($[a]\prec[b]$ ) and $b\nsim c$ and $b<^{\mathfrak{A}}c$ ($[b]\prec[c]$ ), then $a<^{\mathfrak{A}}c$ and $a\nsim c$ ($[a]\prec[c]$ ). Here, we have $a\nsim c$ , as otherwise, $a<^{\mathfrak{A}}b<^{\mathfrak{A}}c=\mathbb{S}^{n}a$ , and $b\nsim a$ , implying for some $0\le k , $\mathbb{S}^{k}a<^{\mathfrak{A}}b<^{\mathfrak{A}}\mathbb{S}^{k+1}a$ , and $b\le^{\mathfrak{A}}\mathbb{S}^{k}a$ (by L1).