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

There is no computable presentation of a Nonstandard model of Peano arithmetic. We prove Tennenbaum theorem by obtaining a computable set separating two recursively inseparable sets.

Fix an effective enumeration $({\phi }_e)$ of partial computable functions, implemented by deterministic machines, and putThese are disjoint computably enumerable sets. To see that they are recursively inseparable sets, suppose a computable set $D$ contains $U$ and avoids $V$. Its indicator function has some index $k$. If ${\phi }_k(k)=0$, then $k\in U\subseteq D$, contradicting that output. If ${\phi }_k(k)=1$, then $k\in V$, contradicting $D\cap V=\varnothing$. Thus neither output is possible.

Let $M\models \mathrm{PA}$ be a Nonstandard model of Peano arithmetic. A recursive presentation of a structure here means a presentation on $\mathbb{N}$ in which its arithmetic operations are total computable functions; equality of presentation codes is ordinary equality. Write $\bar{n}$ for the element represented by the standard numeral $n$. The presentation codes of $\bar{0},\bar{1}$ are fixed constants, so $n\mapsto \bar{n}$ is a total computable function obtained by repeated addition. Presentation codes and the arithmetic values they name must be kept distinct.

Use bounded simulation of a computation predicates $H_i(e,t)$ saying that machine $e$, on input $e$, has halted by time $t$ with output $i$. We can choose these as primitive recursive predicates represented in Peano arithmetic. Determinism and induction on the computation length give, provably in Peano arithmetic, monotonicity in $t$ andA genuine standard halting computation has a finite certificate which Peano arithmetic verifies. Consequently, if $e\in U$ or $e\in V$, the corresponding $H_i(\bar{e},\bar{t})$ holds in $M$ for some standard $t$.

Choose a nonstandard element $c$ of $M$. It exceeds every standard numeral. Let $p_e$ be the $e$th prime number, starting with $p_0=2$. Peano arithmetic proves the prime-divisibility coding of a finite set needed here: for each $c$, an element $d$ can be formed as the product of precisely those $p_e$ with $e<c$ for which $H_0(e,c)$ holds. Formally,This is an internally finite product, not a claim that its externally observed index set is finite. Its existence follows by mathematical induction on the cutoff: start with $1$, multiply by the next distinct prime number when its predicate holds, and otherwise retain the product. Unique prime factorization ensures that earlier divisibility decisions are preserved. The standard prime enumeration and these finite-product constructions are provably total in Peano arithmetic.

Define the external subset $D=\{e\in \mathbb{N}:M\models p_{\bar{e}}\mid d\}$. If $e\in U$, its standard halting time is below $c$, and monotonicity gives $H_0(\bar{e},c)$, so $e\in D$. If $e\in V$, its output-one certificate and the provable incompatibility above exclude $H_0(\bar{e},c)$, so $e\notin D$. Hence $D$ separates $U$ and $V$.

Finally $D$ is a computable set. Given standard $e$, compute the ordinary integer $p_e$ and its numeral in the presentation. Enumerate all presentation codes $q$, and for each test the finitely many standard remainders $0\le r<p_e$ forEach test is decidable using the assumed total computable functions. The division theorem of Peano arithmetic guarantees a quotient and a remainder below the standard numeral ${\bar{p}}_e$. Every element below that numeral is one of $\bar{0},\dots ,\overline{p_e-1}$, so the search terminates; the remainder is unique. Return yes exactly when $r=0$. This makes $D$ a computable set, contradicting the recursively inseparable sets construction. Therefore

The minimal deterministic finite automaton is unique up to an isomorphism preserving the initial state, transitions and accepting states. We use complete deterministic finite automata over the fixed alphabet; the PDF's abbreviation FDA has this meaning. State names themselves cannot be unique.

For words $u,v\in {\Sigma }^{\ast }$, introduce the Myhill-Nerode equivalenceIt is an equivalence relation, and appending the same letter to equivalent words preserves it: a suffix $w$ after $ua$ is the suffix $aw$ after $u$. Since $L$ is a regular language, take any recognizing deterministic finite automaton. Words reaching the same state are equivalent, since every further suffix gives the same computation. Thus ${\sim }_L$ has finite index.

