It is a misconception that an arithmetical statement—such as the one constructed by Kurt Gödel (1931. On formally undecidable propositions of Principia Mathematica and related systems I. In M. Davis. 1965. The Undecidable. p25)—can be intuitively true, and yet not follow formally from the axioms and rules of inference of a first-order Peano Arithmetic, PA.

The misconception arises because PA actually admits two logical entailments, only one of which—Gödelian provability—has, so far, been formally acknowledged.

However, the other—familiar only in its avatar as the intuitive truth of a proposition under PA‘s standard interpretation—does, also, follow formally from the axioms and rules of inference of PA.

Even when this issue is sought to be addressed, the argument is indirect, and this point remains implicit.

For instance, in a critical review of Roger Penrose’s Gödelian argument, Martin Davis (1990. Is Mathematical Insight Algorithmic? Behavioural and Brain Sciences, vol. 13 (1990), pp. 659–660) argues that:

“… There is an algorithm which, given any consistent set of axioms, will output a polynomial equation P = 0 which in fact has no integer solutions, but such that this fact can not be deduced from the given axioms. Here then is the true but unprovable Gödel sentence on which Penrose relies and in a particularly simple form at that. Note that the sentence is provided by an algorithm. If insight is involved, it must be in convincing oneself that the given axioms are indeed consistent, since otherwise we will have no reason to believe that the Gödel sentence is true”.

Note that the first part of Gödel’s argument in Theorem VI of his 1931 paper is that, if PA is consistent, then we can mechanically construct a PA formula—which, syntactically, is of the form [(\forall x)R(x)]—such that:

(i) The formula [(\forall x)R(x)], when viewed as a string of ‘meaningless’ symbols, does not follow mechanically from the axioms of PA as the last of any finite sequence of PA-formulas, each of which is either a PA-axiom, or a consequence of one or more of the formulas preceding it in the sequence, by the mechanical application of the rules of inference of PA;

(ii) For any given numeral [n]—which ‘represents’ the natural number n in PA—the formula [R(n)], when viewed as a string of ‘meaningless’ symbols, does follow mechanically from the axioms of PA as the last of some finite sequence of PA-formulas, each of which is either a PA-axiom, or a consequence of one or more of the formulas preceding it in the sequence, by the mechanical application of the rules of inference of PA.

Now, (i) is the standard definition (due to Gödel) of the meta-assertion:

(iii) The PA-formula [(\forall x)R(x)] is formally unprovable in PA.

However, under standard interpretations of Alfred Tarski’s definitions of the satisfiability and truth of the formulas of a language L under an interpretation M, the L-formula [(\forall x)R(x)] is true in the interpretation M if, and only if, the interpreted relation R^{\prime}(x) is instantiationally satisfied in M (i. e. for any given element of M the interpreted relation can be ‘seen’ to hold in the interpretation).

If we take both L and M as PA (as detailed in ‘Evidence-Based Interpretations of PA‘), and take satisfiability in PA to mean instantiational provability in PA, we arrive at the formal definition of the truth of the PA-formula [(\forall x)R(x)] in PA as:

The PA-formula [(\forall x)R(x)] is formally true in PA if, and only if, the formula [R(x)] is provable in PA whenever we substitute a numeral [n] for the variable [x] in [R(x)].

Hence (ii) is the standard definition (due to Tarski) of the meta-assertion:

(iv) The PA-formula [(\forall x)R(x)] is formally true in PA.

So, by definition, the appropriate interpretation of Gödel’s reasoning (i) and (ii) ought to be:

(v) The PA-formula [(\forall x)R(x)] is formally unprovable in PA, but formally true in PA.

This interpretation also meets Ludwig Wittgenstein’s (Remarks on the Foundations of Mathematics. 1978 edition. MIT Press) requirement that the concept of ‘truth’ in a language must be formally definable, and effectively verifiable, within the language.

As noted by Reuben L. Goodstein (1972. Wittgenstein’s Philosophy of Mathematics. In Ambrose, Alice, and Morris Lazerowitz (eds.), Ludwig Wittgenstein: Philosophy and Language. George Allen and Unwin. pp. 271–86):

“In the realist-formalist controversy in the philosophy of mathematics Wittgenstein’s Remarks offers a solution that is crystal clear and satisfyingly uncompromising. The true propositions of mathematics are true because they are provable in a calculus; they are deductions from axioms by formal rules and are true in virtue of valid applications of the rules of inference and owe nothing to the world outside mathematics.”

However, standard expositions of Gödel’s formal reasoning assert only that:

(vi) The PA-formula [(\forall x)R(x)] is formally unprovable in PA, but intuitively true in the standard interpretation of PA.

They fail to highlight that, actually, (i) and (ii) are both logically entailed by the axioms and rules of inference of PA, and that, classically, the meta-assertion:

(vii) The PA-formula [(\forall x)R(x)] is intuitively true in the standard interpretation of PA.

is both ambiguous and stronger than the meta-assertion:

(viii) The PA-formula [R(x)] is formally true in PA.

The ambiguity surfaces in the presence of the Church-Turing Thesis, for (vii), then, implicitly implies that the arithmetical relation R(x) is algorithmically decidable as always true in the standard interpretation of PA, whereas (viii) does not.

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand

Advertisements