CHAPTER 20

INCOMPLETENESS

20.1. It is well known that Gödel's Uber formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (henceforth [G]) raised hard criticisms. Yet, as far as I know, all of them were affected by an intrinsic weakness: proposing general considerations without tackling the formal procedure. In my opinion this is the reason why Goedel himself neglected such criticisms as lucubrations of no theoretical interest. And really (Wittgenstein) contesting from a philosophical viewpoint the intelligibility of a formula strictly inferred through a constructive procedure or (Perelman) reasoning on the propaedeutically argumentative explanation of such a procedure are intrinsically weak approaches. I agree with their intuitions, I too think that Gödel's undecidable formula 17Gen r is not a proper formula, yet I avow that his First Theorem can be unquestionably confuted only by the exhibition of some formal mistake.

This chapter achieves such a result.

20.1.1. Since I maintain Italic type in compliance with Gödel's convention ([G] p. 179: Diejenigen Klassen.....in Kursivschrift), for the sake of clearness, the quotations are printed in Franklin Gothic. In order to help collations, sometimes reference is also made to van Heijenoort's English translation (henceforth [H]). Anyhow, as far as reasonable, Gödel's original terminology is adopted; so while "Satzformel" ("sentential formula" in [H]) means a free-variable-free formula "Klassenzeichen" ("class sign" in [H]) means a formula where exactly one free variable occurs, "Zahlzeichen" ("numeral" in [H]) means an expression formed by a certain number (also null) of "f" concatenated to a final "0". Finally, for the sake of typographical simplicity, some inconsequential modifications are brought to Gödel's notation for the substitution operator.

20.2. A crucial role is played by the notion of proper formulae ([G] p.174 sinvolle Formeln; [H] p.597 meaningful formulas). The basic difference between proper and improper formulae is clear: while the oppositive negation of an untrue but proper (a false) formula must be true, the oppositive negation of an improper (then an untrue) formula is again an improper formula. For instance, since

Odd( 4 )

is untrue but proper

Even( 4 )

is true; on the other hand, since

Odd(π)

is untrue and improper, also

Even(π)

is untrue and improper.

20.2.1. My central claim can be informally epitomized as follows: a formula stating its own (un)provableness is improper because it violates the dialinguistic orders.

Indeed my claim seems to be immediately contradicted by two pieces of evidence, and precisely

- the formal procedure through which Goedel achieves his undecidable formula is constructive

- many other formal procedures leading to a formula stating its own (un)provability have been proposed.

Nevertheless a more severe analysis lets us understand that both pieces of evidence are misleading.

20.2.2. At first sight, even the distinction between proper and improper formulae may appear of no moment as for the matter under scrutiny; in fact, since natural numbers are the exclusive members of the arithmetized universe Goedel speaks of, all the notions he defines concern strictly natural numbers. In order to prove that such a conclusion too is misleading, I start reasoning before any arithmetization, that is with reference to what I call "standard ambience" (symbolically, "SA"). Of course I follow Gödel's formal system P which results from the insertion of Peano's axioms within the logic of Principia Mathematica ([G] p.176; P ist im wesentlichen das System...).

20.3. Let L be the language for P and ML its metalanguage. Since defined symbols ([G] p.174, footnote 6) are only abbreviations, a P-expression is a concatenation of primitive symbols belonging to L; I call "Peanic" such expressions. Analogously I call "syntactic" the expressions formed by a concatenation of ML-symbols, that is the expressions which, in their standard interpretation, speak of Peanic expressions.

I emphasize that all the following new lines introducing symbolic expressions have a metalinguistic import.

20.3.1. Although Goedel introduces the substitution operator in a wider context ([G] p.177: Unter Subst ...), I mainly focus on substitutions where the initial formula is a Klassenzeichen, and the free variable to substitute is replaced by a constant so that the final formula is a Satzformel.

20.3.2. The properness of a Klassenzeichen is implicitly presupposed by the domain of its free variable. Variables are signs, therefore necessary and sufficient condition for the properness of the Satzformel which we obtain by a substitution is unquestionable: the substitutor must name a value of the substituted variable, that is it must name a member of the domain the same variable ranges over. So, once assumed

(20.i)      x                 y                 z

