Gödel's theorem - history of types. Confession of a Great Logician

Gödel's incompleteness theorems

Gödel's incompleteness theorems

Gödel's incompleteness theorems- two theorems of mathematical logic about 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 an irreducible and irrefutable formula.

The second theorem states that if formal arithmetic is consistent, then it contains a certain formula that meaningfully asserts the consistency of this theory.

Gödel's first incompleteness theorem

The statement of Gödel's first incompleteness theorem can be stated as follows:

When proving the theorem, Gödel constructed the formula G explicitly, it is sometimes called the Gödelian undecidable formula. In the standard interpretation, the sentence G asserts its own irreducibility in S. Therefore, by Gödel's theorem, if a theory S is consistent, then this formula is indeed irreducible in S and therefore true in the standard interpretation. Thus, for natural numbers, the formula G is true, but not derivable in S.

Gödel's proof can 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 the formal derivations of theorems are sequences of formulas, it has become possible to talk about theorems and proofs in terms of natural numbers. For example, let the Gödelian undecidable 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 output number with number m". Such a comparison of formulas and natural numbers is called arithmetization of mathematics and was carried out for the first time by Gödel. This idea subsequently became the key to solving many important problems of mathematical logic.

Sketch of the proof

Let us fix some formal PM system in which elementary mathematical concepts can be represented.

The expressions of a formal system are, viewed from the outside, finite sequences of primitive symbols (variables, logical constants, and parentheses 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 more than finite sequences of formulas (with strictly defined properties). For mathematical consideration, it does not matter which objects we 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 conclusion 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, it is possible to restore, for example, the formula F(v) in PM with one free variable v(the type of which is a number sequence) such that F(v), in an intuitive interpretation, means: v- derived formula. Now let us construct an undecidable sentence of the PM system, that is, the sentence A, for which neither A, nor non-A non-derivable, 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's arrange the class-expressions into 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 determined 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 the class K natural numbers as follows:

(where Bew x means: x- derived formula). Since all the concepts found in this definition can be expressed in PM, the same is true for the concept K, which is constructed from them, that is, there is such an expression class S, that the formula [ S;n], intuitively interpreted, means that a natural number n belongs K. As an expression class, S identical to some specific R(q) in our numbering, that is

holds for some specific natural number q. Now we will show that the sentence [ R(q);q] 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, in accordance with (*), ¬Bew[ R(q);q] will be executed, which contradicts our assumption. On the other hand, if the negation [ R(q);q] was inferable, then ¬ n ∈ K, that is, Bew[ R(q);q] will be true. Hence, [ R(q);q] together with its negation will be deducible, which is again impossible.

Polynomial form

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:

In other words, the consistency of formal arithmetic cannot be proven by means of this theory. However, there are proofs of the consistency of formal arithmetic using means that are not expressible in it.

Sketch of the proof

First the formula is built Con, which meaningfully expresses the impossibility of deriving any formula in theory S along 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 reasoning to prove the first theorem can be expressed and carried out by means of S, that is, the formula is deducible in S Con ⊃ G. Hence, if in S is derivable Con, then it is deducible and G. However, according to Gödel's first theorem, if S is consistent, then G is not deducible in it. Consequently, if S is consistent, then the formula in it is also irreducible Con.

Notes

See also

Links

• V. A. Uspensky Gödel's incompleteness theorem. - M.: Nauka, 1982. - 110 p. - (Popular lectures on mathematics).
• Academician Yu. L. Ershov "Proof in mathematics", A. Gordon program dated 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). - pp. 169–176.
• M. Kordonsky The end of truth. - ISBN 5-946448-001-04
• V. A. Uspensky Gödel's theorem on incompleteness and four roads leading to it // Summer school “Modern mathematics”. - Dubna: 2007.
• Zenkin A. A. The principle of time division and analysis of one class of quasi-finite plausible reasoning (using the example of G. Cantor’s theorem on uncountability) // DAN. - 1997. - T. 356. - No. 6. - P. 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. - P. 60-61.

Wikimedia Foundation. 2010.

See what “Gödel’s Theorems on Incompleteness” are in other dictionaries:

