Three funny proofs of the existence of incomparable Turing degrees
“People would usually spend a whole class in computability theory proving this. What they are doing is they are very carefully proving the Baire category theorem without explicitly saying it.”
I’ve recently learned of a pretty neat proof of the existence of incomparable Turing degrees. And this reminds me that I’ve actually seen quite a few funny (nuking-the-mosquito-type) proofs of this statement, so I decided to record them here.
The first proof was shown to me today by Andrew Marks. You can do this with either measure or category:
Consider the relation
Hence,
The second proof I saw on the internet (for example here). It uses the observation that the continuum hypothesis follows from total comparability of the Turing degrees: each real computes countably many reals, so the reals ordered by
Now just force to negate CH. In the extension,
The third proof is somewhat similar to the second. I came up with it when I was thinking about the question “if a real is computable from a comeager set of reals, is it computable?” The measure analogue of this is true, and this was the first interaction between computability theory and measure theory. That result was indepdently obtained by Sacks, and De Leeuw-Moore-Shannon-Shapiro. The answer to my question is also yes, and the argument I came up with had already appeared in Andreas Blass’s Needed reals and recursion in generic reals 20 years ago.
The proof goes like this: force to add two Cohen reals, then neither computes the other. But again it’s
The key fact used in the proof is that Cohen reals hold no computation power. I think this is an independently interesting fact, so I’ll end this post with a properly written proof.
Theorem. Let
Proof. If
For any
As soon as any of these computations halt, the output will be the correct value of