Timeline for What do we know about the computable surreal numbers?
Current License: CC BY-SA 4.0
50 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 15 at 11:33 | comment | added | Joel David Hamkins | @NoahSchweber It seems that in addition to that account with computable binary sequences, Lurie's paper also has an account of the computable surreals that follow my proposal here, and he made the connection with $L_{\omega_1}^{CK}$ and so forth. Much of what has been observed on this question and its answers also already appears in that paper. | |
| Jun 22 at 13:31 | comment | added | Joel David Hamkins | I have now asked that generalized c.e. set question mathoverflow.net/q/473684/1946. I call them the hereditarily computably enumerable sets. | |
| Jun 22 at 12:01 | vote | accept | Joel David Hamkins | ||
| Jun 18 at 12:05 | comment | added | Philip Ehrlich | @James E Hanson. Then we agree. | |
| Jun 18 at 5:12 | comment | added | Joel David Hamkins | Dan has now proved that the computable surreals are those with a hyperarithmetic sign sequence, and so indeed they form an initial subfield. The computable surreals are exactly the surreals in $L_{\omega_1^{CK}}$, and from this, I believe it follows that they are real-closed. | |
| Jun 18 at 5:09 | comment | added | James E Hanson | @PhilipEhrlich I think not. My argument is just for the algebraic field structure, and it seems like you're talking about the tree structure. | |
| Jun 18 at 2:40 | comment | added | Joel David Hamkins | I've realized that there is a natural generalization of the computable surreal concept to the general concept of a (generalized) c.e. set. Namely, if a program enumerates a list of programs that are generalized c.e., then so is the program itself, and the set it represents is the set whose elements are represented by the programs it has enumerated. So every computable ordinal is generalized c.e., and the generalized c.e. sets are hyperarithmetically presentable. Are they exactly the sets in $L_{\omega_1^{CK}}$? | |
| Jun 17 at 15:47 | comment | added | Joel David Hamkins | @PhilipEhrlich Good, that is what I thought. On Dan's answer, I had suggested the possibility that the computable surreal numbers are exactly the surreals with a hyperarithmetic +- sequence, which would make them initial. I think Dan's idea on the hyperarithmetic reals may generalize to produce this. | |
| Jun 17 at 15:47 | comment | added | Philip Ehrlich | @James E Hansen. I didn't say there might be one isomorphic copy, but rather one initial isomorphic copy. Does your argument rule that out? | |
| Jun 17 at 15:44 | comment | added | Philip Ehrlich | @JoelDavidHamkins. Yes. A subtree $A$ of No is initial if for each x in A, the set of predecessors of x in A coincides with the set of predecessors of x in No, where predecessors are understood in the tree-theoretic sense. There are ordered fields that are not real-closed that are isomorphic to initial subfields of No, but by an early result of mine every real-closed field is. I strongly suspect that like the reals, the structure you are concerned with is isomorphic to exactly one initial subfield of No. Initial subfields can be generated by Conway's definitions applied to the initial tree. | |
| Jun 17 at 5:47 | comment | added | Joel David Hamkins | @PhilipEhrlich Can you remind me what initial means? Does that mean that if something is in, and you take the $+-$ sequence representing it, then all the numbers arising from initial segments of that sequence are in? | |
| Jun 17 at 5:44 | comment | added | James E Hanson | @PhilipEhrlich Given that there are non-computable reals in the computable surreals, there can't only be one copy by a fairly general model-theoretic argument (assuming that by copy we mean copy as a field). This follows because the surreal numbers are a saturated model of RCF. | |
| Jun 17 at 5:41 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 167 characters in body
|
| Jun 16 at 23:47 | comment | added | Philip Ehrlich | @JoelDavidHamkins. Your query "Are the computable surreal numbers a real-closed field?" naturall raises two related queries, since every real-closed field is isomorphic to an initial subfield of No. (1) Is the system of computable surreal numbers initial? (2) Is there precisely one initial copy of the computable surreal numbers in No? | |
| Jun 16 at 8:02 | answer | added | Dan Turetsky | timeline score: 16 | |
| Jun 16 at 1:14 | answer | added | Steven Stadnicki | timeline score: 6 | |
| Jun 15 at 15:27 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
edited body
|
| Jun 15 at 15:19 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 149 characters in body
|
| Jun 15 at 15:17 | answer | added | Joel David Hamkins | timeline score: 10 | |
| Jun 15 at 14:20 | comment | added | Joel David Hamkins | If there is a gap, then the value will simply be the first-born dyadic rational in between. | |
| Jun 15 at 14:00 | comment | added | Andrej Bauer | Ah, you're quite right. Can we fix this so that the upper set is far away from the lower one, and we can't computably get closer? Maybe $x_A + x_B - x^{(n)}_B$? I am just trting to come up with a qualitatively different example, namely one that has an incompressible gap between the lower and the upper cut. | |
| Jun 15 at 13:28 | comment | added | Joel David Hamkins | @AndrejBauer Thanks for the suggestion, and I'm glad you're thinking about this. But have you written what you intended? If $A$ is c.e., then $x_A$ is a c.e. real, hence computable surreal by the argument in my answer. And this is the LUB in ℝ of the lower set in your surreal. But the upper set has $x_A$ as an element, for $n=0$, and so only $n=0$ matters there. So your surreal number is $x_A-\varepsilon$, where $\varepsilon=\{0\mid 2^{-n}\}_{n\in ℕ}$ is the first-born infinitesimal, since $x_A-\varepsilon$ is the first-born surreal filling this gap. This is also computable surreal. | |
| Jun 15 at 11:17 | comment | added | Andrej Bauer | For any $A \subseteq\mathbb{N}$ let $x_A = \sum_{k \in A} 3^{-k}$ and $x_A^{(n)} = \sum_{k \in A, k < n} 3^{-k}$. Given two computably inseparable c.e. sets $A$ and $B$, the surreal $\{ \{ x_A^{(n)} ; n \in \mathbb{N} \} \mid \{ x_A + x_B^{(n)} ; n \in \mathbb{N} \} \}$ should be of some interest. For instance, we shouldn't be able to "squeeze" the left and the right cut together all the way for such a real. | |
| Jun 15 at 0:18 | history | became hot network question | |||
| Jun 15 at 0:17 | comment | converted from answer | Joe Shipman | You only need odd prime degree polynomials to have roots, not odd degree polynomials, to get real closedness. I prefer the algebra of Conway’s other Field “On2”, consisting of the Ordinals as an underlying Class and defining nim-addition (which is just surreal addition) and nim-multiplication as the Field operations. The first algebraically closed subfield is the ordinal omega^(omega^omega); I’m not sure his problem of identifying the next one was ever solved. | |
| Jun 14 at 19:22 | comment | added | Joel David Hamkins | @JamesEHanson Nevertheless, I've realized how to get the c.e. real result. See the update in my answer, below. Every c.e. real is realized as a computable surreal number. I don't see yet, however, how to get effective suprema and infinima in the computable surreals. | |
| Jun 14 at 16:29 | answer | added | Joel David Hamkins | timeline score: 17 | |
| Jun 14 at 12:29 | comment | added | Joel David Hamkins | And this objection might pour cold water on @JamesEHanson's idea about c.e. reals. You can't just approach from one side, since that trivializes in the surreal numeral semantics. | |
| Jun 14 at 12:17 | comment | added | Joel David Hamkins | @Gro-Tsen Indeed that is something like what I had in mind. But the construction you propose doesn't quite work in the way you suggest, since any surreal number with an empty upper set will be an ordinal, an integer in this case. (In particular, it is not $\sup(r_n)$.) You have to approach the real from both sides, and this prevents a straightforward implementation of this approximation idea, since you don't computably know the optimal upper bounds. | |
| Jun 14 at 10:20 | comment | added | pcpthm | Lean mathlib contains a definition of inductively-defined combinatorial games, but inverse is defined using excluded-middle. | |
| Jun 14 at 9:37 | comment | added | Gro-Tsen | Is it not clear that if you call $(r_n)$ the dyadic rational whose $k$-th binary digit is $1$ when $k≤n$ and the $k$-th Turing machine halts in less than $n$ steps, and $0$ otherwise, thus defining a Specker sequence, then $\{r_n|\}$ as a surreal (computable in your sense) equals $\sup(r_n)$ as a real, which is not computable? Your paragraph following question (2) suggests you saw this argument but have at least a little doubt about it: to me it seems convincing, no? | |
| Jun 14 at 4:25 | comment | added | Joel David Hamkins | @Anixx The programs are those that enumerate two sequences of programs, which obey the order condition and which also fulfill the recursive definition. (If they halt, then both sides will be finite, but that is fine, so halting/nonhalting is not necessarily an obstacle, although one expects that interesting surreals will have infinite cuts, so nonhalting.) Nevertheless, as I mention in the post, the decision problem to decide if a program computes a surreal number is $\Pi^1_1$-complete. This is way beyond the halting problem in complexity, and is even beyond what is arithmetically definable. | |
| Jun 14 at 4:19 | comment | added | Anixx | What kind of programs are allowed? I mean, due to the halting problem there could be programs about which we do not know if they denote a number or not... | |
| Jun 14 at 3:41 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
A little more clarity on the definition.
|
| Jun 14 at 2:28 | comment | added | Joel David Hamkins | @NoahSchweber Thanks very much! He seems to take the binary ordinal sequence approach as primitive (which seems misguided to me), and then observes (by Harkleroad), if I've followed, that you can't add. In this sense, my definition seems better. But I need to look more. (It would be the surreal analogue of Turing's mistake with computable real numbers, to insist we can compute the digits...) | |
| Jun 14 at 2:24 | comment | added | Noah Schweber | I suspect Lurie's old paper Effective content of surreal algebra will be relevant here, but it's been a while since I looked at it so I can't immediately say if/how it addresses your specific questions here. | |
| Jun 14 at 2:20 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
edited body
|
| Jun 14 at 2:15 | comment | added | Joel David Hamkins | @HarryAltman Indeed, by earlier born, I meant that the number was born earlier, that is, that it appeared at an earlier stage of the transfinite construction process. I think of this as the core concept, in light of the gap-filling construction process. But indeed you are right, the prefix relation is very commonly considered. I tried to ask about both of these relations, in questions 5 and 6. | |
| Jun 14 at 2:08 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 296 characters in body
|
| Jun 14 at 1:28 | comment | added | Joel David Hamkins | Regarding the earlier @JamesEHanson question, looking in detail at the definitions of $x+y$, $x-y$, $x\cdot y$ and $x/y$, it seems in each case we have a recursive formula, which reduces the desired output to one determined by left/right sets with earlier applications of that same function. By Kleene fixed-point theorem, there is a computable process that solves this recursion, and so it seems to me that all of these are computable operations on the computable surreal numbers. So indeed the computable surreal numbers form a field. | |
| Jun 14 at 1:20 | comment | added | Harry Altman | By "earlier born" do you mean "simpler than" (i.e., is a prefix of, in sign-sequence representation) or do you just mean having a lower birthday? I guess both of these yield canonical forms, but I thought the former was the more usual one? I guess could ask about both, or ask about the "simpler than" relation itself perhaps? | |
| Jun 14 at 0:40 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 4 characters in body
|
| Jun 14 at 0:29 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 365 characters in body
|
| Jun 14 at 0:13 | comment | added | Joel David Hamkins | Regarding $x+y$, perhaps it helps to say that the defining formulas give us computable procedures for the defining the sum of any programs at all, but when $x$ and $y$ are actually computable surreal numbers, then the resulting output $x+y$ will also be a computable surreal number. So the effective transfinite recursion is in effect sublimated. (But I also want to think this through thoroughly.) | |
| Jun 14 at 0:07 | comment | added | Joel David Hamkins | Yes, that seems right, and it is what I was thinking about with the halting problem proposal. My conjecture is that you get exactly the hyperarithmetic reals. Please post an answer explicating this idea, if you would. | |
| Jun 14 at 0:05 | comment | added | James E Hanson | I'll have to think about that. Regarding 2, shouldn't it be fairly immediate that any left (or right) c.e. irrational real is a computable surreal number? Moreover, I think you should get closure under computable infima and suprema (that happen to be irrational) fairly immediately, which should give you all hyperarithmetic reals. | |
| Jun 14 at 0:03 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
edited body
|
| Jun 13 at 23:57 | comment | added | Joel David Hamkins | I thought the usual definitions of $x+y$ and $-x$ and $x/y$ are computable operations. One writes down formulas for the left and right sets of the resulting real in terms of the input sets, and this provides a means of showing that these numbers remain computable if $x$ and $y$ are. Well-foundedness will be preserved, as well as the hereditary order. (Unless: do the formulas require us sometimes to check the order relation on hereditary parts of the numbers? If so, this will be too complicated for computable.) | |
| Jun 13 at 23:56 | comment | added | James E Hanson | This is a really nice question, but is it easy to see that the computable surreals are actually closed under the standard field operations? I assume you need to use effective transfinite recursion or something to show this. | |
| Jun 13 at 23:52 | history | asked | Joel David Hamkins | CC BY-SA 4.0 |