Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 121 2 iii Solution Created 2026-10-03 Updated 2026-10-05
Let be the ordinal height of a model of set theory. First . Indeed, if were countable, the internal axiom of choice would give, for every , a bijection in between and some ordinal below . Such a bijection is also valid externally, making externally countable. In particular every internal rank , , would be countable. Every element of lies in one of these internal ranks, sowould be a countable union of countable sets, a contradiction. This is why an uncountable transitive set model has uncountable ordinal height.
For , absoluteness of constructible levels gives , and that level is an element of . The reason is that satisfaction in a fixed set structure uses the same domain and finite formulas in both universes, so successor definitions agree; transfinite recursion then also makes limit stages agree. Transitivity consequently givesIt remains to locate a countability witness. Given an ambient countable ordinal , choose an injection . Since , it belongs to the constructible universe. Its transitive closure, together with itself, is countable. Choose a countable elementary substructure of a sufficiently large limit level containing this closure pointwise. The condensation lemma for the constructible universe identifies the collapse with for some countable . The collapse fixes , since all its hereditary members were included. Thus .
The ordinal itself is in , since . Being an injection between these fixed sets is a bounded formula in set theory, so recognizes as a countability witness. This proves countable-ordinal correctness under constructibility:The use of condensation supplies a witness below the height of ; merely knowing that belongs somewhere to would not be sufficient.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 121 2 i Solution Created 2026-10-03 Updated 2026-10-05
The constructible hierarchy is defined by transfinite recursion using the definable power set. With parameters permitted in the internal definitions, write for the definable subsets of . ThenIts class union is the constructible universe . Only subsets definable over using a first-order formula and finitely many parameters from enter at a successor stage.
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 130 4 i Solution Created 2026-10-03 Updated 2026-10-05
The two Ramsey properties and the topologies. Write for the space of infinite subsets of the natural numbers, and for the infinite subsets of . The positive integers are used throughout. A Ramsey set of infinite subsets has the property that every infinite contains an infinite for which lies wholly in or wholly in .
For finite and infinite above , letThese are the basic neighbourhoods of the Ellentuck topology, denoted in the question. They form a basis: if belongs to two such sets, their stems are comparable initial segments of ; take the longer stem and the intersection of the two tails beyond that stem. This intersection contains the infinite remaining tail of and yields a basic set contained in both.
A completely Ramsey set allows such a homogeneous refinement inside every , with infinite and the stem kept fixed. Taking shows that complete Ramseyness implies Ramseyness. The ordinary topology on infinite subsets has basic cylindersIt is the usual product topology on increasing enumerations and is coarser than the Ellentuck topology.
Examples distinguishing the properties. A non-Ramsey example uses the axiom of choice. Let and enumerate all infinite sets as . Each has cardinality : an enumeration of gives the upper bound, and choosing one element from each of infinitely many disjoint pairs gives an injection from all binary sequences for the lower bound.
By transfinite recursion, choose two distinct, previously unused elements at each stage. Fewer than elements have been used at stage , so this is possible without any assumption on the Continuum hypothesis. Put . All the remain outside , since subsequent choices also avoid previously chosen elements. Every contains one and one , so is not a Ramsey set of infinite subsets. This is the non-Ramsey set from transfinite selection construction.
Perform the same construction on , giving a non-Ramsey set , and putFor any infinite , the infinite set has , so is a Ramsey set of infinite subsets. But no with infinite is homogeneous, because meets both and its complement. Therefore is not a completely Ramsey set.
Every star-open set is completely Ramsey. We give the full fusion proof for open Ellentuck sets, without quoting an infinite Ramsey theorem. Fix a star-open set and a basic set . For finite and an infinite tail above , say accepts if ; it rejects if no infinite subset of accepts . Both properties persist under passing to infinite subsets. Every infinite tail can be thinned to decide : take an accepting subset if one exists, and otherwise the original tail rejects it.
First thin to decide . If it accepts, the required homogeneous neighborhood has already been found. Otherwise keep a rejecting tail. We now fuse to an infinite set deciding every finite , where the decision for is made by .
To do this, choose successively from an infinite current tail. After choosing , thin the tail above to decide each of the finitely many subsets of , one after another, before choosing the next element. For any finite , at the stage when its largest element is selected, the current tail decides and contains every later selected element. Heredity therefore gives a decision on . For , rejection persists from the initial tail.
If rejects , only finitely many can have accepting . Otherwise let be the infinite set of those . Every member of has a first new element , and its remaining tail lies in . It therefore belongs to by acceptance of . This would make accept , contradicting rejection.
Thin a second time to so that every finite is rejected. Start with the rejected empty set. At a finite stage, all subsets of the selected elements are rejected. For each of these finitely many subsets, avoid its finitely many next elements that would give an accepted extension, and choose the next beyond all excluded elements. Since decides every finite extension, each new extension is rejected. Induction gives the asserted property of .
We claim . If , openness provides a basic set containing . Extend , if necessary, to an initial segment of containing . Write with finite . The infinite tail lies in andIt is therefore an accepting subtail for , contradicting rejection. We have found either an accepting neighborhood or a neighborhood disjoint from . Thus
Basic neighborhoods are clopen. Consider and a point outside it. If is not an initial segment of , take an initial segment of of length at least ; its ordinary cylinder cannot meet . Otherwise some element of is outside ; take through that element, and again is disjoint from .
Thus the complement of is already open in the ordinary topology on infinite subsets, and hence in the finer Ellentuck topology. A basic neighbourhood is open by definition, so
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 1 16G Solution Created 2026-09-24 Updated 2026-10-03
Ordinal exponentiation is defined by transfinite recursion:when is a nonzero limit ordinal. If , each successor step and each supremum show that is nondecreasing. If , transfinite induction strengthens this to strict increase: , and the value at a limit exceeds every earlier value.
Strict increase can disappear when the base changes. For example, with ,because for every positive finite , both finite powers have leading term , and taking the supremum gives .
We next proveApply transfinite induction to . The zero and successor cases follow directly from the recursive definitions and the associativity of ordinal multiplication. At a limit , continuity of ordinal multiplication in its right argument givesThe superficially similar identity is false: for , , and ,
Finally,For the first equivalence, bases zero and one fail, while strict increase embeds every countable ordinal into the powers of any base . For the second, immediately gives . Conversely, if , then . Every exponent below the first uncountable ordinal is countable, so each has cardinality at most ; the supremum of such ordinals still has cardinality at most and is therefore below the second uncountable ordinal .
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 2 16I Solution 2026-10-03
The inductive definition of ordinal addition is the transfinite recursionfor every nonzero limit ordinal . The synthetic definition takes disjoint well-orders and of order types and , puts every member of before every member of , and defines to be the order type of this ordered sum.
These definitions agree by transfinite induction on . The empty second order contributes nothing; adjoining a greatest element gives the successor clause; and a limit well-order is the union of all of its proper initial segments, so its ordered sum with has order type .
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 3 16I Solution 2026-10-03
We prove simultaneously by transfinite induction that every is a transitive set and that . The claims are immediate for . Suppose first that is transitive. If , then , so . Moreover, transitivity says that every satisfies , and henceThus is transitive and . At a limit , if , then for some ; transitivity of gives . The inclusions at successor stages also imply
Finally, the rank of a set is the ordinalEvery belongs to , so . Thereforewhich proves that every set occurs in the hierarchy.
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 2 16F a Solution Created 2026-09-24 Updated 2026-09-25
The synthetic definition takes the order type of the disjoint union of a copy of followed by a copy of : every point of the first copy precedes every point of the second, and each copy retains its original total order.
Fix and use transfinite induction on . The synthetic sum with the empty order is . Appending a greatest element produces the successor ordinal rule. At a limit ordinal , the second copy is the union of its initial segments of types , so the whole order has type
. Thus the synthetic operation satisfies the inductive recursion; uniqueness in transfinite recursion proves the definitions equivalent.
. Thus the synthetic operation satisfies the inductive recursion; uniqueness in transfinite recursion proves the definitions equivalent.
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 4 16F a Solution Created 2026-09-24 Updated 2026-09-25
We prove by transfinite induction that every is a transitive set. The claim is immediate for . If is transitive and , then , so . Transitivity also gives , hence . At a limit stage, if , then for some , so .
Past exam of the mathematics course of the University of Cambridge 2025 ii Paper 1 16H a Solution Created 2026-09-24 Updated 2026-09-25
For a well-order , define recursivelyTransfinite recursion makes an isomorphism from onto a transitive set of transitive sets, hence onto an ordinal. If two ordinals were isomorphic, the first point where the isomorphism differed from the identity would contradict preservation of their initial segments. Thus this ordinal is unique.
Past exam of the mathematics course of the University of Cambridge 2025 ii Paper 3 16H a Solution Created 2026-09-24 Updated 2026-09-25
By choice-function well-ordering construction, use transfinite recursion to choosewhenever the set on the right is nonempty. The chosen elements are distinct, so if this construction continued through the Hartogs theorem ordinal , the map would inject into , a contradiction. It therefore stops at some ordinal . At the stopping stage every element of has been selected, and henceis a bijection .
Assuming the axiom of choice, every set has such a choice function on its nonempty subsets. Transporting the membership order on across the bijection well-orders . Thus the axiom of choice implies the well-ordering theorem.
Proof outline of Zorn's lemma 2026-10-14
Assume the axiom of choice and suppose a poset satisfying the hypothesis has no maximal element. Fix a choice function on its nonempty subsets. By transfinite recursion, choose at each ordinal stage an upper bound of the chain in a partial order already constructed, then choose a strictly larger member. Both choices are available, including the initial empty stage. This produces distinct members throughout the Hartogs ordinal of , contradicting the Hartogs theorem. Thus a maximal element exists. Conversely, apply Zorn's lemma to partial choice functions on a family of nonempty sets, ordered by extension. A chain in a partial order has the compatible union as an upper bound, and a maximal element must be defined on the whole family, since one missing value could be adjoined.
Zorn's lemma was introduced in 1935 to shorten algebra proofs using choice or the well-ordering theorem.[ref]
Zorn’s Lemma and Some Applications by Keith Conrad. Zorn’s Lemma and Some Applications, §1, p. 4, paragraph on the 1935 introduction to shorten algebraic proofs
ZF without foundation 2026-10-31
ZF without foundation consists of the axioms of Zermelo–Fraenkel set theory with the Axiom of foundation omitted. Ordinal-indexed transfinite recursion still defines the cumulative hierarchy. Its union is the well-founded part and need not include all ambient sets.