Gödel's Proof Review

Mathematics and formal logic form the backbone of physical science, and that backbone tends to remain rigid and unchanging. While new physics discoveries abound every day, discoveries and surprises come more slowly in the world of formal logic.

But when logicians uncover something new, the results can absolutely shake the foundations of not only the field but all of physical science. Kurt Gödel did just that in the 1930’s with his now famous incompleteness theorems.

With dozens of pages of dense, rigorous and ingenious mathematical proofs, Gödel revealed two severe problems with the way mathematicians approached their own field.

First, he showed that any consistent mathematical system capable of expressing basic arithmetic will never be able to prove some arithmetical truths – hence the “incompleteness.” Secondly, Gödel demonstrated that such a mathematical system cannot prove its own consistency although external proofs may still exist.

While Gödel’s findings shocked logicians and mathematicians alike, his method remained indecipherable even to many mathematical experts for several years. In 1958, however, philosopher Ernest Nagel and mathematician James R. Newman helped share this discovery with the world in a book aimed toward a popular audience: Gödel’s Proof.

Metamathematics and Gödel’s Language

Nagel and Newman succeeded in their monumental task: taking Gödel’s extremely technical and dense argument and conveying it to a lay audience without “dumbing it down” and degrading its meaning. Although their book demands some patience and curiosity, understanding Gödel’s thinking is well worth the effort required. Nagel and Newman avoid diving straight into the incompleteness theorems; instead, they lay down the necessary historical, mathematical, and logical background first. With that in mind, let’s cover a few of the key terms surrounding logic, mathematics, and Gödel’s theorems.

Axioms – An axiomatic system has several propositions that are assumed to be true. Combining just these starting-point propositions — called axioms — and the rules of formal logic, you can derive (prove) other true statements within the system.

For example, say the following two statements are axioms in our system: 1. Bill either owns a toaster or a refrigerator (or both). 2. Bill does not own a refrigerator.

What other true statements can we conclude from this? Most noticeably, we can conclude that Bill owns a toaster. Since he doesn’t own a refrigerator, ensuring the truth of the first statement requires us to conclude that he owns a toaster.

In a similar way, mathematicians often start with a set of axioms and derive theorems from there.

Consistency — a consistent axiomatic system never leads to a contradiction. In other words, under a consistent system, it’s impossible to derive a contradiction using formal logic and the system’s axioms.

Why is consistency important? To see why, we turn to the principle of explosion — the formal equivalent of the phrase “everything follows from a contradiction.” If you accept that contradictions are true (e.g. the whole statement ‘2+2=4 and 2+2 does not equal 4’), then everything becomes true, rendering the system useless. A mathematical system should allow you to discern truth from falsehood; otherwise, what’s the point?

Metamathematics — The language used to talk about mathematical statements. For instance, compare the following two statements: 1. 2+2=4 2. The expression ‘2+2=5’ is false

The first instance is a simple mathematical statement. In the second instance, however, I’m referring to a mathematical expression (a false one) and saying something about it (namely that it’s false). Thus, the second statement is metamathematical.

Einstein and Gödel developed a strong friendship during their shared time in Princeton.

How He Did It

Nagel and Newman cover the aforementioned terms and contemporary history of mathematics in much more detail before delving into Gödel’s actual proofs. Here I’ll give you just a glimpse of how Gödel derived his monumental theorems.

Perhaps Gödel’s most critical insight was his “arithmetization” of meta-mathematics. In other words, he found a way to indirectly reference meta-mathematical statements through the use of mathematical statements.

To do this, he found a way to ascribe unique, huge natural numbers to meta-mathematical statements. For instance, take the example of the statement ‘Zero does not equal one.’ In formal logic, this statement can be written as ~(0=s0) where the tilde symbol (~) means ‘not’ and ‘s0’ means the natural number after 0, i.e. 1.

Every logical symbol in Gödel’s system, such as the tilde or the parentheses or even zero, has its own number. The total number for the whole formula is composed of several factors of prime numbers. Consequently, there’s a straightforward way of making a meta-mathematical statement by looking at the mathematical properties of the formula’s Gödel number.

Through this method, Gödel was able to show that there’s a true statement related to the natural numbers that nonetheless cannot be proved under any consistent set of axioms. Furthermore, adding a new axiom to “cover” this truth will only lead to another un-provable (under the new axiomatic system) truth cropping up.

That’s Gödel’s first incompleteness theorem. The second half states that if such axiomatic systems are consistent, their consistency absolutely cannot be proved within the system. External proofs of consistency may exist, but mathematicians differ on whether they are strong enough to truly prove a system’s consistency.

Clearly, this overview remains incomplete, but I'll leave Nagel and Newman to fill in the gaps for you. Although their book thoroughly describes Gödel's method, the book remains concise at just over 100 pages.

You may find yourself re-reading several of those pages, however, especially as Nagel and Newman start putting everything together in the second half of the book. Nonetheless, the experience should be highly rewarding.

When everything comes together and starts to make sense, you can truly appreciate Gödel’s painstakingly careful yet beautiful approach. Gödel’s Proof provides a non-technical exploration that’s not only eye-opening but also affecting. And that’s rare to find in any book, let alone one about formal logic.

You can find Godel's Proof on Amazon.