◄ Index                                                                                                                                      ◄ Main essay

 

Gödel’s Incompleteness Theorems hold vacuously

Bhupinder Singh Anand[1]

(A copy of this essay can be downloaded as a .pdf file from http://arXiv.org/abs/math/0207080.)

(This essay has been completely revised and superceded by a later essay.)

Gödel’s Theorem XI essentially states that, if there is a P-formula [Con(P)] whose standard interpretation is equivalent to the assertion “P is consistent”, then [Con(P)] is not P-provable. We argue that there is no such formula.

1.0 Introduction

Gödel’s First Incompleteness Theorem

Theorem VI of Gödel’s seminal 1931 paper [Go31a], commonly referred to as “Gödel’s First Incompleteness Theorem”, essentially asserts:

Meta-theorem 1: Every omega-consistent formal system P of Arithmetic contains a proposition "[(Ax)R(x, p)]” such that both "[(Ax)R(x, p)]” and "[~(Ax)R(x, p)]” are not P-provable.

In an earlier essay [An02b], we argue, however, that a constructive interpretation of Gödel’s reasoning establishes that any formal system of Arithmetic is omega-inconsistent.

It follows from this that Gödel’s Theorem VI holds vacuously.

Gödel’s Second Incompleteness Theorem

In this essay, we now argue that Theorem XI of Gödel’s paper [Go31a], commonly referred to as “Gödel’s Second Incompleteness Theorem”, also holds vacuously.

1.1 Notation

We generally follow the notation of Gödel [Go31a]. However, we use the notation “(Ax)”, whose standard interpretation is “for all x”, to denote Gödel’s special symbolism for Generalisation.

We use square brackets to indicate that the expression (including square brackets) only denotes the string[2] named within the brackets. Thus, “[(Ax)]” is not part of the formal system P, and would be replaced by Gödel’s special symbolism for Generalisation in order to obtain the actual string in which it occurs.

Following Gödel’s definitions of well-formed formulas[3], we note that juxtaposing the string “[(Ax)]” and the formula[4] “[F(x)]” is the formula “[(Ax)F(x)]”, juxtaposing the symbol “[~]” and the formula “[F]” is the formula “[~F]”, and juxtaposing the symbol “[v]” between the formulas “[F]” and “[G]” is the formula “[FvG]”.

The numerical functions and relations in the following are defined explicitly by Gödel [Go31a]. The formulas are defined implicitly by his reasoning.

1.2 Definitions

We take P to be Gödel’s formal system, and define ([Go31a], Theorem VI, p24-25):

(i)     "Q(x, y)" as Gödel’s recursive numerical relation "~xB(Sb(y 19|Z(y)))".

(ii)    "[R(x, y)]" as a formula that represents "Q(x, y)" in the formal system P.

(The existence of such a formula follows from Gödel’s Theorem VII (1).)

(iii)   "q" as the Gödel-number of the formula "[R(x, y)]" of P.

(iv)   "p" as the Gödel-number of the formula "[(Ax)][R(x, y)]"[5] of P.

(v)    "[p]" as the numeral that represents the natural number "p" in P.

(vi)   "r" as the Gödel-number of the formula "[R(x, p)]" of P.

(vii)  "17Genr" as the Gödel-number of the formula "[(Ax)][R(x, p)]" of P.

(viii) "Neg(17Genr)” as the Gödel-number of the formula "[~][(Ax)][R(x, p)]" of P.

(ix)   "R(x, y)" as the arithmetical interpretation[6] of the formula "[R(x, y)]" of P.

(“R(x, y)” is defined by Gödel’s Theorem VII ([Go31a], p29), where it is proved equivalent to “Q(x, y)”.)

(x)   "Wid(P)" as the number-theoretic assertion "(Ex)(Form(x) & ~Bew(x))".

("Wid(P)" is defined by Gödel ([Go31a], p36) as equivalent to the meta-assertion “P is consistent”.)

(xi)    "[Con(P)]" as the formula that represents " Wid(P)" in the formal system P.

(xii)   "w" as the Gödel-number of the formula "[Con(P)]" of P ([Go31a], p37).

(xiii)   "Con(P)" as the arithmetic interpretation of the formula "[Con(P)]" of P.

1.3 Gödel’s semantic theses in Theorem XI

We begin by noting some semantic theses that underlie Gödel’s proof of, and the conclusions he draws from, his Theorem XI ([Go31a], p36).

Thesis 1:    If a formula [F] is P-provable, then its standard interpretation “F” is a true arithmetic assertion.

Thesis 2:    “P is consistent”, abbreviated  “Wid(P)”, can be meaningfully defined as equivalent to the number-theoretic proposition “(Ex)(Form(x) & ~Bew(x))” ([Go31a], p36, footnote 63).

Thesis 3:    “Wid(P)” is equivalent to some arithmetic assertion "Con(P)", that is the interpretation of a P-formula "[Con(P)]".

1.4 A meta-theorem

We now argue that Gödel’s Thesis 3 is false.

Meta-theorem 2: There is no P-formula that asserts, under interpretation, that P is consistent.

Proof: We assume that Gödel’s Thesis 3 is true, and there is some formula [Con(P)] of the formal system P such that, under the standard interpretation:

"Con(P)" is a true arithmetical relation <==> P is a consistent formal system.

We take this as equivalent to the assertion “[Con(P)] is a P-formula that asserts, under interpretation, that P is consistent”.

(i)      By the definition of consistency[7], [Con(P)] is P-provable if P is inconsistent - since every formula of an inconsistent P is a consequence of the Axioms and Rules of Inference of P[8].

(ii)     Now, if [Con(P)] were P-provable then, by Thesis 1, we would conclude, under the standard interpretation, that:

"Con(P)" is a true arithmetical assertion.

We would further conclude, by Theses 2 and 3, the meta-assertion:

P is a consistent formal system.

However, this would be a false conclusion, since P may be inconsistent.

(iii)    It follows that we cannot conclude from the P-provability of [Con(P)] that P is consistent. Hence we cannot have any formula [Con(P)] such that:

"Con(P)" is a true arithmetical assertion ==> "Wid(P)" is a true number-theoretic assertion.

(iv)    We conclude that Gödel’s Thesis 3 is false, and there is no P-formula [Con(P)] such that:

"Con(P)" is a true arithmetical relation <==> P is a consistent formal system.

1.5 A meta-lemma

From the above we may also conclude that[9]:

Meta-lemma 1: Although a primitive recursive relation, and the interpretation of its formal representation, are always arithmetically equivalent, they are not always formally equivalent.

1.6 Gödel’s Proof of Theorem XI

The question arises: Does Meta-theorem 2 contradict Gödel’s Theorem XI [Go31a]?

Now Gödel’s Theorem XI [Go31a] is essentially the following assertion.

Meta-theorem 3: The consistency of P is not provable in P.

Proof:  Gödel [Go31a] argues that:

(i)      If P is assumed consistent, then the following number-theoretic assertions follow from his Theorems V, VI and his definition of “Wid(P)”.

                  Wid(P) => ~Bew(17Genr)

                  Wid(P) => (Ax)~xB(17Genr)

                  17Genr = Sb(p 19|Z(p)))

                  Wid(P) => (Ax)~xB(Sb(p 19|Z(p)))

                  Q(x, y) <=> ~xB(Sb(y 19|Z(y)))

                  (x)Q(x, y) <=> (Ax)~xB(Sb(y 19|Z(y)))

                  Wid(P) => (Ax)Q(x, p)

