Timeline for Would an oracle for Rayo's function let you compute a model of $(V, \in)$?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 20, 2018 at 21:41 | comment | added | Dan Turetsky | @Wojowu Earliest reference I have is the proof of theorem 6.8 from Jockusch's Uniformly Introreducible Sets (JSL 1968). It shows that for every hyperarithmetic set $A$, there is a hyperarithmetic function $f$ such that $A$ is computable from every $g$ majorizing $f$. | |
| Jan 20, 2018 at 20:40 | comment | added | Wojowu | @DanTuretsky Could you give a reference for this "standard result"? | |
| Jan 20, 2018 at 20:31 | comment | added | Dan Turetsky | For pushing it all the way up the hyperarithmetic hierarchy, there's a standard result that any function that dominates all hyperarithmetic functions computes all hyperarithmetic sets. For each $\Sigma^1_1$ set, the Rayo function should uniformly compute a function $f$ such that, if the set is the graph of a function $g$, then $f(n) > g(n)$ for all $n$. Then just taking a diagonal sum gets a dominating function. | |
| Jan 20, 2018 at 19:35 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
deleted 40 characters in body
|
| Jan 20, 2018 at 19:02 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |