Timeline for Is there constructive proof of the fact that every recursive set $A \ne \varnothing$ is recursively enumerable in non-decreasing order?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 12, 2012 at 6:20 | vote | accept | John Rice | ||
| Jan 9, 2012 at 21:43 | vote | accept | John Rice | ||
| Jan 9, 2012 at 21:43 | |||||
| Jan 9, 2012 at 7:32 | comment | added | Andrej Bauer | Ah yes, I misread the question at first I thought we wanted non-decreasing enumerations of c.e. sets. Those can't be had, or else we sovle the Halting problem quite easily. | |
| Jan 9, 2012 at 0:22 | comment | added | Goldstern | (For the reader who did not see the history: my previous comment referred to Andrej's first answer, which pointed out that an enumeration -- even of a finite set -- cannot effectively be turned into an increasing enumeration.) | |
| Jan 9, 2012 at 0:17 | comment | added | Andrej Bauer | @Goldstern: it has to be the code of a characteristic function. If we had recursive sets given by codes of their enumerations, then constructively that would correspond to "countable subsets of $\mathbb{N}$ for which it is false to assume that they are not decidable", a rather convoluted notion. | |
| Jan 8, 2012 at 23:58 | comment | added | Goldstern | Assuming that my answer is correct, together with Andrej Bauer's answer (which is certainly correct) it shows that you have to make your question more specific. How is the recursive set given? By a code for an enumeration, or by a code for its characteristic function? | |
| Jan 8, 2012 at 23:35 | answer | added | Andrej Bauer | timeline score: 11 | |
| Jan 8, 2012 at 20:00 | history | edited | Goldstern |
edited tags
|
|
| Jan 8, 2012 at 19:59 | answer | added | Goldstern | timeline score: 8 | |
| Jan 8, 2012 at 17:03 | history | edited | John Rice | CC BY-SA 3.0 |
added 8 characters in body
|
| Jan 8, 2012 at 16:50 | history | asked | John Rice | CC BY-SA 3.0 |