as Peanic variables whose values are natural numbers, the names of the natural numbers, that is the Zahlzeichen (the numerals) are their proper substitutors. Analogously, once assumed

(20.ii)      g                 v                 n

as syntactic variables ranging over Peanic expressions (sentences, terms and so on), their proper substitutors are the metalinguistic expressions which name Peanic expressions of the right syntactical status.

20.4. The generic substitution operated on a Peanic Klassenzeichen is described by a ML-expression like

(20.iii)      Subst(g; v/n)

where

- the initial formula g (without inverted commas, I am not speaking of the syntactic variable in boldface, I am using it to speak of the generic object formula the same syntactic variable stands for, as for instance "Prim(y)"), is precisely a Peanic Klassenzeichen

- the substituendum v (without inverted commas ...) is the free variable occurring in g ("y", in the previous instance), that is a variable ranging over natural numbers

- the substitutor n (...) is the numeral naming a value of the free variable, that is a number (for instance "ffff0").

Then

(20.iv)       Subst("Prim(y)"; "y"/"ffff0")

is a proper ML-description of

(20.v)      Prim(ffff0)

and (20.v) is a (proper and false) Peanic Satzformel stating that 4 is a prime number.

Precisely because (20.v) is a proper formula,

(20.vi)      Prim ("ffff0")

is an improper one. Reciprocally, once "Num" is assumed to symbolize the syntactic predicate "to be a numeral",

Num("ffff0")

is a proper formula and

(20.vii)      Num (ffff0)

is an improper one. And precisely because the improperness of (20.vi) and (20.vii) follows from a violation of the dialinguistic orders, I say that both formulae are affected by a projective improperness.

20.5. Analogously to (20.iii), the generic substitution operated on a syntactic Klassenzeichen speaking of object formulae is described by a MML-expression like

(20.viii)      Subst(G; V/E)

where

- the initial formula G (that is, for instance, "ProvP(y)", once "ProvP" is assumed to symbolize the predicate of provableness in P), is a syntactic Klassenzeichen

- the substituendum V ("y" in the previous instance) is its syntactic free variable whose domain is formed by P–formulae

- the substitutor E (for instance "Prim(ffff0)") is the name of an "y"-value, that is the name of a P–formula.

Then, analogously to (20.iv),

(20.ix)       Subst("ProvP(y)"; "y"/""Prim(ffff0)"")

is a proper MML-description of

(20.x)      ProvP ("Prim(ffff0)")

and (20.x), though false, is a proper syntactic Satzformel stating that the object Peanic Satzformel (20.v) is provable in P; of course (20.x) is false because actually the opposite of (20.v), that is

~(Prim (ffff0))

is provable in P, that is because the same (20.v) is refutable in P.

20,5.1. The absolute necessity to respect the dialinguistic orders is punctually satisfied by the above formulae. So, since (ix) is a MML-expression, both ML-espressions occur within a single pair of quotation marks and the only L-expression occurs within a double pair of quotation marks.

Let me insist. For instance (20.x) is a proper particularization of the proper syntactic Klassenzeichen

(20.xi)      ProvP (y)

since (20.x), although false, is a proper metalinguistic formula stating that a well specified object Peanic formula ("Prim(ffff0)", I mean) is provable in P. On the contrary

(20.xii)      ProvP(Prim(ffff0))

is a projectively improper particularization of (20.xi), since in (20.xii) the object formula is used, not mentioned.

On the opposite side, also

(20.xiii)      ProvP ("ProvP (y)")

is a projectively improper formula, since what can be proved (or refuted) in P is a Peanic formula, while (20.xi), far from being a Peanic formula, is a syntactic one.

20.6. A point to emphasize is that an improper object formula can be exactly described through a proper use of the substitution operator. For instance

(20.xiv)      Subst("ProvP(y)"; "y"/"ProvP(y)")

is a perfectly meaningful description of (20.xiii); nevertheless the same (20.xiii) is improper.

20.6.1. We can even distinguish three (progressively less evident) levels of improperness corresponding respectively to the violation

- of some formation rule, as for instance in "Prim(00f)"

- of some syntactical rule, as for instance in "ProvP("ffff0")"

- of some projective rule (as for instance in "ProvP("ProvP(y)")").

