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?
Asked
Active
Viewed 832 times
9
-
10Yes, the diagonal argument! – Mahdi Cheraghchi Aug 07 '13 at 14:51
-
1@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 Aug 07 '13 at 14:59
-
4This 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 07 '13 at 15:31
-
9There 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. – Peter Shor Aug 07 '13 at 15:31
-
1imho 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 which in some ways doesnt have much place in theory, in particular. – vzn Aug 07 '13 at 23:37
-
@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 Aug 08 '13 at 21:38
-
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 Aug 08 '13 at 21:44
-
4Please, please please say undecidability from now on. – Vijay D Aug 10 '13 at 05:04
-
@vzn Concerning the counterfactual thinking: I just stumbled upon this, which suggests that counterfactual thinking is actually a valuable habit in mathematics and in other disciplines. – Lenar Hoyt Aug 21 '13 at 16:03
1 Answers
14
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.
