Importantly, I am looking for a constructive proof (which does not rely on the Cantor–Bernstein–Schroeder theorem). Motivated by this discussion.
$\begingroup$
$\endgroup$
16
-
3$\begingroup$ Here is something which might not work exactly, but should be on the right lines: represent pairs of real numbers as pairs of binary strings, then interleave them. (My caveat is because of non-uniqueness issues to do with $\sum_{n\geq 1} 2^{-n} = 2^0$ but one should be able to tweak the idea.) $\endgroup$– Yemon ChoiMar 31, 2013 at 3:53
-
2$\begingroup$ I assume by constructive, you mean just mean "without Cantor–Bernstein–Schroeder and without axiom of choice" (the former is actually provable without the later). But if you happen to mean constructive in the style of, say, Bishop's constructive math, then you need a homoemorphism between $\mathbb{R}$ and $\mathbb{R^2}$, of which none exists (or at least I recall having heard this, I don't know the proof off hand that there is none). This gives some insight into why this is a tricky problem. $\endgroup$– Jason RuteMar 31, 2013 at 8:16
-
2$\begingroup$ @Jason, why does a Bishop-constructive bijection have to be a homeomorphism? (As for why the two are not homeomorphic in their usual topologies, removing a point from R disconnects it, but removing a point from R^2 does not.) $\endgroup$– Yemon ChoiMar 31, 2013 at 8:40
-
5$\begingroup$ Asaf, many constructive systems include the axiom of choice or large fragments thereof, so using the axiom of choice is not a very good test for non-constructiveness. $\endgroup$– François G. DoraisMar 31, 2013 at 13:47
-
4$\begingroup$ The Cantor–Bernstein–Schroeder theorem yields a constructive proof and does not rely on the Cantor–Bernstein–Schroeder theorem. $\endgroup$– YCorMay 29, 2018 at 10:46
|
Show 11 more comments
1 Answer
$\begingroup$
$\endgroup$
4
Here is a bijection that uses the decimal (or binary, whatever) expansion of reals. (Even though I think the approach using continued fractions is more canonical.)
- Let $\alpha:\mathbb Z\times \mathbb Z\to \mathbb Z$ and $\beta:[0,1)\times [0,1)\to [0,1)$ be bijections.
- Let $f:\mathbb R \to \mathbb Z \times [0,1) $ be the natural bijection $x\mapsto (\lfloor x\rfloor, x-\lfloor x\rfloor)$.
- Together, $f$, $\alpha$, $\beta$ will define bijections $$ \mathbb R\times \mathbb R \to^f (\mathbb Z\times [0,1)) \times (\mathbb Z\times [0,1)) \simeq \mathbb Z^2 \times [0,1)^2 \to ^{\alpha,\beta} \mathbb Z \times [0,1) \to^{f^{-1}}\mathbb R$$
The main part is of course the definition of $\beta$. [EDIT: This is not my construction; I am not sure where I first read it. In his book on the real numbers, Oliver Deiser gives a very similar construction (blocking zeroes instead of nines) and calls this Julius König's trick. König's wikipedia page mentions it but omits the details.]
Represent each real number $x\in [0,1)$ as a sequence of DIGITS, where each DIGIT is either in $\{0,\ldots,8\}$ or is of the form $10*(10^k-1)+i$ with $k\ge 1$ and $i\in \{0,\ldots,8\}$ (i.e., in $\{90,\ldots, 98; 990,\ldots, 998; 9990,\ldots, 9998; \ldots\}$.
For example, the number 0.0129449956$\dots$ would be represented by $(0,1,2,94,4,995,6,\ldots)$.
Given a pair $(x,y)$, $\beta$ interleaves these two representations.
-
4$\begingroup$ But is the greatest integer function constructive? After all, one may not constructively decide if a real number is equal to $5$ or slightly less. $\endgroup$ Mar 31, 2013 at 14:04
-
2$\begingroup$ Probably not, depending on what you exactly is meant by "constructive". (As discussed above - if every constructive function is continuous, then there is no bijection.) Also depending on what you mean by "real number" - in my answer I implicitly define a real number to be a decimal representation without an infinite string of 9's. In this context (which is NOT the definition I usually use for real numbers), my answer is constructive. (Well, it needs some tweaking: For negative numbers I really should use $\lceil\cdot\rceil$.) $\endgroup$ Mar 31, 2013 at 18:11
-
1$\begingroup$ "user2145334" leaves the following comment: "This proof is wrong, because there is no inverse image of 0.8689898989.. as (0.88888.., 0.69999..) is not allowed representation." Unfortunately their objection is not correct: the inverse image of 0.8689898989.. is the pair (0.88989898.. , 0.6989898..) $\endgroup$ May 29, 2018 at 10:53
-
1$\begingroup$ @DanPetersen Thanks editing, moving this text into a comment. I agree that the objection was not correct. I would have written "however" instead of "unfortunately", but I will not quarrel about this ... $\endgroup$ May 31, 2018 at 12:29