How was Godels' incompleteness theorem proved

Godel's incompleteness theorem

"Why do you think Einstein took pleasure in talking to me?" Wrote Gödel a few years after Einstein's death. Gödel sees the main motive for friendship as “that I often took the opposite view and made no secret of it”. That says a lot about Einstein

"Why do you think Einstein took pleasure in talking to me?" Wrote Gödel a few years after Einstein's death. Gödel sees the main motive for friendship as “that I often took the opposite view and made no secret of it”. That says a lot about Einstein, but even more about Kurt Gödel: To contradict him was second nature. His obstinacy drove doctors to despair, and he attempted to draw the federal judge's attention to an inconsistency in the US Constitution when he was naturalized. And in a questionnaire he states: "I do not see my work as part of the intellectual atmosphere of the early twentieth century, but rather as the opposite."

The contradiction personified

That's probably true. Gödel had a decisive influence on the twentieth century, and he lived in Vienna as in Princeton in the midst of the intellectual vanguard of his time, but he protrudes like a foreign body into his epoch. The considerations recorded in his estate, including proof of God, fit more into the baroque age than into the modern age. In the questionnaire mentioned above, Gödel states that his views, even when he was nineteen, completely contradicted those of the Vienna Circle.

The contradiction, now not in the sense of a dissenting opinion, but in that of a logical inconsistency, has always played an important role in mathematics. It was already clear to the Greeks that a mathematical theory is based on certain statements that are assumed to be true, the axioms. All other statements must be deduced from this by logical conclusions, i.e. must be proven. A decent theory has to be free of contradiction because any contradiction spreads like wildfire over the entire theory. If a certain proposition A and its negation non-A can be proved, then any proposition B can be proved. Because from A follows “A or B (or both)”. Since “A or B (or both)” applies, but also not-A, B must inevitably apply. The same of course also applies to non-B. Everything stops there!

A contradiction in a mathematical theory is therefore more serious than in other sciences. If, for example, two dates of a bone find contradict each other, this does not immediately call the entire prehistory into question. But a contradiction in a mathematical theory, even if it originally concerns only a minor statement, infects all theorems of the theory. But how can the consistency of a mathematical theory be proven? Perhaps there is already a contradiction in the axioms, even if they seem evident to us. Our senses can be fooled, why not our minds too?

Hilbert's program

David Hilbert (1862-1943), the leading mathematician of his time, developed a "formalistic" program for this purpose. The logical inference can be traced back to the application of a few rules, i.e. mechanized to a certain extent. That a proof helps us understand something or that an axiom makes sense is secondary here: What goes on in our consciousness is a private matter. What is only important in the formalism is the precise documentation of the application of the individual inference rules. Hilbert thus emptied the mathematical theories of their content (straight lines, quantities, numbers, etc.). A handful of characters remain, including those for logical terms such as “not”, “if. . ., then "," for all ", characters for brackets, the equal sign, etc. Mathematical statements are strings. Certain strings correspond to the axioms. A proof is a sequence of character strings, where each of these character strings is either an axiom or is derived from the preceding character strings by transformations that correspond to the logical inference rules. The last string of a proof is a theorem.

Hilbert's plan was now to show that the transformations from the axioms did not allow both a statement A and its negation not-A to be derived. So he wanted to prove the consistency of a mathematical theory. He was aware of the size of the task. "Of course, this requires the dedicated cooperation of generations of younger mathematicians." For a while, success seemed within reach. But then one of these younger mathematicians came along and showed, to everyone's amazement, that Hilbert's program was not feasible.

Godel showed that any consistent mathematical theory rich enough to encompass arithmetic, that is, which allows one to count and add and multiply these numbers, is necessarily incomplete. That means: There are always meaningful statements that are undecidable within the framework of the theory, i.e. cannot be proven or refuted - and the statement that the theory is free of contradictions is one of them! Conversely, it follows from this: If one could prove the consistency of the theory, it would not be free of contradictions.

Godel's proof is demanding and many pages long, but the basic idea is of captivating elegance. Gödel constructed a statement G in the formal system, which says: "This statement G is unprovable." If G is provable, then also not-G and vice versa. So G is not provable (as long as the system is free of contradictions). But that is exactly what G says: So G is true. More precisely: We understand that G is true, but in the formal system this cannot be deduced.

Usually mathematics is about equations, areas or the like. The sentence "This statement is unprovable" doesn't sound like it at all. But whether or not a string of characters can be proven can be precisely formalized, and the apparently suspicious self-reference in the sentence can also be avoided. Gödel assigned a number to each string, which was later referred to as the Gödel number. The statement G actually reads: “The string with the Gödel number g cannot be proven”, and Gödel arranged it so virtuously that g (“to a certain extent random”, as he wrote) is precisely the Gödel number of G - a magical one Sleight of hand.

Hilbert's favorite student, the brilliant John von Neumann, grasped the situation immediately. Twice in dreams he had believed that he had found evidence of consistency. "How lucky that I only dreamed it!" The mathematicians accepted that the consistency cannot be proven. That only makes their job even more interesting. John von Neumann left the field of mathematical logic to Gödel and turned to other questions. A dozen years later, he became one of the fathers of the programmable computer. Hilbert's “formal systems” became machines, and Gödel's theorem of incompleteness turned out to be a statement about the limits of computer programs. Mathematics cannot be mechanized and the profession of mathematician is the only one to this day that has been proven to never become obsolete by computers.

Karl Sigmund