computability, number theory, and continuum hypothesis

293 Views Asked by At

Is there any similarity between proofs of unsolvability results in computability theory (and decision procedures for identities in number theory) and the independence of the continuum hypothesis in set theory? See e.g.,

A. A. Muchnik, On the unsolvability of the problem of reducibility in the theory of algorithms. (in Russian) Doklady Akademii Nauk SSSR (N.S.), vol. 108 (1956), pp. 194–197.

Note 1. Relevant links were pointed out by Noah Schweber: on computability and Ethan Bolker: on number theory.

2

There are 2 best solutions below

1
On

No, there isn't really. The independence of the continuum hypothesis means that (assuming ZFC is consistent) we can find models $A$ and $B$ of ZFC such that CH is true in $A$ but false in $B$, and is proved by developing a method of constructing models of ZFC. The unsolvability of the word problem, meanwhile, just asserts that a certain set is not computable, and is proved by showing that we can code the halting problem into the word problem - this does involve a construction (understanding how to make groups and words "to order"), but the construction is completely unrelated to forcing. These results and proofs don't really have anything to do with each other.

There is a vague connection between forcing and oracle computations in computability theory, where we think of "in $V$" as "computable" and "in $V[G]$" as "computable from $G$" (and I suspect the source you're thinking of is one where Cohen mentioned that this analogy, following his learning of the Friedberg-Muchnik theorem, helped conceptualize forcing - although as I recall, this statement was made long after the discovery of forcing, and contradicts earlier statements of Cohen; I'll try to track down the citation and commentary). However, this doesn't actually relate CH-independence to word problem-unsolvability, it just says that we should expect computability-theoretic intuition to sometimes be useful in understanding forcing arguments (and vice versa).


EDIT: Re: the possibility of a connection with Friedberg-Muchnik (and priority arguments in general) in place of group-theoretic unsolvability, this was addressed at this mathoverflow question. Incidentally, note that there I was unable to track down the reference I remember in which Cohen spoke of this connection, so even that might not have ever been made by Cohen. That said, an analogy was drawn by others (e.g. Kreisel, Nerode, Remmel), and I think it is a very fruitful one. So I would say yes, there is a strong analogy here; however, it may not have ever been noted by Cohen, contrary to my prior claim.

2
On

Both belong to a loose class of mathematical results saying that something is not achievable by such-and-such kit of tools. The irrationality of $\sqrt{2}$ is most likely the first result in this class. Then follow the angle-trisection and a few other similar ancient problems. And a zillion more of the same has come with the modern mathematics, including the CH problem.