the proof of the model existence lemma in Chapter 13. It is outlined in the problems at the end of this chapter. While (true) arithmetic is not an axiomatizable theory, P is, and so the arithmetical Lowenheim¨ –Skolem theorem gives us the following.

25.3 Corollary. There is a nonstandard model of P with domain the natural numbers in which the denotation of every nonlogical symbol is an arithmetical relation or function.

Proof: As in the proof of the existence of nonstandard models of arithmetic, add a constant ∞ to the language of arithmetic and apply the compactness theorem to the theory

P {∞ = n: n = 0, 1, 2, . . . }

to conclude that it has a model (necessarily infinite, since all models of P are). The denotation of ∞ in any such model will be a nonstandard element, guaranteeing that the model is nonstandard. Then apply the arithmetical Lowenheim¨ –Skolem theorem to conclude that the model may be taken to have domain the natural numbers, and the denotations of all nonlogical symbols arithmetical.

The results of the next section contrast sharply with Corollaries 25.2 and 25.3.

25.2 Operations in Nonstandard Models

Our goal in this section is to indicate the proof of two strengthenings of Tennenbaum’s theorem to the effect that there is no nonstandard model of P with domain the natural numbers in which the addition and multiplication functions are both recursive, along with two analogues of these strengthened results. Specifically, the four results are as follows.

25.4a Theorem. There is no nonstandard model of (true) arithmetic with domain the natural numbers in which the addition function is arithmetical.

25.4b Theorem (Tennenbaum–Kreisel theorem). There is no nonstandard model of P with domain the natural numbers in which the addition function is recursive.

25.4c Theorem. There is no nonstandard model of (true) arithmetic with domain the natural numbers in which the multiplication function is arithmetical.

25.4d Theorem (Tennenbaum–McAloon theorem). There is no nonstandard model of P with domain the natural numbers in which the multiplication function is recursive.

The proof of Theorem 25.4a will be given in some detail. The modifications needed to prove Theorem 25.4b and those needed to prove Theorem 25.4c will both be indicated in outline. A combination of both kind of modifications would be needed for Theorem 25.4d, which will not be further discussed.

Throughout the remainder of this section, by formula we mean formula and sentence of the language of arithmetic L, and by model we mean an interpretation of L with domain the set of natural numbers. For the moment our concern will be with models of (true) arithmetic. Let M be such a model that is not isomorphic to the

standard model N, and let us use and as in the preceding section for the denotations it assigns to the addition and multiplication symbols.

A notational preliminary: Our usual notation for the satisfaction in a model M of a formula F(x, y) by elements a and b of the domain has been M |= F[a, b]. For the remainder of this chapter, rather than write, for instance, ‘let F(x, y) be the formulaz x = y · z and let M |= F[a, b]’, we are just going to write ‘let M |= z x = y · z[a, b]’. (Potentially this briefer notation is ambiguous where there is more than one free variable, since nothing in it explicitly indicates that it is a that goes with x and b with y rather than the other way around; actually, context and alphabetical order should always be sufficient to indicate what is intended.) Thus instead of writing ‘Let F(z) be the formula n <z and suppose M |= F[d]’, we just write ‘Suppose M |= n <z[d]’. In this notation, a number d is a nonstandard element of M if and only if for for every n, M |= n <z[d]. (If d is nonstandard, M |= d <z[d].)

We know from the previous section that nonstandard elements exist. The key to proving Theorem 25.4a is a rather surprising result (Lemma 25.7a below) asserting the existence of nonstandard elements with special properties. In the statement of this result and the lemmas needed to prove it, we write π (n) for the nth prime (counting 2 as the zeroth, 3 as the first, and so on). In order to be able to write about π in the language of arithmetic, fix a formula (x, y) representing the function π in Q (and hence in P and in arithemetic), as in section 16.2. Also, abbreviate as x | y the rudimentary formula defining the relation ‘x divides y’. Here, then, are the key lemmas.

25.5a Lemma. Let M be a nonstandard model of arithmetic. For any m > 0,

M |= x m · x = x + · · · + x (m xs).

25.6a Lemma. Let M be a nonstandard model of arithmetic. Let A(x) be any formula of L. Then there is a nonstandard element d such that

M |= y x <z ( w( (x, w) & w | y) ↔ A(x))[d].

25.7a Lemma. Let M be a nonstandard model of arithmetic. Let A(x) be any formula of L. Then there exists a b such that for every n,

M |= A(n) if and only if for some a, b = a · · · a [π (n) as].

