Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 120 (Computability and Logic)

The Knaster-Tarski theorem states that the fixed points of a monotone map $f:L\to L$ on a complete lattice form a complete lattice. LetFor every $x\in P$, monotonicity gives $f(m)\le f(x)\le x$, hence $f(m)\le m$. Applying $f$ once more gives $f(f(m))\le f(m)$, so $f(m)\in P$. The definition of $m$ then gives $m\le f(m)$, and therefore $f(m)=m$. Thusis the least fixed point. The order-dual argument shows thatis the greatest fixed point.

More generally, for a family $S$ of fixed points, let $P_S$ be the set of prefixed points $x$ satisfying $f(x)\le x$ and $s\le x$ for every $s\in S$. Its meet $m_S$ is again prefixed. Since $s=f(s)\le f(m_S)$ for every $s\in S$, the element $f(m_S)$ also lies in $P_S$, so the preceding argument gives $f(m_S)=m_S$. It is the join of $S$ within the fixed-point order. The dual construction gives the meet of $S$ within that order, proving completeness.

For the Myhill-Nerode theorem, let $A\subseteq {\Sigma }^{\ast }$ and define the Myhill-Nerode equivalenceThis is an equivalence relation and a right congruence: $u{\sim }_{A}v$ implies $ua{\sim }_{A}va$ for every letter $a$.

If a deterministic finite automaton accepts $A$, any two words reaching the same state are equivalent, because every continuation has the same subsequent run. Hence ${\sim }_A$ has at most as many classes as the automaton has states. Conversely, if ${\sim }_A$ has finitely many classes, define an automaton with state set ${\Sigma }^{\ast }/{\sim }_A$, initial state $[ϵ]$, transitionand accepting states $[u]$ with $u\in A$. Right congruence makes the transition well defined, and induction on word length shows that the state reached by $u$ is $[u]$, so the automaton accepts exactly $A$. Therefore $A$ is a regular language exactly when ${\sim }_A$ has finite index. Moreover, every automaton for $A$ has at least one state for each equivalence class, so this quotient is the minimal deterministic finite automaton.

We prove the claim by structural induction for primitive recursive functions. A formula is bounded when every quantifier is a bounded quantifier; this is a Delta-0 formula. The graphs of the initial functions have quantifier-free definitions:

Suppose $f(\mathbf{x})=g(h_1(\mathbf{x}),\dots ,h_m(\mathbf{x}))$ and the graphs of $g,h_1,\dots ,h_m$ have existential bounded definitions. Introduce variables $u_1,\dots ,u_m$ for the intermediate values and conjoin the graph formulasPulling all unrestricted existential witnesses to the front leaves a bounded matrix, so the required form is preserved by composition.

For primitive recursion, use Gödel beta-function sequence coding. The relationis bounded in the language of ordered rings. Given any finite sequence $a_0,\dots ,a_n$, choose $c$ larger than all its entries and divisible by $1,\dots ,n+1$. The moduli $1+(i+1)c$ are pairwise coprime, so the Chinese remainder theorem supplies $b$ with $\beta (b,c,i)=a_i$ for every $i\le n$.

Supposeand the induction hypothesis gives existential bounded graph formulas for $g$ and $h$. Then $y=f(\mathbf{x},n)$ exactly when there are $b,c$ coding values $a_0,\dots ,a_n$, together with a common witness bound $W$, such that:Write each $a_i$ using $\beta (b,c,i)$, bound the variables representing $a_i$ by $1+(n+1)c$, and bound every witness used by the graph formulas for $g$ and $h$ by $W$. All quantifiers checking the displayed finite recursion are then bounded; only $b,c,W$ and the finitely many outer coding witnesses are unrestricted existential variables. Conversely, any code passing these bounded checks satisfies the recursion equations, and induction on $i\le n$ forces its $i$th entry to be $f(\mathbf{x},i)$. This proves the existential bounded representation of a primitive recursive function.

