Timeline for A Bijection Between the Reals and Infinite Binary Strings
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 29, 2016 at 16:13 | vote | accept | Austin Mohr | ||
| May 15, 2011 at 7:47 | comment | added | Sridhar Ramesh | I don't suppose there's any way to get a line break to remain in a comment? I feel it would sometimes make them easier to read. (Well, I suppose it's in keeping with the "Don't write lengthy comments" ideology here...) | |
| May 15, 2011 at 7:45 | comment | added | Sridhar Ramesh | @Tony: Of course, "constructive" means different things to different people. For example, any bijection from R to 2^N a fortiori yields (countably many) non-constant (and thus discontinuous) maps from R to 2. But there are consistent models of impredicative intuitionistic logic (i.e., topoi), in which all functions on R (construed as, say, the Dedekind reals) are continuous. So if constructive proofs are identified with those valid in this logic, then there is no constructive proof of the sought bijection. (As opposed to "constructive" in the sense allowing Excluded Middle but not Choice) | |
| May 15, 2011 at 1:50 | answer | added | Peter Luthy | timeline score: 3 | |
| May 14, 2011 at 22:33 | comment | added | George Lowther | Actually, I see that fedja's answer is along the same lines as my comment. | |
| May 14, 2011 at 22:12 | comment | added | user3462 | Would this be too much? Fix an enumeration of a countable basis over $\mathbb{R}$. Now, every element of $\mathbb{R}$ gives you an infinite binary string (of the basis elements it is contained in). | |
| May 14, 2011 at 22:08 | comment | added | George Lowther | You can map an $x\in A$ to a sequence of positive integers $n_0,n_1,\ldots$ encoding the length of each successive run of equal digits in its expansion (this sequence terminates if the expansion ends in recurring 0s or 1s), and also to an $\epsilon\in\{0,1\}$ denoting the first digit in the expansion. This can be used to construct a continued fraction and give a bijection with $\mathbb{R}$ (but I'm not sure of the best way to do this yet). | |
| May 14, 2011 at 21:59 | answer | added | fedja | timeline score: 7 | |
| May 14, 2011 at 21:30 | answer | added | Stefan Geschke | timeline score: 5 | |
| May 14, 2011 at 20:28 | comment | added | Tony Huynh | Correction: Encode each digit $x$ in base 10 as a string of $x+1$ consecutive 1's, and use a 0 as a place holder between digits except use a 00 instead of 0 as a place holder for the decimal point. | |
| May 14, 2011 at 20:27 | comment | added | Seva |
How about this: given a real $x$, consider the binary representation $0.d_1d_2d_3...$ of the number $\frac12+\frac1{\pi}\arctan x$ and map $x$ to $f(x):=10^{-1}d_1+10^{-2}d_2+10^{-3}d_3+...$ Clearly, all digits in the decimal representation of $f(x)$ are equal to either $0$ or $1$, the map $x\mapsto f(x)$ is injective (as far as I can see), and the added benefit is that the domain of $f$ is the set of all real numbers (not only positive).
|
|
| May 14, 2011 at 20:18 | answer | added | KP Hart | timeline score: 2 | |
| May 14, 2011 at 20:11 | comment | added | Tony Huynh | Also, the proof of Cantor-Bernstein does not require the Axiom of Choice, so this is constructive. | |
| May 14, 2011 at 20:09 | history | edited | Austin Mohr | CC BY-SA 3.0 |
edited title
|
| May 14, 2011 at 20:08 | comment | added | Tony Huynh | To expand on gowers comment, just encode digit $x$ by a string of $x$ consecutive 1's, and place a single 0 between each string of 1's. For the digit before the decimal place and the one after put two 0's instead of one. | |
| May 14, 2011 at 19:55 | comment | added | gowers | I should add that you need to encode whether the digit is before or after the decimal point. | |
| May 14, 2011 at 19:53 | comment | added | gowers | How about just encoding the non-terminating decimal expansion as a sequence of 0s and 1s digit by digit? | |
| May 14, 2011 at 19:42 | comment | added | Andrés E. Caicedo | A nice argument goes by seeing that there is an injection ${\mathbb R}\to{\mathcal P}({\mathbb Q})$ (identify reals with left sides of Dedekind cuts). | |
| May 14, 2011 at 19:41 | history | edited | Andrés E. Caicedo | CC BY-SA 3.0 |
deleted 60 characters in body
|
| May 14, 2011 at 19:28 | history | asked | Austin Mohr | CC BY-SA 3.0 |