Gödel’s Contradiction

Page last updated 04 Dec 2024

In 1931 Kurt Gödel, a proponent of intelligent design (see Statements by Kurt Gödel) published a paper (Footnote: The proof is commonly referred to as Gödel’s proof of incompleteness, you can see an English translation of it at English translation of Gödel’s incompleteness paper. For some background on it, see Gödel’s proof of incompleteness.) that has been hailed as a masterpiece of intellectual ability. (Footnote: The mathematician Von Neumann said in 1951 that Gödel’s proof was:
“Kurt Gödel’s achievement in modern logic is singular and monumental - indeed it is more than a monument, it is a landmark which will remain visible far in space and time.”) However, Gödel’s proof of incompleteness leads directly to a contradiction. The cause of the contradiction is easily found - at a crucial point in the proof Gödel simply assumes a crucial proposition to be correct - and which is actually incorrect since it confuses two different levels of language, see Gödel’s Proposition V.

The contradiction inherent in Gödel’s proof can be easily demonstrated, as follows: (Footnote: For those with some familiarity with Gödel’s paper, see the Appendix below for a more detailed account.)

Kurt Gödel

The proof refers to a specific formal system P, and states that if the system is consistent, (Footnote: A consistent system is a system that cannot result in a contradiction.) then there is a proposition in that system that is not provable by that system, and neither is its negation, i.e: that it is incomplete.

However, the proof also supposedly proves that that proposition is correct (commonly referred to as showing that it is “true”).

Having made a proof for one specific formal system, the proof then proceeds to state that the same proof process can be applied to every formal system that includes a sufficient amount of number theory, so that, given any consistent formal system that includes a sufficient amount of number theory, the proof states there always is a proposition in that system that is not provable by that system. And, as above, the proof supposedly also proves, outside of the formal system, that that proposition is correct.

Since the proof that the proposition is correct - but unprovable in the formal system - is made outside of the formal system, that means that, in order to achieve this, the proof must be doing something very special that no formal system can do. You might expect that logicians and mathematicians would have examined the proof to unearth what this magic ingredient is, but you can search high and low, but no-one has ever found the magic ingredient. And you might expect that this should make people wonder if there is any such magic ingredient, and scrutinize the proof very carefully to see if there might actually be an error in the proof. But no, logicians and mathematicians instead prefer to turn a blind eye to this conundrum.

Now, if the proof for a specific formal system is itself logically valid, then it must be possible to formulate that proof within another fully formal system which itself has a fixed definite set of rules of inference and axioms. (Footnote: The formal system that is being examined necessarily has such a clearly defined set of rules and axioms. If this was not the case then that system would not be clearly defined, and we could not rely on any statements produced by it.)

We can call such a formal system S. Given the system S we can produce another formal system S* simply by replacing every symbol used in the system S by a different symbol, where the systems S and S* have no symbols in common.

According to the claim made by Gödel, the formal system S, provided it is consistent, can prove:

“If the system S* is consistent, then there is a proposition A* in that system S* that is not provable by that system S*.”

but that proposition A* is provable by the system S, which is a meta-system to the formal system S*. (Footnote: I’ve given this section a slight rewriting, since some people think that can get around the argument by quibbling about what system the conditional “if … is consistent” is being expressed in. The condition that a meta-system (such as S here) is consistent is simply the overall general assumption that one makes regarding any mathematical system - that the system you are using to formulate your mathematical proofs is consistent. The condition regarding the sub-system “if the sub-system … is consistent” (as for S* here) simply replicates the expression of that condition in the same way that it is present in Gödel’s proof.)

Since the systems S and S* are exactly the same systems, but simply have different symbols, then in precisely the same way, if the proof were correct, one could also say that the formal system S*, provided it is consistent, can prove:

“If the system S is consistent, then there is a proposition A in that system S that is not provable by that system S.”

but that proposition A is provable by the system S*, which is a meta-system to the formal system S.

