Timeline for Is the set of rational numbers recursive?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 29, 2017 at 13:32 | comment | added | Benedict Eastaugh | @FrodeBjørdal if you want to see a standard development along the lines Andreas suggests, have a look at page 74 of Simpson's Subsystems of Second Order Arithmetic. | |
| Mar 18, 2017 at 22:13 | comment | added | Andreas Blass | There may be a reference, but I don't know one. I considered this obvious. | |
| Mar 18, 2017 at 22:12 | comment | added | Frode Alfson Bjørdal | It is first of all important to me simply to know that $\mathbb{Q}$ can be had as a recursive set of natural numbers. Is there a standard reference, or is this simply folklore (obvious)? | |
| Mar 18, 2017 at 22:10 | comment | added | Frode Alfson Bjørdal | mathoverflow.net/questions/264991/is-q-recursive | |
| Mar 18, 2017 at 22:06 | comment | added | Frode Alfson Bjørdal | Thanks! I will consider this. I am just preparing a follow up question where I attempt to use the $\mu$-function. I link to that in these comments when I post it in a minute. | |
| Mar 18, 2017 at 21:57 | comment | added | Andreas Blass | If I were concerned about complexity, I'd define the (positive) rational numbers simply as (codes for) ordered pairs, like the $x;y$ in the question, such that $y\neq 0$ and such that $x$ and $y$ have no common divisor but 1. In other words, fractions in lowest terms (coded as natural numbers). If (unlike the definition you quoted) I also wanted to include negative rationals, I'd code in a sign along with the numerator and denominator. This coding makes $\mathbb Q$ a recursive set of natural numbers. | |
| Mar 18, 2017 at 20:57 | comment | added | Frode Alfson Bjørdal | Are there more effective versions of $\mathbf{Q}$ which are $\Delta_1$? | |
| Mar 18, 2017 at 20:53 | vote | accept | Frode Alfson Bjørdal | ||
| Mar 18, 2017 at 20:47 | history | answered | Andreas Blass | CC BY-SA 3.0 |