Gödel's incompleteness theorems

Question

In the last paragraph of Stephan Hawking's speech "Godel and the End of the Universe", he mentioned

"... I'm now glad that our search for understanding will never come to an end, and that we will always have the challenge of new discovery. Without it, we would stagnate. Godel’s theorem ensured there would always be a job for mathematicians. I think M theory will do the same for physicists...."

My question: Is Mathematics an inexhaustible source of infinite amount of discoveries (or inventions if you like) waited to be unearthed ? if yes, is that a natural conclusion drawn from Gödel's incompleteness theorems ?

Answer 1

Assume you have a systematic way of encoding mathematical propositions, so that for any proposition $P$ there is a unique number $n(P)$ encoding it.

Variants of Gödel's argument show that, for any total computable function $f(n)$, there is always a provable proposition $P$ in number theory, such that the shortest proof for $P$ is longer than $f(n(P))$ steps.

This means that there are theorems whose simplest proofs are huge relative to the length of their statements. Given our time dependencies, we will always be able to find new results.

The potential is to have proofs that are so long, no human could check them in a lifetime. This is possibly true already for the computer proofs of various theorems - essentially theorems that require a huge number of cases.

So, literally, there are always more and more complicated theorems to prove. Whether they are theorems that anybody cares about is another matter. At some point, we get to theorems whose statements are so long it would take a lifetime to read the statements of the theorem. These are really not human-accessible, but there might be a way to approach them via computer...

Answer 2

If we ignore some context, and instead consider the quote at face value, it is not Gödel's result that would be relevant, but rather the fact that the theorems of just about any interesting theory do not form a recursive set. This means that there is no computing device that can predict which statements are provable in the theory and which are not. The existence of such a device would certainly make our profession near obsolete. An immediate consequence of the fact that the collection of theorems is not recursive is that it is not finite, so there are infinitely many theorems we have not proved yet, even if the issue of how interesting they are is debatable. Going beyond this, a nice consequence of closely related results of Gödel is that there are extremely nontrivial speed-ups in the length of proofs if we replace our background theory $T$ with the stronger $T+$"$T$ is consistent". In particular, this gives us that there are families of theorems $t_1,t_2,\dots$ whose shortest proofs are extremely long (Given any pre-established recursive function $f$, there are such $t_1,t_2,\dots$ with the shortest proof of $t_n$ taking longer than $f(n)$ steps) while if we pass from our $T$ to its strengthening, then for some $k$, each $t_n$ is provable in at most $kn$ steps. See here.

The quote makes more sense in the context of other writings by Hawking. A theme that recurs is that there may not be a "correct" physical theory but rather we (expect we) will keep discovering theories that better and better explain the universe. In this context, mentioning Gödel's result for comparison is natural, even if a bit controversial. To see why, you should think of the role of mathematicians as going beyond the business of proving results, which immediately tethers us to a established theory in which our proofs take place (at least in principle), but rather as also seeking to establish mathematical "truths" that go beyond this established theory, together with the "evidence" of this truth. Naturally, not all mathematicians would agree here, and even within the set theoretic community, where this behavior is pretty blatant, there is no uniform consensus. (See here for more on this.)