This term has other meanings, see Gödel's theorem. Gödel’s theorem on incompleteness and Gödel’s second theorem [1] 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 about 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 connection between logical truth... ... Wikipedia

Common name for two theorems established by K. Gödel. First G. t. about n. states 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

One of the most famous theorems in mathematical logic is lucky and unlucky at the same time. In this it is similar to Einstein's special theory of relativity. On the one hand, almost everyone has heard something about them. On the other hand, in the popular interpretation, Einstein’s theory, as is known, “says that everything in the world is relative”. And Gödel’s theorem on incompleteness (hereinafter simply TGN), in an approximately equally free folk formulation, "proves that there are things incomprehensible to the human mind". And so some try to adapt it as an argument against materialism, while others, on the contrary, prove with its help that there is no God. The funny thing is not only that both sides cannot be right at the same time, but also that neither one nor the other bothers to figure out what this theorem actually states.

So what? Below I will try to tell you about it “on the fingers”. My presentation will, of course, be non-rigorous and intuitive, but I will ask mathematicians not to judge me strictly. It is possible that for non-mathematicians (of which, in fact, I am one), there will be something new and useful in what is described below.

Mathematical logic is indeed a rather complex science, and most importantly, not very familiar. It requires careful and strict maneuvers, in which it is important not to confuse what has actually been proven with what is “already clear.” However, I hope that to understand the following “outline of a proof of TGN” the reader will only need knowledge of high school mathematics/computer science, logical thinking skills and 15-20 minutes of time.

Simplifying somewhat, TGN asserts that in sufficiently complex languages ​​there are unprovable statements. But in this phrase almost every word needs explanation.

Let's start by trying to figure out what a proof is. Let's take some school arithmetic problem. For example, let’s say you need to prove the correctness of the following simple formula: “ ” (let me remind you that the symbol reads “for any” and is called the “universal quantifier”). You can prove it by identically transforming it, say, like this:

The transition from one formula to another occurs according to certain well-known rules. The transition from the 4th formula to the 5th occurred, say, because every number is equal to itself - this is an axiom of arithmetic. And the entire proof procedure, thus, translates the formula into the Boolean value TRUE. The result could also be a LIE - if we refuted some formula. In this case, we would prove its denial. One can imagine a program (and such programs have actually been written) that would prove similar (and more complex) statements without human intervention.

Let's state the same thing a little more formally. Suppose we have a set consisting of strings of characters of some alphabet, and there are rules by which from these strings we can select a subset of the so-called statements- that is, grammatically meaningful phrases, each of which is true or false. We can say that there is a function that associates statements with one of two values: TRUE or FALSE (that is, mapping them into a Boolean set of two elements).

Let's call such a pair - a set of statements and a function from to - "language of statements". Note that in the everyday sense the concept of language is somewhat broader. For example, the Russian phrase “Come here!” neither true nor false, that is, from the point of view of mathematical logic, it is not a statement.

For what follows, we need the concept of an algorithm. I will not give a formal definition of it here - that would take us quite far astray. I will limit myself to informal: "algorithm" is a sequence of unambiguous instructions (“program”) that in a finite number of steps converts source data into results. What is in italics is fundamentally important - if the program loops on some initial data, then it does not describe the algorithm. For simplicity and in application to our case, the reader can consider that an algorithm is a program written in any programming language known to him, which, for any input data from a given class, is guaranteed to complete its work producing a Boolean result.

Let us ask ourselves: for every function there is a “proving algorithm” (or, in short, "deductive"), equivalent to this function, that is, transforming each statement into exactly the same Boolean value as it? The same question can be formulated more succinctly as follows: is every function over a set of statements computable? As you already guessed, from the validity of TGN it follows that no, not every function - there are incomputable functions of this type. In other words, not every true statement can be proven.

It is very possible that this statement will cause an internal protest in you. This is due to several circumstances. Firstly, when we are taught school mathematics, we sometimes get the false impression that the phrases “the theorem is true” and “the theorem can be proven or verified” are almost completely identical. But, if you think about it, this is not at all obvious. Some theorems are proven quite simply (for example, by trying a small number of options), while others are very difficult. Consider, for example, Fermat's famous Last Theorem:

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

