Gödel's first theorem

Gödel's incompleteness theorem shows that any consistent formal system of axioms and rules of inference, provided it's strong enough to produce arithmetic, will contain true statements that can't be proven by the procedures provided in the system.

Kurt Gödel (1931).

The Self-Referential Paradoxes

The Liar Paradox
 
The liar paradox dates back to the new Testament:

“It was a Cretan prophet, one of their own countrymen, who said: Cretans are always liars, vicious brutes, lazy gluttons—and he told the truth!” (Titus 1:12-13)

Sample Liar sentences:

  • This very sentence is false.
  • Sentenced 2 is not true.
  • It is true that this very sentence is false.
The liar sentence can't be pinned down to one truth value. It can't be decided whether it is true or false.

Russell's Paradox

In the late 1800s, Gottlob Frege introduced a system of logic that seemed capable of providing a consistent basis for mathematics. In a letter to Frege, Bertrand Russell (1902) introduced a paradox that undermined Frege’s system and inspired a restructuring in the foundations of mathematics.

To understand Russell's paradox, note there are some classes that contain themselves and some that do not.

The class”N” of non-red things is itself non-red. The class contains itself as a member.

  • The class M of all men is not itself a man. It doesn’t contain itself as a member.
The assumption that there is a class of all classes that do not contain themselves leads to a contradiction.

Gödel’s Theorem

Gödel sentences generate a paradox similar to the liar's paradox and Russell's paradox, except from the point of view of the formal system such as Principia Mathematica:

"The analogy of this argument with the Richard antinomy leaps to the eye. It is cloely related to the Liar too… We therefore have a proposition before us that says about itself that it is not provable." Kurt Gödel (1931, p.89-90).

Either, It is provable that G is not provable,

In which case, G is both provable and not provab le.

Or, It is disprovable that G is not provable,

In which case, we can show that it is not the case that G is not provable, so G is provable after all. So, G is both provable and not provable.

In either case, the system can neither prove nor disprove the Gödel sentence G. It can’t be decided whether G is true or false from the point of view of the system in which G is represented.

Alternative Versions of Gödel's Theorem


RELATED ARTICLESExplain
Artificial Intelligence
Are thinking computers mathematically possible? [7]
No: computers are limited by Gödel's theorems
Theorems show limitations of machine thought
Gödel's first theorem
Gödel's second theorem
Gödel's and Church's theorems are psychological laws
Machines can't understand language like humans
Mathematical thought can't be fully formalised
Mathematics is an essentially creative activity
The argument from Church's theorem
A human can't simultaneously beat all machines
Machines may eventually have mathematical intuition
Graph of this discussion
Enter the title of your article


Enter a short (max 500 characters) summation of your article
Enter the main body of your article
Lock
+Comments (0)
+Citations (0)
+About
Enter comment

Select article text to quote
welcome text

First name   Last name 

Email

Skip