# Is there a hidden link between the existence uncountable sets and the undecidability of the halting problem?

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?

• Yes, the diagonal argument! Aug 7 '13 at 14:51
• @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. Aug 7 '13 at 14:59
• 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.
– 042
Aug 7 '13 at 15:31
• 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. Aug 7 '13 at 15:31