Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 26 2 i Solution Created 2026-10-03 Updated 2026-10-14
Order the collection of all chains in a partial order, including the empty chain, by inclusion. Suppose that were an order-preserving injection. The chain-poset nonembedding lemma follows by a transfinite recursion of length the Hartogs ordinal :Inductively, the previously constructed points form a strictly increasing chain. If , then , since belongs to the latter but not the former. Monotonicity gives , and injectivity makes this inequality strict. Thus the recursion continues at every and gives an injection , contradicting the defining property of the Hartogs ordinal. Therefore The empty chain is part of the convention: excluding it would make a one-point poset a counterexample.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 83 1 ii Solution Created 2026-10-03 Updated 2026-10-14
Order the collection of every chain in a partial order, including the empty chain, by inclusion. Suppose that is an order-preserving function and an injection. Let be the Hartogs ordinal: by Hartogs theorem, no injection from to exists.
Use transfinite recursion to define, for ,We verify both that is defined and that the values are strictly increasing. Assume inductively that the earlier values are strictly increasing. Then is a chain in a partial order. For any , , so the fact that is order-preserving gives . Furthermore , whereas by distinctness of the earlier values. Thus , and injectivity gives . We have provedThe empty initial chain starts the induction, and the same argument applies at every limit ordinal.
If a globally defined recursion rule is desired, apply when the earlier range is a chain and otherwise use the fixed value . The induction shows that the fallback case never occurs. Thus no choices of new points are being made: the function uniquely determines every stage.
The resulting function is an injection from to , contrary to its defining Hartogs ordinal property. Hence the chain-poset nonembedding lemma gives