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 2007 iii Paper 88 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Assume is finite and nonempty; the empty case is immediate. Here . Choose a nonempty subset minimizingTaking as a competitor gives , and every subset satisfies , including .
We first prove the Petridis minimal-growth lemma in the particular form needed: for every finite set ,List and let consist of those for which does not belong to an earlier translate , . The sets partition , so .
If , then for some earlier and . Hence every point of already belongs to . Therefore the new points contributed by are contained inTheir number is at mostSumming over proves the lemma. With , it gives
We also prove the Ruzsa triangle inequality directly. For each , choose one representation . The mapfrom into is injective: subtracting the output coordinates recovers , after which either coordinate recovers . Thus . Taking now yieldsThis proves the required growth and difference set estimates directly.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 87 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Write products of endomorphisms as composition, with the rightmost map applied first. Because is terminal, the only hom-sets that can contain multiple arrows are and . If the latter contained only the identity, any point would have , where . Then any other point would satisfy . Thus the category would be a preorder. The hypothesis therefore implies .
If the product object were , its universal property applied to arrows from would give , a singleton, which is impossible. Since there are only two objects, . Similarly, if , the exponential adjunction at would giveagain impossible. Hence as chosen objects.
Let , let be the product projections, and let be evaluation, all now endomorphisms. Pairing is , and for write for its currying. The product identities and the two inverse exponential identities giveThis is the structure of a cartesian closed monoid.
For the converse, start only from the monoid and these identities. The first three make pairing a bijection from to , inverse to . In particularas follows by applying both projections and using uniqueness. Define . The last two identities say that and are inverse bijections. These facts also derive, rather than assume, the naturality lawIndeed ; applying the inverse bijection proves the law.
Put . The law applied to gives, for every ,Taking proves . This stronger absorption identity is what makes the split object terminal.
Assume first that is nontrivial; the degenerate case is handled below. Construct the required category using the two idempotents and , as a two-object part of the Karoubi envelope. Call their objects and . A morphism from the object with idempotent to the object with idempotent is an element satisfying . Composition is monoid multiplication, and the identity on each object is its idempotent. These laws are well-defined and associative. Its hom-sets are concretelyFor example, for every , so the condition for forces . Thus is terminal, and the original monoid appears unchanged at .
Set with projections and the given pairing. The product property works for arrows from either object: for global arrows satisfying , , pairing also satisfies . The original projection identities give existence and uniqueness. Products with are the other object, with its identity and the unique terminal arrow as projections; .
For the exponential set with evaluation . For a parameter object , the given and already establish the universal property. We must additionally verify it for parameter object . An arrow is an arbitrary element of . Define its transpose byNaturality gives for every , because . In particular , so it really is an arrow .
Its uncurrying is . To see this, start from and compose with . Pairing naturality, , and the absorption property of give precisely the claimed equality. Conversely, if satisfies , then for every . ThereforeThus transpose and uncurrying are inverse for the terminal parameter object too. This verifies the full exponential property, rather than only its endomorphism instance.
The remaining exponentials are , , and , by the unit product law and terminality. Hence the constructed two-object category is cartesian closed and .
For nontrivial , the constructed is nonterminal because it has more than one endomorphism, and by the absorption identity. This is the case corresponding to the forward non-preorder hypothesis.
If has one element, all the algebraic identities still hold, but splitting alone would make the original object terminal. To satisfy the literal converse's requirement of a nonterminal object, handle this case separately: take the two-object poset category . Products are meets, , , , and , which verify the exponential adjunction on this two-element order. It is cartesian closed, is nonterminal, and its one-element endomorphism monoid is . It is a preorder, so it does not recover the forward non-preorder setting or the self-exponential equality. Thus the converse's stated endomorphism realization works also in the degenerate case, while the stronger non-preorder reconstruction uses nontrivial .
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 87 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
An embedding-projection pair consists of continuous maps , with and pointwise. Thus is an order embedding and approximates an element of the larger domain from below. Such maps are automatically strict: applying the inequality at gives , and applying then gives .
Suppose is such a pair. Composition with fixed continuous maps is continuous on the pointwise function space of complete partial orders, so both proposed lifted maps are continuous. Their composite on the smaller function space isWriting , the other composite is : for every , by monotonicity. Thus the recursion produces embedding-projection pairs at every stage.
Here is an explicit inverse-limit solution of the reflexive domain equation. Formordered coordinatewise. The bottom sequence is coherent by strictness. A directed family has coordinatewise suprema, and continuity of each preserves the coherence condition. Thus is a pointed complete partial order.
Write for the composite embeddings when , and for the corresponding composite projections, taking both as identities if . Define by , and define byThe pair identities make this sequence coherent, and its coordinates are continuous. They also give and . Put . Since and ,At coordinate , equals once , soThis exhibits the required embedding-projection pair for every finite stage.
To prove the function-space isomorphism, observe that is itself a continuous function . Coherence saysConversely such a coherent function family determines an element of , with initial coordinate . Define its action on the limit byThe maps inside this supremum increase: substituting coherence expresses the th one as with , which is below the next map. The supremum is continuous by the function-space result in Question 3.
In the other direction, for a continuous , define . These satisfy the same coherence equation. Hence define byFor a coherent family, restricting back to stage gives : every term with restricts exactly to , and the earlier terms are below it. Thus is the identity.
Conversely,For the last equality, and continuity give, at every , ; the diagonal is cofinal because the double family increases in both indices. Both and are continuous, by coordinatewise evaluation, continuous composition and directed suprema. Thereforeas complete partial orders with continuous maps, not merely as sets. This supplies the extensional reflexive object needed for a beta-eta model, together with all the stated finite-stage pairs.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 87 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A combinatory logic term over free variables is formed from variables in , the constants , and application, with no abstraction binder. We may regard as primitive, or as the abbreviation . Application associates to the left. Weak combinatory reduction contractsin any application context. Weak equivalence is the equivalence relation generated by these reductions. There is no additional rule identifying terms merely because they behave alike after application to a fresh argument.
Define bracket abstraction on combinatory terms by the following ordered clauses:They cover every term: after excluding the variable case and the case with no free , the term must be an application. Induction gives ; no other variable is introduced or removed. For every argument , the same induction gives : the three cases use respectively the , , and reductions.
The required translation isIt has exactly the same set of free variables as the original lambda term, by the bracket-abstraction identity.
To compare the two reductions, expand the constants into lambda terms:and expand variables and applications homomorphically. Every weak combinatory contraction becomes a finite sequence of beta reductions, so weakly equivalent terms have beta-equivalent lambda expansions. We also haveFor , this is the expansion of . For , the expansion of beta-reduces to , after choosing the binder fresh. For an application, expanding givesby induction and beta contraction. Thus, induction on the lambda syntax gives . Combining these facts proves
The reverse implication fails for this intensional translation. The beta-equivalent lambda terms and translate respectively toBoth are weak normal forms: has no argument, has too few arguments to contract, and the outer has only two arguments. They are syntactically distinct. By the assumed Church–Rosser property of weak combinatory reduction, two distinct weak normal forms cannot be weakly equivalent. The same argument works with , because both fully expanded terms remain distinct weak normal forms. Hence beta-equivalent lambda terms need not have weakly equivalent combinatory translations.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 87 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A lambda term is built recursively as a variable , an application , or a lambda abstraction . Application associates to the left and abstraction binds occurrences of its variable. We identify consistent renamings of bound variables by alpha equivalence. A beta reduction contracts to the capture-avoiding substitution , at any subterm. Write for finitely many such steps, including none. Beta equivalence is the reflexive, symmetric, transitive closure of reduction, so it is represented by a finite zigzag of forward and backward steps.
To prove the Church-Rosser theorem, introduce parallel beta reduction by the four rulesBy structural induction every term parallel-reduces to itself. Each ordinary step is a parallel step. Conversely, each parallel step can be performed by an ordinary finite sequence: reduce the displayed subterms recursively, and in the fourth rule contract the root last. Hence and are the same relation.
The substitution lemma isProve it by induction on the parallel-reduction derivation for . The variable case separates from other variables; application and abstraction follow from their inductive hypotheses. For abstraction, rename its binder fresh for before substituting. For a contracted redex, choose its binder distinct from and fresh for . The substitution identity follows by structural induction with fresh binders; the variable cases use , and application and abstraction preserve the identity. Apply the hypotheses to the body and argument, then the parallel contraction rule and this identity. This proves the lemma for every derivation, including simultaneous contractions inside a redex.
Define the complete development of a lambda term byOnly a root redex already present in the source application is contracted by this clause; a newly created root redex need not be contracted.
We claim that implies . Induct on the derivation. The variable and abstraction cases are immediate. In the ordinary application rule, use the inductive developments of both components. If its original function is an abstraction, also contract the resulting root redex by the parallel contraction rule; otherwise just use the application rule, even if the reduct has acquired a new root redex. In the contraction rule, the reduct has form , and the substitution lemma with , gives . This establishes the claim.
Consequently, any two parallel reducts of each parallel-reduce to . Thus parallel reduction has the one-step diamond property. Its finite transitive closure is confluent: fill a finite grid of elementary diamonds to join two finite reduction paths from the same term. Since its closure equals ordinary finite beta reduction,A finite conversion zigzag now also has a common reduct, by induction along it. If the next zigzag step points forward from a term already having a common reduct, join its two outgoing paths by confluence; if it points backward, compose the new forward path to that common reduct. The reverse implication is immediate because two paths to a common reduct form a conversion zigzag. This proves
A beta-normal form contains no beta-redex, so its only finite reduct is itself. If two normal forms are beta-equivalent, their common reduct must equal both. Hence a term has at most one beta-normal form up to alpha equivalence. The qualification about bound-variable names is essential.
For an example without normal form, take the Omega combinatorIts only redex is the root, and contracting it reproduces . Every finite reduct is therefore , which is not a beta-normal form. By the theorem it cannot even be beta-equivalent to any normal form.
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