Proof of Lemma 25.5a: The displayed sentence is true in N, and hence is true in

M.

Proof of Lemma 25.6a: It is enough to show that the sentence

z y x <z ( w( (x, w) & w | y) ↔ A(x))

is true in N, since it must then be true in M. Now what this sentence says, interpreted over N, is just that for every z there exists a positive y such that for all x < z, the xth prime divides y if and only if A(x) holds. It is enough to take for y the product of the xth prime for all x < z such that A(x) holds.

Before giving the details of the proof of Lemma 25.7a, let us indicate Tennenbaum’s main idea. Lemma 25.6a can be regarded as saying that for every z there is a y that encodes the answers to all questions A(x)? for x less than z. Apply this to a nonstandard element d in M. Then there is a b that encodes the answers to all questions M |= A(x)[i]? for all i LESS THAN d. But since d is nonstandard, the denotations of all numerals are LESS THAN d. So b codes the answers to all the infinitely many questions M |= A(n)? for n a natural number.

Proof of Lemma 25.7a: Let d be as in Lemma 25.6a, so we have

M |= y x <z ( w( (x, w) & w | y) ↔ A(x))[d].

Let b be such that

M |= x <z ( w( (x, w) & w | y) ↔ A(x))[b, d].

Since d is nonstandard, for every n, M |= n <z[d]. Thus we have

as required to complete the proof.

Proof of Theorem 25.4a: Suppose is arithmetical. Then, since it is obtainable from by primitive recursion, the function f taking a to a · · · a(n as) is arithmetical; and then, since it is obtainable from f and π by composition, the function g taking a to a · · · a [π (n) as] is arithmetical. (The proof in section 16.1 that recursive functions are arithmetical shows that processes of composition and primitive recursion applied to arithmetical functions yield arithmetical functions.) Hence the relation H given by

H bn if and only if for some a, b = a · · · a [π (n) as]

or in other words

H bn if and only if a b = g(a, n)

is arithmetical, being obtainable by existential quantification from the graph relation of an arithmetical function.

So let B(x, y) be a formula arithmetically defining H . Let A(x) be the formulaB(x, x). Apply Lemma 25.7a to obtain a b such that for all n, M |= A(n) if and only if H bn. Since the same sentences are true in M and N, for all n, N |= A(n) if and only if H bn. In particular, N |= A(b) if and only if H bb, that is, N |= B(b, b) if and only if H bb. But since B arithmetically defines H , we also have N |= B(b, b) if and only if H bb. Contradiction.

For the proof of Theorem 25.4b, we need extensions of the lemmas used for Theorem 25.4a that will apply not just to models of arithmetic but to models of P. We state these as Lemmas 25.5b through 25.7b below. As in the case of the extension of Theorem 25.1a to Theorem 25.1b, some ‘formalizing’ of the kind done in Chapter 16 is needed. What is needed for Lemma 25.6b, however, goes well beyond this; so, leaving other details to the reader, we give the proof of that lemma, before going on to give the derivation of Theorem 25.4b from the lemmas. The proof of Lemma 25.6b itself uses an auxiliary lemma of some interest, Lemma 25.8 below.

25.5b Lemma. Let M be a nonstandard model of P. For any m > 0,

M |= x m · x = x + · · · + x(m xs).

25.6b Lemma. Let M be a nonstandard model of P. Let A(x) be any formula of L. Then there is a nonstandard element d such that

M |= y x <z ( w( (x, w) & w | y) ↔ A(x))[d].

25.7b Lemma. Let M be a nonstandard model of P. Let A(x) be any formula of L. Then there exists a b such that for every n,

M |= A(n) if and only if for some a, b = a · · · a [π (n) as].

25.8 Lemma (Overspill principle). Let M be a nonstandard model of P. Let B(x) be any formula of L that is satisfied in M by all standard elements. Then B(x) is satisfied in M by some nonstandard element.

Proof of Lemma 25.8: Assume not. Then for any d that satisfies B(x) in M, d is standard, hence d† is standard, and hence d† satisfies B(x) in M. Thus

M |= x(B(x) → B(x ))

since O, being standard, satisfies B(x) in M, M |= B(0). But also

M |= (B(0) & x(B(x) → B(x ))) → x B(x)

since this is an axiom of P. So M |= x B(x) and every element satisfies B(x) in M, contrary to assumption.

Proof of Lemma 25.6b: It is possible to formalize the proof of

z y x <z ( w( (x, w) & w | y) ↔ A(x))

in P, but to do so would be both extremely tedious and entirely unnecessary, since in view of the preceding lemma it is enough to show that

