Gödel’s incompleteness theorem in 20 minutes

Gödel's Incompleteness Theorem , one of the most famous theorems of mathematical logic, was lucky and unlucky at the same time. In this, it resembles Einstein's special theory of relativity. On the one hand, almost everyone heard something about them. On the other hand, in the popular interpretation, Einstein's theory, as is well known, “says that everything in the world is relative . ” And Gödel's incompleteness theorem (hereinafter simply TGN), in approximately the same free folk-language, "proves that there are things that are incomprehensible to the human mind . " And some are trying to adapt it as an argument against materialism , while others, on the contrary, prove with its help that there is no God . It is funny not only that both parties cannot be right at the same time, but also that neither they nor others bother to figure out what, in fact, this theorem asserts.

So what? Below I will try to tell about it “on fingers”. My presentation will be, of course, lax and intuitive, but I will ask mathematicians not to judge me harshly. It is possible that for non-mathematicians (to whom, actually, I belong), in the story below, there will be something new and useful.
')

Mathematical logic - science is really quite complicated, and most importantly - not very familiar. It requires careful and strict maneuvers, in which it is important not to confuse what is really proven with what is “understandable.” However, I hope that in order to understand the following “outline of proof of TGN”, the reader will need only knowledge of school mathematics / computer science, logical thinking skills and 15–20 minutes of time.

Somewhat simplifying, TGN claims that there are unprovable statements in fairly complex languages. But in this phrase, almost every word needs explanation.

Let's start by trying to figure out what evidence is. Take some school arithmetic problem. For example, let it be required to prove the loyalty of the following straightforward formula: “ $$$\ forall x \; (x-1) (x-2) -2 = x (x-3)$ "(Recall that the symbol $$$\ forall$ read "for any" and is called "the quantifier of universality"). It can be proved, identically transforming, say, as follows:

1. $$$\ forall x \; (x-1) (x-2) -2 = x (x-3)$
2. $$$\ forall x \; x ^ 2-3x + 2-2 = x ^ 2-3x$
3. $$$\ forall x \; x ^ 2-3x – x ^ 2 + 3x = 0$
4. $$$\ forall x \; 0 = 0$
5. TRUE

The transition from one formula to another occurs according to some well-known rules. The transition from the 4th formula to the 5th occurred, say, because every number is equal to itself — such is the axiom of arithmetic. And the whole procedure of proving, thus, translates the formula into the boolean value . The result could be - if we denied some formula. In that case, we would prove its denial. One can imagine a program (and such programs are really written ) that would prove such (and more complex) statements without human participation.

Let us state the same a little more formally. Suppose we have a set consisting of strings of characters of an alphabet, and there are rules according to which a subset can be distinguished from these lines $$$S$ the so-called sentences - that is, grammatically meaningful phrases, each of which is true or false. We can say that there is a function $$$P$ matching statements from $$$S$ one of two values: or (i.e., mapping them to the boolean set $$$B$ of two elements).

Let's call such a pair - a lot of statements. $$$S$ and function $$$P$ of $$$S$ at $$$B$ - “the language of statements” . Note that in the everyday sense, the concept of language is somewhat broader. For example, the phrase “Well come here!” Is not true or false, that is, from the point of view of mathematical logic, it is not a statement.

For further, we need the concept of an algorithm. I will not give a formal definition of it here - it would lead us quite far away. I will confine myself to informal: “algorithm” - this sequence of unambiguous instructions (“program”), which in a finite number of steps translates the source data into a result. Italicized is fundamentally important - if the program loops on some initial data, it does not describe the algorithm. For simplicity and in application to our case, the reader can assume that an algorithm is a program written in any programming language known to it, which for any input data from a given class completes its work with the output of a boolean result.

We ask ourselves: whether for any function $$$P$ is there a “proving algorithm” (or, in short, a “deductic” ), equivalent to this function, that is, translating each statement into exactly the Boolean value that it is? More concisely, the same question can be formulated as follows: Is every function over a set of statements computable ? As you can already guess, from the validity of TGN it follows that no, not every one - there are uncomputable functions of this type. In other words, not every correct statement can be proved.

