3
$\begingroup$

We've been asked to teach ourselves a unit on ordinals for our final exam tomorrow, I grasp how to prove that certain ordinals are distinct but I am having trouble figuring out a proof to show ordinal addition is associative. All the proofs I have found online use methods that we have not covered yet. Would someone be able to guide me through a proof of associativity for ordinal addition?

Here's a general overview of what I know:

Two ordinals are equal if they are order isomorphic.

Ordinal addition for two well ordered sets $a=ord(A, <_A) b=ord(B, <_B)$ then$ a+b=ord(AUB, <_+) $ where $x <_+ y$ if either x, y are in A and $x<_A y$, or x, y are in B and $x<_B y$, or x is in A and y is in B

Thank you so much

$\endgroup$
  • $\begingroup$ In arithmetic, the proof of associativity proceed by induction. In the case of ordinal numbers you need transfinite induction. See P.Suppes, Axiomatic set theory (1960-Dover repr), page 211: Theorem 25. $\alpha + (\beta + \gamma)=(\alpha + \beta) + \gamma$. The proof proceeds by transfinite induction on $\gamma$. Basis: from result of page 206 ($\alpha + 0 = 0 + \alpha = \alpha$). The successor case is straightforward by def of addition. The last case is that $\gamma$ is a limit ordinal and for every $\delta \in \gamma$ : $\alpha + (\beta + \delta)= (\alpha + \beta) + \delta$. $\endgroup$ – Mauro ALLEGRANZA Apr 18 '14 at 15:01
  • $\begingroup$ @Mauro: With this definition there's no real need for induction. $\endgroup$ – Asaf Karagila Apr 18 '14 at 15:17
2
$\begingroup$

HINT:

Note that this means that $a+b=c$ if $c$ can be partitioned into an initial segment of order type $a$ and tail segment of order type $b$.

Show that there is a partition of $(a+b)+c$ into three consecutive intervals (initial segment, middle segment, and tail segment) of order types $a,b$ and $c$. And conclude from that that $(a+b)+c=a+(b+c)$.

$\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.