And here’s the contradiction. That proposition A and the proposition A* are precisely the same proposition in both the system S and the system S* - it is only the symbols used that are different, but the logic leading to a proof of the propositions A and A* must proceed in exactly the same way for both the system S and S*. So that if the proof were correct and if the systems S and S* are both consistent, then we would have the result that the system S proves that there is a proposition A* which is not provable in the system S*, but is provable in the system S, but the very same proposition A (which is exactly the same as the proposition A*, but with different symbols) is not provable in the system S, but is provable in the system S*.

This contradiction shows that any such formal system S that “proves” such a result is inconsistent. It follows that Gödel’s proof is not consistent - since the formal system S (and the formal system S*) is simply a system in which Gödel’s proof is fully formalized. The above is an instance of how a formal system could not be a meta-language to itself unless it is inconsistent.

Given this indication that Gödel’s proof is not consistent, then the obvious thing to do next would appear to be to find where and why Gödel’s proof is flawed. The webpages Gödel’s Incompleteness Theorem and A simplified explanation of Gödel’s proof give an outline of the flaw in the proof and a full demonstration is given in the paper The Fundamental Flaw in Gödel’s Proof of his Incompleteness Theorem - I have now added a section to the paper that gives a brief summary of the underlying illogical assumption that the proof relies on, so that the reader can see in a few pages that the proof is flawed. See also Gödel’s 1934 Undecidability lectures, which, although by then Gödel had three years to reflect on his methods of proof, rather ironically allow a much simpler demonstration of the inherent confusion of language that is involved.

It might be noted that Gödel did not actually provide a proof of the crucial step in his incompleteness proof, he simply assumed it to be correct, and amazingly, other mathematicians and logicians all suspend their critical faculties and accept this mathematical no-no. Intuition should never be a substitute for a rigorous proof. And this isn’t the only case of Gödel making intuitive leaps that later turned out to be incorrect, see also Gödel’s Intuitive Error No.2 where it is shown that Gödel’s intuitive conclusion turned out to be precisely the opposite to the correct conclusion.

And it is remarkable how mathematicians and logicians try to avoid any mention of this fact when they talk about Gödel’s proof, for example see David Pierce on Gödel’s incompleteness proof.

We can also note that there have been various attempts to gloss over the contradiction inherent in Gödel’s proof, but these can be shown to be not based on any logical argument, see for example True but unprovable? and Man versus Machine.

And then there are people who attempt to circumvent the contradiction by coming up with weird arguments that only succeed in betraying their lack of in-depth knowledge of the subject, see for example the appendix below regarding A Misunderstanding on Reddit about Gödel’s contradiction.

Appendix: The details of the contradiction

The following is for readers who have some familiarity with Gödel’s paper. We will follow a translation of Gödel’s proof that has clickable cross-reference links. We will call the system that Gödel uses to create his proof the “Proof System S”, and the formal system that is the subject of the proof P. Gödel’s proposition V asserts that given a primitive recursive number-theoretic relation R, then the Proof System can generate a formal system formula R_F that includes in an equivalent form all the relationships between numbers content that the relation R contains, and can also generate a Gödel number r that is the Gödel number of that formal formula R_F. This is a constructive generation of the number r, creating a correspondence between: (Footnote: Which begs the question, what is the definition of a number-theoretic relation, and why does a formula of the formal system not satisfy it? )

1. the primitive recursive number-theoretic relation R, and
2. the formal formula R_F, and
3. the number r.

 

In the following, for convenience, we refer to R only as primitive recursive number-theoretic relations that have one free variable, but the same principle applies for R with multiple free variables.

 

Gödel’s Proposition V claims that if the formula that results from the substitution of the free variable x_R of a primitive recursive relation R(x_R) by a specific value n, then if the resultant formula is provable in the Proof System S (is “true”), the corresponding formal formula R_F(x_F) which has its free variable x_F substituted by n_F is provable by the formal system P, where n_F has the same numerical value as n (provided the number theory of the formal system P is logically identical to the number theory of the Proof System S).

 

Besides that, the proposition claims that there is a number-theoretic relation that states Bew[Sb(r, ^u/_nf )], where u is the number that corresponds to the variable x_F of the formal system P, and that that relation is “true”, if R_F(x_F) is provable by the formal system P.

 

In his Proposition VI, Gödel defines a relation:

 

