Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 19 7 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
One useful form of the Ehrenfeucht-Mostowski theorem is this: for an infinite first-order structure and any total order , there is a first-order model of generated in a chosen Skolem expansion by an order-indiscernible sequence of distinct elements. Every order automorphism of induces an structure automorphism of this expanded hull. One can additionally obtain an elementary extension containing by including its elementary diagram. Uniqueness of the induced structure automorphism is asserted in the Skolem expansion, not among arbitrary structure automorphisms of the reduct.
Choose a Skolem expansion : for every existential first-order formula choose a witness function, satisfying . Iterate the expansion if necessary so witnesses are available for first-order formulas in the resulting language. Add constants and require for distinct indices. For every first-order formula of the expanded language and every two increasing index tuples, addTogether with , this is the indiscernibility theory.
Every finite fragment is satisfiable. It mentions only finitely many first-order formulas and index constants. Choose a countably infinite sequence of distinct elements of . For each relevant arity, colour increasing tuples from that sequence by the finite truth vector of all first-order formulas of that arity in the fragment. Successive applications of the infinite Ramsey theorem for r-sets leave an infinite subset homogeneous for each of these finitely many finite colourings. Interpret the finitely many index constants by distinct elements of that subset in increasing enumeration order. All the required truth-value equivalences then hold, and the original structure satisfies the finite part of its own theory.
If an actual elementary extension of is desired, include constants for its elements and the elementary diagram of . A finite fragment still contains only finitely many parameter instances; include those truth vectors in the same colourings. Thus finite satisfiability is unchanged. The compactness theorem now supplies a first-order model with the entire indiscernible sequence, and in the diagram version an elementary copy of .
Take the Skolem hull of the generators, including the diagram constants when present. The witness functions show directly that the hull is elementary: whenever an existential first-order formula with hull parameters is true in the ambient first-order model, its Skolem witness belongs to the hull. Induction on first-order formulas, or the Tarski-Vaught test, gives elementarity. Its reduct is therefore a first-order model of . In the version without diagram constants its cardinality is at most .
For an order automorphism , defineThis is well defined. If two terms represent the same element, express their equality as a first-order formula on the increasing union of their generator indices. Indiscernibility and preservation of the index order carry that equality to the transported terms. The same argument for every relation shows preservation of the expanded structure; applying it to supplies the inverse. Every element is a term in the generators, so no other structure automorphism of the specified expansion can have the same action on them. HenceFor an application requiring the generators to lie in a definable infinite ordered class, impose that class predicate and its increasing-order first-order formulas too. The finite-fragment proof uses an increasing sequence in that class, so all these additional conditions are preserved. In particular the integer index order and its shift give the structure automorphism used in the NFU construction. The constants are order indiscernibles, not necessarily indiscernibles under arbitrary permutations of the index set.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 19 1 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
The PDF's displayed inequality uses the relation it purports to define and therefore is not itself a complete definition. The absorption order consistent with that inequality and with the requested result isThis is the reverse of the usual natural order of an incline. We specify it explicitly: using instead would make the finite-generation conclusion false in general.
Idempotence gives , proving reflexivity. If and , then associativity givesso the relation is transitive. If also , commutativity forces . Thus it is even a partial order. In this order follows because . Absorption says that multiplying a monomial by any additional factors moves it upward in .
Let generate the incline. Distributivity, commutativity and idempotence expand every element into a finite nonempty sum of monomials with . A zero exponent means that factor is omitted; no multiplicative identity is assumed. If componentwise, then by absorption, or by idempotence when .
We prove the needed reverse-inclusion well-quasi-ordering of monomial ideals directly. Upward-closed subsets of form a well-quasi-ordering under reverse inclusion. For these are the tails, plus the empty set, ordered like . For the induction, write an upset as increasing slices in . Their union is an upset with a finite minimal basis by Dickson lemma. To see that finite-basis fact here, is a well-quasi-ordering by the finite product argument above, so its minimal elements cannot form an infinite antichain; every element lies above a minimal one because its lower coordinate box is finite. All basis elements of the union appear by some finite slice, so the slices eventually stabilize.
Encode by the finite word of slices before stabilization and its final slice. By the finite-word theorem proved in the other alternative, and finite product closure, these encodings are a well-quasi-ordering with slice comparisons given by reverse inclusion. For two comparable encodings, let the earlier pre-stabilization slice match the later slice , where . ThenBeyond the earlier stabilization index, its final slice contains the later final slice and hence every later slice. Therefore . This proves the induction, including empty slices and the empty upset.
For an incline element , choose a finite exponent support of a sum representing it and put . Given an infinite sequence of elements, the just-proved result supplies with . Every monomial in the chosen sum for is therefore absorbed by a monomial in the sum for . Adding these absorptions gives , even if the incline has further identities between terms. HenceThe order direction matters. On the positive integers take and multiplication to be ordinary addition of integers. This is an incline generated by . Its usual natural order is the reverse of the ordinary numerical order, and the sequence is bad in that order. Its reverse absorption order is the ordinary numerical order, consistent with the theorem above.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 19 1 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For finite rooted trees, use rooted-tree homeomorphic embedding: an injective vertex map preserves ancestors and lowest common ancestors, so edges may become paths and distinct branches remain distinct. The root can map to a vertex below the host root. More generally label vertices in a well-quasi-ordering and require each source label to precede its image label. We prove this stronger labelled version of Kruskal's tree theorem, from which the unlabelled result follows by taking one label.
We first need the finite-word closure, and prove it rather than merely invoking Higman lemma. If finite words over were not a well-quasi-ordering under order-preserving subsequence embedding with increased labels, choose a minimal bad sequence , minimizing the length of among words admitting a bad continuation of the already chosen prefix. No is empty. Write by removing its last letter. The perfect subsequence lemma gives with for .
The sequence is still bad. An earlier embedding into a later would embed into , contradicting the original sequence. An embedding of into extends by the last-letter comparison to an embedding of into . Both possibilities are excluded. This contradicts minimality at position , since is shorter. Thus the finite-word closure holds. The perfect subsequence lemma also proves finite product closure: first pass to a nondecreasing subsequence in one coordinate, then in the next, preserving all previous comparisons.
Suppose now that the labelled trees admit a bad sequence . Choose a minimal bad sequence by vertex number. Let be all the proper descendant-rooted subtrees of these trees. We claim that is a well-quasi-ordering. If it had a bad sequence of subtrees , its parent indices can be made strictly increasing, say comes from . Indeed each finite initial collection of parent trees has only finitely many subtrees, and a bad sequence cannot contain infinitely many terms from a finite collection. Passing to a subsequence therefore makes .
Then is bad. A prefix tree embedding into would embed into its parent , contrary to the original badness, and the tail is bad by construction. But has fewer vertices than , contradicting minimality. This proves the claim.
Give the children of each root any fixed order. Its forest of child subtrees is a finite word in . The word theorem and finite product closure show that the pairs consisting of the root label and the child-subtree word are a well-quasi-ordering. Thus some have comparable root labels and an embedding of the child word of into that of . Map the source root to the target root and use the obtained embeddings inside distinct target child subtrees. The paths from the target root into those distinct branches are disjoint except at the root, so this is a label-monotone tree embedding. It contradicts badness. Hence
For Friedman's finite form of Kruskal's theorem, fix . There is such that any trees with contain with . Use indices starting at zero; shifting them only changes . To prove this uniform finite bound, form the finite bad-sequence tree of finite bad prefixes obeying the size bounds. At position there are only finitely many rooted-tree isomorphism types with at most vertices, so every node has finitely many successors.
If no bound existed, this tree would have nodes of arbitrarily large depth. A node with arbitrarily long extensions has a child with arbitrarily long extensions, since it has only finitely many children. Choosing such a child repeatedly produces an infinite branch, as in the König infinity lemma. The branch is an infinite bad tree sequence, contradicting the theorem just proved. Therefore the required exists. The same proof works with any fixed finite label alphabet and any specified size bound finite at each position.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 9 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For , define the Eilenberg-Moore comparison functorThe algebra unit law is a triangle identity. Naturality of the counit at gives its algebra associativity law; naturality at gives , making an algebra morphism.
Suppose first that reflects G-split coequalizers. For every , consider the counit presentationIt equalizes the pair by counit naturality. After applying it becomes , with parallel maps . This is split: take and . The identities , and follow from the algebra law, a monad unit law, and naturality of . Reflection therefore makes a coequalizer in .
For fullness, let be an algebra morphism, so . Put . Its two composites with the counit-presentation pair are equal: by counit naturality they are and . Hence there is a unique with . Applying gives . Since is split epic, . This proves full faithfulness directly by descent.
Conversely suppose is full and faithful. We need the following explicit algebra lifting fact. For algebra morphisms with a split underlying coequalizer , the arrow equalizes . The split diagram is preserved by , so is their coequalizer and there is a unique with . Precomposing the unit equation with the epimorphism gives ; precomposing the associativity equation with the epimorphism gives equality by . Thus is an algebra action. If an algebra map equalizes , its unique underlying factor satisfies . Cancelling shows . This proves monad algebra forgetful functor creates split coequalizers.
Now take any existing equalizing arrow in whose image is such a coequalizer. The lifting fact makes the unique compatible action on its already given action , since preserves that action. Hence is a coequalizer of in the algebra category. For any arrow equalizing the pair, its unique algebra factor lifts to an arrow by fullness of ; faithfulness gives its factorization equation and uniqueness. Therefore is a coequalizer in . We have proved the full comparison and reflection of split coequalizers equivalence
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 9 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A functor-split coequalizer pair for is a parallel pair in whose image has a split coequalizer in . Explicitly there are , , withThese equations give the coequalizer property: if , then , and is split epic so the factor through it is unique. Every functor preserves such a split diagram, since it preserves these equations.
Reflection means that, for such a pair, any existing arrow whose image is a coequalizer is itself a coequalizer in . A coequalizer of the image pair is isomorphic to the specified split one and inherits its splitting. This is reflection of an existing quotient, not an assertion that every base quotient has a lift.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 8 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
First prove strict creation for the canonical forgetful functor . Let a diagram of algebras have a chosen underlying limit cone . The maps form a cone: if is a diagram arrow, then and . Thus the limit property gives a unique action withThe projections are jointly monic. By naturality of and the algebra unit laws, , hence . Likewiseso . Therefore is an algebra and all are algebra morphisms.
For any algebra cone , let be its unique underlying factor. Then , so joint monicity gives . Thus the factor is an algebra morphism, unique as such. The action on the prescribed was itself forced by the cone equations. This proves monad algebra forgetful functor creates limits, without assuming preserves them.
For a monadic with comparison an equivalence, transport and its cone across that equivalence. This yields a limiting cone in whose image is identified with the prescribed base cone by an isomorphism, uniquely up to the corresponding cone-compatible isomorphism. Thus a monadic functor creates limits in the equivalence-invariant sense. If monadicity uses a comparison isomorphism over the base, the lift is literally on the prescribed underlying cone, proving strict creation as well.
A qualification is necessary if equivalence is used to define monadicity but literal unique lifting is demanded. Let be the indiscrete category on two objects , let be the terminal category, and let select . The unique is left adjoint to , and the comparison to the induced algebra category is an equivalence: the two algebra objects have exactly one map between each pair. Yet the chosen terminal cone with vertex in has no literal lift, since the only object in the image of is . The creation of limits up to isomorphism conclusion holds, because and are uniquely isomorphic. This distinguishes the two conventions rather than claiming an invalid strict conclusion from equivalence alone.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 8 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For with unit and counit , setNaturality of the unit and counit makes these natural transformations. The two triangle identities give and . Naturality of at gives . Applying proves . Thus this is the monad induced by an adjunction.
Conversely, for any monad take the free-algebra functor and the forgetful functor . For an algebra , the assignments and give inverse bijections between algebra maps and arrows . For the inverse identities, , while . The algebra and monad laws also make an algebra morphism, since . These bijections are natural, giving the free-forgetful Eilenberg-Moore adjunction. Its unit is , its counit at is , and its induced multiplication is exactly . Thus every monad arises from an adjunction.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 8 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A monad on consists of an endofunctor and natural transformations , , satisfyingAn algebra for a monad is with , and . A morphism is an arrow with . These form the Eilenberg-Moore category .
A functor is monadic when it has a left adjoint and its comparison is an equivalence; this is the monadic adjunction convention. Some strict formulations require to be an isomorphism over the base. The distinction affects the meaning of literal limit creation, discussed in part (iii), but not the algebra construction.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 6 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let be the discrete category on , and the indiscrete category, with exactly one morphism between each ordered pair of objects. A functor is precisely a map ; a functor is precisely a map . Thus .
Let be the set of connected components, where objects are related by finite zigzags of morphisms in either direction. A functor must take the endpoints of every morphism to the same point, so it is exactly a map . This gives the adjoint chain for the objects of a categoryIt cannot extend to the left. The two functors from the terminal category to selecting distinct objects have empty equalizer in . Applying gives two identical maps between singleton sets, whose equalizer is a singleton. Thus does not preserve equalizers and cannot be a right adjoint.
It cannot extend to the right either. The coproduct of two copies of in is the discrete two-object category. But is the indiscrete two-object category, with morphisms between its distinct objects. They are not isomorphic, or even equivalent. Hence does not preserve binary coproducts and cannot be a left adjoint. Neither end of this chain has a further adjoint.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 6 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A presheaf on is an arrow in sets. A morphism of presheaves is a commuting square. DefineA commuting square from to is determined by its map , while a square from to is determined by its map . A square from to is also determined by its map , because the other component is the unique map . Therefore these Hom-set bijections establish the adjoint chain for evaluation in an arrow category:There is a further left adjoint to : . A square is exactly a map , proving .
There is no right adjoint to . If there were, would be a left adjoint and preserve the initial object. But it sends the empty set to , whereas the initial object of this arrow category is . They are not isomorphic. Hence does have a left adjoint, while has no right adjoint.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 5 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Given the natural transformations and triangle identities, define and . Both assignments are natural because are natural. Naturality of the counit at givesNaturality of the unit at similarly givesThus these are inverse natural Hom-set bijections, defining an adjunction . Their identity values are the prescribed unit and counit, by their definitions. Finally every adjunction with this unit must satisfy the first transpose formula, and every one with this counit the second, so the bijections are forced. There is exactly one adjunction structure with these specified unit and counit.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 5 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Apply the inverse transpose formula to , which by definition is the transpose of . This gives . Likewise transposes to , so . Hence the triangle identities for an adjunction areThese are equalities of natural transformations; their components are exactly the two identities just proved.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 5 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Write the adjunction bijections as , natural in . The adjunction unit and adjunction counit areThus and are natural transformations, by naturality of the bijections. For any and , their transposes satisfyThe first follows by naturality in the target applied to ; the second follows by naturality in the source applied to . These formulas make the definitions operational for every arrow.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 4 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
The category of elements of has objects with and morphisms satisfying . Send to the representable presheaf and a morphism to . The Yoneda lemma gives a canonical cocone to , whose leg at corresponds to .
For any target presheaf , a cocone from this diagram to is a family of maps , or equivalently elements , with whenever . Such a family is exactly a natural transformation , via . This bijection respects the canonical cocone, so it proves its colimit universal property. Consequently the canonical colimit presentation of a presheaf isEquivalently, the density coend identifies the disjoint copies of the representables by exactly these element-category arrows. Smallness of and the set-valued fibers make the indexing category small.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 4 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For fixed , the categorical coend on the right is the quotient of by the identificationsDefine . This is well defined because the contravariant functor law gives . Its proposed inverse sends to . The composite to is the identity. In the other direction the coend relation, applied with and initial map , gives . Thus the inverse is genuine andFor , the coend map replaces by ; its image is , proving naturality in . A morphism of presheaves acts on and commutes with every by naturality, proving naturality in . This is the density formula for presheaves.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 4 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let . An end of a functor is an object with maps satisfying for every , universal among all such families. Thus every compatible family with vertex factors uniquely through . Write it as . These are the wedge equations for a dinatural transformation from a constant functor to .
Dually, a coend of a functor is an object with maps satisfying as maps from , universal among compatible families with a common target. Write it as . These are cowedge equations, and every cowedge to factors uniquely through .
For small , if the needed products and equalizers exist, the end is the equalizer of . If the needed coproducts and coequalizers exist, the coend is the coequalizer of . The two arrows in each construction are precisely the two sides of the compatibility equation. This explains both the mixed variance and the universal property, rather than treating the integral notation as an ordinary numerical integral.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 3 iv Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
The categorical commutation of iterated categorical limits theorem is the following. For small categories and a two-variable functor , if the two collections of inner limits and their outer limits exist, then there are canonical isomorphismsIn particular all these limits exist if has all -shaped and all -shaped limits. The isomorphisms are natural in and uniquely characterized by preserving every projection to .
Part (iii) proves that each iterated limit represents the functor of cones on the product diagram, with the same flattened projections. Two such representations have unique inverse cone-compatible arrows, proving the isomorphisms. For a natural transformation , the two composites in any naturality square have the same product-diagram projections, hence agree by limit uniqueness. This proves naturality as well. Completeness of is a convenient sufficient hypothesis, rather than a necessary one for this individual diagram.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 3 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let with projections . The composites form a cone over : the equations hold in each inner limit, and the equations follow from the naturality of and the outer cone.
Given any cone , the inner limit property gives unique with . The cone equations for force by uniqueness of inner mediating arrows. Thus the form a cone to , and there is a unique with . This factors all , and the two stages of uniqueness prove uniqueness for the whole product diagram. Consequently
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 3 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Choose a limit for each diagram , with legs . For an arrow , the maps form a cone over , since the two-variable functor respects the commuting arrows in . The limit property therefore gives a unique arrow satisfyingThe arrows and have identical composites with all projections, so they are equal. The same uniqueness shows . Hence the assignment extends to a functor .
For the chosen limit objects and cones it is uniquely determined, literally, by these equations. Changing the choices gives a unique family of isomorphisms between the limits compatible with their projections; the equations above show that this family is a natural isomorphism of the resulting functors. Thus it is unique up to a unique cone-compatible natural isomorphism, not independent of choices as an equality of objects.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 18 3 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
For a small diagram in a locally small category, define its cone functor on bywhere is the constant diagram. Precomposition acts on cone vertices. A categorical limit is a representation of this functor: an object with natural bijections . The image of is the universal cone, and the inverse bijection supplies the unique mediating arrow for every cone. Thus the representable functor formulation and the usual terminal-cone universal property coincide.
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





