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 2015 iii Paper 25 6 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
A theory is recursively axiomatizable when it has an effective enumeration of axioms, equivalently when its deductive closure is computably enumerable. If the definition requires a decidable axiom set, the equivalent formulation is obtained by replacing an axiom enumerated at stage by a fixed left-associated logical conjunction of copies of it. To recognize a proposed padded axiom, inspect its finitely many possible decompositions into repeated conjuncts and check the corresponding finite enumeration stages. The padding preserves logical equivalence, so the resulting decidable axiom set generates the same theory. In either convention, enumerate formal proofs using the finite sets of axioms seen so far. This effectively enumerates every theorem.
Let be a sound arithmetic theory of the standard natural numbers, sufficiently strong to encode finite computations, proofs and substitution and to establish the diagonal lemma; an extension of Robinson arithmetic suffices. With a semidecidable axiomatization, the arithmetical provability predicate expresses that a proof of the sentence with code exists. A proof certificate can include enumeration stages for its axioms, so this predicate is arithmetically expressible even when the given axiom set is only computably enumerable.
The diagonal lemma produces a sentence such thatHere is the mechanism, including its effectiveness. For the computable substitution function taking a one-variable formula code to the code of that formula with the numeral substituted, let represent its graph. Given , form and let be the code of . The sentence has code . Numeralwise correctness and uniqueness of the represented substitution computation prove . This constructs a fixed point effectively from the code of . Applying it to gives .
If proved , arithmetic soundness would make true, while the existence of that proof would make true. The displayed equivalence would then make false, a contradiction. Thus does not prove . In the standard natural numbers its arithmetical provability predicate is therefore false at this code, so is true. Arithmetic soundness now rules out a proof of as well. Hence is incomplete: neither nor is a theorem, and is true.
For a fixed effective enumeration of computably enumerable sets, a productive set has a partial computable function such thatThe condition applies to every computably enumerable subset, including finite subsets. No condition is imposed on when the inclusion fails.
Let be the set of codes of true arithmetic sentences; numbers which are not sentence codes are excluded. Uniformly in , there is an arithmetic formula expressing : it says that a finite enumeration computation outputs . Apply the effective diagonal lemma to obtain withThe operation producing this sentence code is total computable. Suppose . If , the subset assumption says that is true, while its fixed-point equivalence says it is false, a contradiction. Thus . The same equivalence now says is true, so . We have provedTherefore arithmetic truth is a productive set. This proves productivity of arithmetic truth. It cannot itself be computably enumerable, since taking would contradict the defining property. Applying the productive procedure to the enumerable theorem set of a sound arithmetic theory also gives a true sentence outside that theory. The productive construction does not require the enumerable subset of truths to be a theory or to be deductively closed.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 25 5 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For , write a number in hereditary base : express its base- expansion as , with , and recursively expand every exponent in the same base. Let , for , be the number obtained by replacing every occurrence of the base in this hereditary expression by . Coefficients and the symbols for addition and exponentiation are retained.
For a starting number , define its Goodstein sequence by andThe Goodstein function is the termination-time functionThis choice counts transitions from the initial term; a convention counting the initial term as well shifts the answer by one. For example the sequence starting at is , so . Starting at gives , illustrating why descent of the numerical terms is not the termination argument.
Define the ordinal rank of a Goodstein term by replacing the base in the hereditary expansion by , at every exponent depth. The result is in Cantor normal form and lies below , called epsilon zero, the least nonzero solution of . Finite hereditary expressions have finite nesting depth, so their ranks are bounded by a sufficiently high finite tower of powers of .
For a fixed base, is strictly increasing. To see this, compare two ordinary base- expansions at their largest differing exponent. By induction through the hereditary exponent expressions, their exponents have the same ordering after replacing by ; computable Cantor normal form notation then uses the same first differing exponent or coefficient. AlsoIndeed after the base change all coefficients remain below , the recursively changed exponents remain correctly ordered, and replacing the new base by gives exactly the original ordinal expression. These facts can be proved together by structural induction for primitive recursive functions on the hereditary expression.
Consequently, whenever ,An infinite nonzero Goodstein sequence would give an infinite descending sequence of ordinals below , impossible because ordinals are well-ordered. Thus the Goodstein function is total. Its steps are effective finite operations, so simulating the sequence until zero also proves that it is a total computable function.
The same ordinal notation system gives the requested decidable well-order. Let consist of canonical finite terms for zero and for expressionswhere the exponents are themselves canonical terms. Membership in is decidable by recursively checking the syntax, positive coefficients and decreasing exponents. Comparison is decidable by recursive computable Cantor normal form notation, first of exponents, then coefficients, and then the remaining summands. All recursive calls inspect proper subterms, so the algorithm terminates.
Interpreting these terms as ordinals gives every ordinal below , uniquely. One way to connect this directly to hereditary base representations is to choose, for a given finite ordinal term, a base larger than every coefficient anywhere in that term. Replacing by that base evaluates it to a natural number whose hereditary representation recovers the ordinal term. Thus all bases together supply the complete notation system; a single fixed base is not enough.
Choose an effective injective coding of finite terms by natural numbers, and enumerate the valid codes in increasing numerical order. The resulting bijection is computable: validity is decidable and there are infinitely many finite-ordinal terms. Its inverse is computable by counting valid codes below a given code. DefineThis is a decidable relation on all of . The interpretation into ordinals is an order isomorphism onto , provingDecidability here concerns comparing two notations. Well-foundedness is supplied by their ordinal interpretation, the same mathematical descent principle used to prove Goodstein's theorem.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 25 4 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
We use untyped lambda calculus and normal-order beta reduction. The Church numeral for is . A lambda term represents a partial function if on numeral inputs it has the correct numeral normal form exactly when the function is defined. We use a lambda simulation of a Turing machine; this also ensures that undefined computations do not accidentally produce an output through an ignored argument.
First all total primitive recursive functions are lambda-definable. The initial functions of recursion theory are represented byComposition is obtained by substitution of representing terms. For primitive recursion use Church pairs:If represent the total functions in and , defineAfter iterations the pair has components . Thus the Church numeral executes exactly the required recursion steps. Since these functions are total on numeral inputs, substitution for composition causes no undefined-argument issue.
Now fix a deterministic Turing machine computing the given partial computable function. Encode a configuration by its finite control state and two natural numbers for the tape portions on the two sides of the head, allowing blank bits beyond the finite nonblank tape. For the two-stack encoding of a Turing tape with a binary alphabet, let have the immediately-left cell as its low bit and have the current cell as its low bit. Reading and removing a bit use remainder and quotient by two. If the machine writes , the updates areThe new state is obtained from a finite transition table. These operations, the initial configuration, the halting test, and output decoding are total primitive recursive functions on configuration codes. For instance parity alternates by primitive recursion, and the quotient by two satisfies , . A fixed finite alphabet can be handled by the same stack construction in a larger base. Choose a standard delimited input and output convention, for example unary words in a finite tape alphabet with a distinct blank symbol. Initialization is primitive recursive. On a halting configuration the output is a finite word; decoding can be implemented by a bounded scan of the encoded tape, with a default output for malformed words. This is total primitive recursive and introduces no additional unbounded search. Use nested Church pairs to carry the three fields, and the preceding primitive recursive representations to obtain lambda terms .
Represent Church Booleans by and . A Church numeral zero test is . Use a numerical test equal to zero on halting configurations and one otherwise; applying this zero test gives the required Boolean halting test. With the fixed-point combinatorputNormal-order reduction evaluates the halting test on the current configuration. If it is true, it selects the output branch without evaluating the recursive branch. Otherwise it advances the configuration and repeats. Induction on the number of machine steps shows that a computation halting with output makes reduce to .
If the machine never halts, the normal-order beta reduction repeatedly takes the recursive branch. Each individual configuration transition and test terminates, but there is always another required transition; hence the reduction never reaches a normal form. The normal-order normalization theorem says that a lambda term with a beta-normal form is normalized by normal-order beta reduction. Therefore in the nonhalting case there is no numeral normal form at all. We have provedConfluence of beta reduction ensures uniqueness of the resulting numeral. This handles genuinely partial computations. Simply composing terms for partial subcomputations would need extra care, because lambda reduction can discard an unevaluated argument.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 25 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
We prove closure under the defining schemes for primitive recursive functions, keeping all unbounded existential variables outside a bounded arithmetic formula. A bounded quantifier means or , where does not contain . All formulas are interpreted in the standard natural numbers.
First we need a finite sequence code using only the permitted language of ordered rings. Define the bounded arithmetic formulaFor given , it specifies the unique remainder of modulo . In particular the quotient and remainder variables are bounded by arithmetic terms; division is not a new language symbol.
Every finite list can be coded by some pair . Choose larger than every list entry and divisible by every integer from to . The moduli are pairwise coprime. Indeed a prime dividing both cannot divide , but then divides ; since and is divisible by that integer, this is impossible. The Chinese remainder theorem gives with for every . Since , each holds. This is Gödel beta-function sequence coding. The external choice of a divisible proves that codes exist; factorial and exponentiation do not occur in the existential bounded representation of a primitive recursive function.
For the zero function, successor function and projections use , and . These formulas need no auxiliary variables. For function composition in recursion theory, suppose have representations with bounded arithmetic formulas . A bounded arithmetic formula for isTreat every as an auxiliary variable in the outer existential block. The logical conjunction is true for some such variables exactly when is the desired output.
Now supposeBy structural induction for primitive recursive functions, assume and are bounded arithmetic formulas representing . We code the values with . For finite witness array coding, give each component of the step witness another code pair , so that the witness at step is the remainder specified by .
With these code pairs and as free auxiliary variables, take the following bounded arithmetic formula:The displayed line breaks are only for readability: the bounded quantifiers on the last three lines bind the entire bracket. If , their empty block and logical conjunction are omitted. Expanding every occurrence of leaves only bounded quantifiers, logical conjunctions, the bounded arithmetic formulas already obtained, and the symbols .
If , take the actual finite computation values and select witnesses for the finitely many true instances of , together with witnesses for . The Gödel beta-function sequence coding provides and the finitely many . These make true. Conversely, suppose some code pairs and initial witnesses make true. The unique remainders of give values . The initial clause makes . Every step clause makes , since its coded witnesses satisfy the representing matrix for . Induction on gives , and the final remainder clause gives . This argument includes , when the step condition is empty.
Closure under the initial functions of recursion theory, composition and primitive recursion provesCoding the step witnesses is essential: leaving an unrestricted existential witness block inside would not give the required syntactic form.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 25 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For sets , many-one reducibility means there is a total computable function such thatTuring reducibility means that a Turing machine with oracle computes the indicator function , halting on every input. A many-one reduction supplies a Turing reduction by computing and making one membership query, so implies .
The Friedberg–Muchnik theorem states that there are computably enumerable sets with and . We prove this by a finite-injury priority construction. Fix an effective enumeration of the oracle Turing functionals and arrange the requirements in the orderA requirement owns a private witness, a success flag and a priority restraint on its oracle set. All witnesses ever chosen are distinct. An witness is reserved outside , and only may enumerate that number into ; an witness is treated symmetrically. A priority restraint forbids lower-priority requirements from adding numbers less than to the specified oracle set. Initializing a requirement abandons its witness, clears its success flag and sets its priority restraint to zero; enumeration into or is never undone.
At stage consider the first requirements and serve the highest-priority one requiring attention. An unsuccessful requirement requires attention if it has no witness, or its current witness has a stage- oracle computation with output zero, found within steps. If there is no such requirement, do nothing. When a requirement with no witness is served, choose a fresh number larger than , all previously chosen witnesses and all current higher-priority priority restraints. When an with a witness and observed computation is served, enumerate into , mark it successful, and restrain below the use of that computation. The use is one more than the largest queried oracle position, or zero if there were no queries. An acts in exactly the same way with interchanged. After either kind of service, initialize every currently assigned lower-priority requirement; the remaining lower priorities are already in their initial state.
This is an effective stage construction with finite sets , and , are computably enumerable. Every enumeration respects all higher-priority priority restraints: its private witness was selected above them, and any later service to a higher-priority requirement would have initialized it before it could act. We do not need to restrain a computation whose output is nonzero; a persistent nonzero output already disagrees with an unenumerated witness.
We verify the finite injury assertion by induction along the priority order. After the last service to requirements above a fixed requirement , the requirement is never initialized again. It can be served at most twice thereafter, once to choose its final witness and once to diagonalize. Whenever it needs attention it is eventually served, since the higher-priority requirements have ceased acting and each later stage considers a longer initial segment. Thus has a final witness and makes only finitely many actions; this proves the induction and justifies the assumed last service above it.
For a final witness , if the diagonalization occurs then , while preservation of a restrained oracle computation applies: its zero computation is preserved permanently because higher priorities no longer act and lower priorities respect the priority restraint. Thus . If it never occurs, then . Were , that convergent computation would use finitely many oracle answers. Because increases to , those finitely many answers eventually stabilize, and a sufficiently late stage would discover the zero computation and cause diagonalization. This contradicts its never occurring. So in this case is undefined or nonzero and again disagrees with . The identical argument verifies every .
All the requirements hold, proving the theorem. Both sets are noncomputable: a computable set is Turing reducible to every oracle. Moreover, every computably enumerable set is Turing reducible to the diagonal halting set , and neither nor can have its Turing degree, since that would make it compute the other set. HenceThis also gives many-one incomparability and answers the existence of intermediate computably enumerable Turing degrees.
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





