A finitary arithmetical perspective on the forcing of non-standard models onto PA

(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)

In the previous post we formally argued that the first order Peano Arithmetic PA is categorical from a finitary perspective (\S 5, Corollary 1).

We now argue that conventional wisdom which holds PA as essentially incomplete—and thus precludes categoricity—may appeal to finitarily fragile arguments (as mentioned in this earlier post and in this preprint, now reproduced below) for the existence of non-standard models of the first-order Peano Arithmetic PA.

Such wisdom ought, therefore, to be treated foundationally as equally fragile from a post-computationalist arithmetical perspective within classical logic, rather than accepted as foundationally sound relative to an ante-computationalist perspective of set theory.

Post-computationalist doctrine

“It is by now folklore … that one can view the values of a simple functional language as specifying evidence for propositions in a constructive logic …” (cf. Mu91).

\S 1 Introduction

Once we accept as logically sound the set-theoretically based meta-argument [1] that the first-order Peano Arithmetic PA [2] can be forced—by an ante-computat- ionalist interpretation of the Compactness Theorem—into admitting non-standard models which contain an `infinite’ integer, then the set-theoretical properties [3] of the algebraic and arithmetical structures of such putative models should perhaps follow without serious foundational reservation.

Compactness Theorem: If every finite subset of a set of sentences has a model, then the whole set has a model (BBJ03. p.147).

However we shall argue that, from an arithmetical perspective, we can only conclude by the Compactness Theorem that if Th(\mathbb{N}) is the \mathcal{L}_{A}-theory of the standard model (interpretation) (Ka91, p.10-11), then we may consistently add to it the following as an additional—not necessarily independent—axiom:

(\exists y)(y > x).

Moreover, we shall argue that even though (\exists y)(y > x) is algorithmically computable (Definition 2) as always true in the standard model (whence all of its instances are in Th(\mathbb{N})) we cannot conclude by the Compactness Theorem that:

\cup_{k \in \mathbb{N}}\{Th(\mathbb{N}) \cup \{c > \underline{n}\ |\ n < k\}\}

is consistent and has a model M_{c} which contains an `infinite’ integer [4].

Reason: We shall argue that the condition k \in \mathbb{N} in the above definition of \cup_{k \in \mathbb{N}}T_{k} requires, first of all, that we must be able to extend Th(\mathbb{N}) by the addition of a `relativised’ axiom (cf. Fe92; Me64, p.192) such as:

(\exists y)((x \in \mathbb{N}) \rightarrow (y > x)),

from which we may conclude the existence of some c such that:

M_{c} \models c>\underline{n} for all n \in \mathbb{N}.

However, we shall further show that even this would not yield a model for Th(\mathbb{N}) since, by Theorem 1, we cannot introduce a `completed’ infinity such as \mathbb{N} into either Th(\mathbb{N}) or any model of Th(\mathbb{N})!

\S 1.1 A post-computationalist doctrine

More generally we shall argue that—if our interest is in the arithmetical properties of models of PA—then we first need to make explicit any appeal to non-constructive considerations such as Aristotle’s particularisation (Definition 3).

We shall then argue that, even from a classical perspective, there are serious foundational, post-computationalist, reservations to accepting that a consistent PA can be forced by the Compactness Theorem into admitting non-standard models which contain elements other than the natural numbers.

Reason: Any arithmetical application of the Compactness Theorem to PA can neither ignore currently accepted post-computationalist doctrines of objectivity—nor contradict the constructive assignments of satisfaction and truth to the atomic formulas of PA (therefore to the compound formulas under Tarski’s inductive definitions) in terms of either algorithmical verifiability or algorithmic computability (An12, \S 3).

The significance of this doctrine [5] is that it helps highlight how the algorithmically verifiable (Definition 1) formulas of PA define the classical non-finitary standard interpretation of PA [6] (to which standard arguments for the existence of non-standard models of PA critically appeal).

Accordingly, we shall show that standard arguments which appeal to the ante-computationalist interpretation of the Compactness Theorem—for forcing non-standard models of PA [7] which contain an `infinite’ integer—cannot admit constructive assignments of satisfaction and truth [8] (in terms of algorithmical verifiability) to the atomic formulas of their putative extension of PA.

We shall conclude that such arguments therefore questionably postulate by axiomatic fiat that which they seek to `prove’!

\S 1.2 Standard arguments for non-standard models of PA

In this limited investigation we shall consider only the following three standard arguments for the existence of non-standard models of the first-order Peano Arithmetic PA:

(i) If PA is consistent, then we obtain a non-standard model for PA which contains an `infinite’ integer by applying the Compactness Theorem to the union of the set of formulas that are satisfied or true in the classical `standard’ model of PA [9] and the countable set of all PA-formulas of the form [c_{n} = S(c_{n+1})].