It may well be that this statement will cause you an internal protest. This is due to several circumstances. First, when we are taught in school mathematics, sometimes there is a false impression of the almost complete identity of the phrases “theorem $$$X$ true "and" one can prove or check the theorem $$$X$ ". But, if you think about it, it is absolutely not obvious. Some theorems are proved quite simply (for example, by searching for a small number of variants), and some are very difficult. Recall, for example, the famous Great Fermat theorem :

• There is no such natural $$$x, y, z$ and $$$n> 2$ , what $$$x ^ n + y ^ n = z ^ n$ .

proof of which was found only three and a half centuries after the first formulation (and it is far from elementary). It is necessary to distinguish the truth of the statement and its provability. It does not follow from anywhere that there are no true, but unprovable (and not fully verifiable) statements.

The second intuitive argument against TGN is more subtle. Suppose we have some unprovable (within the framework of this deductic) statement. What prevents us from accepting it as a new axiom? Thus, we will slightly complicate our evidence system, but this is not terrible. This argument would be perfectly true if there were a finite number of unprovable statements. In practice, the following may occur - after postulating a new axiom, you will stumble upon a new unprovable statement. If you accept it as an axiom, you will stumble upon a third one. And so on to infinity. Deductika is said to remain incomplete . We can also take force measures so that the proving algorithm ends in a finite number of steps with some result for any utterance of the language. But at the same time he will begin to lie - to lead to the truth for false statements, or to lie - for the faithful. In such cases, it is said that deduction is controversial . Thus, another formulation of TGN sounds like this: “There are sentence languages ​​for which complete non-contradictory deduction is impossible” - hence the name of the theorem.

It is sometimes referred to as the “Gödel theorem” assertion that any theory contains problems that cannot be solved within the framework of the theory itself and require its generalization. In a sense, this is true, although such a formulation would rather obscure the question rather than clarify it.

I also note that if we were talking about the usual functions that reflect the set of real numbers in it, then the “incomputable” function would not surprise anyone (just do not confuse “computable functions” and “computable numbers” are two different things). Any student knows that, say, in the case of a function $$$\ sin x$ you should be very lucky with the argument so that the process of calculating the exact decimal representation of the value of this function ends in a finite number of steps. And most likely you will calculate it with the help of an infinite series, and this calculation will never lead to an exact result, although it may come as close to it as you please - simply because the sine of most arguments is irrational. TGN simply tells us that even among functions, whose arguments are strings, and the values ​​are zero or one, noncomputable functions, although arranged in a completely different way, also occur.

For further we will describe the “language of formal arithmetic”. Consider the class of lines of text of finite length, consisting of Arabic numerals, variables (letters of the Latin alphabet), taking natural values, spaces, signs of arithmetic actions, equality and inequality, quantifiers $$$\ exists$ ("Exists") and $$$\ forall$ (“For any”) and, perhaps, some other symbols (their exact number and composition are not important for us). It is clear that not all such lines are meaningful (for example, " $$$12 = + \ forall x>$ "- this is nonsense). A subset of meaningful expressions from this class (that is, strings that are true or false from the point of view of ordinary arithmetic) will be our set of statements.

Examples of statements of formal arithmetic:

• $$$1 = 1$
• $$$2 \ times2 = 5$
• $$$\ exists x \; x> 3$
• $$$\ forall y \; \ forall z \; y \ times z> y + z$

etc. Now we will call a “formula with a free parameter” (FSP) a string that becomes a statement if we substitute a natural number in it as this parameter. Examples FSP (with the parameter $$$x$ ):

• $$$x = 0$
• $$$2 \ times2 = x$
• $$$\ exists y \; x + y> x$

etc. In other words, the FSP is equivalent to the functions of the natural argument with a Boolean value.

