I know of the continuum hypothesis (CH) and how it was proven to be unprovable under ZFC, but this was after Gödel's incompleteness theorems. And in fact Gödel (and Paul Cohen) were the ones who proved this. So before the incompleteness theorem, was the notion of proving things unprovable not an inkling in any mathematician's head?

  • 8
    $\begingroup$ Does proving the parallel postulate is not provable from the other Euclidean postulates count? That proof dates back to Lobachevsky and Gauss and one of the Bolyai's. $\endgroup$ – Ethan Bolker Oct 22 '17 at 22:54
  • 1
    $\begingroup$ The classical geometric questions of squaring the circle, doubling the cube, and trisecting an angle with compass and straightedge were proved to be impossible in the 1800s. $\endgroup$ – Michael Biro Oct 22 '17 at 22:57
  • 5
    $\begingroup$ @MichaelBiro Those aren't really unprovability results, though. $\endgroup$ – Noah Schweber Oct 22 '17 at 23:26
  • 9
    $\begingroup$ The independence of CH does not rely on the incompleteness theorem. $\endgroup$ – Asaf Karagila Oct 23 '17 at 6:50
  • $\begingroup$ I would suppose that Con ($ZF$ - Infinity) $\implies$ Con ($ZF$-Infinity+($\neg$ Infinity) ) (....and hence if $ZF$-Infinity is consistent then Infinity is not provable from it ) goes back earlier. A 1930 paper by Zermelo proves that $V_k$ satisfies $ZF$ if $k$ is a strongly inaccessible cardinal so I suppose it had already been observed that $V_{\omega}$ satisfies $ZF$-Infinity+($\neg$ Infinity). $\endgroup$ – DanielWainfleet Oct 24 '17 at 2:49

The parallel postulate is a good example.

Another one is that the proof of any theorem is also a proof of the provability of the theorem.

For one more, Turing, Kleene, and Gödel all worked on proving that a certain problem couldn’t be solved via an algorithm, but didn't solve it before the Incompleteness Theorems came out. You can read about the problem here, but it basically asked if there was an algorithm that could prove any statement from the axioms of arithmetic. It’s called the Entscheidungsproblem, which is German for “the decision problem.”

This last example is really important because it’s what got mathematicians thinking about unprovability in the 20th century, and was published in 1928. This problem was originally posed as “find an algorithm” because previously to this problem people didn’t seriously consider the idea that the answer might be “you can’t do that.” Gödel’s work on this problem is part of what influenced his thinking on the Incompleteness Theorems, published in 1931. The problem wouldn’t be solved until Turing’s 1936 paper though.

Another problem that was foundational was the Halting Problem. This problem is closely related to both incompleteness and Hilbert’s problem. It was also solved by Alan Turing in 1936.

  • 3
    $\begingroup$ +1. For the OP, let me say a bit more: a crucial part of Godel's incompleteness theorem is that the coverse, "provability of provability implies provability," is not true of general formal systems, even those strong enough to "do enough arithmetic." And going further, Lob showed that (as long as we code things nicely) this is almost never true in a precise sense: if (say) ZFC proves "If ZFC proves $p$, then $p$ is true," then ZFC already proves $p$. So there is no way inside ZFC to go from a proof of the ZFC-provability of a sentence to a proof of that sentence except in "trivial" cases. $\endgroup$ – Noah Schweber Oct 22 '17 at 23:42
  • 2
    $\begingroup$ I hadn't even considered provability's relationship with computability and the work done by Turing and Church. It really puts the foundational work done in the early 20th century into perspective. $\endgroup$ – Ozaner Hansha Oct 23 '17 at 0:12
  • 2
    $\begingroup$ @OzanerHansha Although note that that work postdated Godel. $\endgroup$ – Noah Schweber Oct 23 '17 at 0:14
  • 2
    $\begingroup$ You can read a proof of Gödel’s theorem using the halting problem here: scottaaronson.com/blog/?p=710 $\endgroup$ – Stella Biderman Oct 23 '17 at 0:16
  • $\begingroup$ Yeap that's an excellent blog post, which inspired me to write this! $\endgroup$ – user21820 Oct 23 '17 at 18:44

Does proving the parallel postulate is not provable from the other Euclidean postulates count? That proof dates back to Lobachevsky and Gauss and one of the Bolyai's.

  • $\begingroup$ Actually, Gauss, Lobachevsky, and Bolyai conjectured that non-Euclidean geometry was consistent (and so the parallel postulate was not provable), but the proof of the relative consistency result had to wait for Poincaré and Klein. $\endgroup$ – Michael Weiss Oct 28 '17 at 18:42
  • $\begingroup$ @MichaelWeiss Good point thanks. $\endgroup$ – Ethan Bolker Oct 28 '17 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.