[Math] Are (some) axioms “unprovable truths” of Godel’s Incompleteness Theorem

axiomsdiscrete mathematicsincompletenesslogic

Like any math newbie, Godel's Incompleteness Theorems are easy to understand in general layman's terms, but difficult to understand beyond the typical "liar's paradox" and "barber's paradox" type examples.

But then I started thinking, are axioms examples of the truths of mathematics that can't be proven? For example, Peano's Postulates: a very popular "starting point" for deducing other mathematical truths. One of the postulates is, "0 is a natural number." Well wait a second: what is "0"? What is a "natural number"? In order to take that axiom as a truth, there must be a definition for what 0 is, and what a natural number is. But even if we assign them definitions in English, can those definitions be proven?

If I follow this train of thought, I eventually find myself completely outside of mathematics, and more into philosophy — can we even prove what a "natural number" actually is? If I'm not careful, eventually I end up in lala land thinking about the meaning of existence and reality itself.

Does this even make sense? My mind has been blown so many times on this topic, I spend more time scooping my brain off the floor than forming coherent questions.

Best Answer

To the extent that our "axioms" are attempting to describe something real, yes, axioms are (usually) independent, so you can't prove one from the others. If you consider them "true," then they are true but unprovable if you remove the axiom from the system. In that sense, the smaller system has "true" but unprovable theorems.

But the "trueness" of Gödel's statement is a bit more complicated.

Let's say it turned out that the Goldbach conjecture was undecidable. To me, that would mean that it is "intuitively true," since if it was false, we could find a counter-example that was a finite statement. The fact that we can't provide a counter-example, however, is not enough to prove it is true. This might seem strange, even absurd.

One way I like to think of it is that proofs are finite things, but we are often trying to prove things about infinitely many numbers. Induction, for example, can be thought of as a finite way of outlining an infinite proof.

Intuitively, what Gödel showed is that (under enough complexity) there are always theorems that have infinite proofs but for which there are no finite proofs. For example, Goldbach might be one of those cases. Each $2n, n\geq 3$ might be expressible as the sum of two primes, but if we can't outline that proof finitely, we are stuck.

A statement like Gödel's - rougly, "This theorem does not have a (finite) proof from these axioms" - is such an example. We can enumerate all finite logical proofs, and check if it proves our theorem. This would yield an infinite proof of the result. So in that sense, it is "true." But it obviously can't be proven.

The fact that we can't resolve this statement from these axioms means, intuitively, that it is true. Our intuition about the natural numbers says this ought to be true, and that our axioms didn't fully capture our intuition.

Related Question