The canonical residual automaton has one state $[u]$ for each class, initial state $[ϵ]$, transition $[u]\stackrel{a}{\to }[ua]$, and accepting states those with $u\in L$. These choices are well-defined by Myhill-Nerode equivalence. Induction on the input length shows that reading $u$ reaches $[u]$, so the deterministic finite automaton recognizes $L$, and all its states are accessible states of a deterministic finite automaton. The same state can be described by the left quotient of a formal languageTwo states are different precisely when some suffix distinguishes their acceptance behavior.

Every recognizing deterministic finite automaton has at least as many states as there are classes: pick a representative from each class; two different representatives cannot reach the same state. The canonical residual automaton attains this bound, and therefore is a minimal deterministic finite automaton.

For uniqueness, let $\mathcal{A}$ be any minimal deterministic finite automaton. All its states are accessible, since removing inaccessible states leaves a complete recognizing deterministic finite automaton with fewer states. Map a state reached by $u$ to $[u]$. This is well-defined because two words reaching the same state are equivalent. It is surjective because every class has a representative. Both sets have the minimal number of states, so it is a bijection. It preserves the initial state and transitions by construction, and preserves accepting states by taking the empty word as the suffix. This is the required isomorphism with the canonical residual automaton, provingThe empty word is included throughout, and empty or universal regular languages have the corresponding one-state complete deterministic finite automata.

Yes: regular languages are closed under the shuffle of formal languages. The construction must allow letters common to both alphabets to be assigned to either input word.

Take complete deterministic finite automata ${\mathcal{A}}_i=(Q_i,{\Sigma }_i,{\delta }_i,s_i,F_i)$ recognizing $L_i$. Construct a nondeterministic finite automaton on $Q_1\times Q_2$ over $\Sigma ={\Sigma }_1\cup {\Sigma }_2$. Its initial state is $(s_1,s_2)$ and its accepting states form $F_1\times F_2$. On a letter $a$, its possible moves from $(p,q)$ areBoth moves are allowed when $a$ belongs to both alphabets. They may coincide; that causes no difficulty.

For every run, record whether each move updated the first or the second coordinate. The letters assigned to each coordinate, in their original order, form two words $u_1,u_2$. The final coordinate states are exactly the states reached by reading $u_i$ in ${\mathcal{A}}_i$. Thus an accepting run expresses the input as an interleaving of a word of $L_1$ and a word of $L_2$.

Conversely, given such an interleaving, assign each input position to the word from which it came. The corresponding choices of transitions form a run ending in $F_1\times F_2$. This proves equality between the recognized formal language and the shuffle of formal languages, in both directions. No assumption of disjoint alphabets is needed. If one contributing word is the empty word, no move need update that coordinate; the initial pair is accepting exactly when both empty words are accepted.

Apply the powerset construction to this nondeterministic finite automaton to obtain a deterministic finite automaton. In particular,

Every countable structure in a countable first-order language has a Scott sentence whose countable models are precisely its isomorphic copies. In particular two countable structures with the same countable infinitary logic sentences are isomorphic. Countability of both structures is essential to the back-and-forth conclusion; the sentence need not exclude uncountable models.

Let $M$ be a nonempty countable structure in a countable first-order language. The countable infinitary logic $L_{{\omega }_1,\omega }$ permits countable logical conjunctions and logical disjunctions, but only finite strings of quantifiers and finitely many free variables in each formula. We construct a Scott formula ${\varphi }_{\bar{a}}^{\alpha }(\bar{x})$ for every finite tuple $\bar{a}$ from $M$ and every countable ordinal $\alpha$.

At stage zero, let ${\varphi }_{\bar{a}}^0$ be the conjunction of all atomic formulas true of $\bar{a}$ and the negations of all atomic formulas false of $\bar{a}$. Include atomic formulas involving arbitrary terms and constants, not just relation symbols applied directly to variables. There are only countably many such formulas. This complete atomic description ensures that matching tuples determine a partial isomorphism of structures.

At successors putAt a nonzero limit ordinal $\lambda <{\omega }_1$, put ${\varphi }_{\bar{a}}^{\lambda }={\bigwedge }_{\beta <\lambda }{\varphi }_{\bar{a}}^{\beta }$. All these are formulas of countable infinitary logic: each indexing set is countable, and the free variables are only the fixed finite tuple. Rename bound variables when necessary. Transfinite induction also shows $M\models {\varphi }_{\bar{a}}^{\alpha }(\bar{a})$.

