Gödel's incompleteness theorems — Safekipedia Discoverer

Gödel's incompleteness theorems are two important ideas in mathematical logic. They were published by Kurt Gödel in 1931 and show the limits of what we can prove using certain rules in mathematics. These theorems tell us that no matter how good our system of rules is, there will always be true statements about numbers that we cannot prove using those rules.

The first incompleteness theorem says that in any consistent system of rules that can list its theorems using a step-by-step method, there will always be true statements about natural numbers that cannot be proven within that system. This means there are truths that we just cannot show are true using the rules we have.

The second incompleteness theorem goes further and shows that such a system cannot even prove that it is consistent itself. Gödel used a clever method called a diagonal argument to prove these theorems. His work led to many other important results in logic, such as Tarski's undefinability theorem, Church's proof that Hilbert's Entscheidungsproblem is unsolvable, and Turing's theorem about the halting problem.

Formal systems: completeness, consistency, and effective axiomatization

The incompleteness theorems apply to formal systems that can express basic arithmetic of natural numbers and are consistent and effectively axiomatized. A formal system includes a set of axioms and rules for deriving new theorems. An example is Peano arithmetic, where variables represent natural numbers.

Formal systems can have properties like completeness, consistency, and effective axiomatization. The incompleteness theorems show that systems with enough arithmetic cannot have all three properties at once. An effectively axiomatized system has a list of theorems that a computer could, in theory, enumerate. Examples include Peano arithmetic and Zermelo–Fraenkel set theory (ZFC).

Completeness means that for any statement, either it or its opposite can be proven from the axioms. Consistency means the system has no contradictions. Peano arithmetic is consistent but not complete, meaning there are true statements it cannot prove. Similarly, ZFC cannot prove its own consistency or resolve certain statements like the continuum hypothesis.

First incompleteness theorem

Gödel's first incompleteness theorem appeared in 1931 in Gödel's paper "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I". This theorem shows that any consistent formal system that can handle basic arithmetic will always have statements that cannot be proven or disproven within that system. These special statements are called Gödel sentences.

Each system has its own Gödel sentence. Even if we add this sentence as a new rule to the system, the system remains incomplete. The theorem will still find a new Gödel sentence for the expanded system, proving it cannot be made complete.

Second incompleteness theorem

Gödel's second incompleteness theorem shows that a mathematical system cannot prove its own consistency. This means that if a system is consistent (it doesn't prove contradictions), it cannot show that it is consistent within itself. This theorem appeared first in Gödel's 1931 paper "On Formally Undecidable Propositions in Principia Mathematica and Related Systems I".

The theorem has important consequences. For example, it means that certain programs to prove the consistency of all mathematics, like Hilbert's program, cannot be fully achieved. This is because a system cannot use its own rules to prove that it will never make a mistake. Other mathematicians, like Gerhard Gentzen, have found ways around this by using different systems to prove consistency.

Examples of undecidable statements

In mathematics, a statement is called "undecidable" if it can’t be proven true or false using certain rules of logic. This doesn’t mean we don’t know if it’s true or false — it just means those rules can’t show us.

Two famous examples are the continuum hypothesis and the axiom of choice. Neither can be proven true or false using common rules of set theory, a branch of math that studies collections of objects. These results were discovered by mathematicians Kurt Gödel and Paul Cohen.

Relationship with computability

Gödel's incompleteness theorems are closely connected to ideas in computability theory. One key result shows that there are problems, like the halting problem, that no computer program can solve for all possible inputs. This helps explain why it's impossible to have a complete system of arithmetic that can prove every true statement and disprove every false one.

These theorems also relate to other important results in logic, such as the idea that some mathematical problems have no solutions that can be found by any algorithm. This further shows the limits of what can be proven in mathematical systems.

Proof sketch for the first theorem

Main article: Proof sketch for Gödel's first incompleteness theorem

Kurt Gödel showed that in any system good enough to describe basic arithmetic, there are statements that cannot be proven true or false within that system. He did this by showing that statements can be linked to numbers, allowing the system to "talk about" its own proofs. Using a method called "diagonalization," he created a special statement that essentially says, "I cannot be proven." If this statement could be proven, the system would be inconsistent. If its opposite could be proven, the system would also have problems. Therefore, this special statement is neither provable nor disprovable in the system, showing that no such system can be both complete and consistent.

Proof sketch for the second theorem

The second incompleteness theorem is tricky because it needs to show that certain ideas about proof can be expressed inside a mathematical system using a special rule for proof called P. Once this is done, the theorem shows that a system cannot prove its own consistency.

Imagine a special sentence p that cannot be proven or disproven in the system. If we could prove that the system is consistent, we could also prove that p cannot be proven. But this creates a problem because p was designed to be unprovable. This shows that the system cannot prove its own consistency, which is what the second incompleteness theorem states.

Discussion and implications

The incompleteness theorems have big effects on how we think about math. They matter a lot for ideas in the philosophy of mathematics, especially for ways that try to use just one system of logic to explain everything.

Some people think these theorems make it hard to prove that all of math is consistent, meaning it doesn’t contain any contradictions. Others aren’t so sure, and this debate is still going on today. The ideas also lead to interesting questions about whether human thinking can be explained by machines or computer programs. Some thinkers believe that our ability to think and understand math shows we are more than just machines.

History

After Kurt Gödel published his proof of the completeness theorem in 1929, he began working on a new problem. At the time, mathematicians were trying to prove that certain mathematical systems were consistent, meaning they didn’t contain any contradictions.

Gödel announced his first incompleteness theorem in 1930 at a conference in Königsberg. Later that year, he published his findings in a paper titled "On Formally Undecidable Propositions in Principia Mathematica and Related Systems I." His work showed that there are limits to what can be proven within any consistent mathematical system. This was a surprising result because many mathematicians, including David Hilbert, believed that all mathematical problems could eventually be solved.