Any system of mathematical axioms, starting from a certain level of complexity, is either internally inconsistent or incomplete.
In 1900, the World Conference of Mathematicians was held in Paris, at which David Hilbert (1862–1943) presented in the form of abstracts the 23 most important, in his opinion, problems formulated by him, which were to be solved by theoretical scientists of the coming twentieth century. Number two on his list was one of those simple problems that seem obvious until you dig a little deeper. In modern terms, it was the question: is mathematics sufficient on its own? Hilbert's second task was reduced to the need to strictly prove that the system of axioms - basic statements taken in mathematics as a basis without proof - is perfect and complete, that is, it allows mathematical description of everything that exists. It was necessary to prove that it is possible to set such a system of axioms that, firstly, they will be mutually consistent, and secondly, one can draw a conclusion from them regarding the truth or falsity of any statement.
Let's take an example from school geometry. In standard Euclidean planimetry (geometry on a plane), it can be unconditionally proved that the statement "the sum of the angles of a triangle is 180°" is true, and the statement "the sum of the angles of a triangle is 137°" is false. Speaking essentially, in Euclidean geometry, any statement is either false or true, and the third is not given. And at the beginning of the twentieth century, mathematicians naively believed that the same situation should be observed in any logically consistent system.
And then in 1931, some Viennese bespectacled mathematician Kurt Godel took and published a short article that simply overturned the whole world of so-called "mathematical logic". After long and complex mathematical and theoretical preambles, he literally established the following. Let's take any statement like: "Assumption #247 is logically unprovable in this system of axioms" and call it "statement A". So, Gödel simply proved the following amazing property of any system of axioms:
"If a statement A can be proved, then a non-A statement can be proved."
In other words, if it is possible to prove the validity of the statement "Assumption 247 is not provable", then it is also possible to prove the validity of the statement "Assumption 247 is provable". That is, returning to the formulation of the second Hilbert problem, if the system of axioms is complete (that is, any statement in it can be proved), then it is inconsistent.
The only way out of this situation is to accept an incomplete system of axioms. That is, we have to put up with the fact that in the context of any logical system we will still have “type A” statements that are obviously true or false - and we can judge their truth only outside the framework of the axiomatics we have adopted. If there are no such statements, then our axiomatics is contradictory, and within its framework there will inevitably be formulations that can be both proved and refuted.
So, the formulation of Gödel's first, or weak, incompleteness theorem is: "Any formal system of axioms contains unresolved assumptions." But Gödel did not stop there, formulating and proving Gödel's second or strong incompleteness theorem: “The logical completeness (or incompleteness) of any system of axioms cannot be proved within the framework of this system. To prove or disprove it, additional axioms (strengthening of the system) are required.”
It would be safer to think that Godel's theorems are abstract and do not concern us, but only areas of sublime mathematical logic, but in fact it turned out that they are directly related to the structure of the human brain. The English mathematician and physicist Roger Penrose (born 1931) showed that Gödel's theorems could be used to prove fundamental differences between the human brain and a computer. The point of his reasoning is simple. The computer operates strictly logically and is not able to determine whether statement A is true or false if it goes beyond the scope of axiomatics, and such statements, according to Gödel's theorem, inevitably exist. A person, faced with such a logically unprovable and irrefutable statement A, is always able to determine its truth or falsity - based on everyday experience. At least in this, the human brain is superior to a computer shackled by pure logical circuits. The human brain is able to understand the full depth of truth contained in Gödel's theorems, but a computer one can never. Therefore, the human brain is anything but a computer. He is able to make decisions, and the Turing test will pass.
I wonder if Hilbert had any idea how far his questions would take us?
Kurt GOEDEL
Kurt Godel, 1906–78
Austrian, then American mathematician. Born in Brünn (Brünn, now Brno, Czech Republic). He graduated from the University of Vienna, where he remained a teacher in the Department of Mathematics (since 1930 - a professor). In 1931 he published a theorem that later received his name. Being a purely apolitical person, he extremely hard survived the murder of his friend and department employee by a Nazi student and fell into a deep depression, the relapses of which haunted him until the end of his life. In the 1930s, he emigrated to the United States, but returned to his native Austria and got married. In 1940, at the height of the war, he was forced to flee to America in transit through the USSR and Japan. For some time he worked at the Princeton Institute for Advanced Study. Unfortunately, the psyche of the scientist could not stand it, and he died of starvation in a psychiatric clinic, refusing to eat, because he was convinced that they intended to poison him.
| Comments: 0 |
How does the scientific model develop in the natural sciences? Everyday or scientific experience accumulates, its milestones are neatly formulated in the form of postulates and form the basis of the model: a set of statements accepted by everyone who works within this model.
Anatoly Wasserman
In 1930, Kurt Gödel proved two theorems that, translated from mathematical language into human language, mean something like this: Any system of axioms rich enough to be used to define arithmetic will either be incomplete or inconsistent. An incomplete system means that a statement can be formulated in the system, which can neither be proved nor disproved by means of this system. But God, by definition, is the ultimate cause of all causes. Mathematically, this means that the introduction of the axiom about God makes our entire axiom complete. If there is a God, then any statement can either be proved or refuted, referring, one way or another, to God. But according to Gödel, the complete system of axioms is inevitably contradictory. That is, if we believe that God exists, then we are forced to come to the conclusion that contradictions are possible in nature. And since there are no contradictions, otherwise our whole world would crumble from these contradictions, one has to come to the conclusion that the existence of God is incompatible with the existence of nature.
Sosinsky A. B.
Gödel's theorem, along with the discovery of relativity, quantum mechanics, and DNA, is generally regarded as the greatest scientific achievement of the 20th century. Why? What is its essence? What is its meaning? Alexey Bronislavovich Sosinsky, mathematician, professor at the Independent Moscow University, officer of the Order of Academic Palms of the French Republic, laureate of the RF Government Prize in the field of education in 2012, reveals these questions in his lecture within the framework of the Polit.ru Public Lectures project. In particular, several different formulations of it were given, three approaches to its proof were described (by Kolmogorov, Chaitin, and Gödel himself), and its significance for mathematics, physics, computer science, and philosophy was explained.
Uspensky V. A.
The lecture is devoted to the syntactic version of Gödel's Incompleteness Theorem. Gödel himself proved the syntactic version using a stronger assumption than consistency, namely the so-called omega-consistency.
Uspensky V. A.
Lectures of the Summer School "Modern Mathematics", Dubna.
Godel's incompleteness theorem
Uspensky V.A.
Perhaps Gödel's incompleteness theorem is truly unique. Unique in that they refer to it when they want to prove "everything in the world" - from the presence of gods to the absence of reason. I have always been interested in a more "primary question" - and which of those who refer to the incompleteness theorem could not only formulate it, but also prove it? I publish this article for the reason that it presents a very accessible formulation of Gödel's theorem. I recommend that you first read the article by Tullio Regge Kurt Gödel and his famous theorem
The conclusion about the impossibility of a universal criterion of truth is a direct consequence of the result obtained by Tarski by combining Gödel's undecidability theorem with his own theory of truth, according to which there cannot be a universal criterion of truth even for a relatively narrow area of number theory, and hence for any science using arithmetic. Naturally, this result applies a fortiori to the concept of truth in any non-mathematical field of knowledge in which arithmetic is widely used.
Karl Popper
Uspensky Vladimir Andreevich was born on November 27, 1930 in Moscow. Graduated from the Faculty of Mechanics and Mathematics of Moscow State University (1952). Doctor of Physical and Mathematical Sciences (1964). Professor, Head of the Department of Mathematical Logic and Theory of Algorithms of the Faculty of Mechanics and Mathematics (1966). Reads courses of lectures "Introduction to Mathematical Logic", "Computable Functions", "Gödel's Completeness Theorem". Prepared 25 candidates and 2 doctors of sciences
1. Statement of the problem
The incompleteness theorem, the exact formulation of which we will give at the end of this chapter, and perhaps later (if the reader is interested in this) and the proof, states approximately the following: under certain conditions in any language there are true, but unprovable statements.
When we formulate a theorem in this way, almost every word requires some explanation. Therefore, we will begin by explaining the meaning of the words we use in this formulation.
1.1. Language
We will not give the most general possible definition of a language, preferring to confine ourselves to those linguistic concepts that we will need later. There are two such concepts: "the alphabet of the language" and "the set of true statements of the language".
1.1.1. Alphabet
By alphabet, we mean a finite set of elementary signs (that is, things that cannot be broken down into component parts). These characters are called letters of the alphabet. By a word of an alphabet we mean a finite sequence of letters. For example, ordinary words in English (including proper names) are words of the 54-letter alphabet (26 small letters, 26 uppercase letters, a dash and an apostrophe). Another example - natural numbers in decimal notation are words of a 10-letter alphabet, whose letters are signs: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. We will use ordinary capital letters to denote alphabets. If L is an alphabet, then L? will denote the set of all words of the alphabet L, - words formed from its letters. We will assume that any language has its own alphabet, so that all expressions of this language (ie - names of various objects, statements about these objects, etc.) are words of this alphabet. For example, any sentence in the English language, as well as any text written in English, can be considered as a word of the extended 54-letter alphabet, which also includes punctuation marks, interword space, a redline character, and possibly some other useful characters. Assuming that language expressions are words of some alphabet, we thus exclude from consideration "multilayer" expressions like ???f(x)dx. However, this limitation is not too significant, since any such expression, using suitable conventions, can be "stretched" into a linear form. Any set M contained in L? is called a word set of the alphabet L. If we simply say that M is a word set, then we mean that it is a word of some alphabet. Now the language assumption above can be rephrased as follows: in any language, any set of expressions is a word set.
1.1.2. Lots of true claims
We assume that we are given a subset T of the set L? (where L is the alphabet of some language we are considering), which is called the set of "true statements" (or simply "truths"). Passing directly to the subset T, we omit the following intermediate steps of reasoning: firstly, which words of the alphabet L are well-formed expressions of the language, that is, they have a certain meaning in our interpretation of this language (for example, 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 are well-formed expressions, while expressions like +=x are not); secondly, which expressions are formulas, i.e. may depend on a parameter (eg, x=3, x=y, 2=3, 2=2); thirdly, which of the formulas are closed formulas, i.e. statements that do not depend on parameters (for example, 2=3, 2=2); and finally, which closed formulas are true statements (for example, 2=2).
1.1.3. Fundamental language pair
1.2. "Unprovable"
"Unprovable" means having no evidence.
1.3. Proof
Despite the fact that the term "proof" is perhaps one of the most important in mathematics (the Bourbaki begin their book "Fundamentals of Mathematics" with the words: "From the time of the ancient Greeks, saying "mathematics" meant the same as saying "proof""), he does not have a precise definition. In general, the concept of proof with all its semantic branches belongs, rather, to the field of psychology than to mathematics. But be that as it may, evidence is simply an argument that we ourselves find quite convincing in order to convince everyone else.
When written down, the proof becomes a word in some alphabet P, just as any English text is a word in the alphabet L, an example of which was given above. The set of all proofs forms a subset (and quite a large subset) of the set P?. We will not attempt to give a precise definition of this both "naive" and "absolute" concept of proof, or - which is equivalent - to define the corresponding subset of P?. Instead, we will consider a formal analogue of this vague concept, for which we will still use the term "proof" in what follows. This analogue has two very important features that distinguish it from the intuitive concept (although the intuitive idea of the proof still reflects these features to some extent). First of all, we assume that there are different conceptions of proof, that is, different subsets of proofs in P? are allowed, and even more than that: we will, in fact, assume that the alphabet of proofs of P itself can change. In what follows, we will require that for each such conception of a proof there is an efficient method, in other words, an algorithm that would necessarily determine whether a given word of the alphabet P is a proof or not. We also assume that there is an algorithm that can always be used to determine which statement a given proof proves. (In many situations, the statement being proved is simply the last statement in the sequence of steps that form the proof.)
Thus, our final wording of the definition is as follows:
(1) We have the alphabet L (the alphabet of the language) and the alphabet P (the alphabet of the proof).
(2) We are given a set P which is a subset of P? and whose elements are called "proofs". In the following, we will assume that we also have an algorithm that allows us to determine whether an arbitrary word of the alphabet P is an element of the set P, that is, a proof, or not.
(3) Also we have a function? (for finding what exactly has been proven), whose domain is? satisfies the condition P???P?, and whose range is in P?. We assume that we have an algorithm that calculates this function (the exact meaning of the words "algorithm calculates a function" is the following: function values are obtained using this algorithm - a set of special transformation rules). We will say that the element p? P is a proof of the word?(p) of the alphabet L.
Troika<Р, Р, ?>, satisfying conditions (1)-(3) is called a deductive system over the alphabet L.
For the reader familiar with the usual way of defining "proof" in terms of "axiom" and "rule of inference", we will now explain how this method can be regarded as a special case of the definition given in section 1.3.2. That is, a proof is usually defined as a sequence of such language expressions, each of which is either an axiom or previously obtained from already existing statements using one of the inference rules. If we add a new word * to the alphabet of our language, then we can write such a proof as a word composed using the resulting alphabet: the sequence of expressions becomes the word C1*C2*...*Cn. In this case, the function that determines what exactly has been proved has its value in the part of this word immediately following the last letter * in the sequence. The algorithm whose existence is required in Section 1.3.2. definitions, can easily be constructed once we have precisely defined any of the accepted meanings of the words "axiom" and "rule of inference".
1.4. Attempts to accurately formulate the incompleteness theorem
1.4.1. First try
"Under certain conditions for the fundamental pair of the language of the alphabet L and the deductive system<Р, Р, ?>over L, there always exists a word in T that has no proof. This option still looks vague. In particular, we could easily come up with as many deductive systems as we like that have very few provable words. ?) there are no words at all that would have evidence.
1.4.2. Second try
There is another, more natural approach. Suppose we are given a language - in the sense that we are given a fundamental pair of this language. Now we will look for such a deductive system over L (intuitively, we are looking for a proof technique) with which we could prove as many words from T as possible, in the limit all words from T. Gödel's theorem describes the situation in which such a deductive system ( by which every word in T would be provable) does not exist. Thus, we would like to formulate the following statement:
"Under certain conditions regarding the fundamental pair, there is no such deductive system in which every word from T would have a proof."
However, such a statement is obviously false, since it is only necessary to take a deductive system in which P = L, P = P? and?(p) = p for all p in P?; then every word from L? is trivially provable. Therefore, we need to accept some limitation on which deductive systems we use.
1.5. Consistency
It would be quite natural to require that only "true statements", that is, only words from T, can be proved. We will say that the deductive system<Р, Р, ?>is consistent with respect to a fundamental pair if?(P)?T. In all subsequent reasoning, we will be interested only in such consistent deductive systems. If we are given a language, then it would be extremely tempting to find such a consistent deductive system in which every true statement would have a proof. The variant of Gödel's theorem that interests us exactly states that under certain conditions regarding the fundamental pair, it is impossible to find such a deductive system.
1.6. completeness
It is said that the deductive system<Р,Р,?>is complete with respect to the fundamental pair, provided that?(P)?T. Then our formulation of the incompleteness theorem takes the following form:
Under certain conditions regarding the fundamental pair, there is no such deductive system<Р,Р,?>over L that would be both complete and relatively consistent.
Bibliography
For the preparation of this work, materials from the site http://filosof.historic.ru were used.
09senAny system of mathematical axioms, starting from a certain level of complexity, is either internally inconsistent or incomplete.
In 1900, the World Conference of Mathematicians was held in Paris, where David Gilbert(David Hilbert, 1862–1943) outlined in the form of theses the 23 most important, in his opinion, tasks that theoreticians of the coming twentieth century had to solve. Number two on his list was one of those simple problems that seem obvious until you dig a little deeper. In modern terms, it was the question: is mathematics sufficient on its own? Hilbert's second task was reduced to the need to strictly prove that the system of axioms - basic statements taken in mathematics as a basis without proof - is perfect and complete, that is, it allows mathematical description of everything that exists. It was necessary to prove that it is possible to set such a system of axioms that, firstly, they will be mutually consistent, and secondly, one can draw a conclusion from them regarding the truth or falsity of any statement.
Let's take an example from school geometry. In standard Euclidean planimetry (geometry on a plane), it can be unconditionally proved that the statement "the sum of the angles of a triangle is 180°" is true, and the statement "the sum of the angles of a triangle is 137°" is false. Speaking essentially, in Euclidean geometry, any statement is either false or true, and the third is not given. And at the beginning of the twentieth century, mathematicians naively believed that the same situation should be observed in any logically consistent system.
And then in 1931 some Viennese bespectacled mathematician Kurt Gödel- took and published a short article that simply overturned the whole world of so-called "mathematical logic". After long and complex mathematical and theoretical preambles, he literally established the following. Let's take any statement like: "Assumption #247 is logically unprovable in this system of axioms" and call it "statement A". So, Gödel simply proved the following amazing property of any system of axioms:
"If a statement A can be proved, then a non-A statement can be proved."
In other words, if it is possible to prove the validity of the statement "Assumption 247 is not provable", then it is also possible to prove the validity of the statement "Assumption 247 is provable". That is, returning to the formulation of the second Hilbert problem, if the system of axioms is complete (that is, any statement in it can be proved), then it is inconsistent.
The only way out of this situation is to accept an incomplete system of axioms. That is, we have to put up with the fact that in the context of any logical system we will still have “type A” statements that are obviously true or false - and we can judge their truth only outside the framework of the axiomatics we have adopted. If there are no such statements, then our axiomatics is contradictory, and within its framework there will inevitably be formulations that can be both proved and refuted.
So the formulation of Gödel's first, or weak, incompleteness theorem is: "Any formal system of axioms contains unresolved assumptions". But Gödel did not stop there, formulating and proving Gödel's second or strong incompleteness theorem: “The logical completeness (or incompleteness) of any system of axioms cannot be proved within the framework of this system. To prove or disprove it, additional axioms (strengthening of the system) are required.
It would be safer to think that Godel's theorems are abstract and do not concern us, but only areas of sublime mathematical logic, but in fact it turned out that they are directly related to the structure of the human brain. The English mathematician and physicist Roger Penrose (born 1931) showed that Gödel's theorems can be used to prove the existence of fundamental differences between the human brain and a computer. The point of his reasoning is simple. The computer operates strictly logically and is not able to determine whether statement A is true or false if it goes beyond the scope of axiomatics, and such statements, according to Gödel's theorem, inevitably exist. A person, faced with such a logically unprovable and irrefutable statement A, is always able to determine its truth or falsity - based on everyday experience. At least in this, the human brain is superior to a computer shackled by pure logical circuits. The human brain is able to understand the full depth of truth contained in Gödel's theorems, but a computer one can never. Therefore, the human brain is anything but a computer. He is able to make decisions, and the Turing test will pass.
Godel's incompleteness theorems
Godel's incompleteness theorems
Godel's incompleteness theorems- two theorems of mathematical logic on the fundamental limitations of formal arithmetic and, as a consequence, of any sufficiently strong first-order theory.
The first theorem states that if formal arithmetic is consistent, then it contains a non-derivable and irrefutable formula.
The second theorem states that if formal arithmetic is consistent, then some formula is non-derivable in it, which meaningfully asserts the consistency of this theory.
Gödel's first incompleteness theorem
The claim of Gödel's first incompleteness theorem can be stated as follows:
If formal arithmetic S is consistent, then it contains a closed formula G such that neither G nor its negation ¬G are derivable in S .In proving the theorem, Gödel constructed the formula G explicitly, sometimes it is called Gödel's unsolvable formula. In the standard interpretation, the sentence G asserts its own non-derivability in S. Therefore, by Gödel's theorem, if a theory S is consistent, then this formula is indeed non-derivable in S and therefore true in the standard interpretation. Thus, for natural numbers, the formula G is true, but is not deducible in S.
Gödel's proof can also be carried out for any theory obtained from S by adding new axioms, for example, the formula G as an axiom. Therefore, any consistent theory that is an extension of formal arithmetic will be incomplete.
To prove the first incompleteness theorem, Gödel assigned a specific number to each symbol, expression, and sequence of expressions in formal arithmetic. Since formulas and theorems are sentences of arithmetic, and formal derivations of theorems are sequences of formulas, it became possible to speak of theorems and proofs in terms of natural numbers. For example, let the Gödel unsolvable formula G has a number m, then it is equivalent to the following statement in the language of arithmetic: "there is no such natural number n, what n there is a formula derivation number with number m". Such a comparison of formulas and natural numbers is called the arithmetization of mathematics and was carried out by Gödel for the first time. This idea later became the key to solving many important problems of mathematical logic.
proof sketch
Let us fix some formal system PM in which elementary mathematical concepts can be represented.
The expressions of a formal system are, from the outside, finite sequences of primitive symbols (variables, logical constants, and brackets or dots) and it is not difficult to strictly specify which sequences of primitive symbols are formulas and which are not. Similarly, from a formal point of view, proofs are nothing but finite sequences of formulas (with strictly defined properties). For mathematical consideration, it does not matter which objects to take as primitive symbols, and we decide to use natural numbers for these purposes. Accordingly, the formula is a finite sequence of natural numbers, the derivation of the formula is a finite sequence of finite sequences of natural numbers. Mathematical concepts (statements) thus become concepts (statements) about natural numbers or their sequences, and therefore can themselves be expressed in the symbolism of the PM system (at least in part). It can be shown, in particular, that the concepts "formula", "derivation", "derivable formula" are definable within the PM system, that is, one can recover, for example, the formula F(v) in PM with one free variable v(whose type is a numeric sequence) such that F(v), in an intuitive interpretation, means: v- derivable formula. Now let us construct an undecidable sentence of the PM system, that is, the sentence A, for which neither A, nor non-A not deducible, as follows:
A formula in PM with exactly one free variable whose type is a natural number (a class of classes) will be called an expression class. Let us arrange the class-expressions in a sequence in some way, denote n-e through R(n), and note that the concept of "class-expression", as well as the ordering relation R can be defined in the PM system. Let α be an arbitrary class-expression; through [α; n] denote the formula that is formed from the class-expression α by replacing the free variable with the symbol of a natural number n. Ternary relation x = [y;z] also turns out to be definable in PM. Now we will define a class K natural numbers as follows:
n ∈ K≡ ¬Bew[ R(n);n] (*)(where Bew x means: x- derivable formula). Since all concepts occurring in this definition can be expressed in PM, the same is true for the concept K, which is built from them, that is, there is such a class-expression S that the formula [ S;n], which is intuitively interpreted, means that a natural number n belongs K. As a class expression, S identical to some particular R(q) in our numbering, that is
S = R(q)holds for some definite natural number q. Let us now show that the sentence [ R(q);q] is undecidable in PM. So, if the sentence [ R(q);q] is assumed to be derivable, then it turns out to be true, that is, in accordance with what was said above, q will belong K, that is, according to (*), ¬Bew[ R(q);q] will be satisfied, which contradicts our assumption. On the other hand, if the negation [ R(q);q] was derivable, then ¬ n ∈ K, that is, Bew[ R(q);q] will be true. Consequently, [ R(q);q] together with its negation will be derivable, which again is impossible.
Polynomial form
For every consistent theory T one can specify such an integer value of the parameter K that the equation (θ + 2 z − b 5) 2 + (u + tθ − l) 2 + (y + mθ − e) 2 + (n − q 16) 2 + ((g + eq 3 + lq 5 + (2(e − zλ)(1 + g) 4 + λ b 5+λ b 5 q 4)q 4)(n 2 − n) + (q 3 − bl + l + θλ q 3 + (b 5 − 2)q 5)(n 2 − 1) − r) 2 + (p − 2ws 2 r 2 n 2) 2 + (p 2 k 2 − k 2 + 1 − τ 2) 2 + (4(c − ksn 2) 2 + η − k 2) 2 + (r + 1 + hp − h − k) 2 + (a − (wn 2 + 1)rsn 2) 2 + (2r+ 1 + φ − c) 2 + (bw + ca − 2c+ 4αγ − 5γ − d) 2 + ((a 2 − 1)c 2 + 1 − d 2) 2 + ((a 2 − 1)i 2 c 4 + 1 − f 2) 2 + (((a + f 2 (d 2 − a)) 2 − 1)(2r + 1 + jc) 2 + 1 − (d + of) 2) 2 + (((z + u + y) 2 + u) 2 + y − K) 2 = 0 has no solutions in non-negative integers, but this fact cannot be proved in theory T . Moreover, for every consistent theory, the set of values of the parameter K that have this property is infinite and algorithmically non-enumerable.Gödel's second incompleteness theorem
In formal arithmetic S, one can construct a formula that, in the standard interpretation, is true if and only if the theory S is consistent. For this formula, the statement of Gödel's second theorem is true:
If formal arithmetic S is consistent, then it contains a non-derivable formula that substantively asserts the consistency S .In other words, the consistency of formal arithmetic cannot be proved by means of this theory. However, there are proofs of the consistency of formal arithmetic using means that are inexpressible in it.
proof sketch
First, a formula is built Con, meaningfully expressing the impossibility of deriving any formula in the theory S together with its negation. Then the statement of Gödel's first theorem is expressed by the formula Con ⊃ G, where G- Gödel's unsolvable formula. All arguments for the proof of the first theorem can be expressed and carried out by means of S, that is, in S the formula is derivable Con ⊃ G. Hence, if S is derivable Con, then we derive in it and G. However, according to Gödel's first theorem, if S is consistent, then G in it is not deducible. Therefore, if S is consistent, then the formula Con.
Notes
see also
Links
- V. A. Uspensky Godel's incompleteness theorem. - M.: Nauka, 1982. - 110 p. - (Popular lectures on mathematics).
- Academician Yu. L. Ershov "Evidence in Mathematics", A. Gordon's program of June 16, 2003
- A. B. Sosinsky Gödel's theorem // summer school "Modern Mathematics". - Dubna: 2006.
- P. J. Cohen On the foundations of set theory // Advances in Mathematical Sciences. - 1974. - T. 29. - No. 5 (179). - S. 169–176.
- M. Kordonsky End of Truth. - ISBN 5-946448-001-04
- V. A. Uspensky Gödel's incompleteness theorem and four roads leading to it // summer school "Modern Mathematics". - Dubna: 2007.
- Zenkin A. A. Time division principle and analysis of one class of quasi-finite plausible reasoning (on the example of G. Kantor's uncountability theorem) // DAN. - 1997. - T. 356. - No. 6. - S. 733-735.
- Chechulin V. L. On a short version of the proof of Gödel's theorems // "Fundamental problems of mathematics and information sciences", materials of the XXXIV Far Eastern Mathematical School-seminar named after Academician E.V. Zolotova. - Khabarovsk, Russia: 2009. - S. 60-61.
Wikimedia Foundation. 2010 .
See what "Gödel's Incompleteness Theorems" are in other dictionaries:
This term has other meanings, see Gödel's Theorem. Godel's incompleteness theorem and Godel's second theorem [1] are two theorems of mathematical logic about the fundamental limitations of formal arithmetic and, as a consequence, any ... ... Wikipedia
Gödel's incompleteness theorems are two theorems of mathematical logic on the incompleteness of formal systems of a certain kind. Contents 1 Gödel's First Incompleteness Theorem 2 Gödel's Second Incompleteness Theorem ... Wikipedia
This term has other meanings, see Gödel's Theorem. Gödel's theorem on the completeness of the predicate calculus is one of the fundamental theorems of mathematical logic: it establishes an unambiguous relationship between logical truth ... ... Wikipedia
Common name for two theorems established by K. Gödel. The first G. t. about n. claims that in any consistent formal system containing a minimum of arithmetic (signs and the usual rules for handling them), there is a formally undecidable ... ... Mathematical Encyclopedia
on the topic: "GODEL'S THEOREM"
Kurt Gödel
Kurt Gödel - the greatest specialist in mathematical logic - was born on April 28, 1906 in Brunn (now Brno, Czech Republic). He graduated from the University of Vienna, where he defended his doctoral dissertation, was an assistant professor in 1933–1938. After the Anschluss, he emigrated to the United States. From 1940 to 1963 Gödel worked at the Princeton Institute for Advanced Study. Gödel is an honorary doctorate from Yale and Harvard Universities, a member of the US National Academy of Sciences and the American Philosophical Society.
In 1951, Kurt Gödel was awarded the highest scientific award in the United States, the Einstein Prize. In an article dedicated to this event, another of the greatest mathematicians of our time, John von Neumann, wrote: “The contribution of Kurt Gödel to modern logic is truly monumental. This is more than just a monument. This is a milestone separating two eras ... It can be said without any exaggeration that Gödel's work fundamentally changed the very subject of logic as a science.
Indeed, even a dry list of Godel's achievements in mathematical logic shows that their author essentially laid the foundations for entire sections of this science: the theory of models (1930; the so-called theorem on the completeness of the narrow predicate calculus, showing, roughly speaking, the sufficiency of the means of "formal logic ”to prove all true sentences expressed in its language), constructive logic (1932–1933; results on the possibility of reducing some classes of sentences of classical logic to their intuitionistic counterparts, which laid the foundation for the systematic use of “immersing operations” that allow such a reduction of various logical systems to each other), formal arithmetic (1932–1933; results on the possibility of reducing classical arithmetic to intuitionistic arithmetic, showing in a sense the consistency of the first with respect to the second), the theory of algorithms and recursive functions (1934; definition of the concept of a general recursive function, which played a decisive role in establishing the algorithmic unsolvability of a number of important problems in mathematics, on the one hand. And in the implementation of logical and mathematical problems on electronic computers - on the other hand), axiomatic set theory (1938; proof of the relative consistency of the axiom of choice and Cantor's continuum hypothesis from the axioms of set theory, which marked the beginning of a series of important results on relative consistency and independence set-theoretic principles).
Godel's incompleteness theorem
Introduction
In 1931, a relatively small article appeared in one of the German scientific journals with a rather terrifying title "On formally undecidable propositions of Principia Mathematica and related systems." Its author was a twenty-five-year-old mathematician from the University of Vienna, Kurt Gödel, who later worked at the Princeton Institute for Advanced Study. This work played a decisive role in the history of logic and mathematics. In the decision of Harvard University to award Gödel an honorary doctorate (1952), it was characterized as one of the greatest achievements of modern logic.
However, at the time of publication, no title of Gödel's work. Neither its content said anything to most mathematicians. Mentioned in its title, Principia Mathematica is Alfred North Whitehead and Bertrand Russell's monumental three-volume treatise on mathematical logic and the foundations of mathematics; familiarity with the treatise was by no means a necessary condition for successful work in most branches of mathematics. Interest in the issues addressed in Gödel's work has always been the lot of a very small group of scientists. At the same time, the arguments given by Gödel in his proofs were so unusual for their time. That a complete understanding of them required an exclusive knowledge of the subject and familiarity with the literature devoted to these very specific problems.
First incompleteness theorem
Gödel's first incompleteness theorem seems to be the most significant result in mathematical logic. It sounds like this:
For an arbitrary consistent formal and computable theory in which basic arithmetic propositions can be proved, a true arithmetic proposition can be constructed whose truth cannot be proved within the framework of the theory. In other words, any perfectly useful theory sufficient to represent arithmetic cannot be both consistent and complete.
Here the word "theory" means "an infinite set" of statements, some of which are assumed to be true without proof (such statements are called axioms), while others (theorems) can be deduced from the axioms, and therefore are assumed (proved) to be true. The phrase "provable in theory" means "deduced from the axioms and primitives of the theory (constant symbols of the alphabet) using standard (first-order) logic." A theory is consistent (consistent) if it is impossible to prove a contradictory statement in it. The phrase "can be built" means that there is some mechanical procedure (algorithm) that can build a statement based on axioms, primitives and first-order logic. "Elementary arithmetic" is the presence of operations of addition and multiplication over natural numbers. The resulting true but unprovable proposition is often referred to for a given theory as the "Gödel sequence," but there are an infinite number of other propositions in the theory that have the same property of being unprovable within the theory.
The assumption that a theory is computable means that it is in principle possible to implement a computer algorithm (computer program) that (if allowed to compute arbitrarily long times, up to infinity) will compute a list of all the theorems of the theory. In fact, it is sufficient to compute only the list of axioms, and all theorems can be efficiently derived from such a list.
The first incompleteness theorem was titled "Theorem VI" in Gödel's 1931 paper. On Formally Undecidable Propositions in Principia Mathematica and Related Systems I. In Gödel's original recording, it sounded like this:
“The general conclusion about the existence of undecidable propositions is this:
Theorem VI .
For every ω-consistent recursive class k FORMULA there are recursive SIGNS r such that neither (v Gen r), nor ¬( v Gen r)do not belong to Flg (k)(where v is FREE VARIABLE r ) ».
Designation Flg comes from him. Folgerungsmenge- set of sequences, Gen comes from him. generalization- generalization.
Roughly speaking, Gödel's statement G asserts: "truth G cannot be proven." If G could be proved within the theory, then the theory would contain a theorem that contradicts itself, and therefore the theory would be inconsistent. But if G unprovable, then it is true, and therefore the theory is incomplete (the statement G not deducible in it).
This explanation is in ordinary natural language, and therefore not quite mathematically rigorous. To provide a rigorous proof, Gödel numbered statements with natural numbers. In this case, the theory describing numbers also belongs to the set of propositions. Questions about the provability of propositions can be represented in this case in the form of questions about the properties of natural numbers, which must be computable if the theory is complete. In these terms, Gödel's statement says that there is no number with some definite property. A number with this property will be proof of the inconsistency of the theory. If such a number exists, the theory is inconsistent, contrary to the original assumption. So assuming that the theory is consistent (as the premise of the theorem suggests), it turns out that there is no such number, and Gödel's statement is true, but this cannot be proved within the framework of the theory (hence the theory is incomplete). An important conceptual note is that one must assume that a theory is consistent in order to declare Gödel's statement to be true.
Gödel's second incompleteness theorem
Gödel's second incompleteness theorem reads as follows:
For any formally recursively enumerable (i.e. effectively generated) theory T, including basic arithmetic truth statements and certain formal provability statements, a given theory T includes a statement about its consistency if and only if the theory T is inconsistent.
In other words, the consistency of a sufficiently rich theory cannot be proved by means of this theory. However, it may well turn out that the consistency of one particular theory can be established by means of another, more powerful formal theory. But then the question arises of the consistency of this second theory, and so on.
Many have tried to use this theorem to prove that intelligent activity cannot be reduced to calculations. For example, back in 1961, the famous logician John Lucas came up with a similar program. His reasoning turned out to be quite vulnerable - however, he set the task more broadly. Roger Penrose takes a slightly different approach, which is presented in the book completely, "from scratch".
Discussions
The consequences of theorems affect the philosophy of mathematics, especially those formalisms that use formal logic to define their principles. One can rephrase the first incompleteness theorem as follows: it is impossible to find a comprehensive system of axioms that would be able to prove all mathematical truths, and not a single lie". On the other hand, from the point of view of strict formality, this reformulation does not make much sense, since it assumes the concepts of "true" and "false" are defined in an absolute sense, rather than in a relative one for each specific system.
