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.