(ii) If PA is consistent, then we obtain a non-standard model for PA which contains an `infinite’ integer by adding a constant c to the language of PA and applying the Compactness Theorem to the theory P\cup\{c > \underline{n}: \underline{n}\ =\ \underline{0},\ \underline{1},\ \underline{2},\ \ldots\}.

(iii) If PA is consistent, then we obtain a non-standard model for PA which contains an `infinite’ integer by adding the PA formula [\neg (\forall x)R(x)] as an axiom to PA, where [(\forall x)R(x)] is a Gödelian formula [10] that is unprovable in PA, even though [R(n)] is provable in PA for any given PA numeral [n] (Go31, p.25(1)).

We shall first argue that (i) and (ii)—which appeal to Thoralf Skolem’s ante-computationalist reasoning (in Sk34) for the existence of a non-standard model of PA—should be treated as foundationally fragile from a finitary, post-computationalist perspective within classical logic [11].

We shall then argue that although (iii)—which appeals to Kurt Gödel’s (also ante-computationalist) reasoning (Go31) for the existence of a non-standard model of PA—does yield a model other than the classical `standard’ model of PA, we cannot conclude by even classical (albeit post-computationalist) reasoning that the domain is other than the domain N of the natural numbers unless we make the non-constructive—and logically fragile—extraneous assumption that a consistent PA is necessarily \omega-consistent.

(\omega-consistency): A formal system S is \omega-consistent if, and only if, there is no S-formula [F(x)] for which, first, [\neg(\forall x)F(x)] is S-provable and, second, [F(a)] is S-provable for any given S-term [a].

\S 2 Algorithmically verifiable formulas and algorithmically computable formulas

We begin by distinguishing between:

Definition 1: An atomic formula [F(x)] [12] of PA is algorithmically verifiable under an interpretation if, and only if, for any given numeral [n], there is an algorithm AL_{(F,\ n)} which can provide objective evidence (Mu91) for deciding the truth value of each formula in the finite sequence of PA formulas \{[F(1)], [F(2)], \ldots, [F(n)]\} under the interpretation.

The concept is well-defined in the sense that the `algorithmic verifiability’ of the formulas of a formal language which contain logical constants can be inductively defined under an interpretation in terms of the `algorithmic verifiability’ of the interpretations of the atomic formulas of the language (An12).

We note further that the formulas of the first order Peano Arithmetic PA are decidable under the standard interpretation of PA over the domain \mathbb{N} of the natural numbers if, and only if, they are algorithmically verifiable under the interpretation [13].

Definition 2: An atomic formula [F(x)] of PA is algorithmically computable under an interpretation if, and only if, there is an algorithm AL_{F} that can provide objective evidence for deciding the truth value of each formula in the denumerable sequence of PA formulas \{[F(1)], [F(2)], \ldots\} under the interpretation.

This concept too is well-defined in the sense that the `algorithmic computability’ of the formulas of a formal language which contain logical constants can also be inductively defined under an interpretation in terms of the `algorithmic computability’ of the interpretations of the atomic formulas of the language (An12).

We note further that the PA-formulas are decidable under an algorithmic interpretation of PA over \mathbb{N} if, and only if, they are algorithmically computable under the interpretation [14].

Although we shall not appeal to the following in this paper, we note in passing that the foundational significance [15] of the distinction lies in the argument that:

Lemma 1: There are algorithmically verifiable number theoretical functions which are not algorithmically computable. [16]

Proof: Let r(n) denote the n^{th} digit in the decimal expansion \sum_{n=1}^{\infty}r(n).10^{-n} of a putatively given real number \mathbb{R} in the interval 0 < \mathbb{R} \leq 1. By the definition of a real number as the limit of a Cauchy sequence of rationals, it follows that r(n) is an algorithmically verifiable number-theoretic function. Since every algorithmically computable real is countable (Tu36), Cantor’s diagonal argument (Kl52, pp.6-8) shows that there are real numbers that are not algorithmically computable. The Lemma follows. \Box

\S 3 Making non-finitary assumptions explicit

We next make explicit—and briefly review—a tacitly held fundamental tenet of classical logic which is unrestrictedly adopted as intuitively obvious by standard literature [17] that seeks to build upon the formal first-order predicate calculus FOL:

Definition 3: (Aristotle’s particularisation) This holds that from an assertion such as:

`It is not the case that: For any given x, P^{*}(x) does not hold’,

usually denoted symbolically by `\neg(\forall x)\neg P^{*}(x)‘, we may always validly infer in the classical, Aristotlean, logic of predicates (HA28, pp.58-59) that:

`There exists an unspecified x such that P^{*}(x) holds’,

