Introduction

There are two interesting paradoxes that are closely related to Gödel’s incompleteness theorems: Russell’s paradox and Berry’s paradox.

Russell’s paradox:

$$\text{Let } R = \{ x | x \notin x \}$$

A more general form of Russell’s paradox is:

A barber only shaves those who do not shave themselves. Does the barber shave himself?

It’s easy to conduct:
The barber shaves himself $\Leftrightarrow$ The barber does not shave himself.
If $R \in R$, then $R \notin R$; If $R \notin R$, then $R \in R$.
$R \in R \Leftrightarrow R \notin R$ leads to a contradiction.

Berry’s paradox:

All positive integers is definable in under sixty letters.

Let $n$ be the smallest positive integer not definable in under sixty letters. Then $n$ is definable in under sixty letters, leading to a contradiction.

These two paradoxes include self-reference, which is the key to Gödel’s incompleteness theorems.

Hilbert’s Program

The main goal of Hilbert’s program was to lay down some basic axioms and then to write the axioms in a formal language that could be used to prove all mathematical theorems.

Hilbert wanted to prove this system have the following wonderful properties:

1. Consistency: The system should not be able to prove a contradiction.
2. Completeness: The system should be able to prove all true mathematical statements.
3. Decidability: The system should be able to determine whether a statement is true or false.
4. Conservativity: The system should be able to prove all true mathematical statements without adding any new axioms.

If Hilbert’s program could be completed, then all mathematical problems could be solved by a computer and math became impeccable.

Wir müssen wissen, wir werden wissen. (We must know, we will know.)
— David Hilbert

Gödel’s First Incompleteness Theorem

Gödel’s first incompleteness theorem states that there exist true mathematical statements that cannot be proven in the system.

The proof of Gödel’s first incompleteness theorem is based on a self-reference paradox.

Here’s a simplified, informal rundown of how Gödel proved his theorems.

Gödel Numbering

Gödel numbering is a way to encode mathematical statements as numbers.

1. Assign a unique number to each symbol.
   The whole symbol table is:

   Constant Sign	Gödel Number	Usual Meaning
   \~{}	1	Not
   $\lor$	2	Or
   $\supset$	3	If … then …
   $\exists$	4	There is an …
   $=$	5	Equals
   $0$	6	Zero
   $S$	7	Successor of
   $($	8	Left parenthesis
   $)$	9	Right parenthesis
   $,$	10	Comma
   $+$	11	Plus
   $\times$	12	Times

2. Assign prime numbers greater than 12 to the letters representing variables.
   For $x, y, z, \ldots$, assign 13, 17, 19, $\ldots$.

Then any combination of these symbols and variables — that is, any arithmetical formula or sequence of formulas that can be constructed — gets its own Gödel number.

To map a formula to a number, we can use the following formula:

$$\text{Gödel number} = 2^{a_1} \times 3^{a_2} \times 5^{a_3} \times \ldots \times p_n^{a_n}$$

where $a_1, a_2, \ldots, a_n$ are the Gödel numbers of the symbols in the formula.

Take the formula $x \times 0 = 0$ as a simple example:

The Gödel formula of $x \times 0 = 0$ is $2^{13} \times 5^{6} \times 12^{11} \times 6^{6} \times 5^{6}$.

This construct method ensure that all the formulas in the system can be encoded to the only number with a multiplication of a bunch of prime numbers.

Since all the number can be uniquely factorized into prime numbers, we can decode the number to the only original formula easily by factorizing the Gödel number.

Arithmetizing Metamathematics

The real boon is that even statements about arithmetic formulas, called metamathematical statements, can themselves be translated into formulas with Gödel numbers of their own.

For example, the statement “The first symbol of the formula ~(0 = 0) is a tilde.” This (true) metamathematical statement about ~(0 = 0) translates into a statement about the formula’s Gödel number — namely, that its first exponent is 1, the Gödel number for a tilde. In other words, our statement says that $2^1 \times 38 \times 56 \times 75 \times 116 \times 139$ has only a single factor of 2. Had ~(0 = 0) begun with any symbol other than a tilde, its Gödel number would have at least two factors of $2$. So, more precisely, $2$ is a factor of $2^1 \times 38 \times 56 \times 75 \times 116 \times 139$, but $2^2$ is not a factor. Through this kind of mapping, we can translate metamathematical statements into statements about Gödel numbers.

Conversion into symbols is also possible for the metamathematical statement, “There exists some sequence of formulas with Gödel number x that proves the formula with Gödel number k” — or, in short, “The formula with Gödel number k can be proved.” The ability to “arithmetize” this kind of statement set the stage for the coup.

It’s noticable that the way of mapping is not the key of Gödel’s incompleteness theorems, but it is the foundation of the proof. Utlizing any other mapping method, the proof can still be conducted. We don’t need to care about whether all the math statements can be encoded to numbers or not, for now.

The Proof

Take, Find and Replace

The whole proof of Gödel’s first incompleteness theorem is based on a self-reference paradox. Self is what makes all the magic happen.

To make it easier to understand I construct a statement $M$ that says, $(\exists x)(x=sy)$. The Gödel number of $M$ is marked as $m$.

