The need to distinguish between languages of adequate expression and those of unambiguous communication

We now highlight the need to distinguish between the essentially different roles and requirements of mathematical languages of rich and adequate expression (such as ZF) vis-à-vis those of effective and unambiguous communication (such as PA)—a distinction that may be significant for determining logical limits on the interpretation of number-theory in set-theory.

A particular limitation is reflected in the argument that PA does not admit a non-standard model of PA [1].

This challenges the impression given by informal arguments in standard texts which suggest that we may trivially infer the existence of non-standard models of PA from standard set-theoretic theorems of first-order logic.

Another limitation is reflected in the argument that although every PA-theorem relativises to a corresponding ZF-theorem that holds over the finite ordinals if ZF is consistent and has a model, we cannot presume that if a ZF-theorem holds over the finite ordinals in a putative model of ZF, then we may conclude that a corresponding PA-theorem holds over the natural numbers similarly.

We show below that such unqualified extension of set-theoretic reasoning to number-theory can be both misleading and invalid.

Why PA cannot admit a set-theoretical model

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

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

where Sy is the `successor’ of y under any sound interpretation of PA.

If we assume that the standard interpretation of PA is sound, then this translates under any unrelativised interpretation of PA as:

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

Further, in every such interpretation 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 unrelativised interpretation of PA is a `successor’. Further, x can only be a `successor’ of a unique element in any such interpretation of PA.

PA and ZF have no common model

Now, since Cantor’s first limit ordinal, \omega, is not the `successor’ of any ordinal in the sense required by the PA axioms, and if there are no infinitely descending sequences of ordinals [2] in a model—if any—of set-theory, PA and Ordinal Arithmetic [3] cannot have a common model, and so we cannot consistently extend PA to ZF simply by the addition of more axioms.

Notes

Return to 1: See this earlier post

Return to 2: Elliott Mendelson. 1964. Introduction to Mathematical Logic. Van Norstrand, Princeton, p.261.

Return to 3: ibid., p.187.

Bhupinder Singh Anand

Advertisements