A partial function $f:{\mathbb{N}}^k\rightharpoonup \mathbb{N}$ is lambda-definable when a lambda term $F$ sends the corresponding Church numerals to the numeral for $f(\mathbf{n})$ whenever the value is defined and produces no numeral otherwise; in other words, it is a lambda-definable partial function. The initial functions are represented byand the appropriate variable in $\lambda x_1\dots x_k.x_i$. If $G,H_1,\dots ,H_m$ represent $g,h_1,\dots ,h_m$, thenrepresents their composition.

Church Booleans supply a lazy conditional, andtests whether a Church numeral is zero. A standard predecessor term isLet $G$ and $H$ represent the base and step functions of a primitive recursion. With a fixed-point combinator $Y$, defineNormal-order beta reduction evaluates only the selected branch. Induction on the input numeral gives the two recursion equations, so this is the lambda definition of primitive recursion.

For unbounded minimization, let $G$ represent $g(\mathbf{x},n)$ and defineThen $Mx0$ tests $0,1,2,\dots$ in order and returns the least zero of $g$. If no zero is reached, or a required earlier computation is undefined, reduction never produces a Church numeral. This is the lambda definition of unbounded minimization. Since the partial recursive functions are generated from the initial functions by composition, primitive recursion, and minimization, every partial computable function is represented by a lambda term on Church numerals.

The structural induction principle says that a property $P(f)$ holds for every primitive recursive function if it holds for every initial function of recursion theory and is preserved by function composition in recursion theory and primitive recursion. This is justified because primitive recursive functions are, by definition, the smallest class closed under those constructors; equivalently, every such function has a finite construction tree, and ordinary induction on its height proves $P$.

Take $P(f)$ to mean that $f$ is total. The zero, successor, and projection functions are total. A composition of total functions is total. Finally, suppose $g$ and $h$ are total and $f$ is defined from them by primitive recursion. For fixed $\mathbf{x}$, induction on $n$ proves that $f(\mathbf{x},n)$ exists: the value at zero is $g(\mathbf{x})$, and from the existing value at $n$, totality of $h$ gives the value at $n+1$. Therefore every primitive recursive function is total.

Define a natural number to be a Finite von Neumann ordinal: an ordinal $n$ such that every nonempty subset of $n$ has a greatest member. This avoids the usual impredicative description of $\mathbb{N}$ as the intersection of all inductive sets.

Every usual von Neumann natural numberhas this property. The proof is by induction: a nonempty subset of $n+1$ either contains $n$, which is then greatest, or is a nonempty subset of $n$.

Conversely, let $\alpha$ be an ordinal with the stated property. If $\alpha$ were not one of the finite von Neumann ordinals, it would contain every finite ordinal. Indeed, if $n$ were the least finite ordinal not in $\alpha$, ordinal comparability and the presence of all $m<n$ would force $\alpha =n$ or $\alpha =m$ for some $m<n$. The subsetwould then be nonempty and have no greatest element, a contradiction. Thus this definition picks out exactly the natural numbers given by the usual least-inductive-set definition.

Let $T$ have a semidecidable axiomatization. If $T$ is inconsistent, the singleton axiom set $\{\perp \}$ is decidable and independent. If $T$ has no nonlogical axioms, the empty set already works. In the remaining case assume $T$ is consistent, choose a total computable enumeration $A_1,A_2,\dots$ of its axioms, allowing repetitions, and conservatively enlarge the language by fresh nullary predicates $P_1,P_2,\dots$.

For each $i\ge 1$, let $B_i$ be the conjunction of $i$ copies of $P_i\wedge A_i$. The range $\{B_i:i\ge 1\}$ is decidable by the Craig trick. Given a candidate formula of length $m$, only indices $i\le m$ are possible; compute $A_1,\dots ,A_m$, form the corresponding $B_i$, and compare the finite list syntactically.

The new theory has exactly the same consequences in the original language. Every model of $T$ expands to a model of all $B_i$ by interpreting every $P_i$ as true, while the reduct of any model of all $B_i$ satisfies every $A_i$. The axioms are independent: after deleting $B_i$, take any model of $T$, interpret $P_j$ as true for $j\ne i$, and interpret $P_i$ as false. This expansion satisfies every remaining $B_j$ but not $B_i$. Hence the $B_i$ form an independent tagged axiomatization that is decidable. Here equivalence means a conservative extension, or equivalently equality of all consequences in the original language.

