# Halting problem, uncomputable sets: common mathematical proof?

It is known that with a countable set of algorithms (characterised by a Gödel number), we cannot compute (build a binary algorithm which checks belonging) all subsets of N.

A proof could be summarized as: if we could, then the set of all subsets of N would be countable (we could associate to each subset the Gödel number of the algorithm which computes it). As this is false, it proves the result.

This is a proof I like as it shows that the problem is equivalent to the subsets of N not being countable.

Now I'd like to prove that the halting problem is not solvable using only this same result (uncountability of N subsets), because I guess those are very close problem. Is it possible to prove it this way ?

• Clearly both results can be proved by using the same technique (diagonalization). However, I do not think that it is possible to prove the undecidability of the halting problem just by using the uncountability of the family of subsets of ℕ, because the former is about the comparison between RE and R, both of which are countable families of subsets of ℕ. – Tsuyoshi Ito Mar 11 '12 at 12:30
• There are only countably many programs with access to the halting oracle, again characterized by a Godel number. However, the halting problem IS among this countable set. – David Harris Mar 11 '12 at 13:09

The halting theorem, Cantor's theorem (the non-isomorphism of a set and its powerset), and Goedel's incompleteness theorem are all instances of the Lawvere fixed point theorem, which says that for any cartesian closed category, if there is an epimorphic map $e : A \to (A \Rightarrow B)$ then every $f : B \to B$ has a fixed point.