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, 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 tasks, the answer to which seems obvious until you dig a little deeper. talking modern language, that 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.
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), she was characterized as one of greatest achievements 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 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) which (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 particular system.
Uspensky V.A.
Gödel's incompleteness theorem. 1994.
Theoretical Computer Science 130,1994, pp.273-238.
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 who among 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 can be no universal criterion of truth even for relatively
narrow area of number theory, and hence for any science that uses
arithmetic. Naturally, this result applies a fortiori to the concept of truth
in any non-mathematical field of knowledge in which it is widely
arithmetic is 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 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.
We will not give the most general possible definition of a language, preferring to confine ourselves to those language 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 the 10-letter alphabet, whose letters are signs: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. To denote alphabets, we will use ordinary capital letters. 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 proposal in English, as well as any text written in English, can be considered as a word of the extended alphabet of 54 letters, which also includes punctuation marks, interword space, a red line sign, 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, proof 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 won't try to give precise definition this simultaneously "naive" and "absolute" concept of proof, or - which is equivalent - to define the corresponding subset 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, which 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 require that for each such conception of a proof there exists effective 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 ( exact value words "algorithm calculates a function" the following: the values of the function 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.
A triple that satisfies conditions (1)-(3) is called a deductive system over the alphabet L.
For the reader familiar with in the usual way definition of "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 any number of deductive systems that have very few provable words. For example, in an empty deductive system (where P = ?) there are no words at all that would have proofs.
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 a 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 with respect to the fundamental pair, it is impossible to find such a deductive system.
1.6. completeness
It is said that a deductive system is complete with respect to a fundamental pair, provided that ?(P)?T. Then our formulation of the incompleteness theorem takes the following form:
Under certain conditions with respect to the fundamental pair, there is no such deductive system over L that would be both complete and relatively consistent.
Theorems of mathematical logic, showing the impossibility of complete formalization of arithmetic, as well as stronger mathematical theories. Proved and published by Austrian. mathematician K. Gödel in 1931. The first theorem is closely related to the phenomenon of algorithm, undecidability, the second is a much more subtle statement about formal systems. The content of the first incompleteness theorem (if we confine ourselves to arithmetic for the time being) is as follows. Let A be an arithm. formal system containing Peano's axioms (see Arithmetic
formal). It is assumed that A correctly describes arithmetic, i.e., that all f-ly deducible in A are true statements about natural numbers. For any such system A, Gödel's first theorem states that not all true f-s of arithmetic are provable in A. In other words, the notion of the truth of f-l of arithms. language is broader than the concept of provability in any formal system (if the latter is correct). Below is an intuitive idea of the proof of this theorem, which is essential for understanding the content of both incompleteness theorems.
Assume the opposite, i.e., that arithm. truth coincides with provability in A. Since proofs in system A are finite sequences of f-l connected by rules of inference, the test of whether a given fl sequence proof, is done with quite simple algorithm. With suitable encoding, this algorithm can be described in arithm. language (see Arithmetization of Metamathematics). Therefore, you can build an arithm. f-lu, meaning that x is the code of a f-ly provable in A. Now it is not difficult to write a f-lu - let's call it v, which expresses its own unprovability. More precisely, for this f-ly in the system A, the equivalence is provable:
where is the f-ly code. By virtue of the assumption that provability coincides with truth, we obtain that it also expresses its own falsity. But then this formula can be neither true nor false, so that we arrive at the well-known "liar's paradox". Therefore, truth and provability do not coincide. An example of a true, but unprovable in A f-ly is precisely the f-la; it is true, since it asserts its unprovability and is, in fact, unprovable.
The above heuristic considerations essentially use the assumption that only true formulas are provable in A. A more rigorous study shows, however, that unprovability can be deduced from a weaker assumption about the consistency of system A. This refinement is of a fundamental nature. The fact is that the concept of arithm. truth is inexpressible in the language of arithmetic, while the assertion of the consistency of A can be written as a rather simple arithm. f-ly. Thanks to this, the first incompleteness theorem can be expressed in the language of arithmetic using the formula:
It can be shown that this function is itself derivable from Peano's axioms. From this one easily obtains Gödel's second incompleteness theorem, which states (loosely) that the consistency of a formal system A cannot be proved by means of this system. More strictly, if the formal system A is consistent and contains Peano's axioms, then the formula is unprovable in . Indeed, from the provability of f-l (1) and (2) it follows that the formulas and are equivalent in the system A. But it is not provable in A, according to Gödel's first theorem; which means it is also unprovable.
So far, we have only dealt with arithmetic. But all the previous considerations are also applicable to rather arbitrary formal systems. In particular, it is not at all necessary that the language of system A be the language of elementary arithmetic. The only thing that is required here is that the main. the concepts of arithmetic were expressible in the language of the formal system under consideration, and Peano's axioms were provable in this system. Therefore, Gödel's theorems apply to any reasonable axiomatization of arithmetic, analysis, or sets of theory.
Incompleteness theorems reveal one specific difficulty related to consistency proofs. Its essence is most conveniently illustrated by the example of the theory of mn-v. Let ZF be a formal system of the theory of polynomials based on the axioms of Tser-melo-Frenkel. So far there is no consistency proof for ZF. However, it can be said in advance that such a proof must satisfy the following two requirements (of which the first is due to the very formulation of the question, and the second follows from Gödel's theorem): a) this proof must rely only on concepts that are intuitively simpler than those used in the theory of plurals itself; b) it cannot be carried out within the framework of the ZF system. But the ZF system is extremely broad: practically all modern mathematics is formalized in it. Therefore, it is difficult to imagine what a math would look like. proof that satisfies specified requirements. Thus, the complex problems of the foundations of mathematics are touched upon here, due to which Gödel's theorems have a certain philosophical interest.
There is an opinion that incompleteness theorems show the impossibility of mash. modeling any non-trivial forms of mental activity. Such an opinion, apparently, is devoid of sufficient grounds; G. t. about n. have the same relation to the question of machine creativity as, for example, logical paradoxes have to creativity human mind. The question of the capabilities of "machine intelligence" is debatable (see Artificial intelligence).
Lit .: Klini S.K. Mathematical logic. Per. from English. M., 1973 [bibliogr. With. 451-465); FefermanS. Arithmetization of metamathematics in a general setting. "Pundamenta mathematicae", 1960, v. 49; Lyndon P. Notes on Logic. Per. from English. M., 1968 [bibliogr. With. 123]; Arbib M. Brain, machine and mathematics. Per. from English. M., 1968 [bibliogr. With. 217-224]; Nagel E., Newman D. R. Gödel's theorem. Per. from English. M., 1970.