The second intuitive argument against TGN is more subtle. Let's say we have some unprovable (within the framework of this deductive) statement. What prevents us from accepting it as a new axiom? Thus, we will complicate our system of evidence a little, but this is not scary. This argument would be completely correct if there were a finite number of unprovable statements. In practice, the following can happen: after postulating a new axiom, you stumble upon a new unprovable statement. If you accept it as another axiom, you will stumble upon the third. And so on ad infinitum. They say that deduction will remain incomplete. We can also force the proving algorithm to finish in a finite number of steps with some result for any utterance of the language. But at the same time, he will begin to lie - leading to the truth for incorrect statements, or to lies - for the faithful. In such cases they say that deduction contradictory. Thus, another formulation of the TGN sounds like this: “There are propositional languages ​​for which complete consistent deductiveness is impossible” - hence the name of the theorem.

Sometimes called “Gödel’s theorem,” the statement is that any theory contains problems that cannot be solved within the theory itself and require its generalization. In a sense this is true, although this formulation tends to obscure the issue rather than clarify it.

I will also note that if we were talking about familiar functions that map a set of real numbers into it, then the “non-computability” of the function would not surprise anyone (just don’t confuse “computable functions” and “computable numbers” - these are different things). Any schoolchild knows that, say, in the case of a function, you have to be very lucky with the argument in order for the process of calculating the exact decimal representation of the value of this function to be completed in a finite number of steps. But most likely you will calculate it using an infinite series, and this calculation will never lead to an exact result, although it can come as close as you like - simply because the value of the sine of most arguments is irrational. TGN simply tells us that even among functions whose arguments are strings and whose values ​​are zero or one, there are also non-computable functions, although they are structured in a completely different way.

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

Examples of formal arithmetic statements:

etc. Now let’s call a “formula with a free parameter” (FSP) a string that becomes a statement if a natural number is substituted into it as this parameter. Examples of FSP (with parameter):

etc. In other words, FSPs are equivalent to natural argument functions with Boolean values.

Let us denote the set of all FSPs by the letter . It is clear that it can be ordered (for example, first we write out one-letter formulas ordered alphabetically, followed by two-letter formulas, etc.; it is not important to us which alphabet the ordering will take place). Thus, any FSP corresponds to its number in the ordered list, and we will denote it .

Let us now move on to a sketch of the proof of TGN in the following formulation:

• For the propositional language of formal arithmetic there is no complete consistent deductive system.

We will prove it by contradiction.

So, let's assume that such a deductive system exists. Let us describe the following auxiliary algorithm, which assigns a Boolean value to a natural number as follows:

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

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

It is obvious that, under the assumption made above, any FSP can be compared to an algorithm containing a natural number at the input and a Boolean value at the output. The converse is less obvious:

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

Having passed this slippery place, we quickly reach the end.

So, above we described the algorithm. According to the lemma I asked you to believe, there is an equivalent FSP. It has some number in the list - say, . Let's ask ourselves, what is equal to? Let this be the TRUTH. Then, according to the construction of the algorithm (and therefore the function equivalent to it), this means that the result of substituting a number into the function is FALSE. The opposite is checked in the same way: from FALSE follows TRUE. We have reached a contradiction, which means that the original assumption is incorrect. Thus, there is no complete consistent deductive system for formal arithmetic. Q.E.D.

Here it is appropriate to recall Epimenides (see the portrait in the title), who, as is known, declared that all Cretans are liars, himself being a Cretan. In a more succinct formulation, his statement (known as the “liar paradox”) can be stated as follows: “I am lying.” It is precisely such a statement, which itself proclaims its falsity, that we used for proof.

In conclusion, I want to note that TGN does not claim anything particularly surprising. In the end, everyone has long been accustomed to the fact that not all numbers can be represented as a ratio of two integers (remember, this statement has a very elegant proof that is more than two thousand years old?). And not all numbers are roots of polynomials with rational coefficients either. And now it turns out that not all functions of a natural argument are computable.

