How Gödel's proof works

His incompleteness theorems defeated the search for a mathematical theory of everything. Almost a hundred years later, we are still trying to comprehend the consequences of this.

In 1931, the Austrian logician Kurt Gödel pulled off arguably one of the most astounding intellectual tricks in history.



The mathematicians of that era were looking for the unshakable foundations of mathematics: a set of basic facts, axioms that would be consistent and complete, playing the role of the building blocks of all mathematical truths.



However, Gödel's shocking incompleteness theorems, published by him at only 25 years of age, shattered this dream. He proved that any set of axioms you can propose to be the foundation of mathematics will inevitably be incomplete. There will always be true statements about numbers that cannot be proved using these axioms. He also showed that no set of axioms can be used to prove their own consistency.



His incompleteness theorems mean that there can be no mathematical theory of everything, and it is impossible to combine the set of provable statements with the set of true ones. What mathematicians can prove depends on initial assumptions, not on some fundamental truth from which all answers originate.



In the 89 years since Gödel's discovery, mathematicians have stumbled upon similar unanswered questions, the existence of which his theorems predicted. For example, Gödel himself helped establish that the continuum hypothesis concerning the cardinalities of infinities is undecidable - just like the stopping problem, in which it is required to determine whether the execution of a computer program will ever terminate with certain input data, or it will run forever. Unsolvable questions arose even in physics , which suggests that Gödel's incompleteness affects not only mathematics, but in some (not entirely clear) sense, reality.



What follows is a brief, simplified and informal summary of how Gödel proved his theorems.

Gödel numbering

Gödel's main move was the comparison of statements about the axiom system with statements made within this system - with statements about numbers. This juxtaposition allows the axiom system to reason calmly about itself.



The first step is to match any possible mathematical statement, or sequence of statements, with a unique number called the Gödel number .



A slightly revised version of Gödel's numbering as presented in the 1958 book Gödel's Proof by Ernest Nagel and James Newman, starts with 12 elementary symbols, which serve as a dictionary for expressing a set of basic axioms. For example, a statement about the existence of something can be expressed by the symbol ∃, and addition by the symbol +. The s, which stands for "next element", makes it possible to denote numbers: for example, ss0 stands for two.



These twelve characters are then assigned Gödel numbers 1 through 12.







Then letters denoting variables, starting with x, y and z, are matched with prime numbers greater than 12 (13, 17, 19, ..).



Then each of the combinations of these symbols and variables - that is, any arithmetic formula or sequence of formulas that can be made up - gets its own Gödel number.



Consider, for example, the statement 0 = 0. Its three symbols correspond to Gödel's numbers 6, 5 and 6. Gödel needs to replace this sequence of three numbers with one unique one - a number that no other sequence of symbols will produce. To do this, he takes the first three prime numbers (2, 3 and 5), raises each of them to the power equal to the corresponding number in the sequence, and multiplies them. So 0 = 0 becomes 2 ⁶ × 3 ⁵ × 5⁶ , or 243,000,000.



This markup works because no two formulas will give the same Gödel number. Gödel numbers are whole numbers, and numbers can be decomposed into prime factors in a unique way. Therefore, the only way to factor 243,000,000 into factors is 2 ⁶ × 3 ⁵ × 5 ⁶ , that is, there is only one way to decipher this Gödel number: by writing the formula 0 = 0.



Then Gödel went even further. A mathematical proof consists of a sequence of formulas. Therefore, Gödel assigned each sequence of formulas its own Gödel number. In this case, he also starts with a sequence of primes - 2, 3, 5, etc. Then he raises each of them to the power corresponding to the Gödel number for the formula in the same ordinal position in the sequence (say, ^{2,243,000,000} , if the formula 0 = 0 comes first), and multiplies everything together.

Arithmetic mathematics

It is remarkable that even statements concerning arithmetic formulas, the so-called. metamathematical statements can be translated into formulas, and assigned their own Gödel numbers.



Consider first the formula ~ (0 = 0), which means “zero is not zero”. It is clearly false. However, it has a Gödel number: 2 to the power of 1 (Gödel's number for the ~ character), multiplied by 3 to the 8th power (Gödel's number for the left parenthesis), and so on, which ultimately gives 2 ¹ × 3 ⁸ × 5 ⁶ × 7 ⁵ × 11 ⁶ × 13 ⁹ .



Since we can generate Gödel numbers for all formulas, even false ones, we can reason about them meaningfully using their Gödel numbers.



Consider the statement “The first character of the formula ~ (0 = 0) is a tilde”. This true metamathematical statement about ~ (0 = 0) turns into a statement about the Gödel number of a particular formula - namely, that its first degree is 1, that is, the Gödel number for the tilde. In other words, our statement says that there is only one factor "2" in 2 ¹ × 3 ⁸ × 5 ⁶ × 7 ⁵ × 11 ⁶ × 13 ⁹ . If ~ (0 = 0) began with any character other than a tilde, there would be at least two factors in its number. So, to put it more precisely, 2 is a factor of 2 ¹ × 3 ⁸ × 5 ⁶ × 7 ⁵× 11 ⁶ × 13 ⁹ , but 2 ² is not.



We can convert the last sentence into an exact mathematical formula, and write it down using elementary symbols. This formula, naturally, will have its own Gödel number, which we can calculate by matching its symbols to powers of prime numbers.