For tuples of the same length within $M$, define $\bar{a}{\equiv }_{\alpha }\bar{b}$ by $M\models {\varphi }_{\bar{a}}^{\alpha }(\bar{b})$. Induction identifies this with the usual symmetric back-and-forth method equivalence: the tuples have the same atomic description at stage zero, and at a successor every one-element extension on either side has a matching extension at the previous stage. Thus these are decreasing equivalence relations, simultaneously for every finite tuple length.

There are only countably many pairs of finite tuples in $M$. A pair can cease to be equivalent at most once. The supremum of the first separation stages of all pairs that separate below ${\omega }_1$ is a countable ordinal. Choose a countable $\alpha$ at least that supremum. No pair can first separate at $\alpha +1$, soThis justifies stabilization without assuming that all tuples stabilize at one predetermined finite stage.

Now form the following Scott sentence, where the case $n=0$ has no displayed variables or quantifiers:It is a sentence of countable infinitary logic, because the family of all finite tuples is countable. The stabilization above and the truth of ${\varphi }_{\varnothing }^{\alpha }$ show $M\models {\sigma }_M$.

Suppose a countable structure $N$ satisfies ${\sigma }_M$. Start with the empty matching tuples, and maintain $N\models {\varphi }_{\bar{a}}^{\alpha }(\bar{b})$. The corresponding conjunct of ${\sigma }_M$ upgrades this to $N\models {\varphi }_{\bar{a}}^{\alpha +1}(\bar{b})$. The existential conjuncts extend the match by any specified element of $M$. The universal-disjunction conjunct extends it by any specified element of $N$. The atomic formula information makes a new element on one side match a new element on the other, and makes repeated elements agree with their earlier matches.

Enumerate both structures and alternate these two extension steps, including the least element not yet covered at each step. The union is a bijection preserving and reflecting every atomic formula, hence an isomorphism; for function symbols, eventually include both a tuple and the value of its function term to see explicitly that the function is preserved. For finite structures the same construction stops when both are covered. Conversely every isomorphic copy of $M$ satisfies ${\sigma }_M$, since isomorphisms preserve formulas of countable infinitary logic by induction on their construction. ThereforeIf countable $M,N$ have the same $L_{{\omega }_1,\omega }$ sentences, $N$ satisfies this Scott sentence of $M$ and is isomorphic to $M$. This proves Scott isomorphism theorem.

Yes. There is a computable isomorphism, obtained by an effective back-and-forth construction. Decidability of the two orders makes the usual existence argument into an algorithm.

Maintain a finite order-preserving partial isomorphism of structures $f_s$ from $(\mathbb{N},{<}_A)$ to $(\mathbb{N},{<}_B)$, starting with the empty map. At a forth step, take the least ordinary natural number $a$ outside its domain. Look at the finitely many mapped elements below and above $a$ in ${<}_A$. Their images impose an open interval in ${<}_B$: it lies above all the lower images and below all the upper images, with a missing bound interpreted as an unbounded side.

This interval contains a fresh element. If both bounds exist they are ordered correctly by the induction hypothesis; density supplies an element strictly between them. If there is just one bound, the absence of endpoints supplies an element beyond it; if there are no bounds, choose any element. Density and the absence of endpoints moreover give infinitely many points in every such open interval, so finitely many already used images can always be avoided.

Enumerate $b=0,1,2,\dots$ in the ordinary presentation order, test whether $b$ is unused and satisfies every required ${<}_B$ inequality, and choose the first successful candidate. All tests are decidable, and the existence argument proves termination. Extend $f_s$ by $a\mapsto b$.

At a back step, take the least natural number outside the range, interchange the roles of $A$ and $B$, and carry out exactly the same search for a fresh preimage. Alternate forth and back steps. Every stage is an effective terminating finite computation, and every stage remains an order-preserving partial isomorphism of structures.

Let $f={\bigcup }_s{f}_s$. The least-unused scheduling puts every element of $A$ into the domain and every element of $B$ into the range. For example, after $n+1$ forth steps, all ordinary presentation numbers at most $n$ have been included, since each step removes the least missing one. Thus $f$ is a bijection preserving and reflecting the orders. To compute $f(n)$, simulate the construction until $n$ appears in its domain; this terminates. The corresponding range search computes its inverse. HenceThe searches use the decidable presentations, rather than a possibly ineffective choice of points in an abstract dense linear order without endpoints.

Write $Q=(A\to B)\to A$ and $P=Q\to A$. The displayed formula is $(P\to B)\to B$. A proof of logical implication may use its temporary assumption more than once; this is ordinary natural deduction, not a linear proof system.

