Godel's theorem is actually two theorems, among which Godel's first incompleteness theorem is the most important and easily misunderstood, which can be seen from many versions of this theorem. For example:
"If a formal theory T is enough to accommodate number theory and there is no contradiction, then T must be incomplete."
"In any compatible mathematical formalization theory, as long as it is strong enough to define the concept of natural numbers, a proposition that can neither be proved nor proved can be constructed in the system."
"Any strong enough consistent hypothesis system must be incomplete."
The second incompleteness theorem is the corollary of the first theorem: "No compatible formal system can be used to prove its own compatibility"
It is really difficult to understand this theorem without the relevant knowledge base. As for proof, it is even more difficult to understand. I am lazy. Let's skip these and introduce the meaning directly.
Godel theorem is a theorem of first-order logic. In formal logic, mathematical propositions and their proofs are described in symbolic language. Here we can mechanically check the legality of each proof, so we can irrefutably prove a theorem from a set of axioms. At the beginning of the last century, formalism represented by Hilbert hoped to construct a limited set of axioms about number theory (natural numbers) through the method of formal logic, deduce the principles (completeness) of all number theories without contradiction (compatibility), and build the whole formalism mathematical system on this basis. And Godel's first incomplete theorem shattered this idea. These two theorems actually show that such an axiomatic system is either incomplete or contradictory. Gnc( 1909- 1945) proved the compatibility of number theory in 1936 by the transfinite induction of non-deductive logic.
So this theorem reveals that in most cases, such as number theory or real analysis, the complete set of axioms can never be found. You can constantly add new axioms to the axiomatic system, or even form an infinite axiom set, but this axiom list is no longer recursive, and there is no mechanical judgment method to judge whether the added axioms are axioms of the axiomatic system. This is of great significance to computer science. In computer language, the theorems of first-order logic are recursively enumerable. But Godel's first incomplete theorem shows that such a program cannot be compiled, and the truth of the proposition can be proved in a limited time by recursive theorem. Penrose's "The Emperor's New Brain" describes this point with the problem of downtime. He even thinks that computers can never surpass the human brain, or even reach the level of the human brain. Of course, this point is still inconclusive and controversial.
I want to be brief, but I still can't. The following combined with the analysis of common misunderstandings, try to clarify the vague understanding.
Common Myth 1: "All axiomatic systems are incomplete". This is the most common, and some people even use it to deny logic, which is wrong. Euclidean geometry, for example, can be axiomatized into a complete system.
Common misunderstanding 2: "All axiomatic systems involving natural numbers are incomplete". This error can be seen from the description of some Godel theorems above. This theorem only assumes that an axiomatic system can "define" natural numbers. Many systems containing natural numbers, such as "real numbers" and "complex numbers", have complete axiomatic systems.
Common misunderstanding 3: "Because it is incomplete, it can never be proved that an axiomatic system is not contradictory". No, we can prove it in other ways, such as the above-mentioned transfinite induction. In fact, this theorem only shows that we can't prove compatibility from within the system, and it doesn't rule out that it can be proved by other systems. For example, piano's axiom in number theory cannot be proved in the range of number theory alone, but it can be proved in set theory.
It seems like a long story, but my feeling is too thin. This can only be regarded as a brief introduction, hehe. I hope it will help everyone.
two
Godel theorem is mainly used in the field of mathematics. As for its practical application, many of them are blindly applied based on wrong understanding, and some missionary posts in the forum have also appeared many times. If we want to avoid mistakes, we should really understand the meaning of this theorem, but paradoxically, it is really possible based on considerable mathematical knowledge, which is too difficult for many people. So I pointed out some misunderstandings and made a simple analysis. If you pay attention, you can avoid many mistakes. Let me introduce some practical examples, which I personally think are correct and may be helpful for you to understand this theorem.
Since it is a mathematical theorem, the most direct application field is mathematics, especially number theory. Many propositions in number theory need Godel theorem to prove. I won't introduce this much. This theorem shows that some propositions about natural numbers may be true propositions themselves, but they cannot be proved or falsified only from the axiomatic system of natural numbers, but can only be proved by other means or methods, such as set theory. Some people speculate that Goldbach conjecture may be such a proposition. Therefore, even for extremely abstract and formal mathematics, the mathematician's intuition-that is, the accumulation of a lot of practical experience-is more basic and reliable than the pure form of mathematical logic reasoning. But it doesn't mean that logic is useless. The latter can be used to verify whether the former is correct or not, and some new correct propositions can be deduced, but they cannot represent all. As mentioned above, even if it cannot be proved in the formal system, it can be proved by other methods or from other systems. In addition, it is emphasized again that "this theorem only assumes that the axiomatic system can' define' natural numbers", which is a first-order logical theorem and should not be expanded arbitrarily. There are often misunderstandings here. I suggest interested friends know more about the basic knowledge.
Another main application field of this theorem is a branch of mathematics-computer and artificial intelligence. Now let me briefly introduce the downtime mentioned in my article. Computers have made great progress, but the basic principle was put forward by von Neumann, but the speed and efficiency have been greatly improved. Fundamentally speaking, a computer program is a propositional calculus system based on binary digit operation. The axioms given are finite and the rules are computable. When the truth value of a proposition is judged, the result is output, and the machine stops and turns to the next proposition. This accords with the condition of Godel's first incomplete theorem. But as the theorem says, such a system must be incomplete, that is to say, at least one proposition cannot be judged by such a "program", and the system cannot "stop" when dealing with such a proposition. As the saying goes, if you get stuck, you can never get around it. No matter how you expand the axiom set, as long as it is limited, this phenomenon will always exist. Infinite axiom set means infinite storage space for computer, which is obviously impossible. So some mathematicians, such as Penrose I mentioned, think that this shows that computers have fatal defects, and human intuition is not limited by this theorem, so computers can never have the ability of human brains. The truly intelligent "computer" expected by artificial intelligence is just "the emperor's new brain" like "the emperor's new clothes". For details about this problem, please read Penrose's The Emperor's New Brain.
Why is there such a fundamental difference between human brain and computer? Penrose believes that it may be caused by the uncertainty of quantum mechanics and the chaotic action of complex nonlinear systems. However, some mathematicians don't think so. They pointed out that there is no fundamental difference between the basic meaning and working principle of the human brain and the Turing machine of artificial intelligence principle, and the computer also has the above two functions, which shows that the human brain is also limited by Godel's theorem. The difference between them can be explained by an uncertain computing system, which is called "fuzzy" processing. The human brain is such a naturally formed neural network system with uncertainties. The reason why it seems to have "intuition" that computers don't have is precisely the performance of this system's "fuzzy" processing ability and high efficiency. The traditional Turing machine is a deterministic serial processing system. Although such "fuzzy" processing can also be simulated, the efficiency is too low. The quantum computer and computer neural network system being studied can really hope to solve such problems and reach the ability of the human brain.
Whether the computer is the "real brain" or the "emperor's new brain" is still controversial, and there are many problems to be solved, many of which are the frontier topics of the world's top scientists. I don't have the ability to judge right or wrong, but I personally think that "human thinking is also limited by Godel's theorem" is very interesting and probably correct. Various studies show that the basic principle of the human brain is the same as that of the computer, except that the computer is embodied by the "opening and closing" of electronic components and the transmission of electrical signals, while the human brain is expressed by the "impulse and inhibition" of neurons and the transmission of chemical signals (including electrical signals, of course). This is not essentially different from the condition of Godel's theorem. In the cognitive process, "thinking is an approximate reflection of objective reality and language is an approximate expression of thinking" is the result of the restriction of Godel's theorem. Taking language (in form) as an example, it can be completely transformed into a symbolic logic system with finite axioms and certain rules, that is, a formal axiom system that satisfies theorem conditions. This theorem just shows that such a system is incomplete and there are propositions that cannot be proved by this system. For this system, the expression of thinking by language is incomplete, that is, we often say that "it can only be understood, but not expressed." This is also consistent with what we often feel "words fail to convey our meaning", and no formal language can express our thoughts completely and accurately. Another fact also illustrates this point, and that is translation. Although it is not difficult to translate formal language from text to text, it is very difficult or even impossible to express the exact meaning in the original text truthfully. If it can be proved that human thinking can also be transformed into such a formal axiom system, then the human brain must also be limited by Godel's theorem.
But as I said at the beginning, even if it is limited by Godel's theorem, it does not mean that such a system is meaningless and cannot correctly reflect the objective reality. As far as human thinking is concerned, it is a process of constantly summing up the experience gained from it through practice, deepening the understanding of the objective world and pushing forward the "objective truth". This is the epistemology of dialectical materialism.
Again, although this theorem is of great significance, it is really difficult to understand. The above is my personal opinion. I can't guarantee that I am right. I just hope to clarify my understanding through discussion.
Godel's incompleteness theorem can probably be described as "every strong enough formal system has its unverifiable true statement."