Timeline for What do we know about the computable surreal numbers?
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17 at 14:10 | comment | added | Joel David Hamkins | I think perhaps a transfinite modification of your real argument might show this. | |
| Jun 17 at 14:02 | comment | added | Joel David Hamkins | That is an interesting observation. For the general case, I wonder if it would help to think about the +- sequence representation, which is hyperarithmetic, and try the same trick? Perhaps computable surreal = hyperarithmetic +- sequence? It's true for reals, and also for ordinals. | |
| Jun 17 at 13:56 | comment | added | Dan Turetsky | I edited a bit of discussion about reciprocals into my answer. Since computable surreals have computable reciprocals inside the reals, I suspect that this remains true in general. I don't know how to prove it, though. | |
| Jun 17 at 13:14 | comment | added | Dan Turetsky | Suppose $<$ were $\Sigma^0_\alpha$ for some $\alpha$. For any $\Sigma^c_\alpha$ sentence $\phi$, we can build the real $b_\phi$ as I described, and this is entirely uniform. So $\phi$ is true iff $\neg (b_\phi < 1/2)$, which means the truth predict on $\Sigma^c_\alpha$ sentences becomes $\Pi^0_\alpha$, a contradiction. | |
| Jun 17 at 5:50 | comment | added | Joel David Hamkins | I meant nonhyperarithmeticity. And could you elucidate how you show $x<y$ can't be hyperarithmetic? | |
| Jun 17 at 5:29 | comment | added | Joel David Hamkins | @DanTuretsky Oh dear, you are right--I have now edited. I should have said $x<y$ iff $x\leq y_L$ or $x_R\leq y$ in some instance, but this isn't enough for the c.e. argument. Do you think that you can use the hyperarithmeticity of $<$ to produce a computable positive surreal whose reciprocol is not computable? | |
| Jun 17 at 5:28 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
Removed wrong argument about x<y
|
| Jun 17 at 2:36 | comment | added | Dan Turetsky | I don't believe your argument that $<$ is c.e.. Another way to have $x < y$ is for $x = y_L$, for some $y_L$ in the left set of $y$. In fact, my argument about encoding the truth of a sentence $\phi$ into a real would say that $<$ can't be hyperarithmetic. | |
| Jun 16 at 16:33 | comment | added | Joel David Hamkins | It's definitely not Archimedean, since omega is computable (and much more). But also computable surreals are not computable Cauchy complete. | |
| Jun 16 at 14:55 | comment | added | Andrej Bauer | Moschovakis's result ought to be somewhere in this paper, probably around Theorem 5. | |
| Jun 16 at 14:47 | comment | added | Andrej Bauer | There is an old theorem of Moschovakis (from his Ph.D. thesis I think), that characterizes up to computable isomorphism the structurecomputable reals as the computable field with semidecidable $<$, computable $|{-}|$, computably Cauchy complete and computably archimedean. Which of these properties fails for the computable surreals? It must be the archimedean axiom. | |
| Jun 16 at 9:14 | comment | added | Joel David Hamkins | @StevenStadnicki Ah, yes, you are correct to notice this, but it is no problem for the application of Kleene recursion. The point will be that there is a program that carries out that recursion. Whenever it places something into the left set of $1/y$, then it will also be placing this other updated thing as well, and similarly for the right set. That is a nice way of representing the iteration I was talking about above. | |
| Jun 16 at 0:54 | comment | added | Steven Stadnicki | Speaking of iteration, you might want to ponder on the definition of $1/y$ from Wikipedia again; it's qualitatively different from the definitions for $+$ and $\times$ in that it involves the options to previous approximations of $1/y$. Square root (which I found and will offer up in a new answer) has the same issue. | |
| Jun 15 at 21:28 | comment | added | Joel David Hamkins | I suppose, of course, that one will need to iterate that approximation idea. (Obviously it is absurd to think it would always work without iteration.) But how long do we iterate? If transfinite, this might take us out of computability. | |
| Jun 15 at 21:06 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
Edit for subtlety about x<y
|
| Jun 15 at 20:19 | comment | added | Joel David Hamkins | My first idea is also naive, even for $\sqrt{3}$, since $3=\{2\mid \ \}$, but information about $3/2$, $2/3$ and $\sqrt{2}$ will not be enough to determine the cut of $\sqrt{3}$. So, I don't know how to compute $\sqrt{x}$ in the surreals. | |
| Jun 15 at 17:19 | comment | added | Steven Stadnicki | IIRC there's a definition for sqrt() in ONAG, though I wouldn't 100% trust it; I'll take a look when I have a chance. | |
| Jun 15 at 16:54 | comment | added | Joel David Hamkins | But I think the first idea does work for $\sqrt{\omega}$. | |
| Jun 15 at 16:31 | comment | added | Joel David Hamkins | That latter naive idea doesn't work correctly for $\sqrt{\omega}$. | |
| Jun 15 at 16:09 | comment | added | Joel David Hamkins | Or what about $\{\sqrt{x_L}\mid\sqrt{x_R}\}$? If $x>1$, this seemingly has a tighter gap than $x$ itself, so it might equal $\sqrt{x}$? Perhaps that's naive. | |
| Jun 15 at 15:50 | comment | added | Joel David Hamkins | Perhaps an idea for computing $\sqrt{x}$ is the standard way of approximating this by division, namely, for each positive $x_L$ we form $x/x_L$ and then compare the result with $x_L$. The larger of these is above $\sqrt{x}$ and the smaller is below $\sqrt{x}$. So we are getting closer to $\sqrt{x}$. And we can recursively also compute $\sqrt{x_R}$ in the same way, and these will be above $\sqrt{x}$. Does this simple idea produce $\sqrt{x}$? | |
| Jun 15 at 15:37 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 1027 characters in body
|
| Jun 15 at 15:17 | history | answered | Joel David Hamkins | CC BY-SA 4.0 |