<p>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.</p>

<ul>
<li><a href="https://cstheory.stackexchange.com/questions/10635/halting-problem-uncomputable-sets-common-mathematical-proof">CS Theory question</a> asking the same thing</li>
<li><a href="http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theorem/" rel="nofollow noreferrer">Andrej Bauer's blog post</a> about fixed point theorems and Cantor's theorem.</li>
<li><a href="http://xxx.lanl.gov/abs/math.LO/0305282" rel="nofollow noreferrer">A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points</a>, Noson Yanofsky, 2003. Gives you a gentle introduction to Lawvere's paper, below.</li>
<li><a href="http://tac.mta.ca/tac/reprints/articles/15/tr15abs.html" rel="nofollow noreferrer">Diagonal arguments and cartesian closed categories</a>, F. William Lawvere, 2006 republication of a 1969 article making these connections precise.</li>
<li><a href="http://publish.uwo.ca/~jbell/General1.%20doc.pdf" rel="nofollow noreferrer">Incompleteness in a General Setting</a>, John Bell, 2007</li>
<li><a href="http://arxiv.org/abs/1006.0992" rel="nofollow noreferrer">From Lawvere to Brandenburger-Keisler: interactive forms of diagonalization and self-reference</a>, Samson Abramsky and Jonathan Zvesper, 2010. Extension of the Lawvere arguments to game-theoretic impossibility results.</li>
</ul>

CC BY-SA 3.0
2013-08-07T19:21:43.533Z
2013-08-07T19:21:43.533Z
2017-04-13T12:32:28.053Z
Vijay D
<p>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?</p>

CC BY-SA 3.0
2013-08-07T14:51:05.177Z
Yes, the diagonal argument!
Mahdi Cheraghchi
CC BY-SA 3.0
2013-08-07T14:59:32.100Z
@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.
Lenar Hoyt
CC BY-SA 3.0
2013-08-07T15:31:43.220Z
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
CC BY-SA 3.0
2013-08-07T15:31:49.500Z
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](http://mathoverflow.net/questions/12426/is-there-a-computable-model-of-zfc).
Peter Shor 
CC BY-SA 3.0
2013-08-07T23:37:06.890Z
imho the 1st sentence is a good question (a proof in a format that shows the TM incompleteness is very similar to cantors diagonalization was given to me by a CS prof in college, which basically involves putting up a diagram/grid with an x/y axis where one is representing all/enumerable TMs and the other all/enumerable inputs, and then diagonalizing) but the last sentence makes no sense as [counterfactual thinking](http://en.wikipedia.org/wiki/Counterfactual_thinking) which in some ways doesnt have much place in theory, in particular.
vzn
CC BY-SA 3.0
2013-08-08T21:38:17.530Z
@vzn My intuition behind the counterfactual thinking was that the proof of the indecidability of the halting problem might actually rely on the existence of uncountable sets.
Lenar Hoyt
CC BY-SA 3.0
2013-08-08T21:44:27.000Z
mcb, asking a counterfactual question is like asking, logically, "what if false was true?" idea, though, a better question to the 2nd question might be, is there an analogue of the halting problem or diagonalization construction for countable sets. [not sure of the answer to that myself.] the answer seems to be that the construction is similar to fixed point theorems. what are some fixed point theorems that apply to countable sets? not sure.... anyway a question for you, how would one define a halting problem for countable sets anyway? the TMs and inputs in the halting problem _are_ countable!
vzn
CC BY-SA 3.0
2013-08-10T05:04:42.743Z
Please, please please say undecidability from now on.
Vijay D
CC BY-SA 3.0
2013-08-21T16:03:09.510Z
@vzn Concerning the counterfactual thinking: I just stumbled upon [this](http://mathoverflow.net/a/75022/38912), which suggests that counterfactual thinking is actually a valuable habit in mathematics and in other disciplines.
Lenar Hoyt
<halting-problem>
Is there a hidden link between the existence uncountable sets and the undecidability of the halting problem?
Lenar Hoyt
# Is there a hidden link between the existence uncountable sets and the undecidability of the halting problem?

(Asked by: username_0 on 2013-08-07)

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?

**Tags:** halting-problem

> **Comments:**
> **username_1**: Yes, the diagonal argument!  
> **username_0**: @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.  
> **username_2**: 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.  
> **username_3**: 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](http://mathoverflow.net/questions/12426/is-there-a-computable-model-of-zfc).  
> **username_4**: imho the 1st sentence is a good question (a proof in a format that shows the TM incompleteness is very similar to cantors diagonalization was given to me by a CS prof in college, which basically involves putting up a diagram/grid with an x/y axis where one is representing all/enumerable TMs and the other all/enumerable inputs, and then diagonalizing) but the last sentence makes no sense as [counterfactual thinking](http://en.wikipedia.org/wiki/Counterfactual_thinking) which in some ways doesnt have much place in theory, in particular.  
> **username_0**: @username_4 My intuition behind the counterfactual thinking was that the proof of the indecidability of the halting problem might actually rely on the existence of uncountable sets.  
> **username_4**: mcb, asking a counterfactual question is like asking, logically, "what if false was true?" idea, though, a better question to the 2nd question might be, is there an analogue of the halting problem or diagonalization construction for countable sets. [not sure of the answer to that myself.] the answer seems to be that the construction is similar to fixed point theorems. what are some fixed point theorems that apply to countable sets? not sure.... anyway a question for you, how would one define a halting problem for countable sets anyway? the TMs and inputs in the halting problem _are_ countable!  
> **username_5**: Please, please please say undecidability from now on.  
> **username_0**: @username_4 Concerning the counterfactual thinking: I just stumbled upon [this](http://mathoverflow.net/a/75022/38912), which suggests that counterfactual thinking is actually a valuable habit in mathematics and in other disciplines.  

---

## 1 answers

### Answer by username_5 on 2013-08-07. Score: 14 | Accepted answer

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](https://cstheory.stackexchange.com/questions/10635/halting-problem-uncomputable-sets-common-mathematical-proof) asking the same thing
* [Andrej Bauer's blog post](http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theorem/) about fixed point theorems and Cantor's theorem.
* [A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points](http://xxx.lanl.gov/abs/math.LO/0305282), Noson Yanofsky, 2003. Gives you a gentle introduction to Lawvere's paper, below.
* [Diagonal arguments and cartesian closed categories](http://tac.mta.ca/tac/reprints/articles/15/tr15abs.html), F. William Lawvere, 2006 republication of a 1969 article making these connections precise.
* [Incompleteness in a General Setting](http://publish.uwo.ca/~jbell/General1.%20doc.pdf), John Bell, 2007
* [From Lawvere to Brandenburger-Keisler: interactive forms of diagonalization and self-reference](http://arxiv.org/abs/1006.0992), Samson Abramsky and Jonathan Zvesper, 2010. Extension of the Lawvere arguments to game-theoretic impossibility results.


---