20.7. From now on I analyse the situation determined by the arithmetization of the standard ambience SA, and I call "arithmetized ambience" (symbolically, "AA") this new situation. I remind the reader that the Italic type is used to mean the isomorphic arithmetic images of the corresponding standard notions. Of course I agree ([G] p.174: Fur metamatematische Betrachtungen...) that ([H] p. 597) for metamathematical considerations it does not matter what objects are chosen as primitive signs. Yet I underline that Gödel's peculiar choice (numbers as signs) is a very risky one since an autoreferentiality (though theoretically unexceptionable) increases exponentially the possibility of confusing different dialinguistic orders: our mind is not accustomed to thinking of numbers as signs.

Anyhow (and obviously) arithmetization cannot be a safe-conduct to incoherence, the fact that as soon as we choose natural numbers as signs ([G] p.178: Wir ordnen...; [H] p.601 We now assign...), metamathematics becomes L-accessible, this fact does not at all mean that the fundamental distinction concerning the dialinguistic orders can be neglected. In AA we only treat expressions speaking of numbers because, in addition to the previous net of Peanic notions (predicates, relations), numbers are now linked also by a new and radically distinct network of (Gödelian) notions which are the isomorphic images of the syntactic notions we deal with in SA. And actually this distinction is documentable even under a strictly formal approach: it is sufficient to ascertain whether the notion under scrutiny depends on the arithmetization. For instance, among Gödel's 46 definitions,

Prim(x)

(([G] p.182; [H] p.603; Def.2) is a Peanic notion since a number is or is not prime quite independently of any arithmetization; on the contrary

E(x)

(Def.11)) is a Gödelian notion since it does depend on the arithmetization (the product of 211, 317 and 513 is the arithmetic image of "(x)" only because 11 has been co-ordinated (assigned) to "(" et cetera).

In other words: Peano's axioms are sufficient to ascertain whether a certain number is a cube, but surely they are not sufficient to ascertain whether a number is a formula because in order to ascertain whether a number is a formula the resort to some arithmetization becomes a necessary step.

In other other-words. Although both of them concern numbers, the elusive but essential difference between Peanic and Gödelian notions is a difference of dialinguistic order because any arithmetization gives the numbers a double role: referents and signs.

20.8. Now I prove that

(20.xv)      Sb(p; 19/Z(p))

is the proper description of an improper formula.

First of all I prove that, while being a numeral is a sufficient condition to being the proper substitutor of a variable ("variable" not in italic) whose values are numbers, being a numeral is not a sufficient condition to be the proper substitutor of a variable (though its values, obviously, are numbers). In fact, since

- a precise and computable Gödelian is co-ordinated to any (even improper) L-expression (for instance, the product of 21, 31 and 53 is the Gödelian for "00f"); therefore the distinction between proper and improper Gödelians is unquestionable;