(ii)     Assuming that [(Ax)R(x, p)] asserts its own provability[10], Gödel concludes from the above that the instantiation:

wImp(17Genr),

of the recursive number-theoretic relation “xImpy”, is a true numerical assertion.

(iii)    From this, he concludes that:

“[Con(P)] => [(Ax)R(x, p)]” is P-provable.

(iv)    Now, in his Theorem VI, Gödel [Go31a] argues that, if P is assumed consistent, then [(Ax)R(x, p)] is not P-provable. He thus concludes that, if P is assumed consistent, then [Con(P)] too is not P-provable.

(v)     Implicitly assuming that Thesis 3 is true, and so:

"Con(P)" is a true arithmetical assertion <==> "Wid(P)" is a true number-theoretic assertion,

Gödel further concludes that (iv) is equivalent to asserting that the consistency of P is not provable in P.

1.7 Conclusion

However, since, by Meta-theorem 2, Gödel’s Thesis 3 is an invalid implicit assumption, we conclude that Gödel’s Theorem XI is essentially the vacuous meta-assertion:

Meta-theorem 4: If there is a P-formula [Con(P)] whose standard interpretation is equivalent to the assertion “P is consistent”, then [Con(P)] is not P-provable.

References

 

[An01]     Anand, Bhupinder Singh. 2001. Beyond Gödel: Simply constructive systems of first order Peano’s Arithmetic that do not yield undecidable propositions by Gödel’s reasoning. (Web essay).

 

<Web page:  http://alixcomsi.com/Constructivity_abstracts.htm>

 

[An02a]   Anand, Bhupinder Singh. 2002. Reviewing Gödel's and Rosser's non-formal meta-reasoning of “undecidability”. (Web essay).

 

<Web page: http://www.alixcomsi.com/Constructivity_consider.htm>

 

[An02b]   Anand, Bhupinder Singh. 2002. Omega-inconsistency in Gödel's formal system: a constructive proof of the Entscheidungsproblem. (Web essay).

 

<Web page:  http://alixcomsi.com/CTG_00.htm >

 

[Go31a]   Gödel, Kurt. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York.

 

[Go31b]   Gödel, Kurt. 1931. On formally undecidable propositions of Principia Mathematica and related systems I.

 

<Web version: http://www.ddc.net/ygg/etext/godel/godel3.htm>

 

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

 

 (Acknowledgement: My thanks to Professor Karlis Podnieks for suggesting the need for a comparison between Gödel’s approach and that of the arguments underlying this essay.)

 

(Updated: Wednesday 2^nd June 2004 11:02:14 PM IST by re@alixcomsi.com)

◄ Index           ▲ Top of page