Since both proofs make use of the diagonal argument, I’m wondering whether there is an obscure link between the existence of uncountable infinite sets and the undecidability of the halting problem. Would the halting problem be decidable if all sets were countable?
$\begingroup$
$\endgroup$
9
-
10$\begingroup$ Yes, the diagonal argument! $\endgroup$– Mahdi CheraghchiAug 7, 2013 at 14:51
-
1$\begingroup$ @MCH My thought was that there is maybe a different characterization besides the diagonal argument that connects both. This question is maybe too blurry for SE. $\endgroup$– Lenar HoytAug 7, 2013 at 14:59
-
4$\begingroup$ This may be a partial link: clearly, the set of all languages over a given alphabet is uncountable. However, the set of all Turing machines is countable. This directly implies the existence of undecidable problems. However, this reasoning implies nothing about the halting problem. $\endgroup$– 042Aug 7, 2013 at 15:31
-
9$\begingroup$ There are certainly set-theoretic models of ZFC where all sets are countable (although not within the model), but the halting problem is always undecideable. See this MathOverflow question. $\endgroup$– Peter ShorAug 7, 2013 at 15:31
-
4$\begingroup$ Please, please please say undecidability from now on. $\endgroup$– Vijay DAug 10, 2013 at 5:04
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
It's not a hidden link but one that has been made explicit using the language of category theory and also a very natural question to ask and study. There is a fair bit of material on the subject.
- CS Theory question asking the same thing
- Andrej Bauer's blog post about fixed point theorems and Cantor's theorem.
- A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points, Noson Yanofsky, 2003. Gives you a gentle introduction to Lawvere's paper, below.
- Diagonal arguments and cartesian closed categories, F. William Lawvere, 2006 republication of a 1969 article making these connections precise.
- Incompleteness in a General Setting, John Bell, 2007
- From Lawvere to Brandenburger-Keisler: interactive forms of diagonalization and self-reference, Samson Abramsky and Jonathan Zvesper, 2010. Extension of the Lawvere arguments to game-theoretic impossibility results.