- every Gödelian n (def.17) has a numeral Z(n) (for instance the product of the first 750 prime numbers raised to the cube and of the 751st prime number is the numeral for the Gödelian image of "00f";

being a numeral is not a sufficient condition to be the proper substitutor of a variable.

Yet, as Gödel's proof does not involve improper Gödelians (that is, with reference to §20.6: it does not involve any improperness of first level), once their existence is recognized, we can neglect them.

Now I prove that even being the numeral for a proper Gödelian (that is for the image of a proper L-expression) is not a sufficient condition to be the proper substitutor of a variable. In fact, for instance, if the values of the variable to substitute are formulae, the numeral for a numeral is a manifestly improper substitutor, just as "ffff0" is an improper substitutor of the free variable in (20.xi) (what does it mean to state that the number 4 is provable in P?). Yet, as Gödel's proof does not involve this second level of improperness, we can neglect it, too.

Finally (and here is the crucial passage) I prove that even being the numeral for the Gödelian image of a formula is not a sufficient condition to be the proper substitutor of a variable whose values are formulae. In fact if the values of the variable are object formulae and the substitutor is the numeral for the Gödelian image of a syntactic formula, the general and fundamental condition is violated according to which, in order to obtain a proper Satzformel from a proper Klassenzeichen, the substitutor of the free variable must name a value of the same variable. This is just the case of (20.xv), since by definition ([G] p.188, formula (9)) p is a Klassenzeichen whose range is constituted by object formulae while Z(p), consequently, is not the numeral for an object formula.

Indeed, though (20.xv) is a number we can actually compute, its computability is far from entailing its properness. Exactly as (20.xiv) is the proper description of the improper (20.xiii), (20.xv) is the proper description of an improper Satzformel.

With reference to §20.6.1, we see that computable Gödelians correspond to every level of improperness.

20.8.1. The immediate intuitive understanding of this argument is restrained by the fact that usually we reason about numbers in SA, where actually being a numeral is a sufficient condition to be the proper substitutor of a numerical variable. But as soon as numbers are assumed as signs, we charge them with further (syntactical, so written) duties. Therefore, the properness of a Goedelian obtained by substitution can be assured only by the fact that the substitutor is the numeral for a Goedelian of the right sortal range, that is for a value of the substituted variable.

20.9. Goedel ([G], p.189: ... die (effektiv aufweisbare) Satzformel 17Gen r....; [H] p. 609 ...the sentential formula...) claims that

(20.xvi)      17Gen r

is a (proper) Satzformel; therefore, ([G] p.188, formula (13) , [H] p. 608) since (20.xvi) and (20.xv) are equivalent, he claims that (20.xv) is a (proper) Satzformel. But in order to prove his claim it is not at all sufficient to remark (ibidem) that p is a Klassenzeichen with the free variable 19) since his remark, at the most, could only succeed in assuring that no free variable occurs in (20.xv), where the free variable has been substituted by a numeral. First of all Goedel should prove that Z(p) is a proper substitutor of 19, then he should prove that Z(p) is the numeral of a formula (which is true) and, above all, he should prove that Z(p) is the numeral of a formula belonging to the domain of 19 (which is untrue). Substituting in the Klassenzeichen p the free variable 19, whose range is constituted by object formulae, with the numeral of a formula (as p actually is) which refers to the unprovability of an object formula means falling into the same projective mistake affecting (20.xiii): therefore the final formula cannot be a proper Satzformel.

As far as I understand, Goedel is not even touched by any suspicion about the properness of his undecidable formula precisely because, missing the distinction between Peanic and syntactic formulae, he tacitly presupposes that substituting a variable ranging over formulae with a numeral for a formula cannot but transform the initial sinvolle Klassenzeichen into a sinvolle Satzformel. And just this presupposition is the unwitting trick by which eighty years of close investigations have been misled, particularly because such a presupposition was seemingly legitimated by the formal mistake focused in §11 below.

20.9.1. Let me resume. To claim at the same time that

- 19 is the free variable. occurring in the class sign p;

- 19 can be properly substituted by the numeral for p

is to fall into a (projective) contradiction because p cannot be a value of its own free variable.

20.9.2. The proof that, if (20.xvi) were provable, then

(20.xvii)      Neg(17Gen r)

would be provable, too, does not represent a surprising result ([G] p.176: überraschenden Resultaten; [H] p. 599) but the obvious consequence of the projective improperness affecting (20.xv), and therefore (20.xvi). Ex absurdo quodlibet. Aphoristically: what Goedel actually proves is not the incompleteness of the system, but the improperness of his undecidable formula.

20.9.2.1. In order to help the intuitive understanding, the situation can be visualized through two concentric circles where opposite formulae are represented by a pair of points corresponding in a polar symmetry. So if we agree that the circular crown A represents the improper formulae, the interior circle B (split diametrically in B1 and B2 respectively for provable and refutable formulae) represents the proper ones. It would be an astonishing result to prove that if the point representing 17Gen r should fall into B1, then its symmetric could not fall into B2. But as soon as we realize that, on the contrary, the point representing 17Gen r falls into A, the fact that its symmetric cannot fall into B2 is an obviousness, since it too falls into A. So the puzzle vanishes.

20.10. The just ascertained improperness of 17Gen r bears immediately, so to say, an intriguing meta-puzzle: how can an improper formula intrude into a formal system whose axioms are proper and whose transformation rules are properness-conservative? The detailed answer, focusing the formal mistake through which such an intrusion is accomplished, represents the best validation of the above analysis. Here it is.

20.10.1. First of all I remind the reader (§15.14) that the choice of variables must respect two fundamental rules:

R1: not to choose the same variable for non-necessarily-identical numbers

R2: not to choose different variables for necessarily identical numbers.