Fix an effective enumeration $({\phi }_e)$ of the unary partial computable functions. Suppose the setwere computably enumerable, say as $e_0,e_1,\dots$. Thenwould be a total computable function. Hence $g={\phi }_{e_k}$ for some $k$, buta contradiction. Thus the set of Gödel numbers of total computable functions is not recursively axiomatizable; this is the totality problem is not computably enumerable argument.

Let $T$ be a recursively axiomatized theory of arithmetic. For each program index $e$, fix an arithmetical sentenceexpressing that the computation with index $e$ halts on every input. Enumerate all formal $T$-proofs and output $e$ whenever a proof ending in $\mathrm{Tot}(e)$ appears. This enumerates exactly the Gödel numbers of the computable functions that $T$ proves total, namely the provably total computable functions, so that set is recursively axiomatizable.

Assume now that $T$ is sound. Repeat every discovered index indefinitely, obtaining an effective infinite list $e_0,e_1,\dots$ of the functions whose totality $T$ proves. DefineSoundness makes every ${\phi }_{e_n}$ genuinely total, so $f_T$ is total and computable. If $T$ proved its totality, an index $e$ for $f_T$ would occur in the list, say $e_k=e$, and thenwhich is impossible. Thus $f_T$ is a total computable function whose totality is not provable in $T$.

Let $M$ be a nonstandard model of the Theory of true arithmetic whose carrier is $\mathbb{N}$, and suppose for contradiction that the graphs of ${+}^M$ and ${\times }^M$ are decidable. Because these operations are total, searching their decidable graphs computes their output on any pair of carrier elements.

Choose disjoint recursively inseparable sets $A,B$ that are computably enumerable, with primitive recursive stage predicates $E_A(n,s)$ and $E_B(n,s)$. Let $c\in M$ be nonstandard. True arithmetic proves finite sequence coding, so inside $M$ there is an element $a$ such that, for every $i<c$,where $p_i$ is the $i$th prime. This can be obtained by taking the product of the selected primes internally; it is the same finite coding mechanism as Gödel beta-function sequence coding.

Define the external setThis set is decidable from the assumed operations. For fixed standard $n$, compute the model element $p_n^M$. The division algorithm in $M$ gives unique $q$ and a remainder among the finitely many standard residuessuch that $a=q{\times }^M{p}_n^M+r$. Dovetail the search over $q$ and these finitely many residues, using the computable model operations. It eventually finds the unique remainder, and $n\in C$ exactly when that remainder is zero.

If $n\in A$, it enters $A$ at a standard stage below the nonstandard $c$, so $n\in C$. If $n\in B$, the true arithmetical sentence asserting that the two enumerations are disjoint holds in $M$, so $n$ cannot enter the coded $A$-set below $c$; hence $n\notin C$. Thuscontradicting recursive inseparability. The two operation graphs therefore cannot both be decidable. This is the recursively inseparable-set proof of Tennenbaum theorem.

No. The complement of the finite validity problem for first-order logic is computably enumerable: enumerate finite structures in the sentence's finite vocabulary, evaluate the sentence in each, and halt when a countermodel appears.

For the converse hardness, fix a Turing machine $P$ and input $w$. Effectively construct a first-order sentence ${\sigma }_{P,w}$ describing a halting computation tableau. Use finite linearly ordered sets for times and tape positions, predicates for the state, head position, and tape symbol at each cell, and first-order local clauses saying that the first row is the initial configuration, consecutive rows obey the transition table, and the final row is halting. ThenA halting run gives its finite tableau; conversely, the linear orders and local transition clauses make every finite model decode to such a run.

If the sentences true in every finite structure were computably enumerable, then for each $(P,w)$ we could enumerate until either a finite model of ${\sigma }_{P,w}$ appeared or $\neg {\sigma }_{P,w}$ appeared among the finite validities. This would decide the halting problem. Equivalently, $\neg {\sigma }_{P,w}$ is finitely valid exactly when $P$ does not halt, so finite validity cannot be computably enumerable. This is Trakhtenbrot theorem.