Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 1 / 16G / Solution

A well-order is a linearly ordered set in which every nonempty subset has a least element. First note that a well-order cannot be isomorphic to a proper initial segment of itself: the least element moved by such an isomorphism would have exactly the same predecessor set on each side, forcing it to be fixed. The same least-disagreement argument makes an isomorphism between initial segments unique.

Match $a\in A$ to $b\in B$ exactly when their strict predecessor sets are order-isomorphic. The preceding observation makes each match unique. Matches preserve order and fill initial segments on both sides, since restricting an isomorphism matches every earlier element. If both sides had an unmatched element, take the least unmatched $a$ and $b$. Their predecessor sets would be exactly the already matched segments, so they too would match, a contradiction. Therefore the matching exhausts at least one well-order and gives an isomorphism of that whole set onto an initial segment of the other. Uniqueness follows from the same predecessor-set argument. The whole set is allowed as an initial segment; this includes equal order types.

For ordinal division, let $\beta >0$ and chooseThis supremum is a set ordinal because $\beta \eta \ge \eta$ bounds the displayed ordinals by $\alpha$. Strict increase and continuity of multiplication in the right argument imply $\beta \gamma \le \alpha <\beta (\gamma +1)$. Take the order type $\delta$ of the remaining tail of $\alpha$ after its initial segment of type $\beta \gamma$. Then $\alpha =\beta \gamma +\delta$; if $\delta \ge \beta$ it would contradict the strict upper inequality. ThusThe half-open intervals $[\beta \eta ,\beta (\eta +1))$ are disjoint, so $\gamma$ is unique, and uniqueness of the tail gives uniqueness of $\delta$. This is left-divisor ordinal division: the order of multiplication cannot be interchanged.

Apply it with $\beta =\omega$. The remainder is finite. A nonzero remainder makes $\omega \gamma +\delta$ a successor, while a nonzero $\omega \gamma$ is a limit: for successor $\gamma$ it ends in a full block of type $\omega$, and for limit $\gamma$ it is the supremum of the earlier blocks. Consequently