The formal mistake we are pursuing depends exactly on a violation of R1 (and a violation of the worst kind, since the same variable is chosen for necessarily-non-identical numbers).

20.10.2. In SA (that is: before any arithmetization), the Theorem of Representability STR (in two words: every recursive relation is representable) can be formulated (with reference to a dyadic arithmetic relation R) by

(20.xviii)       Rec(R) (Sv,w ((R(x,y)ProvP (Subst(Sv,w; v/nu(x) w/nu(y))&

& ~ R(x,y)ProvP (Subst(~Sv,w; v/nu(x) w/nu(y)))

where

- "Rec" is the predicate of recursivity

- Sv,w is a binary sign of relation with the free variables v and w (without inverted commas, analogously to (iii) I am not speaking of the syntactic variables in boldface, I am using them to speak of two generic object variables as for instance "u" and "z")

- nu(x) and nu(y) are the numerals for the numbers x and y.

Since I peacefully admit both the recursivity of the relations involved in Gödel's proof and the existence of the respective sign of relation, and since the extrapolation from R(x,y) to ~ R(x,y) is immediate, I simplify (20.xviii) in

(20.xix)      R(x,y)ProvP (Subst(Sv,w; v/nu(x) w/nu(y))

remarking that while the protasis of (20.xix) is formulated in L (it speaks of numbers) the apodosis is formulated in ML (it speaks of L-expressions). Just to mean that protasis and apodosis belong to different dialinguistic orders I say that STR is a projective theorem.

20.10.3. As long as we are in SA, the symbols occurring in the protasis of (20.xix) belong to L and the symbols occurring in its apodosis belong to ML; therefore any risk is banned of violating R1 through some abusive identification between the variables occurring in the protasis and the variables occurring in the apodosis. Of course avoiding choices which might be sources of superficial misunderstandings would be a welcome agreement; so, since in (20.xix) x and y are already the generic numbers we are speaking of in the protasis and whose numerals we are speaking of in the apodosis, choosing just "x" and"y" as values of v and w would be a rather spiteful decision. Nevertheless, strictly, such a decision too is formally unobjectionable:

(20.xx)       R(x,y) ProvP(Subst(S"x","y"; "x"/nu(x) "y"/nu(y))

is a formally correct formulation because no abusive identification is possible between x or y (which are numbers) and "x" or "y" (which are symbols). In (20.xx) the only connection between protasis and apodosis continues consisting in the fact that the number of "f" concatenated in the numeral substitutor of the free variable "x" is just x and that the number of "f" concatenated in the numeral substitutor of the free variable "y" is just y.

Yet arithmetization changes radically the context.

20.11. Gödel's Theorem V ([G] p.186: Satz V: Zu jeder rekursiven relation...; [H] p.607: Theorem V. For every recursive...) is the arithmetization (ATR) of STR. So, since in ATR both protases and apodoses speak of numbers, all the variables Theorem V deals range over numbers.

This simple consideration shows that, with all its apparent plausibility, what Goedel claims in his footnote 38 (ibidem) is abusive. The choice of variables is not at all arbitrary; in fact the risk does exist of violating R1 through some formally illegitimate identification among the variables of the protasis and the variables of the apodosis. In his formulae (3) e (4), that is, shortly, in

R(x1, x2) Sb(r; u1/Z(x1) u2/Z(x2))

such a risk is implicitly avoided by the resort to different symbols ("x" and "u") and by the tacit presupposition that none of the "x"s occurring in the protasis identifies itself with some of the "u"s occurring in the apodosis. Yet such a risk is not at all avoided in the application of Theorem V to his formulae (9) and (10) ([G] p.188; [H] p.608) where the same 19 which in the protases occurs as the free variable of the formula y, in the apodoses occurs as a variable whose range is constituted by formulae like y. Therefore (9) and (10) are improper exactly as an SA formula where the same variable stands for an object formula in its first occurrence and for a syntactic formula in its second occurrence. Here is the formal mistake no authentic orthodoxy can accept; a (projective) mistake whose consequence is exactly the (projective) improperness of (20.xv). In fact should the illegitimate choice of the same free variable 19 not be used to carry out the proof, such a choice could be forgiven as a notational flaw of no theoretical moment. But this is not the case. In order to obtain (ibidem)

Sb(p; 19/Z(p)) = .... = 17Genr                 (13)

Goedel applies (11) and (12) to the apodoses of (9) and (10), therefore he assumes that the range of the free variable 19 is constituted by formulae like y, but in order to obtain (15) and (16) he uses (13) for a substitution in the protases, thus he activates the projectively illegitimate identification the improperness of his undecidable formula is born by.

20.11.1. Another (and very concise) way to realize the improperness of (9) and (10) is to remark that Z(y) cannot be at the same time the proper substitutor of the free variable 19 occurring in the protases and of the free variable 19 occurring in the apodoses , since the two ranges are separated by a dialinguistic order.

Here is the rabbit Goedel pulls out of a hat, contrary to what Humphries (1979, p.539) thinks.

20.12. The only formally detailed proof I know is Goedel's original one; yet I had the opportunity to read many other concise attempts at proving his First Theorem. Indeed to confute them is a quite superfluous task, since, in spite of any arithmetization, the documented projective improperness of a formula stating its own (un)provability implies that some incorrect passage hides in every procedure leading to an analogous formula. And in effect an equivalent projective mistake can be found out in all of them. Let me analyse briefly two celebrated attempts.

20.12.1. The incorrect passage disqualifying Shoenfield's argument concerns the proof of Church's theorem (Shoenfield 1967 §6.8). The assumption of natural numbers as signs entails the already discussed consequence that not every numeral can be the proper subtitutor of a variable. Then, since a necessary condition for the properness of

P(a,b)

is that a and b belong to two consecutive dialinguistic orders, (more specifically: if b is a syntactic formula, a must be a Peanic one) the definition

Q(a) P(a,a)

is improper: (~)TeorT is not recursive simply because it is improper.

20.12.2. Smullyan's diagonalization (Smullyan 1993, Chapter 1) is the glorification of improperness. He argues under the presupposition that diagonalization is an always legitimate operation:

H(h) is the diagonalization of H and H(h) is a sentence

he explicitly claims (p.50). Probably the responsibility of his untenable presupposition depends also on the predicate

(20.xxi)      is read by John

he repeatedly proposes as a privileged example. But (20.xxi) is a highly particular predicate (a dialinguistically polivalent predicate, so to say) since any expression, quite independently of any consideration about its dialinguistic order, can be read by John. In other words: since any text belongs to the sortal range of (20.xxi), its assumption as the subject of such a predicate yields a proper and properly diagonalizable sentence. But of course many predicates do not yield properly diagonalizable sentences; for instance while

Prim (x)

is proper,

(20.xxii)      Prim ("Prim (x)")

is improper. And to claim that such an improperness is legitimated by some arithmetization means to contradict the same isomorphism because, in this case, we could exhibit some improper formula whose isomorphic image is a proper formula. Therefore, first of all, Smullyan ought to prove that (20.xi) is properly diagonalizable, which is not, since (20.xiii) is not less improper than (20.xxii).

20.12.2.1. A pedantry. Indeed a difference does exist between the improperness of (20.xiii) and of (20.xxii); in fact, contrary to "Prim", "Prov", once mutilated of its reference to the system (P, in the case), is extrapolable to any dialinguistic order (provided the axiomatization of the corresponding system). Yet such a difference is theoretically negligible because, obviously, speaking of provability without specifying the axiomatic system of reference is an elliptic formulation totally inadmissible in a formal procedure.

20.13. Both the Liar and 17Gen r hide the same incoherence: the identification of an object sentence with the metalinguistic sentence attributing a certain predicate (of falsity in the Liar, of refutability in the present case) to the same object sentence. Arithmetization is exactly the attempt to avoid this logically unavoidable hiatus.

20.14. Of course the fall of Gödel's First Incompleteness Theorem entails the fall of the consequences he draws ([G] p.191: Wir zichen nun aus Satz VI weitere Folgerungen...). The general consideration (and the formal mistake affecting Schoenfinkel's reduction is another symptomatic example) is that formalism is a powerful weapon rather hard to deal with. Particularly because, until the logical mistake is not recognized, we tend to venerate an improper but formally inferred statement as a supremely profound achievement. A tendency not so strange as it may appear: in fact improperness disconcerts our mind, and such a disconcertment may be interpreted as the extreme difficulty in understanding some transcendent truth.