Texte de l’article qu’a présenté samedi ma collègue Yu Li de l’Université de Picardie, au congrès Unilog 2022 qui se tenait à Chania en Crète.
Gödel’s Incompleteness Theorem revisited
– What is the undecidable problem?
I would rather have questions that can’t be answered than answers that can’t be questioned. – Richard P. Feynman
Yu Li * * Laboratoire MIS, Université de Picardie Jules Verne, 33 rue Saint-Leu, 80090 Amiens, France
- Introduction
In a famous article written in 1931 : « On Formally Undecidable Propositions of Principia Mathematica and Related Systems I » [1], Kurt Gödel claimed to have proved the incompleteness of the system reported in Principia Mathematica (i.e. Peano arithmetic), and by that answered negatively the Entscheidungsproblem (the « decision problem »), a challenge put forward by David Hilbert and Wilhelm Ackermann in 1928.
The Entscheidungsproblem was originally expressed as « Determination of the solvability of a diophantine equation », i.e., the 10th of the 23 problems proposed by Hilbert in his lecture at the International Congress of Mathematicians in Paris in 1900 [2]. Church formulated the Entscheidungsproblem as : « By the Entscheidungsproblem of a system of symbolic logic is here understood the problem to find an effective method by which, given any expression Q in the notation of the system, it can be determined whether or not Q is provable in the system » [3] (Copeland 2004: 45). If it is not possible to find such a method, some propositions would be regarded as « undecidable ». Such a realisation would then establish the incompleteness of Principia Mathematica (PM).
Gödel claimed that the PM system is incomplete, as it is possible to show at least one such undecidable proposition. As a proof, Gödel gave a paradox similar in nature to the Liar’s paradox: a proposition Q asserting about itself that it is unprovable.It is nowadays a commonly accepted view that Gödel proved the incompleteness of the PA system, thus revealing that truth is simply bigger than proof [4].
However, Gödel’s proof of the incompleteness theorem has been continuously challenged since its publication. Let us note that as early as 1936 the logician Chaïm Perelman had drawn the attention to the fact that there wasn’t anything more to Gödel’s demonstration than the generation of a paradox [5]; and the logician Wittgenstein held a similar view [6]. Paul Jorion, a former pupil of Perelman, has claimed in a different context [7] that Gödel’s proof is marred by several other errors, due to his disdain towards the tight or lax persuasive quality of the various steps in his demonstration. Ernst Zermelo stated in a letter to Gödel in 1931 that Gödel’s proof of the existence of undecidable propositions exhibits an « essential gap » [8]. Alan Turing alluded to the errors made by Gödel without mentioning his name and ventured to fix them in his article in 1936, entitled « On Computable Numbers, with an Application to the Entscheidungsproblem » [9].
Gödel’s thesis consists of three chapters: Chapter 1 outlines the main idea of the proof; Chapters 2 and 3 formalise the idea of Chapter 1. In this paper, I focus on Chapter 1, where I examine Gödel’s proof from the perspective of a dynamic process by considering the generation of hypotheses and the reasoning from hypotheses to conclusion as an organic whole, and analyze how Gödel constructed the paradoxical proposition Q.
I try to point out that by confusing the proof of formula with the formula, Gödel’s proof becomes an infinite regress that would have made it impossible to construct any meaningful proposition. Unfortunately, Gödel did not realize this, but introduced improper presuppositions which allow to construct the paradoxical proposition Q. Moreover, he considered Q as an undecidable proposition that exists in PM.
II. The crux of Gödel’s proof
Gödel’s proof is framed by a proof by contradiction [1] (p. 17-19), which assumes that PM is complete, according to him it means that all formulas in PM or their negations are provable; in addition, all formulas in PM can be divided into classes offormulas (class sign) and be enumerated. Gödel then resorts to Cantor’s diagonal argument to construct a paradox similar in nature to the Liar’s paradox: a proposition Q asserting about itself that it is unprovable.
Gödel enumerates accordingly all classes of formulas in PM :
R(1) : [R(1), 1] [R(1), 2] [R(1), 3]… [R(1), n] …
R(2) : [R(2), 1] [R(2), 2] [R(2), 3]… [R(2), n] …
R(3) : [R(3), 1] [R(3), 2] [R(3), 3]… [R(3), n] …
R(4) : [R(4), 1] [R(4), 2] [R(4), 3]… [R(4), n] …
…
R(q) : [R(q), 1] [R(q), 2] [R(q), 3]… [R(q), q] … [R(q), n] …
…
R(n) denotes a class of formulas and [R(n), j] denotes the jth formula of R(n). Gödel takes the formulas on the diagonal: [R(1), 1] [R(2), 2] [R(3), 3] [R(4), 4]… [R(n), n], … derives the negations of them, and defines the formula class K, K = {n|Bew¬[R(n); n]}, while Bew x means that the formula x is provable. K is actually the set of the negations of [R(n), n], K = {¬[R(1), 1],¬[R(2), 2],¬[R(3), 3],¬[R(4), 4]… ¬[R(q), q]，… }.
Gödel considers that the formula class K falls within the sequence of enumerated formula classes, say corresponding to R(q). Thus, on the one hand, [R(q); q] is the formula A on the diagonal, and on the other hand, it is the formula ¬Q in K. There is a paradox: Q = ¬Q, that is, the proposition Q says about itself that it is unprovable!
The gist of our argument below, is that there exist improper presuppositions inGödel’s proof.
III. An analysis of the proof of Gödel’s Incompleteness Theorem
At the beginning of the proof, Gödel unconsciously took proof of formula as formula, which led to an infinite regress; unfortunately, Gödel was not aware of this and introduced an improper presupposition, provable formulas, which led to the paradoxial proposition Q.
- Proof of a formula and formula: confusion of meta-language with object language
We consider a familiar instance :
Illustration 1. Proposition P: √2 is a rational number; its negation ¬P: √2 is not a rational number.
« √2 is not a rational number » (¬P) cannot be proved directly, but there exists the familiar proof by contradiction to prove that « √2 is a rational number » (P), thus ¬P is proved to be true indirectly.
Proof :
Assume that « √2 is a rational number » , then √2 = p/q, where p and q are both positive integers and mutually prime;
p = √2 × q,
p^2 = 2 × q^2,
p^2 is thus even and so is p, since only the even square of an even number is even.
Since p is even, we can regard p as being the double of s : p = 2 x s
Let’s substitute 2s to p in p^2 = 2 × q^2,
(2 x s)^2 = 2 × q^2
4 x s^2 = 2 × q^2
2 x s^2 = q^2
q^2 is thus even and so is q
p and q are even numbers, thus not mutually prime, contradicting the assumption that p and q are mutually prime;
Therefore, the assumption « √2 is a rational number » is invalid, and « √2 is not a rational number » has been proven.
P and ¬P are the formulas about the numbers themselves; while the proof by contradiction is about the provability of P and ¬P.
The relation between the formula and the proof of formula is generally expressed as the relation between the object language and the meta-language. What is about mathematical objects and what is about the provability of formulas are two concepts completely different in nature but intrinsically related.
However, Gödel made such a claim with surprising imprudence: « Similarly, proofs, from a formal point of view, are nothing but finite sequences of formulae (with certain specifiable properties)». In this way, the formula and the proof of formula are confused.
2. A provable formula : infinite regress and improper presumption
As Gödel shows in the end of chapter 1, the provable formula is the key concept in his proof :
« The method of proof just explained can clearly be applied to any formal system that, first, when interpreted as representing a system of notions and propositions, has at its disposal sufficient means of expression to define the notions occurring in the argument above (in particular, the notion ‘provable formula’) and in which, second, every demonstrable formula is true in the interpretation considered. » [1] (p. 19).
What is the meaning of a « provable formula » in PM?
From common sense, a provable formula means that there exists a valid proof of this formula, that is, the provable formula concerns the existence of the proof.
In illustration 1, the proposition « √2 is not a rational number » is a provable formula since there is a valid proof by contradiction for proving that √2 is not a rational number.
Since Gödel treats the proof of formula as the formula, the provable formula in PM means that the proof is provable in PM, that is, the validity of proof can be verified in PM, which leads to an infinite regress. Lewis Carroll’s fable « What the Tortoise Said to Achilles » provides an illustration of infinite regress [10].
Suppose that « P0 is provable », that implies that there exists P1, the proof of P0, and since P1 is treated as a formula, « P1 is provable ». Similarly, « P1 is provable » implies that there exists P2, the proof of formula P1, and « P2 is provable », … and so on, resulting in an infinite regress (Figure 1).
A proof of infinite regress cannot establish any conclusion, so the verification of the validity of proof in PM becomes problematic, then the existence of proof in PM becomes problematic, and the existence of provable formulas in PM becomes also problematic.
Consequently, Gödel cannot talk about the enumeration of classes of formulas, nor about the use of diagonal method to construct the paradoxical proposition Q in PM. In other words, the paradoxical proposition Q cannot be constructed in Gödel’s proof.
But Gödel constructed the paradoxical proposition Q after all, because he presupposed the verification of the validity of proof in PM, which made the provable formula an improper presupposition.
Russell gave a simple example of an improper presupposition in « On Denoting » : « the present king of France is bald. » [11] Whether this proposition is judged to be true or false, it presupposes the existence of the present King of France, who, however, does not exist.
IV. Conclusion
The brief analysis in this paper shows that there are improper presuppositions in Gödel’s proof that enable Gödel to construct the paradoxical proposition Q as evidence for the existence of undecidability problems of PM, and thus to conclude that PM is incomplete.
Therefore, taken as a whole, the actual formulation of Gödel’s incompleteness theorem is :
– PM is incomplete, because there are undecidable problems similar to the liar’s paradox in PM.
Let’s remember what Bertrand Russell once wrote in a letter to Leon Henkin: « I realised, of course, that Gödel’s work is of fundamental importance, but I was puzzled by it. […] If a given set of axioms leads to a contradiction, it is clear that at least one of the axioms must be false » [1] (p. 90)
I hope to initiate a debate :
- Is the paradoxical proposition Q similar to the liar’s paradox an undecidable proposition in PM?
- Is Gödel’s proof valid? If not, what is a valid proof for the incompleteness of PM?
- By revisiting Gödel’s incompleteness theorem today, what would be the insights for us from the perspective of epistemology? What would be the insights for solving the « P vs NP » problem, as well as some underlying theoretical problems of artificial intelligence, from the perspective of algorithm theory?
Reference :
[1] S.G. Shanker (ed.), Gödel’s Theorem in Focus, Croom Helm 1988, https://pdfslide.net/documents/godels-theorem-in-focus-philosophers-in-focus.html
[2] David Hilbert, Mathematical Problems, http://aleph0.clarku.edu/~djoyce/hilbert/problems.html
[3] Brian Jack Copeland, The EssentialTuring, http://www.cse.chalmers.se/~aikmitr/papers/Turing.pdf
[4] Casti, John L. & Werner DePauli, Gödel. A Life of Logic, Cambridge (Mass.) Perseus: 2000
[5] Jean Ladrière, Les limitations internes des formalismes. Etude sur la signification du théorème de Gödel et des théorèmes apparentés dans la théorie des fondements des mathématiques, ed. Nauwelaerts-Gauthier-Villars, Leuven-Paris, 1957, pages 140 à 142
[6] Kreisel, G. (1958). « Wittgenstein’s Remarks on the Foundations of Mathematics ». The British Journal for the Philosophy of Science. IX (34): 135–58. doi:10.1093/bjps/IX.34.135
[7] Paul Jorion, Comment la vérité et la réalité furent inventées (Gallimard 2009)
[8] NOTE Completing the Godel-Zermelo Correspondence, https://www.sciencedirect.com/science/article/pii/0315086085900709
[9] Turing, A.M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2 (published 1937), 42
[10] https://en.wikisource.org/wiki/What_the_Tortoise_Said_to_Achilles
Répondre à un lecteur Annuler la réponse