Then we replace $y$ in $M$ with $m$ and get a new statement $N$ that says, $(\exists x)(x=sm)$. The Gödel number of $N$ is marked as $n$.

Now we can define a special function called $\mathrm{sub}(a, b, c)$. The result of $\mathrm{sub}(a, b, c)$ is a Gödel number of a new proposition.

The construction of the new proposition of $\mathrm{sub}(a, b, c)$ contains three steps:

1. Take the proposition with Gödel number $a$ marked as $A$.
2. Find the position of the symbol with Gödel number $c$ in the proposition $A$.
3. Replace the position with the number $b$.

Let’s continue to use the same example as above, we want to find what is the proposition of Gödel number $\mathrm{sub}(m, m, 17)$.

We follow the TFR three steps:

1. Take the proposition with Gödel number $m$.
   The proposition is $(\exists x)(x=sy)$ marked as $M$.
2. Find the position of the symbol with Gödel number $17$ in the proposition.
   The symbol with Gödel number $17$ is $y$.
3. Replace the position with the number $m$.
   The proposition becomes $(\exists x)(x=sm)$.

The Construction of a Self-Reference Proposition

Firstly, we construct a new proposition that says, “it is impossible to prove the proposition with Gödel number $\mathrm{sub}(y, y, 17)$”. We mark the proposition as $N$ with Gödel number $n$.

Here may casued some confusion. We still use the TFR three steps to find the proposition of Gödel number $\mathrm{sub}(y, y, 17)$:

1. Take the proposition with Gödel number $y$.
   The proposition is marked as $Y$. The proposition may contains a lots of symbols, including $y$ which is the symbol with Gödel number $17$.
2. Find the position of the symbol with Gödel number $17$ which is $y$ in the proposition $Y$.
3. Replace the position with the number $y$.

The confusing part is that $y$ sometimes acts as a symbol and sometimes acts as a number. In step 2, we need to find the position of the symbol with Gödel number $17$ in the proposition $Y$. But in step 3, we need to replace the position with the number $y$ from the original $\mathrm{sub}(y,y,17)$.

The symbol $y$ here appear to enact different roles, but they are ensentially the same.

Previously, we have a proposition $N$ that says, “it is impossible to prove the proposition with Gödel number $\mathrm{sub}(y, y, 17)$”. The Gödel number of $N$ is $n$.

We continue our construction and get a new proposition $P$ that says, “it is impossible to prove the proposition with Gödel number $\mathrm{sub}(n, n, 17)$”.

Focusing on the Gödel number $\mathrm{sub}(n, n, 17)$ in $P$, we still use the TFR three steps to find the Gödel number of the Gödel number $\mathrm{sub}(n, n, 17)$:

1. Take the proposition with Gödel number $n$.
   The proposition is $N$ which says “it is impossible to prove the proposition with Gödel number $\mathrm{sub}(y, y, 17)$”.
2. Find the position of the symbol with Gödel number $17$ in the proposition.
3. Replace the position with the number $n$.

Finally, we get the proposition of Gödel number $\mathrm{sub}(n, n, 17)$ that says, “it is impossible to prove the proposition with Gödel number $\mathrm{sub}(n, n, 17)$”. The Gödel number of this proposition is coincidentally $\mathrm{sub}(n, n, 17)$.

Let’s take a careful look at Gödel number $\mathrm{sub}(n, n, 17)$ and it’s proposition $P$. The proposition says, “it is impossible to prove the proposition with Gödel number $\mathrm{sub}(n, n, 17)$”.

If $P$ is false, which means it is possible to prove the proposition with Gödel number $\mathrm{sub}(n, n, 17)$, then the proposition with Gödel number $\mathrm{sub}(n, n, 17)$ is true. But the proposition with Gödel number $\mathrm{sub}(n, n, 17)$ says, “it is impossible to prove the proposition with Gödel number $\mathrm{sub}(n, n, 17)$”. This leads to a contradiction.

There should be one and only one way to fix the paradox: the proposition $P$ is true.

Thus proposition $P$ becomes a true but unprovable proposition, which proves Hilbert’s completeness property is impossible.

This is the core of Gödel’s first incompleteness theorem.

Any consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of $F$ which can neither be proved nor disproved in $F$.

Gödel’s Second Incompleteness Theorem

For any consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out, the consistency of $F$ cannot be proved in $F$ itself.

The only condition we set to prove the first incompleteness theorem is the consistency of the system.

The second incompleteness theorem is a direct result of the first incompleteness theorem. If the consistency of $F$ can be proved in $F$, then we can prove the proposition $P$ in $F$. But the proposition $P$ is unprovable in $F$. This leads to a contradiction.

The one and only way to fix the paradox is that the consistency of $F$ cannot be proved in $F$ itself.

As a side note, Gödel immigrated to the United States in 1947. When he took the citizenship test, he found a contradiction in the U.S. Constitution and told to Albert Einstein. However, he didn’t point it out to others.

Turing’s Halting Problem

Gödel’s incompleteness theorems pointed out the consistency and completeness of a formal system cannot be proved in the system itself. Turing’s halting problem further proved that the mathematics is undecidable.