Since both proofs make use of the diagonal argument, Im 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?
Is there a hidden link between the existence uncountable sets and the undecidability of the halting problem?
halting problem
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 thingAndrej 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, 2007From 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.