usually denoted symbolically by `(\exists x)P^{*}(x)‘.

\S 3.1 The significance of Aristotle’s particularisation for the first-order predicate calculus

Now we note that in a formal language the formula `[(\exists x)P(x)]‘ is an abbreviation for the formula `[\neg(\forall x)\neg P(x)]‘; and that the commonly accepted interpretation of this formula tacitly appeals to Aristotlean particularisation.

However, as L. E. J. Brouwer had noted in his seminal 1908 paper on the unreliability of logical principles (Br08), the commonly accepted interpretation of this formula is ambiguous if interpretation is intended over an infinite domain.

Brouwer essentially argued that, even supposing the formula `[P(x)]‘ of a formal Arithmetical language interprets as an arithmetical relation denoted by `P^{*}(x)‘, and the formula `[\neg(\forall x)\neg P(x)]‘ as the arithmetical proposition denoted by `\neg(\forall x)\neg P^{*}(x)‘, the formula `[(\exists x)P(x)]‘ need not interpret as the arithmetical proposition denoted by the usual abbreviation `(\exists x)P^{*}(x)‘; and that such postulation is invalid as a general logical principle in the absence of a means for constructing some putative object a for which the proposition P^{*}(a) holds in the domain of the interpretation.

Hence we shall follow the convention that the assumption that `(\exists x)P^{*}(x)‘ is the intended interpretation of the formula `[(\exists x)P(x)]‘—which is essentially the assumption that Aristotle’s particularisation holds over the domain of the interpretation—must always be explicit.

\S 3.2 The significance of Aristotle’s particularisation for PA

In order to avoid intuitionistic objections to his reasoning, Kurt Gödel introduced the syntactic property of \omega-consistency [18] as an explicit assumption in his formal reasoning in his seminal 1931 paper on formally undecidable arithmetical propositions (Go31, p.23 and p.28).

Gödel explained at some length [19] that his reasons for introducing \omega-consistency explicitly was to avoid appealing to the semantic concept of classical arithmetical truth in Aristotle’s logic of predicates (which presumes Aristotle’s particularisation).

The two concepts are meta-mathematically equivalent in the sense that, if PA is consistent, then PA is \omega-consistent if, and only if, Aristotle’s particularisation holds under the standard interpretation of PA [20].

\S 4 The ambiguity in admitting an `infinite’ constant

We begin our consideration of standard arguments for the existence of non-standard models of PA which contain an `infinite’ integer by first highlighting and eliminating an ambiguity in the argument as it is usually found in standard texts [21]:

Corollary. There is a non-standard 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 \infty to the language of arithmetic and apply the Compactness Theorem to the theory

P\cup\{\infty \neq n: n\ =\ 0,\ 1,\ 2,\ \ldots\}

to conclude that it has a model (necessarily infinite, since all models of P are). The denotations of \infty in any such model will be a non-standard element, guaranteeing that the model is non-standard. Then apply the arithmetical Löwenheim-Skolem theorem to conclude that the model may be taken to have domain the natural numbers, and the denotations of all nonlogical symbols arithmetical.”

… BBJ03, p.306, Corollary 25.3.

\S 4.1 We cannot force PA to admit a transfinite ordinal

The ambiguity lies in a possible interpretation of the symbol \infty as a `completed’ infinity (such as Cantor’s first transfinite ordinal \omega) in the context of non-standard models of PA. To eliminate this possibility we establish trivially that, and briefly examine why:

Theorem 1: No model of PA can admit a transfinite ordinal under the standard interpretation of the classical logic FOL[22].

Proof: Let [G(x)] denote the PA-formula:

[x=0 \vee \neg(\forall y)\neg(x=Sy)]

Since Aristotle’s particularisation is tacitly assumed under the standard interpretation of FOL, this translates in every model of PA, as:

If x denotes an element in the domain of a model of PA, then either x is 0, or x is a `successor’.

Further, in every model of PA, if G(x) denotes the interpretation of [G(x)]:

(a) G(0) is true;

(b) If G(x) is true, then G(Sx) is true.

Hence, by Gödel’s completeness theorem:

(c) PA proves [G(0)];

(d) PA proves [G(x) \rightarrow G(Sx)].

Gödel’s Completeness Theorem: In any first-order predicate calculus, the theorems are precisely the logically valid well-formed formulas (i. e. those that are true in every model of the calculus).

Further, by Generalisation:

(e) PA proves [(\forall x)(G(x) \rightarrow G(Sx))];

Generalisation in PA: [(\forall x)A] follows from [A].

Hence, by Induction:

(f) [(\forall x)G(x)] is provable in PA.

Induction Axiom Schema of PA: For any formula [F(x)] of PA:

[F(0) \rightarrow ((\forall x)(F(x) \rightarrow F(Sx)) \rightarrow (\forall x)F(x))]

In other words, except 0, every element in the domain of any model of PA is a `successor’. Further, the standard PA axioms ensure that x can only be a `successor’ of a unique element in any model of PA.

Since Cantor’s first limit ordinal \omega is not the `successor’ of any ordinal in the sense required by the PA axioms, and since there are no infinitely descending sequences of ordinals (cf. Me64, p.261) in a model—if any—of a first order set theory such as ZF, the theorem follows. \Box

\S 4.2 Why we cannot force PA to admit a transfinite ordinal

