Kurt Gödel's incompleteness theorems were a turning point in 20th-century mathematics. And in his manuscripts, published after his death, a logical proof of the existence of God was preserved. At the last Christmas readings interesting report Associate Professor of the Tobolsk Theological Seminary, Candidate of Theology Priest Dimitry KIRYANOV spoke about this little-known heritage. “NS” asked to explain the scientist’s main ideas.
Gödel's Incompleteness Theorems: A Hole in Mathematics
— Is there any popular way to explain Gödel’s incompleteness theorems? The barber shaves only those who do not shave themselves. Does a barber shave himself? This famous paradox does it have anything to do with them?
The main thesis of the logical proof of the existence of God, put forward by Kurt Gödel: “God exists in thought. But existence in reality is more than existence only in thought. Therefore, God must exist.” In the photo: the author of the incompleteness theorem, Kurt Gödel, with his friend, the author of the theory of relativity, Albert Einstein. Priston. America. 1950
- Yes, of course it does. Before Gödel, there was the problem of axiomatization of mathematics and the problem of such paradoxical sentences that can be formally written in any language. For example: “This statement is false.” What is the truth of this statement? If it is true, then it is false, if it is false, then it is true; This results in a linguistic paradox. Gödel studied arithmetic and showed in his theorems that its consistency cannot be proven based on its self-evident principles: the axioms of addition, subtraction, division, multiplication, etc. We require some additional assumptions to justify it. This is on the most the simplest theory, but what about more complex ones (physics equations, etc.)! To justify any system of inferences, we are always forced to resort to some additional inference, which is not justified within the framework of the system.
First of all, this indicates the limitations of claims human mind in the knowledge of reality. That is, we cannot say that we will build some kind of comprehensive theory of the universe that will explain everything - such a theory cannot be scientific.
— How do mathematicians now feel about Gödel’s theorems? Is no one trying to refute them or somehow get around them?
“It’s like trying to disprove the Pythagorean theorem.” The theorems have strict logical proof. At the same time, attempts are being made to find restrictions on the applicability of Gödel's theorems. But mainly the debate revolves around the philosophical implications of Gödel's theorems.
— How far has Gödel’s proof of the existence of God been developed? Is it finished?
“It was worked out in detail, although the scientist himself did not dare to publish it until his death.” Gödel develops ontological (metaphysical. - "NS") argument first proposed by Anselm of Canterbury. In a condensed form this argument can be presented in the following way: “God, by definition, is the One greater than whom nothing can be conceived. God exists in thinking. But existence in reality is more than existence only in thought. Therefore, God must exist." Anselm's argument was later developed by René Descartes and Gottfried Wilhelm Leibniz. Thus, according to Descartes, to think of the Supreme Perfect Being, which lacks existence, means falling into a logical contradiction. In the context of these ideas, Gödel develops his version of the proof; it fits literally on two pages. Unfortunately, it is impossible to present his argument without introducing the basics of very complex modal logic.
Of course, the logical flawlessness of Gödel's conclusions does not force a person to become a believer under the pressure of the force of evidence. We should not be naive and believe that we can convince anyone intelligently thinking man to believe in God using an ontological argument or other evidence. Faith is born when a person comes face to face with the obvious presence of the supreme transcendental Reality of God. But we can name at least one person whom the ontological proof led to religious faith, - this is the writer Clive Staples Lewis, he himself admitted this.
The distant future is the distant past
— How did contemporaries treat Gödel? Was he friends with any of the great scientists?
— Einstein's assistant at Princeton testifies that the only person, with whom he was friends in last years life, was Kurt Gödel. They were different in almost everything - Einstein was sociable and cheerful, while Gödel was extremely serious, completely lonely and distrustful. But they had overall quality: both walked directly and sincerely towards central issues science and philosophy. Despite his friendship with Einstein, Gödel had his own specific view of religion. He rejected the idea of God as an impersonal being, as God was for Einstein. On this occasion, Gödel remarked: “Einstein’s religion is too abstract, like Spinoza’s and Indian philosophy. Spinoza's God is less than a person; my God is more than a person; since God can play the role of personality.” There may be spirits that do not have a body, but can communicate with us and influence the world."
— How did Gödel end up in America? Fled from the Nazis?
— Yes, he came to America in 1940 from Germany, despite the fact that the Nazis recognized him as an Aryan and a great scientist, freeing him from military service. He and his wife Adele made their way through Russia along the Trans-Siberian Railway. He left no memories of this journey. Adele only remembers constant fear at night, that they will stop and return back. After eight years of living in America, Gödel became a US citizen. Like all applicants for citizenship, he had to answer questions regarding the American Constitution. Being a scrupulous person, he prepared for this exam very carefully. Finally he said that he had found an inconsistency in the Constitution: “I have discovered a logically legitimate possibility in which the United States can become a dictatorship.” His friends recognized that, regardless of the logical merits of Gödel's argument, this possibility was purely hypothetical in nature, and warned against talking at length about this topic in the exam.
— Did Gödel and Einstein use each other’s ideas in scientific work?
— In 1949, Gödel expressed his cosmological ideas in a mathematical essay, which, according to Albert Einstein, was an important contribution to the general theory of relativity. Gödel believed that time - "that mysterious and at the same time self-contradictory essence that forms the basis of the world and our own existence" - would eventually become the greatest illusion. It “someday” will cease to exist, and another form of existence will come, which can be called eternity. This idea of time led the great logician to an unexpected conclusion. He wrote: “I am convinced of an afterlife, regardless of theology. If the world is intelligently designed, then there must be an afterlife."
- “Time is a self-contradictory entity.” Sounds strange; it has some physical meaning?
— Gödel showed that within the framework of Einstein’s equation it is possible to construct a cosmological model with closed time, where the distant past and the distant future coincide. In this model, time travel becomes theoretically possible. It sounds strange, but it is mathematically expressible - that's the point. This model may or may not have experimental implications. It is a theoretical construct that may be useful in constructing new cosmological models—or may turn out to be unnecessary. Modern theoretical physics, in particular quantum cosmology, has such a complex mathematical structure that these structures are very difficult to give an unambiguous philosophical understanding. Moreover, some of its theoretical designs are so far untestable experimentally for the simple reason that their verification requires the detection of very high-energy particles. Remember how people were alarmed about the launch of the Large Hadron Collider: means mass media constantly frightened people with the approaching end of the world. In fact, it was taken seriously scientific experiment on model checking quantum cosmology and the so-called “grand unified theories”. If it were possible to detect the so-called Higgs particles, this would be the next step in our understanding of the most early stages existence of our Universe. But while there is no experimental data, competing models of quantum cosmology continue to remain simply mathematical models.
Faith and intuition
— “...My God is more than a person; since God can play the role of a person...” Still, Gödel’s faith is far from the Orthodox confession?
— Very few of Gödel’s statements about his faith have survived; they have been collected bit by bit. Despite the fact that the first drafts own version Gödel made this argument back in 1941; until 1970, fearing ridicule from his colleagues, he did not talk about it. In February 1970, sensing death was approaching, he allowed his assistant to copy a version of his proof. After Gödel's death in 1978, a slightly different version of the ontological argument was discovered in his papers. Kurt Gödel's wife, Adele, said two days after her husband's death that Gödel, "although he did not attend church, was religious and read the Bible in bed every Sunday morning."
When we talk about scientists like Gödel, Einstein or, say, Galileo or Newton, it is important to emphasize that they were not atheists. They saw that behind the Universe there is a Mind, a kind of Higher Power. For many scientists, the belief in the existence Supreme Intelligence was one of the consequences of their scientific reflection, and this reflection did not always lead to the emergence of a deep religious connection between man and God. In relation to Gödel, we can say that he felt the need for this connection, since he emphasized that he was a theist and thought of God as a person. But, of course, his faith cannot be called orthodox. He was, so to speak, a “home Lutheran.”
- You can give historical examples: how do different scientists come to believe in God? Here is the geneticist Francis Collins, according to his confessions, the study of the structure of DNA led him to faith in God...
— Natural knowledge of God in itself is not sufficient for knowledge of God. It is not enough to discover God by studying nature; it is important to learn to know Him through the Revelation that God gave to man. A person's coming to faith, whether he is a scientist or not, always relies on something that goes beyond just logical or scientific arguments. Francis Collins writes that he came to faith at age 27 after a long intellectual debate with himself and under the influence of Clive Staples Lewis. Two people are in the same historical situation, in the same initial conditions: one becomes a believer, the other an atheist. For one, the study of DNA leads to the belief in the existence of God. Another studies and does not come to this conclusion. Two people look at a picture: one thinks it’s beautiful, and the other says: “So-so, an ordinary picture!” One has taste, intuition, and the other does not. Professor of Orthodox St. Tikhon's humanitarian university Vladimir Nikolaevich Katasonov, doctor philosophical sciences, a mathematician by training, says: “No proof in mathematics is possible without intuition: the mathematician first sees the picture, and then formulates the proof.”
The question of a person’s coming to faith is always a question that goes beyond just logical reasoning. How can you explain what led you to faith? The man answers: I went to the temple, thought, read this and that, saw the harmony of the universe; but the most important, the most exceptional moment in which a person suddenly knows that he has encountered the presence of God cannot be expressed. It's always a mystery.
- You can identify problems that you cannot solve modern science?
— After all, science is a sufficiently confident, independent and well-progressing enterprise to speak out so harshly. It is a good and very useful tool in human hands. Since the time of Francis Bacon, knowledge has truly become a force that has changed the world. Science develops in accordance with its internal laws: the scientist strives to comprehend the laws of the universe, and there is no doubt that this search will lead to success. But at the same time, it is necessary to recognize the boundaries of science. One should not confuse science and those ideological questions that can be raised in connection with science. The key problems today are related not so much to the scientific method as to value orientations. Science during the long twentieth century was perceived by people as an absolute good that contributes to the progress of mankind; and we see that the twentieth century became the most cruel in terms of human casualties. And here the question of values arises scientific progress, knowledge in general. Ethical values do not follow from science itself. A brilliant scientist can invent a weapon to destroy all humanity, and this raises a question about the moral responsibility of the scientist, which science cannot answer. Science cannot indicate to man the meaning and purpose of his existence. Science will never be able to answer the question, why are we here? Why does the Universe exist? These questions are resolved at another level of knowledge, such as philosophy and religion.
— Besides Gödel’s theorems, is there any other evidence that the scientific method has its limits? Do scientists themselves admit this?
— Already at the beginning of the 20th century, the philosophers Bergson and Husserl pointed out relative value scientific knowledge nature. It has now become almost universal belief among philosophers of science that scientific theories represent hypothetical models for explaining phenomena. One of the creators quantum mechanics— Erwin Schrödinger said that elementary particles are only images, but we can easily do without them. According to the philosopher and logician Karl Popper, scientific theories are like a net through which we try to catch the world, they are not like photographs. Scientific theories are situated in constant development and change. The creators of quantum mechanics, such as Pauli, Bohr, and Heisenberg, spoke about the boundaries of the scientific method. Pauli wrote: “...Physics and psyche can be considered as additional aspects of the same reality” - and emphasized the irreducibility higher levels being to the lower ones. The various explanations cover only one aspect of matter at a time, but a comprehensive theory will never be achieved.
The beauty and harmony of the universe presupposes the possibility of knowing it scientific methods. At the same time, Christians have always understood the incomprehensibility of the mystery behind this material universe. The universe has no basis in itself and points to the perfect source of existence - God.
Any system of mathematical axioms starting from a certain level 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 tasks, the answer to which seems obvious until you dig a little deeper. Speaking modern language, it was a question: is mathematics self-sufficient? Hilbert's second task boiled down to the need to strictly prove that the system axioms- basic statements taken as a basis in mathematics 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. Standard Euclidean planimetry(plane geometry) one can unconditionally prove 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 any axiom systems:
“If statement A can be proven, then statement not-A can be proven.”
In other words, if it is possible to prove the validity of the statement “assumption 247 Not provable", then it is possible to prove the validity of the statement "assumption 247 provable" 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 only judge their truth outside the framework of the axiomatics we have adopted. 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 wording first,or weak Gödel's incompleteness theorems: “Any formal system of axioms contains unresolved assumptions.” But Gödel did not stop there, formulating and proving second, or strong Gödel's 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 human brain superior to a computer bound by pure logic circuits. The human brain is capable of understanding the full depth of truth contained in Gödel's theorems, but the computer brain never can. Therefore, the human brain is anything but a computer. He is capable decisions, and the Turing test will pass.
I wonder if Hilbert had any idea how far his questions would take us?
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.
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 theorists 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 test Turing will pass successfully.
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.
| Comments: 0 |
How the scientific model develops in 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 complete system- this means that in the system it is possible to formulate a statement that cannot be either proven or refuted by the 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 considered to be the largest scientific achievement XX century. Why? What is its essence? What is its significance? These questions in his lecture as part of the project “ Public lectures"Polit.ru" reveals 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.
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 summer school « Modern mathematics", Dubna.
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 approximately the same 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 school mathematics/computer science, skills logical thinking 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 behind final number 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 math, then sometimes there is a false impression of almost complete identity of the phrases “the theorem is true” and “the theorem can be proven or verified.” 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 framework of 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 The value of this function ended 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 Latin alphabet), receiving natural values, spaces, characters arithmetic operations, 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 one-character words, on 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 this kind of 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 the roots of polynomials with rational coefficients Not all numbers are 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 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?
on the topic: “GODEL’S THEOREM”
Kurt Gödel
Kurt Gödel is a leading expert on mathematical logic– born April 28, 1906 in Brunn (now Brno, Czech Republic). He graduated from the University of Vienna, where he defended his doctoral dissertation, and was an assistant professor in 1933–1938. After the Anschluss he emigrated to the USA. From 1940 to 1963 Gödel worked at the Princeton Institute higher studies. Gödel - honorary doctorate from Yale and Harvard Universities, member National Academy Sciences of the USA and the American Philosophical Society.
In 1951, Kurt Gödel was awarded the highest scientific award USA - Einstein Prize. In an article dedicated to this event, another major mathematician of our time, John von Neumann, wrote: “Kurt Gödel’s contribution to modern logic is truly monumental. This is more than just a monument. This is a milestone that separates two eras... Without any exaggeration, it can be said that Gödel’s work radically changed the very subject of logic as a science.”
Indeed, even a dry list of Gödel’s achievements in mathematical logic shows that their author essentially laid the foundations for entire sections of this science: model theory (1930; the so-called theorem on the completeness of 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 certain classes of sentences of classical logic to their intuitionistic analogues, which laid the foundation for the systematic use of “embedding operations” that allow such a reduction of various logical systems 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 the most important problems in mathematics, on the one hand. And in the implementation of logical-mathematical problems on electronic computers, on the other), axiomatic set theory (1938; proof of the relative consistency of the axiom of choice and Cantor’s continuum hypothesis from the axioms set theory, which laid the foundation for a series of important results on the relative consistency and independence of set-theoretic principles).
Gödel's incompleteness theorem
Introduction
In 1931, in one of the German scientific journals a relatively small article appeared with the rather intimidating title “On Formally Undecidable Propositions of Principia Mathematica and Related Systems.” Its author was a twenty-five-year-old mathematician from University of Vienna Kurt Gödel, who later worked at the Princeton Institute for Advanced Studies. This work played a decisive role in the history of logic and mathematics. In Harvard University's decision to award Gödel an honorary doctorate(1952) she was characterized as one of greatest achievements modern logic.
However, at the time of publication, neither the name of Gödel's work. Neither its content meant anything to most mathematicians. Mentioned in its title, Principia Mathematica is a monumental three-volume treatise by Alfred North Whitehead and Bertrand Russell on mathematical logic and the foundations of mathematics; acquaintance 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 preserve of a very small group of scientists. At the same time, the reasoning given by Gödel in his proofs was so unusual for its time. That to fully understand them required exceptional mastery of the subject and familiarity with the literature devoted to these very specific problems.
First incompleteness theorem
Gödel's first incompleteness theorem, apparently, is the most significant result in mathematical logic. It sounds like this:
For an arbitrary consistent formal and computable theory in which basic arithmetic statements can be proven, a true arithmetic statement can be constructed, the truth of which cannot be proven within the framework of the theory. In other words, any completely useful theory, sufficient to represent arithmetic, cannot be both consistent and complete.
Here the word "theory" means " infinite set“statements, some of which are believed to be true without proof (such statements are called axioms), while others (theorems) can be deduced from the axioms, and therefore are believed (proven) to be true. The phrase “theoretically provable” means “derivable 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 constructed” means that there is some mechanical procedure (algorithm) that can construct a statement based on axioms, primitives and first-order logic. “Elementary arithmetic” consists of the operations of addition and multiplication on natural numbers. The resulting true but unprovable statement is often referred to for a given theory as a “Gödel sequence,” but there are an infinite number of other statements in the theory that have the same property: unprovable truth 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 in an arbitrarily long time, up to infinity) will compute a list of all the theorems of the theory. In fact, it is enough to compute only the list of axioms, and all theorems can be efficiently obtained from such a list.
The first incompleteness theorem was entitled "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:
“The general conclusion about the existence of undecidable propositions is this:
Theorem VI .
For each ω-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– many sequences, Gen comes from him. Generalization– generalization.
Roughly speaking, Gödel's statement G states: "the truth G cannot be proven." If G could be proven within the framework of the theory, then in this case the theory would contain a theorem that contradicts itself, and therefore the theory would be contradictory. But if G unprovable, then it is true, and therefore the theory is incomplete (statement G cannot be deduced in it).
This is an explanation in plain English natural language, and therefore not entirely mathematically rigorous. To provide a rigorous proof, Gödel numbered the statements using natural numbers. In this case, the theory describing numbers also belongs to the set of statements. Questions about the provability of statements 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 specific 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 assumed in the premise of the theorem), it turns out that such a number does not exist, and Gödel's statement is true, but within the framework of the theory it is impossible to prove it (hence the theory is incomplete). An important conceptual point is that it is necessary to assume that the 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 (that is, effectively generated) theory T, including basic arithmetic truth statements and certain formal provability statements, this theory T includes a self-consistency claim if and only if the theory T is inconsistent.
In other words, the consistency of a sufficiently rich theory cannot be proven by means of this theory. However, it may well turn out that the consistency of one specific theory can be installed using another, more powerful formal theory. But then the question arises about the consistency of this second theory, etc.
Use this theorem to prove that intelligent activity It doesn’t come down to calculations, many have tried. 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 outlined in the book completely, “from scratch.”
Discussions
The consequences of the theorems affect the philosophy of mathematics, especially those formalisms that use formal logic to define their principles. We can rephrase the first incompleteness theorem as follows: “ it is impossible to find an all-encompassing 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 has no special meaning, since it assumes the concepts of “truth” and “false” are defined in an absolute sense rather than in a relative sense for each specific system.