The sketch of the proof given was for formal arithmetic, but it is easy to see that TGN is applicable to many other propositional languages. Of course, not all languages ​​are like this. For example, let's define a language as follows:

• “Any phrase in the Chinese language is a true statement if it is contained in the quotation book of Comrade Mao Zedong, and incorrect if it is not contained.”

Then the corresponding complete and consistent proving algorithm (one might call it “dogmatic deductive”) looks something like this:

• “Flip through the quotation book of Comrade Mao Zedong until you find the saying you are looking for. If it is found, then it is true, but if the quotation book is over and the statement is not found, then it is incorrect.”

What saves us here is that any quotation book is obviously finite, so the process of “proving” will inevitably end. Thus, TGN is not applicable to the language of dogmatic statements. But we were talking about complex languages, right?

Any system of mathematical axioms, starting from a certain level of complexity, is either internally contradictory or incomplete.

In 1900, the World Conference of Mathematicians was held in Paris, at which David Hilbert (1862–1943) presented in the form of theses the 23 most important, in his opinion, problems that theoreticians of the coming twentieth century had to solve. Number two on his list was one of those simple problems whose answer seems obvious until you dig a little deeper. In modern terms, this was the question: is mathematics self-sufficient? Hilbert's second task boiled down to the need to strictly prove that the system of axioms - basic statements accepted in mathematics as a basis without proof - is perfect and complete, that is, it allows one to mathematically describe everything that exists. It was necessary to prove that it was possible to define such a system of axioms that they would, firstly, be mutually consistent, and secondly, from them a conclusion could be drawn 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 proven beyond doubt 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. Essentially speaking, in Euclidean geometry any statement is either false or true, and there is no third option. 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 bespectacled Viennese mathematician Kurt Gödel published a short article that simply upset the entire world of so-called “mathematical logic.” After long and complex mathematical and theoretical preambles, he established literally the following. Let’s take any statement like: “Assumption No. 247 in this system of axioms is logically unprovable” and call it “statement A.” So, Gödel simply proved the following amazing property of any system of axioms:

“If statement A can be proven, then statement not-A can be proven.”

In other words, if the truth of the statement “assumption 247 is unprovable” can be proven, then the truth of the statement “assumption 247 is provable” can also be proven. That is, returning to the formulation of Hilbert’s second problem, if a system of axioms is complete (that is, any statement in it can be proven), then it is contradictory.

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 accepted. If there are no such statements, then our axiomatics are contradictory, and within its framework there will inevitably be formulations that can be both proven and disproved.

So, the formulation of Gödel's first, or weak, incompleteness theorem: “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 proven within the framework of this system. To prove or disprove it, additional axioms are required (strengthening the system).”

It would be safer to think that Gödel’s theorems are abstract in nature 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. English mathematician and physicist Roger Penrose (b. 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 meaning of his reasoning is simple. The computer acts strictly logically and is not able to determine whether statement A is true or false if it goes beyond the 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 respect the human brain is superior to a computer constrained by pure logical circuits. The human brain is capable of understanding the full depth of truth contained in Gödel's theorems, but a computer brain never can. Therefore, the human brain is anything but a computer. He is capable of making decisions and will pass the Turing Test.

I wonder if Hilbert had any idea how far his questions would take us?

Kurt GÖDEL
Kurt Godel, 1906–78

Austrian, then American mathematician. Born in 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 - professor). In 1931 he published a theorem that later received his name. Being a purely apolitical person, he had an extremely hard time with the murder of his friend and department colleague by a Nazi student and fell into a deep depression, relapses of which haunted him for the rest of his life. In the 1930s he emigrated to the USA, 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. He worked for some time at the Princeton Institute for Advanced Study. Unfortunately, the scientist’s psyche could not stand it, and he died in a psychiatric clinic from hunger, refusing to eat, because he was convinced that they were going to poison him.

How does a scientific model develop in the natural sciences? Everyday or scientific experience is accumulated, its milestones are carefully formulated in the form of postulates and form the basis of the model: a set of statements accepted by everyone who works within the framework of this model.

Anatoly Wasserman

