Why the usual argument for a non-standard model of PA is unconvincing

Although we can define a model of Arithmetic with an infinite descending sequence of elements [1], any such model is isomorphic to the “true arithmetic” [2] of the integers (negative plus positive), and not to any model of PA [3].

Moreover—as we shall show—we cannot assume that we can consistently add a constant c to PA, along with the denumerable axioms [\neg (c = 0)], [\neg (c = 1)], [\neg (c = 2)], …, since this would presume that which is sought to be proven, viz., that PA has a non-standard model.

We cannot therefore—as suggested in standard texts [4] —apply the Compactness Theorem and the (upward) Löwenheim-Skolem Theorem to conclude that PA has a non-standard model!

Compactness Theorem: If every finite subset of a set of sentences has a model, then the whole set has a model [5].

Upward Löwenheim-Skolem Theorem: Any set of sentences that has an infinite model has a non-denumerable model [6].

A formal argument for a non-standard model of PA

The following argument [7] attempts to validate the above line of reasoning suggested by standard texts for the existence of non-standard models of PA:

1. Let:

\mathbb{N} … the set of natural numbers;

= … equality;

S … the successor function;

+ … the addition function;

\ast … the product function;

0 … the null element.

be the structure that serves to define a sound interpretation of PA, say [\mathbb{N}].

2. Let T[\mathbb{N}] be the set of PA-formulas that are satisfied or true in [\mathbb{N}].

3. The PA-provable formulas form a subset of T[\mathbb{N}].

4. Let \Gamma be the countable set of all PA-formulas of the form [c_{n} = Sc_{n+1}], where the index n is a natural number.

5. Let T be the union of \Gamma and T[\mathbb{N}].

6. T[\mathbb{N}] plus any finite set of members of \Gamma has a model, e.g., [\mathbb{N}] itself, since [\mathbb{N}] is a model of any finite descending chain of successors.

7. Consequently, by Compactness, T has a model; call it M.

8. M has an infinite descending sequence with respect to S because it is a model of \Gamma.

9. Since PA is a subset of T, M is a non-standard model of PA.

Now, if—as claimed above—[\mathbb{N}] is a model of T[\mathbb{N}] plus any finite set of members of \Gamma, then all PA-formulas of the form [c_{n} = Sc_{n+1}] are PA-provable, \Gamma is a proper sub-set of the PA-provable formulas, and T is identically T[\mathbb{N}]!

Reason: The argument cannot be that some PA-formula of the form [c_{n} = Sc_{n+1}] is true in [\mathbb{N}] but not PA-provable, as this would imply that PA+[\neg (c_{n} = Sc_{n+1})] has a model other than [\mathbb{N}]; in other words, it would presume that PA has a non-standard model.

The same objection applies to the usual argument found in standard texts [8] which, again, is essentially that if PA has a non-standard model at all, then one such model is obtained by assuming we can consistently add a single non-numeral constant c to the language of PA, and the countable axioms c \neq 0,\ c \neq 1,\ c \neq 2,\ \ldots to PA. However, as noted earlier, this argument too does not resolve the question of whether such assumption validly allows us to conclude that there is a non-standard model of PA in the first place.

The prime number theorem

To place this pedantry in perspective, Legendre and Gauss independently conjectured in 1796 that, if \pi (x) denotes the number of primes less than x, then \pi (x) is asymptotically equivalent to x/In(x).

Between 1848/1850, Chebyshev confirmed that if \pi (x)/\{x/In(x)\} has a limit, then it must be 1.

However, the crucial question of whether \pi (x)/\{x/In(x)\} has a limit at all was answered in the affirmative independently by Hadamard and de la Vallée Poussin only in 1896.

Consequently, the postulated model M of T in (7), by `Compactness’, is the model [\mathbb{N}] that defines T[\mathbb{N}]. However, [\mathbb{N}] has no infinite descending sequence with respect to the successor function S, even though it is a model of \Gamma. Hence the argument does not establish the existence of a non-standard model of PA with an infinite descending sequence with respect to the successor function S.

The (upward) Skolem-Löwenheim theorem applies only to first-order theories that admit an axiom of infinity

We note, moreover, that the non-existence of non-standard models of PA would not contradict the (upward) Skolem-Löwenheim theorem, since the proof of this theorem implicitly limits its applicability amongst first-order theories to those that are consistent with an axiom of infinity—in the sense that the proof implicitly requires that a constant, say c, along with a denumerable set of axioms to the effect that c \neq 0,\ c \neq 1,\ \ldots, can be consistently added to the theory. However, as seen in the previous section, this is not the case with PA.

Notes

Return to 1: eg. George S. Boolos, John P. Burgess, Richard C. Jeffrey. 2003. Computability and Logic. (4th ed) Cambridge University Press, Cambridge, Section 25. 1, p303.

Return to 2: ibid., p.150. Ex. 12. 9.

Return to 3: ibid., Corollary 25. 3, p306.}

Return to 4: eg. George S. Boolos, John P. Burgess, Richard C. Jeffrey. 2003. Computability and Logic. (4th ed) Cambridge University Press, Cambridge, p.306; Elliott Mendelson. 1964. Introduction to Mathematical Logic. Van Norstrand, Princeton, p.112, Ex.\ 2.

Return to 5: George S. Boolos, John P. Burgess, Richard C. Jeffrey. 2003. Computability and Logic. (4th ed) Cambridge University Press, Cambridge, p147.

Return to 6: ibid., p163.

Return to 7: Laureano Luna. 2008. On non-standard models of Peano Arithmetic. The Reasoner, Vol(2)2 p7.

Return to 8: eg. George S. Boolos, John P. Burgess, Richard C. Jeffrey. 2003. Computability and Logic. (4th ed) Cambridge University Press, Cambridge, p.306; Elliott Mendelson. 1964. Introduction to Mathematical Logic. Van Norstrand, Princeton, p.112, Ex. 2.

Bhupinder Singh Anand

Advertisements