If you are interested, then the formulation turns out like this: there is an integer x such that x, multiplied by 2, will be equal to 2 ¹ × 3 ⁸ × 5 ⁶ × 7 ⁵ × 11 ⁶ × 13 ⁹ , but there is no such integer x that it multiplied by 4 gave 2 ¹ × 3 ⁸ × 5 ⁶× 7 ⁵ × 11 ⁶ × 13 ⁹ . The corresponding formula looks like this:



(∃x) (x × ss0 = sss… sss0) ⋅ ~ (∃x) (x × ssss0 = sss… sss0)



Where sss… sss0 means 2 ¹ × 3 ⁸ × 5 ⁶ × 7 ⁵ × 11 ⁶ × 13 ⁹ copies of the character of the next element s. The ⋅ symbol stands for “and,” and is a shorter notation for the fundamental vocabulary: p ⋅ q means ~ (~ p ∨ ~ q).



This example, as Nagel and Newman wrote, “illustrates a general and profound idea underlying Gödel's discovery: we can speak very accurately about the typographic properties of long sequences of characters, but not directly, but through the properties of the factorization of large integers.



Metamathematical statements can also be transformed into symbols. “There is a certain sequence of formulas with Gödel number x, proving a formula with Gödel number k” - or, in short, “a formula with Gödel number k is provable”. It was the ability to "arithmetic" such statements that laid the foundations for the coup.

G by itself

In addition, Gödel realized that it was possible to substitute Gödel's own number, denoting a formula, in the formula itself - and this already leads to endless problems.



To understand how this substitution works, consider the formula (∃x) (x = sy). It means "there is a variable x that is the next element for y", or, more simply, "y '' has the next element". Like all formulas, it has its own Gödel number - some large integer, let's call it m.



Now we will enter the number m in the formula instead of the symbol y. The result is a new formula (∃x) (x = sm), meaning “m has the next element”. What is the Gödel number for this formula? We need to convey three features: we started with a formula that has Gödel's number m. In it, we replaced the y symbol with the m symbol. And, according to the previously described comparison scheme, the Gödel number of the symbol y is 17. Let us then denote the Gödel number of the new formula sub (m, m, 17).



Substitution forms the basis of Gödel's proof.





Student Kurt Gödel in Vienna. He published incompleteness theorems in 1931, a year after receiving his diploma.



He considered the following mathematical statement: "The formula with Gödel number sub (y, y, 17) cannot be proved." Recalling the notation we just adopted, we know that we obtain the formula with the Gödel number sub (y, y, 17) by taking the formula with the Gödel number y (some unknown variable) and substituting this variable y wherever the symbol with Gödel number 17 (that is, wherever y occurs).



The head is already starting to spin, but, nevertheless, we can definitely translate our metamathematical statement, “a formula with Gödel's number sub (y, y, 17) cannot be proved”, into a formula with a unique Gödel number. Let's call it n.



And the last stage of substitutions: Gödel creates a new formula, substituting the number n wherever y appears in the previous formula. His new formula is as follows: “The formula with Gödel's number sub (n, n, 17) cannot be proved”. Let's call this formula G.



G naturally has a Gödel number. What is this number? Voila - it should be sub (n, n, 17). By definition, sub (n, n, 17) is the Gödel number for the formula, which is obtained by taking the formula with the Gödel number n and substituting n wherever a symbol with the Gödel number equal to 17 occurs in the formula. And G is exactly such a formula and there is! Since integers are decomposed into prime factors in a unique way, it becomes clear to us that Formula G tells us only about Formula G itself, and nothing else.



G says that it itself cannot be proven.



But can G be proven? If it were possible, it would mean that there is some sequence of formulas proving a formula with Gödel number sub (n, n, 17). But this is the opposite of Formula G, which says there is no such proof. Opposite statements, G and ~ G, in a consistent system of axioms cannot be simultaneously true. Therefore, G must be unprovable.



However, even though G cannot be proven, it is definitely true. G says that “the formula with the Gödel number sub (n, n, 17) cannot be proved”, which is exactly what we have established! Since G is a true but unprovable statement that exists within the axiomatic system that we used to construct it, this system is incomplete.



You might think that we can just add some additional axiom, use it to prove G, and resolve this paradox. But this is impossible. Gödel showed that the augmented system of axioms will make it possible to create a new true formula G 'according to the same scheme as before, which cannot be proved within the framework of the new, augmented system. Trying to build a complete mathematical system, you will only unsuccessfully chase your own tail.

Lack of proof of consistency

We now know that if a set of axioms is consistent, it is incomplete. This is Gödel's first incompleteness theorem. The second follows easily from it - no set of axioms can prove its consistency.



What would it mean if a set of axioms could prove that it would never be controversial? This would mean that there is a sequence of formulas built on these axioms, proving a formula that metamathematically means “this set of axioms is consistent”. But then, according to the first theorem, this set of axioms would necessarily be incomplete.



However, to say that “the set of axioms is incomplete” is the same as saying “there is a true formula that cannot be proved”. And this is equivalent to our formula G. And we know that the axioms cannot prove G.



So Gödel constructed a proof by contradiction: if a set of axioms could prove its own consistency, then we could prove G. But we cannot. Consequently, no set of axioms proves its own consistency.



Gödel's proof killed the quest for a consistent and complete mathematical system. Mathematicians “failed to grasp the full depth” of incompleteness, wrote Nagel and Newman in 1958. And today this statement remains true.

See also:

• " Why Gödel's incompleteness theorems difficult to prove: it is in the wording, and not only in fact "
• " Gödel's Incompleteness Theorem in 20 Minutes "
• " Secrets of Consciousness and Mathematics "