Assume $h:P\to B$, then $f:Q$, then $a:A$, then $g:Q$. The identity weakening rule derives $a:A$ from the hypotheses $a:A$ and $g:Q$. Discharging $g$ by the implication introduction rule gives $\lambda g^Q.a:P$. Applying $h$ by the implication elimination rule gives $h(\lambda g^Q.a):B$. Discharge $a$ to obtain $\lambda a^A.h(\lambda g^Q.a):A\to B$. Applying $f$ gives an $A$; discharge $f$ to obtain a $P$; apply $h$ once more to obtain $B$, and finally discharge $h$.

Here is the complete decorated natural deduction derivation, split at its intermediate $A\to B$ conclusion to keep the tree readable. Superscript labels mark which assumption occurrences are discharged; both occurrences labelled $1$ are discharged together.To avoid an excessively wide final tree, continue the same derivation as follows, using the right-hand derived premise above:followed byThus the concise lambda term, with bound-variable types determined by the displayed tree, isUnder the Curry-Howard correspondence, implication introduction rules correspond to lambda abstractions, implication elimination rules to applications, and the identity weakening rule retains the first term while allowing an unused second hypothesis. No other inference rule or classical axiom is required.

A well-quasi-ordering is a reflexive transitive relation for which every infinite sequence has $i<j$ with $x_i\le x_j$. A bad sequence has no such pair. The labelled version of Kruskal's tree theorem says that finite rooted trees labelled in any well-quasi-ordering are themselves well-quasi-ordered by label-monotone tree embedding.

More explicitly, an embedding is an injective map of vertices preserving lowest common ancestors, and satisfying ${\ell }_T(v)\le {\ell }_S(h(v))$ at every vertex. The root need not map to the host root. This is a homeomorphic embedding of a rooted tree: an edge can map to a longer path, but distinct branches must separate at the image of their common ancestor. We shall prove the stronger version in which every vertex's children are linearly ordered and embeddings respect that ordering. Forgetting the child order gives the stated result for unordered rooted trees.

We first establish the two well-quasi-ordering facts used in the proof. Every infinite sequence in a well-quasi-ordering has an infinite nondecreasing subsequence. Indeed, color an index pair $i<j$ according to whether $x_i\le x_j$. The infinite two-color Ramsey theorem gives a homogeneous infinite set; the negative color would be a bad sequence, so the positive color gives the required subsequence. It follows that the componentwise product of two well-quasi-orderings is a well-quasi-ordering: first extract a nondecreasing subsequence in one coordinate, then find a good pair in the other.

Next prove Higman lemma: finite words over a well-quasi-ordering $Q$, ordered by subsequence embedding with coordinatewise increase of letters, are a well-quasi-ordering. Suppose not, and choose a minimal bad sequence $w_0,w_1,\dots$ by making the length of $w_n$ minimal among all choices admitting an infinite bad continuation of the already fixed prefix. No word is the empty word, since that embeds in every later word. Write $w_n=v_n{a}_n$ with $a_n\in Q$. Extract indices $i_0<i_1<\cdots$ for which $a_{i_0}\le a_{i_1}\le \cdots$. ConsiderIt cannot be a bad sequence, since its first replacement is shorter than the minimal choice $w_{i_0}$. But a good pair within the original prefix is impossible. A prefix word embedding into $v_{i_j}$ would embed into $w_{i_j}$, contradicting the original bad sequence. And $v_{i_j}$ embedding into $v_{i_k}$ would, after appending the ordered last letters, embed $w_{i_j}$ into $w_{i_k}$, also impossible. This contradiction proves Higman lemma, including words of arbitrary finite length.

Now suppose there is a bad sequence of finite ordered labelled rooted trees. Choose a minimal bad sequence $T_0,T_1,\dots$ by minimizing the number of vertices of $T_n$, subject to the fixed prefix having an infinite bad continuation. Existence of a least possible size uses ordinary well-ordering of the natural numbers; after selecting such a tree retain a bad continuation to make the next choice.

Let $\mathcal{S}$ be the collection of all proper rooted subtrees of all $T_n$, with inherited labels and child ordering. These are the subtrees rooted at vertices other than the root, and each embeds into its containing tree. We claim $\mathcal{S}$ is a well-quasi-ordering under the same label-monotone tree embedding.