Q(x,y) = ¬{x B_c [Sb(y, ¹⁹/_Z(y))]}

 

and asserts that for all x, by applying his Proposition V (which he assumes to be correct instead of proving it correct), either:

 

¬{x B_c [Sb(y, ¹⁹/_Z(y))]} ⇒ Bew_c[Sb(q, ¹⁷/_Z(x) ¹⁹/_Z(y))]

or

x B_c [Sb(y, ¹⁹/_Z(y))]   ⇒ Bew_c[Neg Sb(q, ¹⁷/_Z(x) ¹⁹/_Z(y))]

 

where q is the Gödel number of a formal formula R_F with two free variables, and which corresponds to the relation Q as outlined above.

 

He then substitutes the y by 17 Gen q to give:

 

For all x, either:

 

(A)

¬{x B_c [Sb(17 Gen q, ¹⁹/_{Z(17 Gen q)})]}   ⇒ Bew_c[Sb(q, ¹⁷/_Z(x) ¹⁹/_{Z(17 Gen q)})]

 

 or

(B)

  x B_c [Sb(17 Gen q, ¹⁹/_{Z(17 Gen q)})]   ⇒ Bew_c[Neg Sb(q, ¹⁷/_Z(x) ¹⁹/_{Z(17 Gen q)})]

 

He gives Sb(q, ¹⁹/_{Z(17 Gen q)}) the designation r, giving: (Footnote: Note: the renaming of Sb(q, ¹⁹/_{Z(17 Gen q)}) is immaterial to the principle of the proof.)

 

For all x, either:

 

(15)

¬{x B_c (17 Gen r)} ⇒ Bew_c[Sb(r, ¹⁷/_Z(x))]

 

 or

(16)

x B_c (17 Gen r) ⇒ Bew_c[Neg Sb(r, ¹⁷/_Z(x))]

 

Gödel concludes that (15) must apply for all x, otherwise there is a contradiction.

 

 

But in order for Gödel’ Proof System S to assert that there is a contradiction, it must assert, as is asserted in Gödel’s Proposition V (besides the correspondences noted in i, ii, iii above) that there is a correspondence between:

1. a primitive recursive number-theoretic relation R being “true” in the Proof System S itself, and is provable in that system S, and
2. the corresponding formal formula R_F being provable in the formal system P, and
3. the corresponding Gödel number r satisfying the number-theoretic relation Bew.

 

Given the assertion in the Proof System S that:

For all x, ¬{x B_c (17 Gen r)}

 

from that, by (15) above it can be proved in the Proof System S that:

 

For all x, Bew_c[Sb(r, ¹⁷/_Z(x))]

 

and since the correspondences noted (1, 2, 3 above) necessarily exist in the Proof System S, then the Proof System S can also prove that:

For all x, R(x)

where

R(x) = ¬{x B_c (17 Gen r)}

 

i.e: R(x) is a primitive recursive number-theoretic relation that corresponds to the Gödel number r. (Footnote: Note that there have been numerous cases where it has been claimed that a human can see the truth of the assertion that R(x) applies for all x, but that no formal system could do so. This is, of course, complete hogwash - if the human is using a completely logical method of inference, then that method can be replicated formally. See also True but unprovable? and Man versus Machine.

 

So the Proof System S supposedly proves that while it can prove the relationship between numbers that is given by:

For all x, R(x)

it also proves that the formal system P (the formal system it is examining) cannot prove that same relationship between numbers.

 

So, applying in the same way the Proof System S to the Proof System S* (where the Proof System S* is as described above, and is exactly the same as the Proof System S except that symbols are different) we find that the Proof System S supposedly proves that it can prove the relationship between numbers given by:

For all x, R(x)

but the formal system Proof System S* cannot prove that same relationship between numbers.

 

And, applying the Proof System S* to the Proof System S, we find that the Proof System S* supposedly proves that it can prove the very same relationship between numbers given by:

For all x, R(x)

but the formal system Proof System S cannot prove that same relationship between numbers.

 

And that is the contradiction that is inherent in Gödel’s intuitive “proof ”.

Footnotes: