What is Gödel’s incompleteness theorem, and why is it so infamous in Mathematics?


What is Gödel’s incompleteness theorem, and why is it so infamous in Mathematics?

In: Mathematics

There are actually two incompleteness theorems. They are in the realm of logic, which attempts to axiomatize mathematics. Both theorems are about *formal systems*, which you can think of a set of rules for inferring from axioms. Kind of like meta math in a way.

The **first incompleteness theorem** says that all *consistent* (you can think of this as there are no contradictions) formal systems of mathematics that can carry out *Peano arithmetic* (just normal addition/multiplication, basically, with integers that are ordered) are *incomplete*. Here, incomplete means that there are statements you can formulate but you can’t prove.

The **second incompleteness theorem** says that no consistent formal systems of mathematics that can carry out Peano arithmetic can prove their own consistency.

I don’t think they are really “infamous”, by the way—Gödel is very respected, and no serious mathematician thinks these theorems are wrong. But maybe they can be considered depressing or disheartening. The first theorem says that there are some mathematical questions we don’t know the answer to and that we *can’t* know the answer to! To mathematicians whose whole purpose is to get those answers, it seems horrifying. And the second theorem says that you can’t really “know for sure you’re correct” since the formal system can’t prove its own consistency.

In math we have basic statements which are accepted as true called axioms. These are basically the fundamental ground rules of math. These, combined with rules of logic, allow us to deduce other, more complicated statements.

For a while in mathematics there was a big push by a handful of mathematicians/logicians to try and root *everything* that you could possibly prove into as few axioms as possible. Basically they wanted to take nothing for granted if it could be avoided and, from those few axioms, prove everything that could be proved true.

Stated more formally, they wanted a system that was both *complete* (everything that is actually true can be proved true) and *consistent* (nothing that is actually false can be proved true)

Gödel proved that this was false. That any but the most rudimentary systems will either be incomplete (there is something that is true that the system can’t prove true) or inconsistent (that there is something the system says is true but it actually isn’t).

It was infamous because it not only dashed the hopes of the top mathematicians at the time but it is somewhat counterintuitive to think that you can’t reduce all of math to a handful of simple axioms and rules.

Perhaps it would be useful to add that, at the core and in simple terms, Gödel showed that there will always be a theorem stating “I can’t be proved” (self-referential):

* if true, it can’t be proved;
* if false, it can’t be proved either as it is false.

Which means that as soon as you have the conditions (axioms) to do a modicum of mathematics (find theorems), there will always be *true but “unreachable” results*. (Others have discussed the “conditions”.)

And also that you can’t just put a computer on the task of churning out all true results, it will always at some point hit a snag and never return a true/false result. (That’s Turing’s “halting problem”.)