Timeline for What Turing degree would allow you to "compute" the axioms of ZFC in some countable model of ZFC?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 31, 2017 at 19:46 | history | edited | Asaf Karagila♦ |
edited tags
|
|
| Sep 6, 2017 at 13:18 | comment | added | Noah Schweber | @EmilJeřábek It definitely can't compute BB as such, since BB is equivalent to $0'$ and there are PA degrees not computing $0'$ (e.g. low PA degrees). | |
| Sep 6, 2017 at 13:14 | answer | added | Noah Schweber | timeline score: 2 | |
| Jul 18, 2017 at 6:35 | comment | added | Christopher King | @JoelDavidHamkins okay | |
| Jul 17, 2017 at 18:18 | comment | added | Joel David Hamkins | @PyRulez I have a way of answering your recently deleted question about computing relative to a nonstandard number $H$, and if you want to undelete it, I can post it. | |
| Jul 17, 2017 at 12:56 | comment | added | Emil Jeřábek | I'm not sure it can compute the BB function as such, but it can compute the function that the model thinks is the BB function. (Note that the model has nonstandard integers.) | |
| Jul 17, 2017 at 12:48 | comment | added | Christopher King | @EmilJeřábek oh sorry. Can a PA-degree compute the busy Beaver finding, since the busy Beaver function is definable in ZFC? | |
| Jul 17, 2017 at 12:46 | comment | added | Emil Jeřábek | Sorry, can you make that a complete sentence? The Busy Beaver function what? | |
| Jul 17, 2017 at 12:07 | comment | added | Christopher King | @EmilJeřábek even the busy Beaver function? | |
| Jul 17, 2017 at 2:31 | comment | added | Christopher King | @AndreasBlass each individual axiom of replacement asserts the existence of only one set. Each set has a specific code, so each individual axiom is computable. (Oh wait, nvm, it quantifies over the domain, I'll fix that later.) | |
| Jul 16, 2017 at 21:54 | comment | added | Andreas Blass | Although Emil has answered the question, I'm wondering about one aspect of the question, namely the idea that replacement is somehow easier than specification. "Hard coding constants" looks reasonable for the axiom of infinity, since it asserts the existence of a single set with some properties, but I don't see how it would work for replacement (and not for specification). | |
| Jul 16, 2017 at 21:48 | comment | added | Emil Jeřábek | A PA-degree computes a Henkin completion of ZFC, i.e., a model of ZFC along with its satifaction predicate. So, it computes all definable relations in the model, which also implies it computes any (multi)function definable in the model. This includes all the listed properties. | |
| Jul 16, 2017 at 20:22 | history | edited | Christopher King | CC BY-SA 3.0 |
edited title
|
| Jul 16, 2017 at 20:11 | history | asked | Christopher King | CC BY-SA 3.0 |