323
Gödel's incompleteness theorem in 20 minutes
The gödel incompleteness theorem, one of the most famous theorems of mathematical logic, was lucky and unlucky at the same time. In this it is similar to the special theory of relativity.
On the one hand, almost all of them heard something. On the other hand, people's interpretation of Einstein's theory, as we know, "says everyone in the world is relative". And gödel's incompleteness theorem (hereinafter CBI), is equally the free folk formulation, "proves that there are things incomprehensible to the human mind".
And here some are trying to adapt it in an argument against materialism, while others, on the contrary, prove it, that there is no God. It's funny not only that both sides cannot be right simultaneously, but that neither one nor the other do not bother to understand what this theorem States.
So what? I will try "on fingers" to tell about it. My presentation will, of course, fuzzy and intuitive, but I'll ask mathematicians not to judge me too harshly. It is possible that for amathematical (which, actually, I am one), explained below, will be something new and useful.
Mathematical logic — science is really quite complex, and most importantly, very familiar. It requires careful and strict maneuvers in which it is important not to confuse real proven from the fact that "so clear". However, I hope to understand the following "outline of the proof TGN", the reader will need only a knowledge of school mathematics/computer science, logical thinking skills and 15-20 minutes of time.
Simplifying somewhat, the CBI argues that in difficult languages, there are unprovable statements. But in this phrase, almost every word needs to be explained.
To begin with, that will try to understand what is proof. Take some school problem in arithmetic. For example, suppose you want to prove loyalty to the following simple formula: "∀x(x−1)(x−2)-2=x(x−3)" (recall that the symbol ∀ is read "for all" and is called the "universal quantifier"). To prove it, transforming identically, like so:
∀x(x−1)(x−2)-2=x(x−3)
∀xx2−3x+2-2=x2−3x
∀xx2−3x–x2+3x=0
∀x0=0
The TRUTH
The transition from one formula to another takes place according to some known rules. The transition from 4-th formula to the 5th happened, say, because any number is equal to itself — that is an axiom of arithmetic. And the whole process of proof, therefore, translates the formula into a Boolean value of TRUE. The result could be a LIE if we denied some kind of formula. In this case, we have proved its negation. You can imagine the program (and such programs are really written), which would prove similar (and more complex) statements without human intervention.
Describe the same thing a little more formally. Suppose we have a set consisting of strings of symbols of some alphabet, and there are rules for which of these strings can identify a subset S so-called speech that is grammatically meaningful sentences, each of which is true or false. We can say that there is a function P that maps the statements of S one of two values: TRUE or FALSE (that is, displays them in the Boolean set B with two elements).
We call such a pair — a set of sentences S and a function P from >S to B — the"language statements". Note that in the casual sense, the concept of language is somewhat broader. For example, the phrase of the Russian language "come here!" is not true and not false, that is statement, from the point of view of mathematical logic, is not.
Further, we need the concept of the algorithm. To give here a formal definition, I will not — it would lead us quite far to the side. Limited informal: "algorithm" is a sequence of unambiguous instructions ("program"), which for a finite number of steps translates source data into the result.
In italics is fundamentally important — if for any initial data, the program loops, the algorithm it describes. For simplicity and in application to our case, the reader can assume that the algorithm is a program written in any known programming language, which for any input of a given class is guaranteed to complete its work with the results of the Boolean result.
Ask yourself: for every function P there is a "proving algorithm" (or, in short, "deductio") equivalent of this function, that is, translating each statement in the Boolean value, what is it? Succinctly, the same question can be formulated as follows: every function over the set of computable statements?
As you may have guessed, TGN justice, it follows that no, not every — there are non-computable function of this type. In other words, not every true statement can be proved.
It may well be that this claim will cause you internal protest. This is due to several factors. First, when we teach school math, sometimes there is a false impression of almost complete identity of the words "theorem X is true" and "you can prove or verify a theorem X".
But if you think about it, it's quite obvious. Some theorems are proved is quite simple (for example, by iterating over a small number of variants), and some of them very difficult. Recall, for example, the GreatFermat's theorem:
There is no such natural x,y,z and n>2, xn+yn=zn,
the proof of which is found only in three and a half century after the first formulation (and it is far from elementary). Withshould discern the truth of the statements and provability. It does not follow that there are true but unprovable (and not check fully) statements.
The second intuitive argument against TGN thinner. Let's say we have some unprovable (within the framework of this deductibe) statement. What prevents us from accepting it as a new axiom? Thus, we slightly complicate our proof system, but it's not terrible.
This argument would be completely true if unprovable statements was a finite number. In practice, the following may occur after postulating new axioms you run into a new unprovable statement. Accept it as another axiom, we drop to third. And so on to infinity.
Say deductio will remain incomplete. We can also take forceful measures to prove the algorithm ends after a finite number of steps with some result for any expression of language. But he will begin to lie cause the truth for incorrect statements, or to false for the true.
In such cases we say that deductio contradictory. Thus, another definition of TGN is: "are the language utterances that cannot be fully consistent deductio" — hence the name of the theorem.
Sometimes referred to as "Godel's theorem" the assertion that any theory contains problems that cannot be resolved within the theory itself and asks for its synthesis. In some sense this is true, although this formulation clouds the issue rather than clarifies it.
Also note that if we were talking about the usual functions that map the set of real numbers to itself, "devicelist" function would not surprise anyone (not to be confused with "computable function" and "computable number" are different things).
Kurt Godel
Any schoolboy knows that, for example, in the case of sinx, you must be lucky with the argument that the process of calculating the exact decimal representation of the value of this function ended in a finite number of steps.
And most likely you will calculate it using an infinite series, and this computation will never lead to accurate results, although it may approach it arbitrarily close, simply because the value of the sine of the most irrational arguments. TGN just tells us thateven among the functions, arguments which are strings, and values are zero or one, non-computable functions, though very differently constructed, too, are.
To further describe the "language of formal arithmetic". Consider a class of text strings of finite length consisting of Arabic numbers, variables (letters) taking natural values, gaps, signs of arithmetic operations, equality and inequality, quantifiers, ∃ ("exists") and ∀ ("for all") and maybe some more characters (the precise number and composition isn't important to us).
Clearly, not all such strings are meaningful (e.g., "12=+∀x>" is meaningless). A subset of the meaningful expressions of this class (that is, strings that are true or false from the point of view of ordinary arithmetic) and will be our set of statements.
Examples of statements of formal arithmetic:
etc. Now let "formula with the free parameter" (FAK) is a string that becomes a statement when this parameter to substitute in her a natural number. Examples of FSP (x):
etc. in Other words, the FSP is equivalent to the functions of natural argument with a Boolean value.
We denote the set of all FSP the letter F. it is Clear that it can be streamlined (for example, first write out an alphabetical single-letter formulas, two-letter, etc.; what kind of alphabet will be ordering us not important). Thus, any FSP complies with its number k in the ordered list, and we will designate it Fk.
We will now sketch a proof of TGN in this formulation:
For the language of formal arithmetic statements it is not entirely consistent deductibe.
Will prove by contradiction.
So, let's say that this deductio exist. Let us describe the following auxiliary algorithm A, which puts in conformity to the natural number k a Boolean value as follows:
1. Find the k-th formula in the list F.
2. Substitute into it the integer k as argument.
3. Applied to the statement of proving our algorithm (under our assumption that it exists), which translates it to TRUE or FALSE.
4. Apply the logical negation to the result.
Simply put, the algorithm yields the value TRUE when, and only when the result of the lookup in its own FSP number in our list gives a false statement.
Here we come to the only place where I will ask the reader to take my word.
It is obvious that under the above assumption, any FSP of F is to compare the algorithm with input a positive integer, and the output is a Boolean value.
Less obvious is the converse:
Lemma: Any algorithm that transforms a natural number into a Boolean value, corresponds to some FSP from the set F.
The proof of this Lemma would require at least a formal rather than intuitive, definition of algorithm. However, if you think about it, it's quite plausible.
In fact, algorithms written in algorithmic languages, among which are such exotic, as, for example, Brainfuck, consisting of eight single-character words, which, however, it is possible to implement any algorithm. It would be strange if we have described a richer formula language of formal arithmetic would be poorer — though, no doubt, for ordinary programming it is not very suitable.
After going through this slippery place, we quickly get to the end.
So, above we have described the algorithm A. Lemma, in which I asked you to believe, there exists an equivalent FSP. It has a number in the list of F — say, n. Ask yourself, what is Fn(n)? Let it be the TRUTH. Then, by the construction of algorithm A (and, hence, its equivalent of Fn), it means that the result of substituting numbers n to the function Fn is a LIE.
Similarly, it is checked in reverse: from Fn(n)=FALSE it follows Fn(n)=TRUE. We came to a contradiction, and hence the initial assumption is incorrect. Thus, for formal arithmetic it is not entirely consistent deductibe. What we wanted to prove.
It is appropriate to recall the Epimenides, who said that all Cretans are liars, being himself a Cretan.In more concise wording of his statement (known as the "paradox of the liar") can be formulated as follows: "I am lying". It is this statement, itself provozglashayu its falsity, we used for the proof.
In conclusion, I want to note that nothing special is an amazing TGN does not approve. In the end, all accustomed to the fact that not all numbers can be represented as the ratio of two integers (remember, this statement has a very elegant proof, which is more than two thousand years?). And roots of polynomials with rational coefficients are also not all the numbers. And now it turned out that not all the functions of natural argument computable.
Given a sketch of the evidence related to formal arithmetic, but it is easy to see that TGN applicable to many other languages statements. Of course, not all languages are. For example, define the language as follows:
"Any phrase of the Chinese language is a true statement if it is contained in the quotations of comrade Mao TSE Tung, and false if not contained".
Then the corresponding complete and consistent proving the algorithm (it can be called "dogmatic didaktikos") looks like this:
"Flipping the quotations of comrade Mao Zedong until you find the desired expression. If it is found, it is true, and if the quote ended, and the statement is not found, then it is wrong."
Here saves us is that any quote is obviously finite, so the process of "proof" will inevitably end. Thus, the language of dogmatic statements not applicable TGN. But we're talking about complicated languages, right? published
Source: geektimes.ru/post/284486/
On the one hand, almost all of them heard something. On the other hand, people's interpretation of Einstein's theory, as we know, "says everyone in the world is relative". And gödel's incompleteness theorem (hereinafter CBI), is equally the free folk formulation, "proves that there are things incomprehensible to the human mind".
And here some are trying to adapt it in an argument against materialism, while others, on the contrary, prove it, that there is no God. It's funny not only that both sides cannot be right simultaneously, but that neither one nor the other do not bother to understand what this theorem States.
So what? I will try "on fingers" to tell about it. My presentation will, of course, fuzzy and intuitive, but I'll ask mathematicians not to judge me too harshly. It is possible that for amathematical (which, actually, I am one), explained below, will be something new and useful.
Mathematical logic — science is really quite complex, and most importantly, very familiar. It requires careful and strict maneuvers in which it is important not to confuse real proven from the fact that "so clear". However, I hope to understand the following "outline of the proof TGN", the reader will need only a knowledge of school mathematics/computer science, logical thinking skills and 15-20 minutes of time.
Simplifying somewhat, the CBI argues that in difficult languages, there are unprovable statements. But in this phrase, almost every word needs to be explained.
To begin with, that will try to understand what is proof. Take some school problem in arithmetic. For example, suppose you want to prove loyalty to the following simple formula: "∀x(x−1)(x−2)-2=x(x−3)" (recall that the symbol ∀ is read "for all" and is called the "universal quantifier"). To prove it, transforming identically, like so:
∀x(x−1)(x−2)-2=x(x−3)
∀xx2−3x+2-2=x2−3x
∀xx2−3x–x2+3x=0
∀x0=0
The TRUTH
The transition from one formula to another takes place according to some known rules. The transition from 4-th formula to the 5th happened, say, because any number is equal to itself — that is an axiom of arithmetic. And the whole process of proof, therefore, translates the formula into a Boolean value of TRUE. The result could be a LIE if we denied some kind of formula. In this case, we have proved its negation. You can imagine the program (and such programs are really written), which would prove similar (and more complex) statements without human intervention.
Describe the same thing a little more formally. Suppose we have a set consisting of strings of symbols of some alphabet, and there are rules for which of these strings can identify a subset S so-called speech that is grammatically meaningful sentences, each of which is true or false. We can say that there is a function P that maps the statements of S one of two values: TRUE or FALSE (that is, displays them in the Boolean set B with two elements).
We call such a pair — a set of sentences S and a function P from >S to B — the"language statements". Note that in the casual sense, the concept of language is somewhat broader. For example, the phrase of the Russian language "come here!" is not true and not false, that is statement, from the point of view of mathematical logic, is not.
Further, we need the concept of the algorithm. To give here a formal definition, I will not — it would lead us quite far to the side. Limited informal: "algorithm" is a sequence of unambiguous instructions ("program"), which for a finite number of steps translates source data into the result.
In italics is fundamentally important — if for any initial data, the program loops, the algorithm it describes. For simplicity and in application to our case, the reader can assume that the algorithm is a program written in any known programming language, which for any input of a given class is guaranteed to complete its work with the results of the Boolean result.
Ask yourself: for every function P there is a "proving algorithm" (or, in short, "deductio") equivalent of this function, that is, translating each statement in the Boolean value, what is it? Succinctly, the same question can be formulated as follows: every function over the set of computable statements?
As you may have guessed, TGN justice, it follows that no, not every — there are non-computable function of this type. In other words, not every true statement can be proved.
It may well be that this claim will cause you internal protest. This is due to several factors. First, when we teach school math, sometimes there is a false impression of almost complete identity of the words "theorem X is true" and "you can prove or verify a theorem X".
But if you think about it, it's quite obvious. Some theorems are proved is quite simple (for example, by iterating over a small number of variants), and some of them very difficult. Recall, for example, the GreatFermat's theorem:
There is no such natural x,y,z and n>2, xn+yn=zn,
the proof of which is found only in three and a half century after the first formulation (and it is far from elementary). Withshould discern the truth of the statements and provability. It does not follow that there are true but unprovable (and not check fully) statements.
The second intuitive argument against TGN thinner. Let's say we have some unprovable (within the framework of this deductibe) statement. What prevents us from accepting it as a new axiom? Thus, we slightly complicate our proof system, but it's not terrible.
This argument would be completely true if unprovable statements was a finite number. In practice, the following may occur after postulating new axioms you run into a new unprovable statement. Accept it as another axiom, we drop to third. And so on to infinity.
Say deductio will remain incomplete. We can also take forceful measures to prove the algorithm ends after a finite number of steps with some result for any expression of language. But he will begin to lie cause the truth for incorrect statements, or to false for the true.
In such cases we say that deductio contradictory. Thus, another definition of TGN is: "are the language utterances that cannot be fully consistent deductio" — hence the name of the theorem.
Sometimes referred to as "Godel's theorem" the assertion that any theory contains problems that cannot be resolved within the theory itself and asks for its synthesis. In some sense this is true, although this formulation clouds the issue rather than clarifies it.
Also note that if we were talking about the usual functions that map the set of real numbers to itself, "devicelist" function would not surprise anyone (not to be confused with "computable function" and "computable number" are different things).
Kurt Godel
Any schoolboy knows that, for example, in the case of sinx, you must be lucky with the argument that the process of calculating the exact decimal representation of the value of this function ended in a finite number of steps.
And most likely you will calculate it using an infinite series, and this computation will never lead to accurate results, although it may approach it arbitrarily close, simply because the value of the sine of the most irrational arguments. TGN just tells us thateven among the functions, arguments which are strings, and values are zero or one, non-computable functions, though very differently constructed, too, are.
To further describe the "language of formal arithmetic". Consider a class of text strings of finite length consisting of Arabic numbers, variables (letters) taking natural values, gaps, signs of arithmetic operations, equality and inequality, quantifiers, ∃ ("exists") and ∀ ("for all") and maybe some more characters (the precise number and composition isn't important to us).
Clearly, not all such strings are meaningful (e.g., "12=+∀x>" is meaningless). A subset of the meaningful expressions of this class (that is, strings that are true or false from the point of view of ordinary arithmetic) and will be our set of statements.
Examples of statements of formal arithmetic:
- 1=1
- 2×2=5
- ∃xx>3
- ∀y∀zy×z>y+z
etc. Now let "formula with the free parameter" (FAK) is a string that becomes a statement when this parameter to substitute in her a natural number. Examples of FSP (x):
- x=0
- 2×2=x
- ∃yx+y>x
etc. in Other words, the FSP is equivalent to the functions of natural argument with a Boolean value.
We denote the set of all FSP the letter F. it is Clear that it can be streamlined (for example, first write out an alphabetical single-letter formulas, two-letter, etc.; what kind of alphabet will be ordering us not important). Thus, any FSP complies with its number k in the ordered list, and we will designate it Fk.
We will now sketch a proof of TGN in this formulation:
For the language of formal arithmetic statements it is not entirely consistent deductibe.
Will prove by contradiction.
So, let's say that this deductio exist. Let us describe the following auxiliary algorithm A, which puts in conformity to the natural number k a Boolean value as follows:
1. Find the k-th formula in the list F.
2. Substitute into it the integer k as argument.
3. Applied to the statement of proving our algorithm (under our assumption that it exists), which translates it to TRUE or FALSE.
4. Apply the logical negation to the result.
Simply put, the algorithm yields the value TRUE when, and only when the result of the lookup in its own FSP number in our list gives a false statement.
Here we come to the only place where I will ask the reader to take my word.
It is obvious that under the above assumption, any FSP of F is to compare the algorithm with input a positive integer, and the output is a Boolean value.
Less obvious is the converse:
Lemma: Any algorithm that transforms a natural number into a Boolean value, corresponds to some FSP from the set F.
The proof of this Lemma would require at least a formal rather than intuitive, definition of algorithm. However, if you think about it, it's quite plausible.
In fact, algorithms written in algorithmic languages, among which are such exotic, as, for example, Brainfuck, consisting of eight single-character words, which, however, it is possible to implement any algorithm. It would be strange if we have described a richer formula language of formal arithmetic would be poorer — though, no doubt, for ordinary programming it is not very suitable.
After going through this slippery place, we quickly get to the end.
So, above we have described the algorithm A. Lemma, in which I asked you to believe, there exists an equivalent FSP. It has a number in the list of F — say, n. Ask yourself, what is Fn(n)? Let it be the TRUTH. Then, by the construction of algorithm A (and, hence, its equivalent of Fn), it means that the result of substituting numbers n to the function Fn is a LIE.
Similarly, it is checked in reverse: from Fn(n)=FALSE it follows Fn(n)=TRUE. We came to a contradiction, and hence the initial assumption is incorrect. Thus, for formal arithmetic it is not entirely consistent deductibe. What we wanted to prove.
It is appropriate to recall the Epimenides, who said that all Cretans are liars, being himself a Cretan.In more concise wording of his statement (known as the "paradox of the liar") can be formulated as follows: "I am lying". It is this statement, itself provozglashayu its falsity, we used for the proof.
In conclusion, I want to note that nothing special is an amazing TGN does not approve. In the end, all accustomed to the fact that not all numbers can be represented as the ratio of two integers (remember, this statement has a very elegant proof, which is more than two thousand years?). And roots of polynomials with rational coefficients are also not all the numbers. And now it turned out that not all the functions of natural argument computable.
Given a sketch of the evidence related to formal arithmetic, but it is easy to see that TGN applicable to many other languages statements. Of course, not all languages are. For example, define the language as follows:
"Any phrase of the Chinese language is a true statement if it is contained in the quotations of comrade Mao TSE Tung, and false if not contained".
Then the corresponding complete and consistent proving the algorithm (it can be called "dogmatic didaktikos") looks like this:
"Flipping the quotations of comrade Mao Zedong until you find the desired expression. If it is found, it is true, and if the quote ended, and the statement is not found, then it is wrong."
Here saves us is that any quote is obviously finite, so the process of "proof" will inevitably end. Thus, the language of dogmatic statements not applicable TGN. But we're talking about complicated languages, right? published
Source: geektimes.ru/post/284486/