Denote the set of all FSPs by the letter $$$F$ . It is clear that it can be ordered (for example, we first write out alphabetically ordered single-letter formulas, followed by two-letter formulas, etc., according to which alphabet the ordering will occur, is not fundamental to us). Thus, any FSP corresponds to its number. $$$k$ in an ordered list, and we will denote it $$$F_k$ .

We now turn to the outline of the proof of TGN in the following formulation:

• For the language of statements of formal arithmetic, there is no complete consistent deduction.

We will prove by contradiction.

So, let us assume that such a deduktika exists. We describe the following auxiliary algorithm $$$A$ matching natural number $$$k$ Boolean value as follows:

1. Find $$$k$ formula in the list $$$F$ .
2. Substitute the number in it $$$k$ as an argument.
   
3. We our proving algorithm to the resulting statement (by our assumption, it exists), which translates it into or .
4. We apply a logical negation to the result obtained.

Simply put, an algorithm results in a value if and only if the result of the substitution in the FSP of its own number in our list gives a false statement.

Here we come to the only place in which I will ask the reader to take my word for it.

Obviously, with the above assumption, any FSP from $$$F$ You can compare the algorithm containing a natural number at the input, and a boolean value at the output. The reverse is less obvious:

• Lemma: Any algorithm converting a natural number to a boolean value corresponds to any FSP from the set $$$F$ .

The proof of this lemma would require, at a minimum, a formal, rather than an intuitive, definition of the concept of an algorithm. However, if you think a little, it is quite plausible. In fact, algorithms are written in algorithmic languages, among which there are such exotic ones as, for example, Brainfuck , consisting of eight single-character words, on which, however, any algorithm can be implemented. It would be strange if the richer language of formulas of formal arithmetic described by us were poorer — although, without a doubt, it is not very suitable for ordinary programming.

Having passed this slippery place, we quickly get to the end.

So, above we have described the algorithm $$$A$ . According to the lemma, in which I asked you to believe, there is an equivalent FSP. She has some number in the list. $$$F$ - let's say $$$n$ . Ask yourself what is $$$F_n (n)$ ? Let it be true. Then, by the construction of the algorithm $$$A$ (and therefore its equivalent function $$$F_n$ ), this means that the result of substituting a number $$$n$ in function $$$F_n$ - . Similarly, the reverse is verified: from $$$F_n (n) =$ should $$$F_n (n) =$ . We have come to a contradiction, which means that the initial assumption is wrong. Thus, for formal arithmetic, there is no complete consistent deduction. Q.E.D.

Here it is appropriate to recall Epimenides (see the portrait in the title), who, as you know, said that all Cretans are liars, being themselves Cretans. In a more concise formulation, his statement (known as the “paradox of the liar” ) can be formulated like this: “I lie”. It is this statement, which itself proposes its falsity, that we used for the proof.

In conclusion, I want to note that nothing special surprising TGN does not claim. In the end, all have long been accustomed to, that not all numbers are representable as the ratio of two integers (remember, this statement has very elegant proof , which is more than two thousand years old?). And the roots of polynomials with rational coefficients are also not all numbers . And now it turned out that not all functions of the natural argument are computable.

The above proof of the sketch related to formal arithmetic, but it is not difficult to understand that the TGN applies to many other utterances. Of course, not all languages ​​are as follows. For example, we define a language as follows:

• "Any phrase of the Chinese language is a correct statement, if it is contained in the quotation book of Comrade Mao Dze Dong, and is incorrect if it is not contained."

Then the corresponding complete and consistent proving algorithm (it can be called “dogmatic deduction”) looks like this:

• “Scroll through the quotation of Comrade Mao Dze Dong until you find the statement you’re looking for. If it is found, then it is true, and if the quotation is over, but the statement is not found, then it is incorrect. ”

Here we are saved by the fact that any quote book is obviously finite, so the process of “proving” will inevitably end. Thus, the language of the dogmatic statements TGN is not applicable. But we did talk about difficult languages, right?