Timeline for Difference between constructive Dedekind and Cauchy reals in computation
Current License: CC BY-SA 4.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 11 at 7:56 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
http -> https (the question was bumped anyway)
|
| Dec 31, 2023 at 15:05 | comment | added | Paul Taylor | @CarlMummert: please would you give (me) citations for "people have seriously considered computing with Dedekind cuts in computable analysis and Reverse Mathematics". | |
| Dec 27, 2023 at 18:28 | answer | added | Gro-Tsen | timeline score: 5 | |
| Dec 27, 2023 at 16:49 | answer | added | Christopher King | timeline score: 6 | |
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Dec 13, 2016 at 14:28 | answer | added | Ben | timeline score: 8 | |
| Apr 20, 2016 at 14:07 | vote | accept | Rubi Shnol | ||
| Apr 20, 2016 at 11:55 | history | edited | Rubi Shnol | CC BY-SA 3.0 |
Made the title shorter with keeping its content
|
| Apr 19, 2016 at 20:30 | history | edited | Paul Taylor | CC BY-SA 3.0 |
changed title
|
| Apr 19, 2016 at 18:20 | comment | added | Carl Mummert | @Paul Taylor: the example is for decidable cuts, so the right side is just the complement of the left side, modulo possibly the rational value of the cut. But the example has open cuts. (You responded to that part of the comment). In any case, I do believe that people have seriously considered computing with Dedekind cuts in computable analysis and Reverse Mathematics, at least, and that cuts were abandoned exactly because they were not as convenient a framework as quickly converging Cauchy sequences. Whether cuts are more convenient in other areas is most likely a matter of opinion. | |
| Apr 19, 2016 at 18:16 | comment | added | Paul Taylor | @CarlMummert - If the cut is "decidable" then it has a decision procedure, which is extra structure, not just a property, and that amounts to providing the right cut. Also, the two parts of the cut are not complementary if the real number that they define is rational. (The comment to which I was replying has vanished.) | |
| Apr 19, 2016 at 16:42 | comment | added | Paul Taylor | @CarlMummert - Your example is an artificial difficulty. It amounts to saying that you can't obtain the right cut from the left. This is why I said below that cuts are two-sided. | |
| Apr 19, 2016 at 13:52 | answer | added | Carl Mummert | timeline score: 13 | |
| Apr 19, 2016 at 11:49 | comment | added | Carl Mummert | @Paul Taylor: there is no algorithm that, given any two left sides of Dedekind cuts, computes the left side Dedekind cut of their difference. The arithmetical operations on Dedekind cuts have several issues of this sort. This is why the formalization in Reverse Mathematics uses quickly converging Cauchy sequences, and why some other formulations use a kind of binary expansion with bits for $1$, $0$, and $-1$. | |
| Apr 19, 2016 at 8:20 | comment | added | Paul Taylor | "Dedekind cuts are notoriously unpleasant in terms of actual computation." Where is the evidence for this? Who, apart from @AndrejBauer and me, has ever seriously considered computation with Dedekind cuts? | |
| Apr 18, 2016 at 19:00 | answer | added | Paul Taylor | timeline score: 9 | |
| Apr 17, 2016 at 23:09 | comment | added | Jason Rute | My initial guess is that you want the definition so that you know if q is in the set U or L, but not if it is not in U and not in L. Otherwise, you will have trouble with the boundary $x$ of U and L (if there is such a point) which by (1) shouldn't be in either set. | |
| Apr 17, 2016 at 23:05 | comment | added | Jason Rute | In the Dedekind definition, if I am given L and q, do I know if q is in L? If q is not in L? (I am more of a computability theorist than a constructivist, so I am sort of asking if L and U are $\Sigma^0_1$ or $\Pi^0_1$ or computable sets. I guess it comes down to that I still have no idea what a "set" is in constructive mathematics.) | |
| Apr 17, 2016 at 22:51 | comment | added | Jason Rute | @James, I think the located condition ensures downward (and upward) closer. If q' < q and q in L, then since the sets are disjoint, q' in L by the locatedness condition. | |
| Apr 17, 2016 at 21:36 | comment | added | James | Also, there is an efficient way to convert between the two. We can code a Dedekind real (L,U) by a set X of natural numbers, and there is a Turing machine which computes a Cauchy representation of a real given the code for the Dedekind representation as an oracle, and vice versa. | |
| Apr 17, 2016 at 21:28 | comment | added | James | Your definition of Dedekind real also needs that L is closed downwards and U is closed upwards. | |
| Apr 17, 2016 at 20:14 | history | edited | Rubi Shnol | CC BY-SA 3.0 |
added 424 characters in body
|
| Apr 17, 2016 at 20:01 | comment | added | Jason Rute | Can you remind me exactly what a Dedekind and Cauchy real is in this context? Are the Dedekind reals one or two-sided Dedekind cuts? From your question, it also seems the Cauchy sequences need rates of convergence. | |
| Apr 17, 2016 at 19:28 | history | asked | Rubi Shnol | CC BY-SA 3.0 |