y x <z ( w( (x, w) & w | y) ↔ A(x))

is satisfied by all standard elements, and for this it is enough to show that for every n, the following is a theorem of P:

Let n = m + 1. First recall that the following is a theorem of P:

(2) x(x <n ↔ (x = 0 · · · x = m)).

Since represents π , writing pi for π (i), for all i < n the following is a theorem of P:

For each sequence e = (e0, . . . , em ) of length n of 0s and 1s, let Ae be the conjunction of all ( )A(i), where the negation sign is present if ei = 0 and absent if ei = 1. Let Be(y) be the analogous formula with pi | y in place of A(i). Then the formula after the initial quantifier in (4) is logically equivalent to the disjunction of all conjunctions Ae & Be(y). The existential quantifier may be distributed through the disjunction, and in each disjunct confined to the conjuncts that involve the variable y. Thus (4) is logically equivalent to the disjunction of all conjunctions Ae & y Be(y). Hence (1) is provably equivalent in P to this disjunction. But y Be(y) is a true -rudimentary sentence, and so is provable in P. Hence (1) is provably equivalent in P to the disjunction of all Ae. But this disjunction is logically valid, hence provable in P or any theory. So (1) is provable in P.

Proof of Theorem 25.4b: We need a fact established in the problems at the end of Chapter 8 (and in a different way in those at the end of Chapter 16): there exist disjoint semirecursive sets A and B such that there is no recursive set containing A and disjoint from B. Since the sets are semirecursive, there are -rudimentary formulasyα(x, y) and yβ(x, y) defining them. Replacing these by

y(α(x, y)) & z ≤ yβ(x, y)) and y(β(x, y) & z ≤ y α(x, y))

we get -rudimentary formulas α*(x) and β*(x) also defining A and B, and for whichx(α*(x) & β*(x)) is a theorem of P. If n is in A, then since α*(n) is -rudimentary and true, it is a theorem of P, and hence M |= α*(n); while if n is in B, then similarly β*(n) is a theorem of P and hence so is α*(n), so that M |= α*(n).

Now by Lemma 25.7b, there are elements b+ and b− such that for every n,

we have

Y + = {n: for some a, b+ = a · · · a (π (n) as)}.

If the function is recursive, then (much as in the proof of Theorem 25.4a) since the function g taking a to a · · · a (π (n) as) is obtainable from by primitive recursion and composition with π , this g is recursive. Since

Y + = {n: a b+ = g(a, n)}.

Y + is semirecursive. A similar argument with b− in place of b+ shows that the complement Y − of Y + is also semirecursive, from which it follows that Y + is recursive. But this is impossible, since Y + contains A and is disjoint from B.

For the proof of Theorem 25.4c, we need lemmas analogous to those used for Theorem 25.4a, with in place of . We state these as Lemmas 25.5c through 25.7c below. These lemmas pertain to exponentiation. Now the notation x y for exponentiation is not available in L, any more than the notation π for the function enumerating the primes. But we allow ourselves to use that in stating the lemmas, rather than use a more correct but more cumbersome formulation in terms of a formula representing the exponential function. We also write x ↓ y for ‘y has an integral xth root’ or ‘y is the xth power of some integer’. The only real novelty comes in the proof of Lemma 25.6c, so we give that proof, leaving other details to the reader.

25.5c Lemma. Let M be a nonstandard model of arithmetic. For any m > 0,

M |= x xm = x · · · · · x (m xs).

25.6c Lemma. Let M be a nonstandard model of arithmetic. Let A(x) be any formula of L. Then there is a nonstandard element d such that

M |= y x <z ( w( (x, w) & w ↓ y) ↔ A(x))[d].

25.7c Theorem. Let M be a nonstandard model of arithmetic. Let A(x) be any formula of L. Then there exists a b such that for every n,

M |= A(n) if and only if for some a, b = a · · · a (π (n) as).

Proof of Lemma 25.6c: It is enough to show that

z y x <z ( w( (x, w) & W ↓ y) ↔ A(x))

is true in N, since it must then be true in M. Recall that we have shown in the proof of Lemma 25.6b that

z y x <z ( w( (x, w) & w | y) ↔ A(x))

is true in N. It suffices to show, therefore, that the following is true in N:

y v w(w ↓ v ↔ w | y).

In fact, given y, 2y will do for v (unless y = 0, in which case v = 0 will do). For suppose w divides y, say y = uw. Then 2y = 2uw = (2u )w , and 2y is a wth power.