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 2017 iii Paper 135 6 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Use untyped lambda calculus and normal-order beta reduction. Write for the Church numeral of . We will construct a closed term such thatwhen is defined, and with no head normal form otherwise. The latter condition implies that the result is not in beta equivalence with any Church numeral, so both definedness and the output are represented.
First represent all total primitive recursive functions. The zero function is , the successor function isand the th projection function is . Function composition in recursion theory is represented by . This composition claim is used here for total functions, whose inner terms all reduce to numerals.
For primitive recursion use Church pairs and iteration. PutSuppose represent the total constituents of and . DefineAfter iterations the pair reduces to , by mathematical induction on . Its second projection is the required result. This lambda definition of primitive recursion by pair iteration and structural induction on the primitive recursive construction give terms for all primitive recursive functions.
For an arbitrary partial computable function use the Kleene normal form theorem with its program index fixed. There are total primitive recursive functions and such that is zero exactly when codes a valid halting computation history on , and extracts that history's output. Checking finite coded configurations and each transition is primitive recursive. Determinism ensures that every accepted history on an input has the same output. HenceIf the input computation never halts, no history is accepted. Let be the total numeral-representing terms already obtained. The Church numeral zero test is , returning exactly on zero. A Church Boolean applied to two arguments selects the appropriate branch without evaluating the other.
Take the fixed-point combinator . For the input tuple defineExpanding the displayed abbreviations gives a genuine finite combinator. At a numeral code , the total predicate computation terminates. If it returns a positive numeral, the false Church Boolean selects the next search code. If it returns zero, the true Church Boolean selects , which reduces to the output numeral. If the least accepted code is , a finite sequence of these tests reaches it and then produces .
If there is no accepted code, every test is false and head reduction moves through codes forever. At no finite point can a head variable or an outer numeral abstraction be produced: the applied search term must first unfold the fixed point and evaluate the next total test, and the decoder branch is always discarded. Thus it has no head normal form. The standard head-normalization property, or the Church-Rosser theorem together with normalization of normal-order reduction, rules out beta equivalence to a numeral. In particular, we have avoided a lazy-composition pitfall: an outer function that discards an argument need not force a divergent inner computation. The decoder is reached only after the guarded search succeeds. This proves lambda representation of partial computable functions:
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 135 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Use the Gödel-Gentzen negative translation, writing for the translated first-order formula. On atomic formulas , including logical equality, put , and put . Extend recursively byLogical negation abbreviates logical implication to logical falsity, so . The displayed logical disjunction and existential clauses are intuitionistically equivalent to the usual negative clauses and , respectively. Thus these clauses specify the same negative interpretation. Translation commutes with capture-avoiding substitution of terms for free variables.
First prove by structural induction the stability of a formula under double negation:Every double logical negation is stable, since intuitionistic first-order logic proves ; logical falsity is stable as well. Stability passes to logical conjunction by obtaining double logical negation of each component. For a logical implication with stable , assume and . An assumption would give , a contradiction, so and then . For a universal first-order formula, implies for arbitrary fresh ; use stability pointwise and generalize. Logical disjunction and existential translations are already double negations. This proves all cases.
Now regard classical first-order natural deduction as intuitionistic natural deduction plus unrestricted double-negation elimination, and induct on a classical derivation. The rules for logical conjunction, logical implication, universal quantification and logical falsity translate directly. Logical disjunction introduction gives and then its double logical negation. For logical disjunction elimination, the translated premise is and the two translated branches yield the stable conclusion . Assuming makes each branch contradictory, giving and , hence , which contradicts the premise. We have and remove it by stability.
Existential introduction likewise adds a double logical negation to the ordinary witness introduction. In existential elimination, the witness branch has the original fresh-variable condition. Assuming makes that branch give ; generalization gives and therefore , contradicting the translated premise. Again stability supplies . The universal-rule side conditions are preserved because the translation introduces no new free variables.
For logical equality, reflexivity gives and then its double logical negation. For substitution, from and , temporarily assume . An assumption would transport to by intuitionistic logical equality substitution, so it gives a contradiction and hence . The first premise contradicts this. Thus holds and stability gives . Finally a classical double-negation elimination step translates precisely to , already proved. Every rule is therefore covered, giving negative translation of a classical proof:In particular a classical thesis has an intuitionistic, constructive translated proof. If nonlogical assumptions are present, they must be translated too.
In classical logic, double-negation elimination gives on atoms. Structural induction propagates equivalence through logical conjunction, logical implication and both quantifiers, and removes the added double negations on logical disjunction and existence. Therefore
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 135 4 Solution by
Codex 0 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 2017 iii Paper 135 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
The countable form of the omitting types theorem is as follows. Let be a countable first-order language and a consistent first-order theory in . For any countable family of nonprincipal partial types in finite tuples of variables, there is an at most countable first-order model of omitting all of them. Nonprincipality means that no -consistent first-order formula entails every member of the type modulo . A complete first-order theory with nonisolated complete types is the usual special case; neither an uncountable language nor an arbitrary uncountable family is covered by this statement.
Use the Godel completeness theorem to pass between consistency and the existence of a first-order model. Adjoin a countable stock of new constants. Construct finite conditions with consistent, interleaving three countable lists of requirements: decide each -sentence; provide a fresh constant witness for each existential sentence; and, for each and each tuple of closed terms of its arity, add for some . Sentence decisions preserve consistency by choosing a consistent sign. For an existential sentence , add with fresh for that condition and first-order formula. This is consistent: any first-order model of the old condition can interpret as a witness if one exists, and otherwise arbitrarily in the nonempty domain.
The omission step is the key Henkin omission extension lemma. Let be the logical conjunction of the current finite condition, listing every new constant occurring either there or in . If adding were inconsistent for every , then would entail for each such . Replace the new constants by fresh variables and formIt is consistent with and entails every , contradicting nonprincipality. Hence some omission extension is consistent. The construction need not be computable; countability merely permits all these requirements to be scheduled.
Let be the deductive closure of . It is consistent by the finite character of formal proofs, complete by sentence decisions, and has the Henkin witness property. Its term model consists of closed terms modulo provable logical equality and has at most countably many elements. The truth lemma for a Henkin term model proves that it is a first-order model of . Every tuple in it is represented by closed terms, whose scheduled omission requirement supplies a negated member of each corresponding type. Thus
A universal sentence has the form with quantifier-free , including an empty quantifier block. Embeddings preserve and reflect quantifier-free truth, so universal sentences pass to substructures of a first-order structure. For the converse Łoś-Tarski preservation theorem, let be all universal consequences of an arbitrary first-order theory , and take . We claim is consistent, where the diagram of a structure contains both atomic and negated atomic sentences in constants naming the elements of .
If inconsistent, the compactness theorem gives a finite logical conjunction of diagram sentences for which . The added constants do not occur in , soThis universal sentence belongs to but is false in at the named tuple, a contradiction. The compactness theorem therefore produces containing an isomorphic embedded copy of . The signed diagram ensures a genuine substructure of a first-order structure: functions are preserved, constants are included and relations are preserved and reflected. If the first-order model class of is closed under substructures of a first-order structure, this copy, and hence , is a first-order model of . We have provedNo countability assumption is needed for this second argument. An inconsistent first-order theory is covered as well, with a universally false axiom and an empty first-order model class.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 135 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
For subsets , a many-one reduction is a total computable function with . A Turing reduction is an oracle machine with oracle computing the total indicator function . It may make several adaptive oracle queries. A many-one reduction gives a Turing reduction using one query; the definitions impose no enumerability assumption on .
The Friedberg–Muchnik theorem asserts that there exist computably enumerable sets withWe give the finite-injury priority construction. Fix an effective list of Turing functionals and imposein priority order . Each strategy has an unassigned, waiting or protected state; a private witness when assigned; and a restraint on the oracle set when protected. All witnesses, even abandoned ones, are permanently recorded and never reused. A strategy for is the only strategy ever allowed to enumerate its witness into ; the analogous statement holds for and .
Start with finite sets . At stage , inspect the first strategies. An unassigned strategy needs attention. A waiting strategy needs attention if the computation converges within steps; waiting is symmetric. Act on the highest-priority strategy needing attention, if any. On assignment choose a fresh witness greater than , every earlier witness and every higher-priority restraint, and enter the waiting state. On a convergence with output and oracle use , act as follows: if , enumerate the witness into its own target set; if , leave the witness out. Enter the protected state and restrain the oracle below . The current characteristic value at the witness is now different from , including outputs other than zero or one. Whenever a strategy acts, initialize every lower-priority strategy, discarding its current witness and restraint but retaining the permanent record of used witnesses. If none needs attention, change nothing.
Every enumeration respects higher-priority restraints: its witness was chosen beyond them after its last initialization, and a later higher-priority action would have initialized it. Each stage is effective, finite and monotone in , so and are computably enumerable. Lower-priority restraints may be violated by a higher-priority action, exactly the allowed injuries.
Induct on priority to verify finite injury and satisfaction. Once all higher-priority strategies have made their last actions, the current strategy receives its final assignment and can act at most once more, on a convergence. If convergence is observed it is then protected permanently; otherwise it waits without further action. In either case every strategy acts only finitely often. After the final initialization of , if it acts on a convergence, no higher strategy subsequently changes its assumptions and every lower strategy respects its restraint. The observed oracle computation therefore remains valid for the final , while the permanently private witness retains the opposite characteristic value in .
If it waits forever, then cannot converge. A convergent final computation uses only finitely many oracle bits; those bits in the increasing enumeration eventually equal their final values. For a sufficiently large stage the same finite computation would have been observed, and after the higher strategies have stopped it would receive attention, contradicting perpetual waiting. Thus is satisfied either by disagreement or by divergence. The same proof satisfies every . This is private-witness diagonalization for incomparable enumerable sets, with the finite-injury verification supplying the required permanent disagreements.
A computable set reduces to every oracle, so incomparability makes both sets noncomputable. Every computably enumerable set reduces to the halting problem; if either of these sets had the halting degree, the other would reduce to it. Thus their c.e. degrees are also incomplete, giving the intermediate degrees sought by the Post problem.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 135 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Work in ZF with the law of excluded middle, without the axiom of choice. The paper's terminology is an infinite Dedekind-finite set. The useful common principle is countable union of explicitly ordered finite lists without choice: given an actual sequence of finite lists, enumerate their entries by list number and position using a Cantor pairing function. If the union of entries is infinite, repeatedly take the entry with the least code not already selected. This produces an injection from without choosing any enumerations of unordered sets.
Consequently, if a family of objects has an explicitly ordered finite list of labels for each object, and only finitely many objects can be made from any given finite pool of labels, then a countably infinite list of distinct objects forces a countably infinite subset of the label set. For a Dedekind-finite label set this is impossible. If the label set embeds into the object family as well, infinitude is preserved. ThusThe distinction between ordered lists supplied by the data and arbitrary finite subsets is essential: a blanket countable-union theorem for unordered finite sets would introduce a choice principle.
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