Theorem 1 reflects the fact that we can define the usual order relation `<‘ in PA so that every instance of the PA Axiom Schema of Finite Induction, such as, say:

(i) [F(0) \rightarrow ((\forall x)(F(x) \rightarrow F(Sx)) \rightarrow (\forall x)F(x))]

yields the weaker PA theorem:

(ii) [F(0) \rightarrow ((\forall x) ((\forall y)(y < x \rightarrow F(y)) \rightarrow F(x)) \rightarrow (\forall x)F(x))]

Now, if we interpret PA without relativisation in ZF [23]— i.e., numerals as finite ordinals, [Sx] as [x \cup \left \{ x \right \}], etc.— then (ii) always translates in ZF as a theorem:

(iii) [F(0) \rightarrow ((\forall x)((\forall y)(y \in x \rightarrow F(y)) \rightarrow F(x)) \rightarrow (\forall x)F(x))]

However, (i) does not always translate similarly as a ZF-theorem, since the following is not necessarily provable in ZF:

(iv) [F(0) \rightarrow ((\forall x)(F(x) \rightarrow F(x \cup \left \{x\right \})) \rightarrow (\forall x)F(x))]

Example: Define [F(x)] as `[x \in \omega]’.

We conclude that, whereas the language of ZF admits as a constant the first limit ordinal \omega which would interpret in any putative model of ZF as the (`completed’ infinite) set \omega of all finite ordinals:

Corollary 1: The language of PA admits of no constant that interprets in any model of PA as the set N of all natural numbers.

We note that it is the non-logical Axiom Schema of Finite Induction of PA which does not allow us to introduce—contrary to what is suggested by standard texts [24]—an `actual’ (or `completed’) infinity disguised as an arbitrary constant (usually denoted by c or \infty) into either the language, or a putative model, of PA [25].

\S 5 Forcing PA to admit denumerable descending dense sequences

The significance of Theorem 1 is seen in the next two arguments, which attempt to implicitly bypass the Theorem’s constraint by appeal to the Compactness Theorem for forcing a non-standard model onto PA [26].

However, we argue in both cases that applying the Compactness Theorem constructively—even from a classical perspective—does not logically yield a non-standard model for PA with an `infinite’ integer as claimed [27].

\S 5.1 An argument for a non-standard model of PA

The first is the argument (Ln08, p.7) that we can define a non-standard model of PA with an infinite descending chain of successors, where the only non-successor is the null element 0:

1. Let <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 model of PA, say N.

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

3. The PA-provable formulas form a subset of T[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[N].

6. T[N] plus any finite set of members of \Gamma has a model, e.g., N itself, since 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.

\S 5.2 Why the argument in \S 5.1 is logically fragile

However if—as claimed in \S 5.1(6) above—N is a model of T[N] plus any finite set of members of \Gamma, and the PA term [c_{n}] is well-defined for any given natural number n, then:

\bullet All PA-formulas of the form [c_{n} = Sc_{n+1}] are PA-provable,

\bullet \Gamma is a proper sub-set of the PA-provable formulas, and

\bullet T is identically T[N].

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

Consequently, the postulated model M of T in \S 5.1(7) by `Compactness’ is the model N that defines T[N]. However, N has no infinite descending sequence with respect to 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.

\S 5.3 A formal argument for a non-standard model of PA

The second is the more formal argument [29]:

“Let Th(\mathbb{N}) denote the complete \mathcal{L}_{A}-theory of the standard model, i.e. Th(\mathbb{N}) is the collection of all true \mathcal{L}_{A}-sentences. For each n \in \mathbb{N} we let \underline{n} be the closed term (\ldots(((1+1)+1)+ \ldots +1))) (n\ 1s) of \mathcal{L}_{A}; \underline{0} is just the constant symbol 0. We now expand our language \mathcal{L}_{A} by adding to it a new constant symbol c, obtaining the new language \mathcal{L}_{c}, and consider the following \mathcal{L}_{c}-theory with axioms

\rho (for each \rho \in Th(\mathbb{N}))

and

c>\underline{n} (for each n \in \mathbb{N})

This theory is consistent, for each finite fragment of it is contained in

T_{k} = Th(\mathbb{N}) \cup \{c > \underline{n}\ |\ n < k\}

for some k \in \mathbb{N}, and clearly the \mathcal{L}_{c}-structure (\mathbb{N},\ k) with domain \mathbb{N},\ 0,\ 1,\ +,\ \cdot and < interpreted naturally, and c interpreted by the integer k, satisfies T_{k}. Thus by the compactness theore \cup_{k \in \mathbb{N}}T_{k} is consistent and has a model M_{c}. The first thing to note about M_{c} is that

M_{c} \models c>\underline{n}

for all n \in \mathbb{N}, and hence it contains an `infinite’ integer.”

\S 5.4 Why the argument in \S 5.3 too is logically fragile

We note again that, from an arithmetical perspective, any application of the Compactness Theorem to PA cannot ignore currently accepted computationalist doctrines of objectivity (cf. Mu91) and contradict the constructive assignment of satisfaction and truth to the atomic formulas of PA (therefore to the compound formulas under Tarski’s inductive definitions) in terms of either algorithmical verifiability or algorithmic computability (An12, \S 3).

Accordingly, from an arithmetical perspective we can only conclude by the Compactness Theorem that if Th(\mathbb{N}) is the \mathcal{L}_{A}-theory of the standard model (interpretation), then we may consistently add to it the following as an additional—not necessarily independent—axiom:

(\exists y)(y > x).

Moreover, even though (\exists y)(y > x) is algorithmically computable as always true in the standard model—whence all instances of it are also therefore in Th(\mathbb{N})—we cannot conclude by the Compactness Theorem that \cup_{k \in \mathbb{N}}T_{k} is consistent and has a model M_{c} which contains an `infinite’ integer.

Reason: The condition `k \in \mathbb{N}‘ in \cup_{k \in \mathbb{N}}T_{k} requires, first of all, that we must be able to extend Th(\mathbb{N}) by the addition of a `relativised’ axiom (cf. Fe92; Me64, p.192) such as:

(\exists y)((x \in \mathbb{N}) \rightarrow (y > x)),

from which we may conclude the existence of some c such that:

M_{c} \models c>\underline{n}

for all n \in \mathbb{N}.

However, even this would not yield a model for Th(\mathbb{N}) since, by Theorem 1, we cannot introduce a `completed’ infinity such as \mathbb{N} into any model of Th(\mathbb{N})!

As the argument stands, it seeks to violate finitarity by adding a new constant c to the language \mathcal{L}_{A} of PA that is not definable in \mathcal{L}_{A} and, ipso facto, adding an atomic formula [c=x] to PA whose satisfaction under any interpretation of PA is not algorithmically verifiable!

Since the atomic formulas of PA are algorithmically verifiable under the standard interpretation (An12, Corollary 2), the above conclusion too postulates that which it seeks to prove!

Moreover, the postulation would be false if Th(\mathbb{N}) were categorical.

Since Th(\mathbb{N}) must have a non-standard model if it is not categorical, we consider next whether we may conclude from Gödel’s incompleteness argument (in Go31) that any such model can have an `infinite’ integer.

\S 6 Gödel’s argument for a non-standard model of PA

We begin by considering the Gödelian formula [(\forall x)R(x)] [30] which is unprovable in PA if PA is consistent, even though the formula [R(n)] is provable in a consistent PA for any given PA numeral [n].

Now, it follows from Gödel’s reasoning [31] that:

Theorem 2: If PA is consistent, then we may add the PA formula [\neg (\forall x)R(x)] as an axiom to PA without inviting inconsistency.

Theorem 3: If PA is \omega-consistent, then we may add the PA formula [(\forall x)R(x)] as an axiom to PA without inviting inconsistency.

Gödel concluded from this that:

Corollary 2: If PA is \omega-consistent, then there are at least two distinctly different models of PA. \Box

If we assume that a consistent PA is necessarily \omega-consistent, then it follows that one of the two putative models postulated by Corollary 2 must contain elements other than the natural numbers.

We conclude that Gödel’s justification for the assumption that non-standard models of PA containing elements other than the natural numbers are logically feasible lies in his non-constructive—and logically fragile—assumption that a consistent PA is necessarily \omega-consistent.

\S 6.1 Why Gödel’s assumption is logically fragile

Now, whereas Gödel’s proof of Corollary 2 appeals to the non-constructive Aristotle’s particularisation, a constructive proof of the Corollary follows trivially from evidence-based interpretations of PA (An12).

Reason: Tarski’s inductive definitions allow us to provide finitary satisfaction and truth certificates to all atomic (and ipso facto to all compound) formulas of PA over the domain N of the natural numbers in two essentially different ways:

(1) In terms of algorithmic verifiabilty (An12, \S 4.2); and

(2) In terms of algorithmic computability (An12, \S 4.3).

That there can be even one, let alone two, logically sound and finitary assignments of satisfaction and truth certificates to both the atomic and compound formulas of PA was hitherto unsuspected!

Moreover, neither the putative `algorithmically verifiable’ model, nor the `algorithmically computable’ model, of PA defined by these finitary satisfaction and truth assignments contains elements other than the natural numbers.

(a) Any algorithmically verifiable model of PA is necessarily over \mathbb{N}

For instance if, in the first case, we assume that the algorithmically verifiable atomic formulas of PA determine an algorithmically verifiable model of PA over the domain \mathbb{N} of the PA numerals, then such a putative model would be isomorphic to the standard model of PA over the domain N of the natural numbers (An12, \S 4.2 & \S 5, Corollary 2).

However, such a putative model of PA over \mathbb{N} would not be finitary since, if the formula [(\forall x) F(x)] were to interpret as true in it, then we could only conclude that, for any numeral [n], there is an algorithm which will finitarily certify the formula [F(n)] as true under an algorithmically verifiable interpretation in \mathbb{N}.

We could not conclude that there is a single algorithm which, for any numeral [n], will finitarily certify the formula [F(n)] as true under the algorithmically verifiable interpretation in \mathbb{N}.

Consequently, the PA Axiom Schema of Finite Induction would not interpret as true finitarily under the algorithmically verifiable interpretation of PA over the domain \mathbb{N} of the PA numerals.

Thus the algorithmically verifiable interpretation of PA would not define a finitary model of PA.

However, if we were to assume that the algorithmically verifiable interpretation of PA defines a non-finitary model of PA, then it would follow that:

\bullet PA is necessarily \omega-consistent;

\bullet Aristotle’s particularisation holds over N; and

\bullet The `standard’ interpretation of PA also defines a non-finitary model of PA over N.

(b) The algorithmically computable interpretation of PA is over \mathbb{N}

The second case is where the algorithmically computable atomic formulas of PA determine an algorithmically computable model of PA over the domain N of the natural numbers (An12, \S 4.3 & \S 5.2).

The algorithmically computable model of PA is finitary since we can show that, if the formula [(\forall x) F(x)] interprets as true under it, then we may always conclude that there is a single algorithm which, for any numeral [n], will finitarily certify the formula [F(n)] as true in N under the algorithmically computable interpretation.

Consequently we can show that all the PA axioms—including the Axiom Schema of Finite Induction—interpret finitarily as true in N under the algorithmically computable interpretation of PA, and the PA Rules of Inference preserve such truth finitarily (An12, \S 5.2 Theorem 4).

Thus the algorithmically computable interpretation of PA defines a finitary model of PA from which we may conclude that:

\bullet PA is consistent (An12, \S 5.3, Theorem 6).

\S 6.2 Why we cannot conclude that PA is necessarily \omega-consistent

By the way the above finitary interpretation (b) is defined under Tarski’s inductive definitions (An12, \S 4.3), if a PA-formula [F] interprets as true in the corresponding finitary model of PA, then there is an algorithm that provides a certificate for such truth for [F] in N; whilst if [F] interprets as false in the above finitary model of PA, then there is no algorithm that can provide such a truth certificate for [F] in N (An12, \S 2).

Now, if there is no algorithm that can provide such a truth certificate for the Gödelian formula [R(x)] in N, then we would have by definition first that the PA formula [\neg(\forall x)R(x)] is true in the model, and second by Gödel’s reasoning that the formula [R(n)] is true in the model for any given numeral [n]. Hence Aristotle’s particularisation would not hold in the model.

However, by definition if PA were \omega-consistent then Aristotle’s particularisation must necessarily hold in every model of PA.

It follows that unless we can establish that there is some algorithm which can provide such a truth certificate for the Gödelian formula [R(x)] in N, we cannot make the unqualified assumption—as Gödel appears to do—that a consistent PA is necessarily \omega-consistent.

Conclusion

We have argued that standard arguments for the existence of non-standard models of the first-order Peano Arithmetic PA with domains other than the domain N of the natural numbers should be treated as logically fragile even from within classical logic. In particular we have argued that although Gödel’s argument for the existence of a non-standard model of PA does yield a model of PA other than the classical non-finitary `standard’ model, we cannot conclude from it that the domain is other than the domain N of the natural numbers unless we make the non-constructive—and logically fragile—assumption that a consistent PA is necessarily \omega-consistent.

References

BBJ03 George S. Boolos, John P. Burgess, Richard C. Jeffrey. 2003. Computability and Logic (4th ed). Cambridge University Press, Cambridge.

Be59 Evert W. Beth. 1959. The Foundations of Mathematics. In Studies in Logic and the Foundations of Mathematics. Edited by L. E. J. Brouwer, E. W. Beth, A. Heyting. 1959. North Holland Publishing Company, Amsterdam.

BF58 Paul Bernays and Abraham A. Fraenkel. 1958. Axiomatic Set Theory In Studies in Logic and the Foundations of Mathematics. Edited by L. E. J. Brouwer, E. W. Beth, A. Heyting. 1959. North Holland Publishing Company, Amsterdam.

Bo00 Andrey I. Bovykin. 2000. On order-types of models of arithmetic. Thesis submitted to the University of Birmingham for the degree of Ph.D. in the Faculty of Science, School of Mathematics and Statistics, The University of Birmingham, Edgbaston, Birmingham, B15 2TT, United Kingdom, 13 April 2000.

Br08 L. E. J. Brouwer. 1908. The Unreliability of the Logical Principles. English translation in A. Heyting, Ed. L. E. J. Brouwer: Collected Works 1: Philosophy and Foundations of Mathematics. Amsterdam: North Holland / New York: American Elsevier (1975): pp.107-111.

Co66 Paul J. Cohen. 1966. Set Theory and the Continuum Hypothesis. (Lecture notes given at Harvard University, Spring 1965) W. A. Benjamin, Inc., New York.

Da82 Martin Davis. 1958. Computability and Unsolvability. 1982 ed. Dover Publications, Inc., New York.

EC89 Richard L. Epstein, Walter A. Carnielli. 1989. Computability: Computable Functions, Logic, and the Foundations of Mathematics. Wadsworth & Brooks, California.

Fe92 Solomon Feferman. 1992. What rests on what: The proof-theoretic analysis of mathematics Invited lecture, 15th International Wittgenstein Symposium: Philosophy of Mathematics, held in Kirchberg/Wechsel, Austria, 16-23 August 1992.

Go31 Kurt Gödel. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. Translated by Elliott Mendelson. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York.

HA28 David Hilbert & Wilhelm Ackermann. 1928. Principles of Mathematical Logic. Translation of the second edition of the Grundzüge Der Theoretischen Logik. 1928. Springer, Berlin. 1950. Chelsea Publishing Company, New York.

Hi25 David Hilbert. 1925. On the Infinite. Text of an address delivered in Münster on 4th June 1925 at a meeting of the Westphalian Mathematical Society. In Jean van Heijenoort. 1967.Ed. From Frege to Gödel: A source book in Mathematical Logic, 1878 – 1931. Harvard University Press, Cambridge, Massachusetts.

HP98 Petr Hájek and Pavel Pudlák. 1998. Metamathematics of First-Order Arithmetic. Volume 3 of Perspectives in Mathematical Logic Series, ISSN 0172-6641. Springer-Verlag, Berlin, 1998.

Ka91 Richard Kaye. 1991. Models of Peano Arithmetic. Oxford Logic Guides, 15. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1991.

Ka11 Richard Kaye. 2011. Tennenbaum’s theorem for models of arithmetic. In Set Theory, Arithmetic, and Foundations of Mathematics. Eds. Juliette Kennedy & Roman Kossak. Lecture Notes in Logic (No. 36). pp.66-79. Cambridge University Press, 2011. Cambridge Books Online. http://dx.doi.org/10.1017/CBO9780511910616.005.

Kl52 Stephen Cole Kleene. 1952. Introduction to Metamathematics. North Holland Publishing Company, Amsterdam.

Kn63 G. T. Kneebone. 1963. Mathematical Logic and the Foundations of Mathematics: An Introductory Survey. D. Van Norstrand Company Limited, London.

Ko06 Roman Kossak and James H. Schmerl. 2006. The structure of models of Peano arithmetic. Oxford Logic Guides, 50. Oxford Science Publications. The Clarendon Press, Oxford University Press, Oxford, 2006.

Li64 A. H. Lightstone. 1964. The Axiomatic Method. Prentice Hall, NJ.

Ln08 Laureano Luna. 2008. On non-standard models of Peano Arithmetic. In The Reasoner, Vol(2)2 p7.

Me64 Elliott Mendelson. 1964. Introduction to Mathematical Logic. Van Norstrand, Princeton.

Mu91. Chetan R. Murthy. 1991. An Evaluation Semantics for Classical Proofs. Proceedings of Sixth IEEE Symposium on Logic in Computer Science, pp. 96-109, (also Cornell TR 91-1213), 1991.

Nv64 P. S. Novikov. 1964. Elements of Mathematical Logic. Oliver & Boyd, Edinburgh and London.

Qu63 Willard Van Orman Quine. 1963. Set Theory and its Logic. Harvard University Press, Cambridge, Massachusette.

Rg87 Hartley Rogers Jr. 1987. Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge, Massachusetts.

Ro53 J. Barkley Rosser. 1953. Logic for Mathematicians. McGraw Hill, New York.

Sh67 Joseph R. Shoenfield. 1967. Mathematical Logic. Reprinted 2001. A. K. Peters Ltd., Massachusetts.

Sk28 Thoralf A. Skolem. 1928. On Mathematical Logic. Text of a lecture delivered on 22nd October 1928 before the Norwegian Mathematical Association. In Jean van Heijenoort. 1967. Ed. From Frege to Gödel: A source book in Mathematical Logic, 1878 – 1931 Harvard University Press, Cambridge, Massachusetts.

Sk34 Thoralf A. Skolem. 1934. \”{U}ber die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abz\”{a}hlbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen. Fundamenta Mathematicae, 23, 150-161. English version: Peano’s axioms and models of arithmetic. In Mathematical interpretations of formal systems. North Holland, Amsterdam, 1955, pp.1-14.

Sm92 Raymond M. Smullyan. 1992. Gödel’s Incompleteness Theorems. Oxford University Press, Inc., New York.

Su60 Patrick Suppes. 1960. Axiomatic Set Theory. Van Norstrand, Princeton.

Tu36 Alan Turing. 1936. On computable numbers, with an application to the Entscheidungsproblem In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York. Reprinted from the Proceedings of the London Mathematical Society, ser. 2. vol. 42 (1936-7), pp.230-265; corrections, Ibid, vol 43 (1937) pp. 544-546.

Wa63 Hao Wang. 1963. A survey of Mathematical Logic. North Holland Publishing Company, Amsterdam.

An12 Bhupinder Singh Anand. 2012. Evidence-Based Interpretations of PA. In Proceedings of the Symposium on Computational Philosophy at the AISB/IACAP World Congress 2012-Alan Turing 2012, 2-6 July 2012, University of Birmingham, Birmingham, UK.

An13 … 2013. A suggested mathematical perspective for the EPR argument. Presented on 7’th April at the workshop on `Logical Quantum Structures‘ at UNILOG’2013, 4^{th} World Congress and School on Universal Logic, 29^{th} March 2013 – 7^{th} April 2013, Rio de Janeiro, Brazil.

Notes

Return to 1: By which we mean arguments such as in Ka91 (see pg.1), where the meta-theory is taken to be a set-theory such as ZF or ZFC, and the logical consistency of the meta-theory is not considered relevant to the argumentation.

Return to 2: For purposes of this investigation we may take this to be a first order theory such as the theory S defined in Me64, pp.102-103.

Return to 3: eg. Ka91; Bo00; BBJ03,\ ch.25,\ p.302; Ko06; Ka11.

Return to 4: As argued in Ka91, p.10-11.

Return to 5: Some of the—hitherto unsuspected—consequences of this doctrine are detailed in An12.

Return to 6: An12, Corollary 2; `non-finitary’ because the Axiom Schema of Finite Induction cannot be finitarily verified as true under the standard interpretation of PA with respect to `truth’ as defined by the algorithmically verifiable formulas of PA.

Return to 7: eg., BBJ03, p.155, Lemma 13.3 (Model existence lemma).

Return to 8: cf. The standard non-constructive set-theoretical assignment-by-postulation (S5) of the satisfaction properties (S1) to (S8) in BBJ03, p.153, Lemma 13.1 (Satisfaction properties lemma), which appeals critically to Aristotle’s particularisation.

Return to 9: For purposes of this investigation we may take this to be an interpretation of PA as defined in Me64, p.107.

Return to 10: In his seminal 1931 paper Go31, Kurt Gödel defines, and refers to, the formula corresponding to [R(x)] only by its `Gödel’ number r (op. cit., p.25, Eqn.(12)), and to the formula corresponding to [(\forall x)R(x)] only by its `Gödel’ number 17\ Gen\ r.

Return to 11: By `classical logic’ we mean the standard first-order predicate calculus FOL where we neither deny the Law of the Excludeds Middle, nor assume that the FOL is \omega-consistent (i.e., we do not assume that Aristotle’s particularisation must hold under any interpretation of the logic).

Return to 12: Notation: For the sake of convenience, we shall use square brackets to indicate that the expression enclosed by them is to be treated as denoting a formula of a formal theory, and not as denoting an interpretation.

Return to 13: However, as noted earlier, the Axiom Schema of Finite Induction cannot be finitarily verified as true under the standard interpretation of PA with respect to `truth’ as defined by the algorithmically verifiable formulas of PA .

Return to 14: In this case however, the Axiom Schema of Finite Induction can be finitarily verified as true under the standard interpretation of PA with respect to `truth’ as defined by the algorithmically computable formulas of PA (An12, Theorem 4).

Return to 15: The far reaching—hitherto unsuspected—consequences of this distinction for PA are detailed in An12.

Return to 16: We note that algorithmic computability implies the existence of an algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions, whereas algorithmic verifiability does not imply the existence of an algorithm that can decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions. From the point of view of a finitary mathematical philosophy, the significant difference between the two concepts could be expressed (An13) by saying that we may treat the decimal representation of a real number as corresponding to a physically measurable limit—and not only to a mathematically definable limit—if and only if such representation is definable by an algorithmically computable function.

Return to 17: See Hi25, p.382; HA28, p.48; Sk28, p.515; Go31, p.32.; Kl52, p.169; Ro53, p.90; BF58, p.46; Be59, pp.178 & 218; Su60, p.3; Wa63, p.314-315; Qu63, pp.12-13; Kn63, p.60; Co66, p.4; Me64, pp.45, 47, 52(ii), 214(fn); Nv64, p.92; Li64, p.33; Sh67, p.13; Da82, p.xxv; Rg87, p.xvii; EC89, p.174; Mu91; Sm92, p.18, Ex.3; BBJ03, p.102.

Return to 18: The significance of \omega-consistency for the formal system PA is highlighted inAn12.

Return to 19: In his introduction on p.9 of Go31.

Return to 20: For details see An12.

Return to 21: cf. HP98, p.13, \S 0.29; Me64, p.112, Ex. 2.

Return to 22: For purposes of this investigation we may take this to be the first order predicate calculus K as defined in Me64, p.57.

Return to 23: In the sense indicated by Feferman Fe92.

Return to 24: eg. HP98, p.13, \S 0.29; Ka91, p.11 & p.12, fig.1; BBJ03. p.306, Corollary 25.3; Me64, p.112, Ex. 2.

Return to 25: A possible reason why the Axiom Schema of Finite Induction does not admit non-finitary reasoning into either PA, or into any model of PA, is suggested in \S 6.1 below.

Return to 26: eg. Ln08, p.7; Ka91, pp.10-11, p.74 & p.75, Theorem 6.4.

Return to 27: And as suggested also by standard texts in such cases; eg. BBJ03. p.306, Corollary 25.3; Me64, p.112, Ex. 2.

Return to 28: To place this distinction in perspective, Adrien-Marie Legendre and Carl Friedrich 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, Pafnuty Lvovich 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 using analytic methods independently by Jacques Hadamard and Charles Jean de la Vallée Poussin only in 1896, and using only elementary methods by Atle Selberg and Paul Erdös in 1949.

Return to 29: Ka91, pp.10-11; attributed as essentially Skolem’s argument in Sk34.

Return to 30: In his seminal 1931 paper Go31, Kurt Gödel defines, and refers to, the formula corresponding to [R(x)] only by its `Gödel’ number r (op. cit., p.25, Eqn.(12)), and to the formula corresponding to [(\forall x)R(x)] only by its `Gödel’ number 17\ Gen\ r.

Return to 31: Go31, p.25(1) & p.25(2).

Bhupinder Singh Anand

Advertisements