Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Importantly, I am looking for a constructive proof (which does not rely on the Cantor–Bernstein–Schroeder theorem). Motivated by this discussion.

share|improve this question
2  
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.) –  Yemon Choi Mar 31 '13 at 3:53
1  
@Mark, if you want to suggest using a transcendence basis, how would that be constructive? It relies on the axiom of choice. –  Asaf Karagila Mar 31 '13 at 6:33
1  
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. –  Jason Rute Mar 31 '13 at 8:16
2  
@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.) –  Yemon Choi Mar 31 '13 at 8:40
3  
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. –  François G. Dorais Mar 31 '13 at 13:47

1 Answer 1

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 N$ 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.

share|improve this answer
2  
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. –  Joel David Hamkins Mar 31 '13 at 14:04
1  
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$.) –  Goldstern Mar 31 '13 at 18:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.