Past exam of the computer science course of the University of Oxford 2018 Algorithms 1 a Solution 2026-10-31
A binary search tree is a binary tree storing distinct keys from a total order, with every key in a node's left subtree smaller than that node's key and every key in its right subtree larger. The condition concerns entire subtrees, not just immediate neighbours.
For membership, start at the root of a tree and compare the target with the current key. Return true on equality; continue into the left subtree for a smaller target and the right subtree for a larger target; return false on an empty subtree. The binary search tree ordering ensures that a discarded subtree cannot contain the target. Each step descends one level, so the algorithm terminates and uses time complexity for height of a binary tree , under constant-time key comparison.
Past exam of the logic and set theory course of the University of Oxford 2009 B 5 vii Solution 2026-10-31
For the cardinality of total orders on a countably infinite set, a total order on is a subset of , so there are at most such orders. To obtain the lower bound, associate to every binary sequence an order by placing the two-element blocks in increasing order of . Inside block , use when and reverse them when .
This is a total order for every sequence. Distinct sequences differ on the comparison of some adjacent pair and therefore produce distinct relations. Thus binary sequences inject into the order set, provingThe construction counts distinct orders on the labelled set, even though the resulting order types are all isomorphic to the usual natural-number order.
Past exam of the mathematics course of the University of Cambridge 2002 ib Paper 2 13G b Solution Created 2026-09-24 Updated 2026-10-14
The lexicographic order is a total order. Each point lies in the order interval between and , so the order intervals cover .
If lies in both and , let and in that total order. Then andIn particular an order interval contains and is contained in the intersection. Both conditions of part (a) hold, proving that these intervals form a basis of a topology. The resulting topology is the lexicographic order topology on the real plane.
Past exam of the mathematics course of the University of Cambridge 2002 iii Paper 4 2 Solution 2026-10-14
The Ohnishi orderability criterion states that, for each finite list , there are signs such that the semigroup of nonempty products of conjugates of does not contain . The conjugates are essential for a two-sided invariant total order. Necessity follows by choosing all signed elements positive: their conjugates and nonempty products are still positive.
For sufficiency, consider the compact product . Impose the closed conditions that an inverse has the opposite sign, that conjugation preserves sign, and that a product of two positive elements is positive whenever it is nonidentity. A positive pair cannot multiply to the identity because of the inverse condition. Each condition uses finitely many coordinates. Given finitely many conditions, collect every nonidentity element appearing in them into a finite list and choose signs using the criterion. These signs satisfy the conditions: an incorrectly negative product would contribute its positive inverse to the generated semigroup, producing identity with the positive factors; an incorrect conjugate or inverse gives the same contradiction. Extend the signs arbitrarily to the remaining coordinates. Thus the finite intersection property and compactness give a global sign assignment. Its positive elements form a conjugation-invariant semigroup with and . Defining by gives the required linearly ordered group.
Restriction shows that every finitely generated subgroup of an orderable group is orderable. Conversely, suppose every such subgroup is orderable. If the criterion failed on , each of the finitely many sign choices would have an identity witness made of finitely many conjugates. Collect all and all conjugating elements in these witnesses into one finitely generated subgroup . An order on supplies one positive sign choice, but its corresponding witness is a nonempty product of positive elements in , a contradiction. Hence the criterion holds in .
Finally, a finitely generated subgroup of a torsion-free abelian group is by the Fundamental theorem of finitely generated abelian groups. Its lexicographic order is two-sided invariant. Applying the local-to-global conclusion proves that every torsion-free abelian group admits the required order.
Past exam of the mathematics course of the University of Cambridge 2002 iii Paper 4 3 A Solution 2026-10-14
For each , choose a value in a lattice-ordered group , using Zorn's lemma. Such a value is a prime convex lattice subgroup. Otherwise the last construction in Question 1(i) would give two larger convex lattice subgroups whose intersection is ; maximality among subgroups omitting would put in both, hence in their intersection. Thus the right coset set is a totally ordered set.
Right multiplication defines an action . It is well-defined, preserves the total order, and has inverse . The coset formulas from Question 1(i) show pointwise preservation of both join and meet, becauseand likewise for the meet.
Take the disjoint union of these chains, arranged in any fixed order sum of the indices . Let every act on each component by . This gives a lattice-ordered group homomorphism into the order automorphisms of one chain. It is injective: a nonidentity moves the identity coset in , since . Its image is closed under pointwise join and meet, giving exactly the required lattice-ordered permutation group. This is the Holland representation theorem.
Past exam of the mathematics course of the University of Cambridge 2002 iii Paper 4 5 Solution 2026-10-14
The additive Abelian group is divisible because it is a real vector space. Each convex subgroup is divisible too: for in and a positive integer , its unique additive quotient satisfies , hence belongs to . Negative elements follow by taking inverses. Thus all are rational vector subspaces, independently of whether the given real scalar multiplication respects the order.
Choose an ordered-group isomorphism . It is rational-linear, since additive homomorphisms between divisible torsion-free groups preserve division by integers. Extend a rational basis of to one of ; equivalently choose a rational-linear section of composed with the quotient map. ThenSince and the union is , each has a unique expression with only finitely many nonzero coefficients. Define . This is an injective additive group homomorphism. If is the largest active coefficient, the image of in the ordered quotient has sign equal to that of . Convexity ensures that this is also the sign of .
The maximum-support convention for the Hahn group uses precisely finite supports and the sign of the largest active coefficient. Hence preserves and reflects the total order, and therefore preserves join and meet. This proves the finite-support Hahn embedding along a countable convex chain. In fact every finite coefficient sequence is obtained, so is an ordered-group isomorphism in this convention; the requested embedding follows.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 36 1 c Solution Created 2026-10-03 Updated 2026-10-14
First pass from the preorder to a partial order. Define the indifference relation by and . Reflexivity and transitivity make this an equivalence relation. On the quotient set , putTransitivity makes this independent of the representatives, and the quotient relation is antisymmetric, hence a partial order.
We need its order-extension property, including freedom to order incomparable classes. Here is the argument. Order all partial order extensions of by inclusion. The union of a chain of extensions is again a partial order: any finite list of comparisons needed to check an axiom occurs together in one member of the chain. Zorn's lemma therefore supplies a maximal extension. If two classes remain incomparable, adjoin and take the transitive closure of a relation. The only possible new comparisons have the form . A cycle would require a previously existing path , contradicting incomparability. The enlarged relation is still a partial order, contradicting maximality. Consequently the maximal extension is a total order. This also proves the Szpilrajn extension theorem used here.
Lift such a total order to the original bundles by comparing their equivalence classes. The lifted preference relation is complete and transitive, contains , and preserves its strict preference: if , their distinct classes satisfy , and antisymmetry of the extended order prevents the reverse comparison. In particular, the class is nonempty and .
For the reverse inclusion, take a pair with . If , then , so every member of strictly ranks above and excludes . If neither comparison holds, their classes are incomparable. First adjoin , which creates no cycle by the preceding argument, and then extend to a total order. Its lift belongs to and again excludes . Thus every pair outside is outside at least one member of , provingThe intersection proof is an order-theoretic fact about any preorder. The congruence axiom additionally ensures exact rationalization of the observed demand correspondence: every chosen bundle weakly outranks every affordable bundle, while an affordable unchosen bundle is strictly worse by part (b). Hence each completion's budget-maximizing set is exactly the observed chosen set.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 25 8 Solution Created 2026-10-03 Updated 2026-10-14
For the Ehrenfeucht-Mostowski theorem, start with an infinite structure and a total order . Choose a Skolem expansion , and adjoin constants for . Require the elementary diagram of , distinctness of these new constants, and the order-indiscernible sequence schema: any two increasing tuples of the of the same length satisfy the same first-order formulas in the expanded language. Every finite fragment mentions finitely many new constants and finitely many first-order formulas. Enumerate a countably infinite subset of . For each of the finitely many first-order formulas, color its increasing tuples by its truth value in , including whatever fixed parameters occur in the fragment. Successive applications of the infinite Ramsey theorem leave an infinite subset homogeneous for all these colorings. Assign the finitely many new constants to distinct elements of this subset in their index order. Their finite indiscernibility requirements and the elementary diagram are then simultaneously satisfied.
The compactness theorem supplies an elementary extension containing the required distinct indiscernibles. Their Skolem hull is an elementary substructure: an existential first-order formula true of its elements has its chosen Skolem-function witness in the hull, so the Tarski-Vaught test applies. Any order automorphism of acts on this hull byIndiscernibility makes this well defined, since every equality of two term representations is preserved. The same argument preserves every first-order formula; the inverse is given by . Thus it is an automorphism, uniquely determined in the language of the chosen Skolem expansion by its values on the generators. This proves both the indiscernible-model and automorphism forms of the Ehrenfeucht-Mostowski theorem. Uniqueness is not claimed for automorphisms of the reduct which need not preserve the chosen Skolem functions.
For simple typed set theory with atoms, write for the set predicate at sort . Members have sort one lower; urelements have no typed members, extensionality applies to sets, and every well-typed first-order formula defines a set at the next sort. Typical ambiguity adds for each closed sentence, where raises every sort by one. We prove finite satisfiability using Ramsey theorem, rather than assuming that adjacent sorts have the same cardinality.
Let . If , then . For increasing integers , interpret sort by , interpret by the objects of , and interpret adjacent-sort membership by actual membership restricted to these designated sets. All other objects of a sort are typed urelements. Every subset of is a designated set in , so comprehension holds for every first-order formula, including first-order formulas with quantifiers and parameters at other sorts. Two designated sets with the same members are equal, while the other objects have no typed members. Thus this is a full model of the typed axioms for every increasing sequence of levels. The extra preceding level gives a consistent interpretation of the bottom set predicate as well.
Take finitely many ambiguity sentences and let bound their highest sort before raising. Color increasing -tuples by the vector of truth values of these sentences in the corresponding finite sorted structure. There are finitely many colors. The infinite Ramsey theorem supplies an homogeneous set of indices. Choose the level sequence from it. The sentence is evaluated in the window , while is evaluated in the next window ; homogeneity makes their truth values equal. Sentences using fewer sorts simply ignore the unused final levels. Thus every finite family of ambiguity axioms has a model satisfying all the typed axioms. Apply many-sorted first-order compactness theorem to obtainThis is a relative consistency construction in the ordinary set-theoretic metatheory. Allowing urelements is essential here: skipping ranks leaves objects outside the represented power sets, and those objects must be permitted as urelements.
Past exam of the mathematics course of the University of Cambridge 2006 ii Paper 3 16H a Solution Created 2026-09-24 Updated 2026-10-14
The reflexivity, antisymmetry, transitivity and totality axioms for a total order are universal with quantifier-free formula matrices, and hence inductive with an empty existential block. Add and , with strict inequalities expressed using and inequality. These exclude least and greatest elements. This theory is inductive.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 26 6 Solution Created 2026-10-03 Updated 2026-10-14
The Ehrenfeucht-Mostowski theorem asserts that an infinite first-order structure has, for any prescribed total order , an elementary extension containing distinct order-indiscernibles . After a Skolem expansion, the Skolem hull of those generators is a model of the original complete theory. Every order automorphism of extends to a unique automorphism of this specified Skolem hull in the expanded language.
Choose a Skolem expansion of the original infinite structure: for each existential formula, select a witness function, including nullary functions when needed. Add constants for and the elementary diagram of a structure of , using separate names for its elements. Require for distinct indices, and for each formula in the Skolem language requirewhenever both index tuples are strictly increasing. These are the order-indiscernible sequence requirements.
Every finite fragment is satisfiable in . Choose a countably infinite sequence of distinct elements of . The fragment mentions only finitely many formulas and arities. Color increasing -tuples of that sequence by the finite vector of truth values of its relevant -ary formulas. The Ramsey theorem supplies an infinite homogeneous subsequence; repeat for the finitely many arities. Assign the finitely many named to distinct elements of the final homogeneous subsequence in increasing index order. The fixed finite part of the elementary diagram of a structure already holds in . By the compactness theorem proved in Question 5, the full set of requirements has a model , giving the required elementary extension and order-indiscernible sequence.
Let comprise all values of Skolem-language terms in finitely many . It is closed under the witness functions. If for parameters in , the specified witness function supplies a witness in . Induction on formulas therefore gives ; its reduct is a model of . For infinite , its cardinality is at most and at least .
For an order automorphism , defineRewrite any finite list of indices in increasing order, allowing a term to repeat or omit variables. The order-indiscernible sequence property transfers every equality between terms and every relation among their values, making this definition well defined and elementary. Applying gives its inverse. All of is generated by the and the named Skolem functions, so an automorphism extending must have precisely this action. Thus , with uniqueness in the Skolem expansion. This uniqueness need not hold in the unexpanded reduct.
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 23 4 c Solution Created 2026-10-03 Updated 2026-10-06
Use the one-relation language and the total orderswhere the second is the order sum: every point in its natural-number block lies below every point in its integer block.
To show II wins every finite Ehrenfeucht-Fraïssé game, use the interval threshold strategy for discrete linear orders. With rounds left, corresponding open intervals and end rays between already matched points have either the same size below , or both have at least elements. Their sizes may be infinite. The chosen-point correspondence is order preserving. Initially the unique interval is infinite in both orders, so the invariant holds.
If I chooses a repeated point, II repeats its counterpart. If I chooses in a short interval, II chooses the point with the same finite rank in the matching interval. In a long interval, let . If one side of the chosen point has fewer than elements, reproduce that size in the other interval; the opposite sides then both have at least elements. Otherwise choose a response having at least elements on each side. Such a response exists because the interval has at least elements. The endpoint and successor/predecessor properties of these two discrete orders allow the finite small-side counts to be reproduced. This establishes the invariant with rounds left and gives a finite-game winning strategy. Therefore II wins the timed game.
In the infinite Ehrenfeucht-Fraïssé game, I first chooses a point in the integer block of . It has infinitely many predecessors. II must respond with some , which has exactly predecessors. I then chooses distinct predecessors of . To preserve order and equality, II would need distinct points below , which is impossible. ThusI chooses the required finite length only after seeing II's first response, which explains why this does not contradict the timed-game result.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 135 4 Solution Created 2026-10-03 Updated 2026-10-05
One form of the Ehrenfeucht-Mostowski theorem says that, for every infinite first-order structure and every total order , an elementary extension contains distinct elements forming an order-indiscernible sequence. After a suitable Skolem expansion, their Skolem hull is a first-order model of , and every order automorphism of extends to a structure automorphism of that hull. If has a definable infinite linearly ordered subset , the generators may lie in and their order may agree with that definable order. Uniqueness of the extended structure automorphism is asserted in the chosen Skolem expansion, rather than for every structure automorphism of its reduct.
Here is an ultraproduct proof of the Ehrenfeucht-Mostowski theorem. First expand to with Skolem functions for all existential first-order formulas, iterating through the enlarged languages if necessary. This is done in the ordinary classical metatheory; the choice restriction in question 1 is not a restriction on this question. Fix a nonprincipal ultrafilter on .
We can obtain an infinite sequence of distinct elements in an elementary extension of by one preliminary ultrapower. For each choose a finite list of distinct elements of . Represent by the function taking the th entry when , with an arbitrary default otherwise. Distinctness holds on a cofinite set, so follows from Łoś theorem. In the definably ordered variant, first name any parameters defining , and choose each finite list increasingly inside instead; then and for . Infinitude of an ordered set supplies every finite increasing chain. This preparatory step uses no Ramsey theorem.
For a finite subset of , define the ultrafilter on by nested membership, in this order:where means . This is the ordered Fubini product of ultrafilters. Closure under intersections and the decision between a set and its complement hold at each nested level, proving it is an ultrafilter. For take the principal ultrafilter on the one-point product. PutIf , pull a function back along the projection . A test independent of an omitted coordinate is unchanged by its ultrafilter quantifier, so projection pushes to . The induced map is therefore an elementary embedding by Łoś theorem. These maps are coherent, giving a directed system indexed by finite subsets of .
Take its directed limit of elementary embeddings . One can verify elementarity directly: representatives of a finite tuple occur at a common stage; functions and atomic relations are interpreted there. In the existential step, a witness in the limit occurs with the parameters at some later common stage, and elementarity pulls the existence statement back. Thus every embeds elementarily into , which contains an elementary copy of .
For , let be the class of the coordinate function . Projection coherence makes this independent of . If , then for each fixed the set is cofinite. The nested test therefore gives . In the ordered variant, the same argument with gives and .
For every first-order formula of the expanded language and every increasing tuple , Łoś theorem givesThe right-hand side depends on the first-order formula and tuple length, not on the indices. This proves order indiscernibility in the expanded language. Let be the Skolem hull of the generators in . The Tarski-Vaught test gives , and its reduct is a first-order model of .
An order automorphism of acts byIndiscernibility makes this well defined: combine the finite supports of two term expressions into one increasing tuple, and apply indiscernibility to their logical equality. Applying it to relation first-order formulas proves preservation of all relations; the inverse is induced by . Every element of the hull is such a term, so the extension is unique among structure automorphisms preserving the Skolem expansion. MoreoverThis proves the theorem, including its ordered version and structure automorphism conclusion, using ultrapowers and a directed limit throughout.
Past exam of the mathematics course of the University of Cambridge 2022 iii Paper 120 2 c Solution 2026-09-28
The Ehrenfeucht-Mostowski theorem says that if a first-order theory has an infinite model, then for every total order there is a model generated as the Skolem hull of distinct order indiscernibles , and every order automorphism of extends to an automorphism of .
Given an infinite cardinal , let with the lexicographic order, viewed as consecutive copies of the rational order. In each copy independently choose either the identity or a fixed nonidentity order automorphism of . These choices give distinct order automorphisms of .
Apply the theorem to this order. Distinct order automorphisms act differently on the distinct generators , so their extensions give an injection into the automorphism group of a first-order structure . Therefore , proving that has models with arbitrarily large automorphism groups.
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 3 16F v Solution Created 2026-09-24 Updated 2026-09-25
This class is not axiomatisable. It contains an infinite model, for example the total order . If a theory in any fixed expanded language axiomatized it, choose a cardinalThe Upward Lowenheim-Skolem theorem would give a model of of cardinality at least . Its underlying order cannot be isomorphic to a subset of , because every such subset has cardinality at most . This contradiction proves the claim.
Take the natural numbers including zero with their usual total order:A nonempty subset with an upper bound is contained in the finite set . It therefore has a greatest element, which is its least upper bound. The empty subset has least upper bound . Thus is a bounded-complete partially ordered set.
But is a directed set, since is above any two members. It has no upper bound in : for any proposed bound , the member is larger. It therefore has no least upper bound. Hence
Totality of the binary relation is expressed byWhen is already an order, this adds comparability and makes it a total order. In fact this first-order sentence alone entails .
By the definition of semantic entailment, means that every first-order structure satisfying also satisfies . Let be any such first-order structure, and let be any element of its domain of a first-order structure. The instance of with gives , which is true only if is true. Since was arbitrary, . ThereforeThere is no exception for in the displayed totality axiom; that case is exactly what forces the reflexive relation property.
In this first-order structure, says and . Thus is an upper bound of . The universally quantified clause says that if is any other upper bound, then . Therefore is their least upper bound. In the usual total order on the natural numbers, this is their maximum:This describes a condition on the values assigned to the free variables ; itself is not a closed first-order sentence.
Use an upper type bound requiring each element type to implement the supplied comparison interface for its own type. This is F-bounded polymorphism.Use this locally defined
trait Ordered[T] {
def <(that: T): Boolean
}
class MinSet[T <: Ordered[T]](contents: List[T])
extends Set[T](contents) {
def min: T = {
require(elems.nonEmpty)
var best = elems.head
var rest = elems.tail
while (rest.nonEmpty) {
if (rest.head < best) best = rest.head
rest = rest.tail
}
best
}
}Ordered, rather than silently substituting the standard library's different comparison interface. The type bound makes rest.head < best well typed. To interpret the result as a minimum, require the comparison to be a consistent strict total order; merely providing a method named < cannot establish its mathematical laws.The loop invariant is that
best is a minimum among the entries already inspected, and rest is exactly the uninspected suffix. Comparing its next head with best preserves that property. The loop variant is the length of rest. On termination,The method leaves the set unchanged, takes time complexity under constant-cost comparisons, and uses constant auxiliary space. It requires a nonempty set; inherited insertion and deletion continue to preserve the duplicate-free representation invariant.