Timeline for Would an oracle for Rayo's function let you compute a model of $(V, \in)$?
Current License: CC BY-SA 3.0
35 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 9, 2019 at 7:14 | comment | added | Christopher King | @lyricallywicked I think the confusion is in the term "first order set theory". First order set theory is not a set of statements implied by axioms, but is a set of sentences, which represents what syntactic validity is in that language. The name "theory" is actually a misnomer; its actually a language. However, Rayo's number is only needs the language of first order set theory. No where in the definition of Rayo's number does Rayo use a first-order set theory in the sense of a list of axioms. Im going to leave some more notes in chat. | |
| Feb 9, 2019 at 7:06 | comment | added | lyrically wicked | @PyRulez: > even though it is a very precise definition, it doesn't actually define anything, so to speak. < What does it mean? Note that Rayo's function was required (by the rules of the game) to define a specific natural number. If it does not define anything, then there is no such thing as "Rayo's number". Does this question imply that the exact value of Rayo's number depends on the underlying first-order set theory? If yes, then Rayo's number is variable, which contradicts the rules of the game. | |
| Feb 8, 2019 at 9:50 | comment | added | Christopher King | @lyricallywicked (2/2) The definition is definitely a syntactically valid definition in second order set theory (which makes reference to to first order set theory), but there are no standard semantics of second order set theory. I think these are the subtleties you were talking about. Therefore, although we know exactly what Rayo is saying, we have no idea what he means. I "fixed" this in the question by specifying that I wanted to use KM, which allows you to make assertions in second order set theory. In KM, the definition Rayo gave is correct, detailed, and verified. In ZFC, not so. | |
| Feb 8, 2019 at 9:47 | comment | added | Christopher King | @lyricallywicked (1/2) The original description (this link you sent me) seems to go to great lengths to describe Rayo's number in very precise language. The reason someone might have a problem with it is even though it is a very precise definition, it doesn't actually define anything, so to speak. | |
| Feb 8, 2019 at 9:31 | comment | added | lyrically wicked | It needs both some first-order set theory and some second-order theory. The most detailed explanation that I have found is here, but note that the author writes "I still don't understand quite how this works"! All I can say is that the amount of mathematical subtleties here is overwhelming, and this is why I wrote that it would be very interesting to see a mathematically correct, detailed and verified definition of Rayo's function... | |
| Feb 8, 2019 at 9:17 | comment | added | Christopher King | @lyricallywicked The article says that Rayo was working in the theory of second order set theory. | |
| Feb 8, 2019 at 9:14 | comment | added | lyrically wicked | I just wanted to emphasize that the mathematically correct definition (I mean any verified and established definition) of Rayo's function does not exist. This question links to the "Rayo's number" page, but that page just copies the original description, which does not contain a sufficient amount of technical details: for example, it does not mention any particular theory, and it is not clear how to interpret this (without a theory, we cannot even assume that a set exists!). | |
| Feb 8, 2019 at 8:09 | comment | added | Christopher King | @lyricallywicked I should probably specify what the question means in finite terms. Kelly Morse set theory proves certain statements about sets and classes. KM proves "$(V, \in)$ is a model of set theory. In particular, it is a model of ZFC." I make not assumptions as to whether that is "true" in any platonic sense, but KM does prove it. My original question was if KM also proves "Does Rayo's function let you compute a model of $(V, \in)$?" Again, no judgement as to whether that is true, or if it even makes sense, but we could in theory just check every possible proof to see if KM proves it. | |
| Feb 8, 2019 at 7:55 | comment | added | lyrically wicked | @PyRulez: thank you for the clarifications! It remains for me to clarify one important subtlety: is it possible that the original description does not mention any particular set theory $T$ because we can assume that $T$ itself should be included in a formula somehow (namely, prefixed to a formula)? This means that we quantify over all possible consistent theories such that for any given theory $T$, we have $(V, \in)$ as its model? | |
| Feb 8, 2019 at 7:28 | comment | added | Christopher King | @lyricallywicked No, just $(V, \in)$. And the questions asked by "satisifcation is not absolute" don't work in this context, because we are talking about satisifcation in the meta-theory, not a theory. | |
| Feb 8, 2019 at 7:16 | comment | added | lyrically wicked | One basic thing that I don't understand: is a formula required to be true in all models? Do we need to take into account that satisfaction is not absolute?.. | |
| Feb 8, 2019 at 7:10 | comment | added | Christopher King | @lyricallywicked Rayo's function takes sentences in set theory under a certain length, and sees if they are definitions of natural numbers in $(V, \in)$. If they are, since the natural numbers in $(V, \in)$ are $\mathbb N$, it just outputs the largest number corresponding to one of the definitions. $(V, \in)$ is not very special in this regard. You could also use $L$ or something. | |
| Feb 8, 2019 at 7:08 | comment | added | lyrically wicked | I am not sure what this means. In Wikipedia, I read that "If $\kappa$ is an inaccessible cardinal, then $V_{\kappa}$ is a model of Zermelo-Fraenkel set theory (ZFC) itself, and $V_{\kappa+1}$ is a model of Morse–Kelley set theory." On the other hand, "each individual stage $V_\alpha$ is a set, their union $V$ is a proper class" and Morse–Kelley set theory can handle proper classes. | |
| Feb 8, 2019 at 6:51 | comment | added | Christopher King | @lyricallywicked Rayo's function is based on the theory corresponding to the model $(V, \in)$. You can also use any model that is elementarily equivalent to it. | |
| Feb 8, 2019 at 6:50 | comment | added | lyrically wicked | I mean that if we consider a formula in the language of set theory, we need a notion of "truth in a model". But this notion is based on a given set of axioms in a theory $T$. | |
| Feb 8, 2019 at 6:44 | comment | added | Christopher King | @lyricallywicked You mean that $T$ proves that the definition is a definition, or that it proves a specific value is equal to it? | |
| Feb 8, 2019 at 6:43 | comment | added | lyrically wicked | It would be very interesting to see a mathematically correct definition of "The smallest number bigger than any finite number named by an expression in the language of set theory with $N$ symbols or less, assuming that the definition is based on a set of axioms of a set theory $T$"... I have never seen one... | |
| Feb 8, 2019 at 6:32 | comment | added | Christopher King | @lyricallywicked The question assumes kelly-morse set theory. | |
| Feb 8, 2019 at 6:31 | comment | added | lyrically wicked | @PyRulez 2/2: For example, see this post: > ZFC set theory is not sufficient [...] it is not so difficult to formalise the definition under specific axioms and semantics of second order logic or even first order MK set theory. < | |
| Feb 8, 2019 at 6:29 | comment | added | lyrically wicked | @PyRulez: Does this question imply that Rayo's number is based on some particular set theory? If yes, then I just want to note that the situation is more complex and does not necessarily allow to make such assumption (the original description does not mention any particular set of axioms). The problem is that there does not exist any established interpretation of a definition of Rayo's number. | |
| Apr 6, 2018 at 15:20 | comment | added | Christopher King | @lyricallywicked That's why I specified that we are working in Kelley-morse set theory, in which you can prove that it is well-defined. So, even if you disagree about whether or not its well-defined, you can agree that KM at least proves as much, and that KM is probably at least a consistient set of axioms to work with in. | |
| Apr 6, 2018 at 6:42 | comment | added | lyrically wicked | It's not clear to me whether Rayo's function is mathematically well-defined (Source 1, Source 2). The key requirement to such a function is given in Source 3: Even a formalist — someone who sees CH, AC, large-cardinal axioms, etc. as having no definite truth-values — should be able to agree that we've picked out a specific positive integer. | |
| Jan 21, 2018 at 2:33 | comment | added | Joel David Hamkins | Generally, if you perform more and more collapse forcing, then things can become less definable (but not always strictly so). One can definitely arrange that there is suddenly a big drop in the growth rate when $\aleph_\omega$ is collapsed, for example, since perhaps the ground model had coded an extremely fast function into the GCH pattern there. | |
| Jan 21, 2018 at 1:44 | comment | added | Christopher King | @JoelDavidHamkins I wonder how slow you can get it to grow. | |
| Jan 21, 2018 at 0:22 | comment | added | Joel David Hamkins | I should have said...and the forcing is definable and homogeneous... | |
| Jan 20, 2018 at 22:57 | comment | added | Joel David Hamkins | It seems to me that forcing in general can cause big changes in the R function, and even very mild forcing can cause big changes. But if the ground model is definable in the extension and the forcing is homogeneous, then one can get those relationships. | |
| Jan 20, 2018 at 19:59 | comment | added | Dan Turetsky | @JoelDavidHamkins You're right, I was being sloppy. Forcing will keep the two functions at the same growth rate (mod computable speedup), but getting them identical would be far more delicate (though I'm not convinced it's not true). Also, there shouldn't be any problem defining the function for a given (set) model of ZFC; it's just external to the model. | |
| Jan 20, 2018 at 19:41 | comment | added | Joel David Hamkins | Another issue concerning the forcing question is that even if you can bound the growth rate of the Rayo function of the forcing extension, by something like $R(n)^{V[G]}\leq R^V(n+k)$, for example, this doesn't mean that $R^{V[G]}$ and $R^V$ are Turing equivalent, since the Turing degree is not necessarily reflected in the growth rate. | |
| Jan 20, 2018 at 19:02 | answer | added | Joel David Hamkins | timeline score: 11 | |
| Jan 20, 2018 at 18:38 | comment | added | Joel David Hamkins | Meanwhile, one can show that $R$ computes arithmetic truth, by using it to bound the searches on existential quantifiers (shall I post an answer with this argument?). So the complexity of $R$ is at least $0^{(\omega)}$. I'm not sure how much one can push this into the hyperarithmetic hierarchy. You want to push it all the way up to $\text{Th}(V)$, which is considerably farther. | |
| Jan 20, 2018 at 18:36 | comment | added | Joel David Hamkins | @DanTuretsky I had similar ideas early this morning, but it seems to me now that things are much more subtle than this. First, it doesn't make sense to refer to Rayo's function in ZFC, since you need a truth predicate to define it. But second, it isn't at all clear that most standard forcing notions preserve Rayo's function exactly. Although it often happens that forcing preserves the definable sets and preserves which ordinals are definable, the sizes of the definitions can definitely change, and this affects the values of $R$. | |
| Jan 20, 2018 at 16:47 | comment | added | Dan Turetsky | I strongly suspect this depends on the choice of V. First, every Rayo's function is Turing Complete, so they compute some common completion of KM. So for a model of that completion, yes. I'm not terribly familiar with KM, but in ZFC, it wouldn't be hard to show that most standard forcings preserve Rayo's function. So one would be able to get uncountably many theories with the same Rayo's function, indicating that one of them isn't computed from it. Does the same work for KM? | |
| Jan 20, 2018 at 14:17 | comment | added | Joel David Hamkins | This is a great question! Note that computing a model like that is equivalent to computing the theory $\text{Th}(V)$, since from the theory we can compute a Henkin model by the effective completeness theorem. So the question is: does Rayo's function compute the first-order theory of $V$? | |
| Jan 20, 2018 at 8:57 | comment | added | Christopher King | Related | |
| Jan 20, 2018 at 8:24 | history | asked | Christopher King | CC BY-SA 3.0 |