Timeline for Awfully sophisticated proof for simple facts
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 10 at 5:12 | comment | added | Lucenaposition | First time I saw somebody assume CH is false to prove something that holds unconditionally. | |
| Dec 28, 2010 at 20:38 | comment | added | Andreas Blass | A lesser form of overkill: Instead of forcing to violate CH, just adjoin two independent Cohen reals. Neither is computable from the other, because neither is in the model of ZFC generated by the other. Then invoke absoluteness. About John Steel's comment that eliminating the machinery leaves one with a Baire category argument: If you eliminate even more machinery by inserting the proof of the Baire category theorem (for this special case), you get back to the original Kleene-Post proof. | |
| Oct 19, 2010 at 14:23 | comment | added | Andrés E. Caicedo | Hi Joel, I once had an interesting conversation with a recursion theorist about this; Andre Nies, I believe. There is some amount of literature on this idea (for example, Sacks book begins with forcing, and the one time I taught recursion theory, I presented several examples, even using the forcing language); but there are also some known results indicating some constructions that cannot be achieved this way (meaning, there is a point to priority arguments). | |
| Oct 19, 2010 at 13:38 | comment | added | Joel David Hamkins | Andres, thanks for mentioning this! My view is that many constructions in computability theory are fruitfully thought of as forcing constructions, and this is the natural destination of that view. When I teach computability theory, for example, I try when possible to set up the constructions as the problem of meeting dense sets in a partial order, specifically to emphasize this. | |
| Oct 17, 2010 at 19:12 | comment | added | Andrés E. Caicedo | I was learning recursion theory from John Steel, and when I thought of this, of course I had to mention it to him. He laughed briefly and said that eliminating all the machinery leaves one with a Baire category argument. Of course, this gives more information, we get that there is a comeager set of reals $x$ with $\omega_1^{CK}(x)=\omega_1^{CK}$. | |
| Oct 17, 2010 at 19:05 | comment | added | Stefan Geschke | Also Noam Greenberg has this argument on his homepage. The simple diagonalization that you mention can actually be cast as a Baire category argument: For each Turing machine $M$, the set of pairs $(x,y)$ such that $M$ witnesses $x\leq_Ty$ is nowhere dense. Since there are only countably many Turing machines, there is a pair of incomparable Turing degrees by the Baire category theorem. | |
| Oct 17, 2010 at 18:18 | history | edited | Andrés E. Caicedo | CC BY-SA 2.5 |
Added some details.
|
| Oct 17, 2010 at 18:12 | history | edited | Andrés E. Caicedo | CC BY-SA 2.5 |
deleted 1 characters in body
|
| Oct 17, 2010 at 16:49 | history | answered | Andrés E. Caicedo | CC BY-SA 2.5 |