Otherwise choose a bad sequence $U_0,U_1,\dots$ from $\mathcal{S}$, and choose for each a containing tree $T_{n_j}$. The indices $n_j$ are unbounded in every tail: finitely many containing trees have only finitely many rooted subtrees, and an infinite bad sequence cannot repeatedly use one of these, since it embeds into itself. Passing to a subsequence, arrange $n_0<n_1<\cdots$. The spliced sequenceis bad. A good pair within either piece is already excluded. A comparison $T_k⪯U_j$, where $k<n_0\le n_j$, would compose with $U_j⪯T_{n_j}$ to give $T_k⪯T_{n_j}$, contradicting the original bad sequence. But $U_0$ is smaller than $T_{n_0}$, contradicting the minimal choice at that position. This proves the claim about $\mathcal{S}$.

Describe $T_n$ by its root label $q_n\in Q$ and its finite ordered list $C_n$ of child subtrees. Every entry of $C_n$ lies in $\mathcal{S}$. By Higman lemma, ${\mathcal{S}}^{\ast }$ is a well-quasi-ordering; hence so is $Q\times {\mathcal{S}}^{\ast }$. There exist $i<j$ with $q_i\le q_j$ and an increasing injection matching the child subtrees in $C_i$ to child subtrees in $C_j$, each by an embedding. Map root to root and combine these child embeddings. Different matched children lie in different target branches, so their paths meet exactly at the target root; within each branch the chosen embedding already preserves lowest common ancestors. The resulting map is a label-monotone tree embedding $T_i⪯T_j$, a contradiction. ThereforeThe empty labelled tree, if included by convention, embeds into every tree and causes no exception. A common stronger formulation requires the source root to map to the target root. It also follows: the theorem just proved makes all labelled child subtrees a well-quasi-ordering, and the product $Q\times \mathcal{T}(Q{)}^{\ast }$ then provides a good pair with roots explicitly matched, by the same final assembly. Internal child roots may map further down their matched branches. This must not be confused with edge-to-edge embedding, for which the theorem is false in general.

As printed, yes: the relation is universal. The original PDF puts the existentially quantified element in the same subset as the universally quantified element; this is not an OCR substitution. For each element of that subset, choose the element itself as witness, using reflexivity of the underlying well-quasi-ordering. For an empty subset the condition is vacuous. The truth value therefore never depends on the proposed target subset. On the power set this is a reflexive transitive relation, and every two terms of any infinite sequence are related:A well-quasi-ordering need not be antisymmetric, so universal comparability is allowed.

If the existential element is instead intended to belong to the target subset, the natural relation is the Hoare domination preorderFor arbitrary subsets the answer to that corrected question is no. Here is a complete counterexample, the Rado order. TakeThis is a partial order. Reflexivity is immediate. For transitivity, two same-row comparisons compose ordinarily. If the first comparison crosses rows and the second stays in its row, its target first coordinate is unchanged, so the cross-row inequality persists. If the first stays in its row and the second crosses, use $n\le l<k^{\prime }$; if both cross, use $n<k<l<k^{\prime }$. Antisymmetry follows because comparisons across distinct rows in both directions would require $n<k<l<m<n$.

The Rado order is a well-quasi-ordering. Given an infinite sequence $(m_i,n_i)$, if a first coordinate $m$ repeats infinitely often, its corresponding natural-number second coordinates have a nondecreasing pair, giving a same-row comparison. Otherwise each first coordinate occurs only finitely often, so the first coordinates in every tail are unbounded. In particular some later $m_j$ exceeds $n_0$, giving $(m_0,n_0){\le }_R(m_j,n_j)$.

For each $m$, take the infinite row $S_m=\{(m,n):n>m\}$. For distinct $m,k$, choose $n>\max (m,k)$. The element $(m,n)\in S_m$ is below no member $(k,l)$ of $S_k$, since its first coordinate is different and $n<k$ fails. Thus $S_m/{\le }_H{S}_k$ for every pair of distinct indices. These subsets form an infinite antichain, so the Hoare domination preorder on $\mathcal{P}(R)$ is not a well-quasi-ordering.

If only finite subsets were intended, the answer changes again: the finite-subset lifting of a well-quasi-order is a well-quasi-ordering. Enumerate each finite subset as a finite word. Higman lemma gives an earlier word embedding into a later one with every letter increased, which witnesses Hoare domination preorder comparison of the underlying subsets. The PDF specifies no finiteness restriction, so this observation supplements rather than replaces the literal answer and the arbitrary-subset counterexample.