In 1930, Kurt Gödel proved two theorems that, translated from mathematical language into human language, mean approximately the following: Any system of axioms rich enough to be used to define arithmetic will either be incomplete or contradictory. Not a complete system - this means that in the system it is possible to formulate a statement that cannot be either proven or disproved by means of this system. But God, by definition, is the final cause of all causes. From the point of view of mathematics, this means that the introduction of the axiom about God makes our entire axiomatics complete. If there is a God, then any statement can either be proven 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 entire world would crumble from these contradictions, we have 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 discoveries 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 significance? These questions are addressed in his lecture within the framework of the project “Public Lectures “Polit.ru”” by Alexey Bronislavovich Sosinsky, mathematician, professor at the Independent Moscow University, officer of the Order of Academic Palms of the French Republic, laureate of the Russian Government Prize in the field of education in 2012. In particular, several different formulations of it were given, three approaches to its proof were described (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 at the summer school “Modern Mathematics”, Dubna.

I admit that I read the very idea of ​​​​considering the question of the existence of God from this side from Anatoly Aleksandrovich Wasserman:
http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D1%82%D0%BE%D0%BB%D0%B8%D0%B9_%D0%90%D0 %BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87_%D0%92 %D0%B0%D1%81%D1%81%D0%B5%D1%80%D0%BC%D0%B0%D0%BD#.D0.A0.D0.B5.D0.BB.D0.B8. D0.B3.D0.B8.D0.BE.D0.B7.D0.BD.D1.8B.D0.B5_.D0.B2.D0.B7.D0.B3.D0.BB.D1.8F.D0. B4.D1.8B

But I would like to develop this idea and describe it in a little more detail.
In religion (as well as in non-religion) there is a certain axiomatics of construction. At least in an ideal case, if this is not just a blind belief, but a conscious and informed choice. For example, an axiom of physics can be considered “nature is knowable through reason and logical conclusions, all laws of physics are the same at all points in space and at any time.” For example, the axiom of religion can be considered the statement “God exists and is the first cause of all things.” In other words, there is no doubt that all the numerous particulars and branches can be reduced to several important, unprovable statements, which are those very axioms.

Let us consider religious beliefs from these positions. The most important axiom of religion: “God exists and is the first cause of all things.”
Now let's remember one of the most important mathematical theorems, Gödel's theorem.
http://elementy.ru/trefil/21142
Weak Gödel's theorem: "Any formal system of axioms contains unresolved assumptions" or "if a system of axioms is complete, then it is inconsistent."
Gödel's strong theorem: "The logical completeness (or incompleteness) of any system of axioms cannot be proven within the framework of this system. To prove or disprove it, additional axioms are required (strengthening the system)."

Let's remember some definitions. A system of axioms is complete if any statement formulated for a given system of axioms is provable (that is, it is either true or false). An unresolved assumption is a statement about which neither its truth nor falsity can be proven, that is, the statement is not logically provable. A system of axioms is contradictory if one and the same statement can be proven to be both true and false.

From Gödel’s theorem it follows that if the concept of God is included in an axiomatic system, then this system is not complete, that is, there are consequences (phenomena) that are not provable, that is, they may or may not exist, this is not provable.
But this contradicts the following two provisions (choose whichever is most convincing): nature does not contain phenomena that can be considered both existing and non-existent; any natural phenomenon either exists or does not exist. The second position says that, by definition, God is the root cause of everything, therefore God either leads to the existence of certain things (statements) or to their non-existence, referring to God can either prove or disprove any statement. This contradicts the incompleteness of the system.

Or else. If you include the concept of God in the axiomatic system and assume it is complete (any statement in a complete system of axioms is provable), then according to Gödel’s theorem such a system of axioms will be contradictory, that is, there will be phenomena about which it can be proven that they both exist and do not exist.

There is no point in including God in a contradictory system of axioms, since it is contradictory, that is, it contains phenomena that can be proven to both exist and not exist, which, as stated, contradicts the nature and concept of God.

Finally, if the concept of God is not included in the axiomatic system, then it cannot be considered the fundamental basis of the universe, from which everything that exists follows, which essentially contradicts the definition of God.

For the validity of this proof, it is necessary to recognize the validity of the laws of mathematical logic (propositional logic + predicate calculus), which make it possible to establish the laws of consequence, truth, falsity, inconsistency, consistency of statements and other properties and relationships between statements.

If we assume that mathematical logic is not applicable to the study of the question of the existence of God, then the consequence will be that it is not possible to study this question with the help of reasoning, with the help of reason. In other words, consistent reason always comes to a negative answer to the question of the existence of God.

What happens in the end... any even remotely rational person, of course, recognizes the validity of the laws of logic, which means he invariably comes to the conclusion that God in the definition of “the cause of all things” does not exist. A non-rational person who claims that God can be known only through feelings (and not reason), of course, can say so, but there is no way to convince another of this; feelings cannot be conveyed. Moreover, the concept of God is a concept formulated by reason. How it is proposed to translate the concept of reason into sensation, and even in such a way that it can be conveyed to another person, is not clear. Again, even a somewhat rational person will say that this is not possible: to translate the abstract concept of reason into feeling and feel it.

Finally, there is another option: “God is not the first cause of everything.” Then such contradictions do not arise, however, this is a significant weakening of the position of religion, since it is precisely the fact that God created everything, that God is the beginning of all beginnings, that is the foundation for numerous statements of religion and justifications in disputes.

P.S. It is worth noting one more curious thing, interesting for physicists. This definition of God says nothing about his rationality. That is, one could add “God is the rational cause of all things,” but this is a narrowing of the definition, which is not initially required for proof. Without rationality, the concept of “god” can easily be replaced with “the singularity and the big bang are the cause of all things.” And the answer will be the same: the singularity and the big bang are not the root cause of everything that exists.
Carrying out even greater abstraction, we can say that not a single phenomenon or cause can be the root cause of all things, that is, the root cause does not exist in principle. Reasoning within the framework of any axiomatics, one can come to the conclusion that the root cause of everything does not exist. To put it very simply, no matter how fundamentally we understand the universe, questions will always remain in the spirit of: “where did the big bang come from, where did the singularity come from, where did the pulsating universe come from, where did the multiverse come from, why does the universe always exist?” etc. The root cause of everything cannot be found in principle; it is not contained in any object, phenomenon or concept. Therefore, for a person this is equivalent to its absence. Theoretically, one can assume the existence of an outside observer outside our universe, who will answer the question of where everything came from (that same additional axiom, an extension in Gödel’s theorem), but then the question will arise where the outside observer, his universe and the root cause of all this came from.

The idea of ​​proof is to construct an expression that would indicate its

own unprovability. This construction can be done in three stages:

The first stage is the establishment of a correspondence between formal arithmetic and the set of integers (Goedelization);

The second stage is the construction of some special property about which it is unknown whether it is a theorem of formal arithmetic or not;

The third stage is the substitution in place of x of a certain integer associated with itself, i.e., replacement of all with these numbers

First stage. Gedelization of formal arithmetic

Formal arithmetic can be arithmetized (i.e., Godelized) in the following way: each of its theorems is associated with a certain number. However, since every number is also a theorem, then every theorem can be considered, on the one hand, as a theorem of formal arithmetic, and on the other, as a theorem over the set of theorems of formal arithmetic, i.e., as a metatheorem corresponding to the proof of a certain theorem.

Thus, we can conclude that the system of formal arithmetic also contains its own metasystem.

Now we will present the results obtained more specifically and in detail.

Firstly, we can associate with each symbol and formal arithmetic a special code designation, called in this case a Gödel number

Secondly, we associate each sequence of symbols with the same Gödel number using some composition function. Let where represent the sequences of symbols that form

Thirdly (and this is essential), each proof of a sequence of axioms and substitution rules (or substitution rules) is associated with a number where denotes the sequence of theorems used in the proof

Thus, every proof in formal arithmetic corresponds to a certain number - its Gödel number. Any reasoning in formal arithmetic is transformed into calculations on the set of natural numbers.

So, instead of manipulating symbols, theorems, and proofs, you can use

calculations on a set of integers. Any expression like, for example, the following: “provable in formal arithmetic” now corresponds to a certain number, which we will denote as

Let us formulate the following position.

Formal metaarithmetic is contained in the set of natural numbers, which itself is contained in the interpretation of formal arithmetic.

This situation with formal arithmetic is reminiscent of the situation with natural language: after all, nothing prevents us from using it in order to formulate its basic concepts and rules in it.

The proper choice of function allows for an unambiguous transition from A to, i.e., assigning two different numbers to two different proofs. For example, one can choose the Gödel numbers in such a way that each symbol of the alphabet of formal arithmetic corresponds to its own prime number, as shown, for example, in Table. 3.2.

Table 3.2

Each formula (consisting of symbols varying from 1 to is in turn encoded by a sequence consisting of the first prime numbers, i.e. the number

where is a prime number.

In turn, the proof, i.e. the sequence of formulas will be encoded in a similar way with the number

And vice versa, thanks to this method of constructing numbers, it becomes possible, starting from a certain number, using its decomposition into prime factors (due to the uniqueness of the decomposition of natural numbers into products of powers of prime numbers), to return in two steps to exponents, i.e. to primitive symbols formal arithmetic. Of course, this is mostly only theoretical, since the numbers quickly become too large

so that they can be manipulated. However, it should be noted that the fundamental possibility of this operation is essential.

Example. Let a number T be given, corresponding to some proof and representing a product of prime numbers:

This expansion means that the proof of the theorem contains two stages: one corresponding to the number 1981027125 253, and the other to the number 1981027125 211. Factoring each of these numbers again into prime factors, we get

From the alphabet coding table of formal arithmetic (Table 3.2) we find that our Gödel numbers for these two numbers

the following proof will correspond:

From the formula follows the formula

Thus, in metaarithmetic, the value of the original number is obtained from formal arithmetic.

Second stage. Gödel's Lemma

Every number T associated with a proof corresponds to a theorem provable in formal arithmetic. “Goedelized” formal arithmetic is called arithmetized formal arithmetic. Since each axiom and each rule of arithmetized formal arithmetic corresponds to some arithmetic operation, then using a systematic test it is possible to determine whether a given number T corresponds to the proof of some theorem. Numbers T and in this case form a pair of conjugate numbers. The expression and are conjugate” Presentable within the arithmetized formal arithmetic itself. This means that there is a Gödel number that digitally expresses this statement.

We have reached the critical point of Gödel's proof. Let A be an expression of arithmetized formal arithmetic that contains some free variable. Instead, you can substitute some term. In particular, you can replace expression A with expression A itself. In this case, the number-expression A simultaneously performs two different roles (see above construction

Cantor and Richard): it is both a true expression for substitution and a resulting term. We will denote this special substitution as So the formula means that the number is the Gödel number obtained by performing the substitution - to expression A:

Gödel then constructs an expression (which is unknown whether it is a theorem or a non-theorem) into which he introduces this substitution. The expression looks like this:

Third stage. Final substitution

In arithmetized formal arithmetic, this expression is represented in digital form. Let E be its Gödel number. Since the expression contains a free variable, we have the right to perform a substitution - over replacing the number E and denoting - the substitution E:

We denote this second expression by a and its Gödel number by E. Let us give interpretations of the expression e.

First interpretation. There is no such pair for which the following would simultaneously hold: on the one hand, T is the number of the arithmetized proof of the theorem arithmetized by itself, and on the other hand, there would be a substitution. But since there is the same transformation as the others, it is representable in terms and in their code designations - Gödel numbers and, therefore, such a number exists. Then maybe the T number doesn't exist.

Second interpretation. There is no arithmetized proof of the T theorem that would be a -replacement of E. So, if there is no proof, it is because it itself is not a theorem. This leads to the third interpretation.

Third interpretation. An expression for which the Gödel number is -substitution E is not a theorem of arithmetized formal arithmetic. But this is where the contradiction lies, since by construction it is itself that is a -substitution for E and the number is, by construction, nothing other than the number E itself. From here follows the final interpretation of e.