Order isomorphism 2026-10-06
An order isomorphism is a bijection preserving and reflecting the order relation. It transfers well-foundedness and order type between a coded order and its ordinal interpretation.
Past exam of the logic and set theory course of the University of Oxford 2011 B 6 b Solution 2026-10-31
Assume the well-ordering theorem. Every set with a chosen well-order has an order isomorphism to a unique ordinal. Any two ordinals are comparable, and the smaller embeds into the larger as an initial segment. Transporting that embedding back to the original sets proves the cardinal comparability principle.
Conversely, assume the cardinal comparability principle and let be any set. The Hartogs theorem, provable in ZF, supplies an ordinal for which no injection exists. Comparison forces an injection . Pulling back the well-order on its image gives a well-order on . ThereforeThe assumed ordinal facts are that every well-ordered set has an ordinal order type and that any two ordinals are comparable; the other assumed theorem is precisely the stated Hartogs theorem.
Past exam of the mathematics course of the University of Cambridge 2005 ii Paper 2 16F i Solution Created 2026-09-24 Updated 2026-10-14
This assertion is always true. Synthetically, either bracketing places three disjoint blocks of order types in that order. The identity on these blocks is an order isomorphism, so both sums have the same order type. This proves associativity of ordinal addition for successor and limit ordinals alike.
Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 3 16G Solution Created 2026-09-24 Updated 2026-10-14
The induced ordering on is a well-order. By transfinite recursion define for . Induction shows that each is an ordinal, that these values strictly increase, and that their range is the ordinal . The map is an order isomorphism from to this ordinal. Any order isomorphism between ordinals must fix their elements successively, so this ordinal is unique.
An increasing map between ordinals satisfies by induction: its predecessors include for all . Hence . Apply this to the inclusion , transported through their order isomorphisms, and then to . It follows that .
If each is an initial segment of later , uniqueness makes their ordinal enumerations compatible: the enumeration of restricts to that of . Their union is consequently an order isomorphism from to . This proves the asserted equality. Without the initial segment condition it fails: in , take . Then , whose union is , but .
For decreasing sets, is a nonincreasing sequence of ordinals. Its set of values has a least member, attained at some ; all later values must equal it. Hence the sequence is eventually constant. The intersection formula nevertheless fails: take . Every has order type , whereas their intersection is empty and has order type zero. Thus .
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 83 4 Solution Created 2026-10-03 Updated 2026-10-14
The maximum is . We construct that many aleph-one-like linear orders, whose proper initial segments are countable, and prove that they are nonisomorphic. As usual the rational-type requirement concerns nonempty proper initial segments; the empty segment occurs in every order.
Let be the club set of nonzero limit ordinals below . For , form the order sumHere means a new least point followed by a copy of the rational numbers; distinct blocks are disjoint, and all points of an earlier block precede every point of a later one. Every block is countable, dense and has no greatest point. Since , the full total order has neither a least nor a greatest point. It has size .
The sum is dense: within a block use density, and for points in different blocks choose a larger point in the earlier block. If is a proper initial segment and lies in block , then is contained in the union of the blocks through . There are only countably many such blocks, each countable. Thus is countable, rather than an uncountable interval in an aleph-one-dense order.
Every nonempty is dense and has no least point. If it has no greatest point either, the back-and-forth method gives : enumerate both orders, alternately include the least unused element from either enumeration in a finite partial order isomorphism, and choose its partner in the appropriate open interval. Density and absence of endpoints always supply a new partner. The union is a bijective order isomorphism. If has a greatest point, remove it, apply the same argument, and reattach it. Hence every nonempty proper initial segment is isomorphic to or .
The stationary information is recorded at the limit cuts. WriteThis is a continuous increasing kappa-filtration by countable initial segments. At a limit , the complement has a least point exactly when .
Suppose is an order isomorphism. Since each filtration stage is countable, its image under and the corresponding image under are bounded in block index: the supremum of their countable collection of countable ordinals remains below . Choose so thatThe setis a club set. To see unboundedness, start above any given ordinal and recursively choose larger than every for . The supremum of the countable sequence remains below and belongs to . Closure follows because below a limit of members of , each fixed lies below one of those members.
For , continuity of the filtrations gives both inclusions needed forThe isomorphism therefore preserves whether the complementary final segment has a least point. ConsequentlyThis club agreement of countable filtrations proves the invariant: if is stationary, the orders cannot be isomorphic.
We also construct enough pairwise different stationary encodings. For each , fix an injection , and setFor fixed , these sets partition the stationary tail . At least one is stationary: otherwise choose a club avoiding each one and intersect the countably many clubs to obtain a club avoiding the entire tail. The countable-intersection fact follows directly: above any starting point choose an increasing sequence, visiting each club infinitely often; its countable supremum belongs to every club by closure. For each let be the least such . One value occurs for uncountably many , since a countable union of countable sets is countable. For that fixed the cells are pairwise disjoint, by injectivity of . Enumerating those cells givesa family of pairwise disjoint stationary subsets of . This is the explicit Ulam matrix on omega-one proof of disjoint stationary subsets of omega-one.
For put . If , their symmetric difference contains an entire and is stationary. The stationary encoding in an aleph-one-like dense order therefore produces pairwise nonisomorphic orders .
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 25 5 Solution Created 2026-10-03 Updated 2026-10-06
For , write a number in hereditary base : express its base- expansion as , with , and recursively expand every exponent in the same base. Let , for , be the number obtained by replacing every occurrence of the base in this hereditary expression by . Coefficients and the symbols for addition and exponentiation are retained.
For a starting number , define its Goodstein sequence by andThe Goodstein function is the termination-time functionThis choice counts transitions from the initial term; a convention counting the initial term as well shifts the answer by one. For example the sequence starting at is , so . Starting at gives , illustrating why descent of the numerical terms is not the termination argument.
Define the ordinal rank of a Goodstein term by replacing the base in the hereditary expansion by , at every exponent depth. The result is in Cantor normal form and lies below , called epsilon zero, the least nonzero solution of . Finite hereditary expressions have finite nesting depth, so their ranks are bounded by a sufficiently high finite tower of powers of .
For a fixed base, is strictly increasing. To see this, compare two ordinary base- expansions at their largest differing exponent. By induction through the hereditary exponent expressions, their exponents have the same ordering after replacing by ; computable Cantor normal form notation then uses the same first differing exponent or coefficient. AlsoIndeed after the base change all coefficients remain below , the recursively changed exponents remain correctly ordered, and replacing the new base by gives exactly the original ordinal expression. These facts can be proved together by structural induction for primitive recursive functions on the hereditary expression.
Consequently, whenever ,An infinite nonzero Goodstein sequence would give an infinite descending sequence of ordinals below , impossible because ordinals are well-ordered. Thus the Goodstein function is total. Its steps are effective finite operations, so simulating the sequence until zero also proves that it is a total computable function.
The same ordinal notation system gives the requested decidable well-order. Let consist of canonical finite terms for zero and for expressionswhere the exponents are themselves canonical terms. Membership in is decidable by recursively checking the syntax, positive coefficients and decreasing exponents. Comparison is decidable by recursive computable Cantor normal form notation, first of exponents, then coefficients, and then the remaining summands. All recursive calls inspect proper subterms, so the algorithm terminates.
Interpreting these terms as ordinals gives every ordinal below , uniquely. One way to connect this directly to hereditary base representations is to choose, for a given finite ordinal term, a base larger than every coefficient anywhere in that term. Replacing by that base evaluates it to a natural number whose hereditary representation recovers the ordinal term. Thus all bases together supply the complete notation system; a single fixed base is not enough.
Choose an effective injective coding of finite terms by natural numbers, and enumerate the valid codes in increasing numerical order. The resulting bijection is computable: validity is decidable and there are infinitely many finite-ordinal terms. Its inverse is computable by counting valid codes below a given code. DefineThis is a decidable relation on all of . The interpretation into ordinals is an order isomorphism onto , provingDecidability here concerns comparing two notations. Well-foundedness is supplied by their ordinal interpretation, the same mathematical descent principle used to prove Goodstein's theorem.