# Simple bijection between reals and sets of natural numbers

Using the Cantor–Bernstein–Schröder theorem, it is easy to prove that there exists a bijection between the set of reals and the power set of the natural numbers. However, it turns out to be difficult to explicitly state such a bijection, especially if the aim is to find a bijection that is as simple to state as possible.

The simplest explicit bijection that I could come up with can be defined as follows:

I actually define a bijection from the reals to binary sequences (i.e. sequences of 0s and 1s). Since there is a trivial canonical bijection between binary sequences and the power set of natural numbers, this can easily be modified to a bijection from reals to the power set of natural numbers.

We say that a binary sequence has an infinite tail iff from some term onwards all terms in the sequence are 0s or all are 1s.

For every real x between 0 and 1 there are either one or two binary sequences that qualify as binary representations of x. If there are two binary representations of x, then both of them have an infinite tail, one in 0s and the other in 1s.

Let [x] denote the integer part of a real x.

Now the bijection f is defined on a real x by distinguishing four cases:

1. x-[x] has two binary representations and [x] is non-negative: Then f(x) is set to be the sequence starting with [x] many 1s followed by one 0 and the binary representation of x-[x] that has an infinite tail in 0s.

2. x-[x] has two binary representations and [x] is negative: Then f(x) is set to be the sequence starting with -[x]-1 many 1s followed by one 0 and the binary represenation of x-[x] that has an infinite tail in 1s.

3. x-[x] has one binary representation and [x] is non-negative: Then f(x) is set to be the sequence starting with 1 followed by [x] many 1s, one 0 and the binary representation of x-[x].

4. x-[x] has one binary representation and [x] is negative: Then f(x) is set to be the sequence starting with 0 followed by -[x]-1 many 1s, one 0 and the binary representation of x-[x].

So the idea is that for the reals with two binary representation, you use the choice between the two as an indication of sign, whereas for the reals with just one binary represenation, the sign has to be mentioned in a separate bit.

Is there a bijection from the reals to the power set of the natural numbers that is easier to define explicitly then the one just presented?

-
Use tan/inverse tan to go between (0,1) and R. That would simplify things a fair bit. – Spencer Feb 25 '11 at 14:41
Use continued fractions. You only have to be mildly careful about the mild non-uniqueness of finite ones. – Qiaochu Yuan Feb 25 '11 at 14:44
@Spencer: As far as I can see, it is not so easy to explicitly state a bijection between P(N) and (0,1). The simple bijections are either between P(N) and [0,1) or between P(N) and (0,1], but tan cannot biject such half-open intervals to R. – Marcos Cramer Feb 25 '11 at 22:22
It's easy to implement Spencer's suggestion. Enumerate the set $D$ of dyadic rationals in $(0, 1)$: 1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, etc. Enumerate the set $E$ of $\{0, 1\}$-sequences that are eventually constant: after the constant sequences 000... and 111..., the rest are finite nonempty $\{0, 1\}$-words w followed by 0's if w ends in 1, or by 1's if w ends in 0. Using such enumerations, set up a bijection $E \to D$. Binary representation $(a_1, a_2, \ldots) \mapsto \sum_n a_n/2^n$ gives a bijection $2^N - E \to (0, 1) - D$ on their complements. Thus we get a bijection $2^N \to (0, 1)$. – Todd Trimble Oct 12 at 21:39

I think this question is more interesting than it appears at first glance.

The answer depends partly on how you define a real number. For example, a standard way to define real numbers is by means of Dedekind cuts. Then, assuming that the standard zigzag bijection between the rationals and the integers is taken for granted, the problem reduces to finding an explicit bijection between certain sets of integers (those corresponding to Dedekind cuts) and all sets of integers. I haven't ever seen anyone attempt to do this directly.

As you've posed the problem, you seem to take binary representations of reals for granted. Then the basic difficulty is the annoying dichotomy between finite sets and infinite sets. (Using continued fractions, as others have suggested, does not help much here, because you're still stuck with the annoying finite/infinite issue.) Reals between 0 and 1 are easily put in bijection with infinite sets of integers, by disallowing binary representations that end with repeating 0's. Letting $\cal I$ denote the family of all infinite sets of integers, we now want to find a bijection $\phi$ between $\cal I$ and $2^{\mathbb N}$. One simple way to do this is to let $\phi(x) = x$ unless $x$ is cofinite, since there are only countably many cofinite sets of integers, and then pick your favorite bijection between one copy of $\mathbb N$ and two copies of $\mathbb N$ to biject cofinite sets with finite/cofinite sets.

If you want all reals, rather than just reals between 0 and 1, then you'll need to modify the above construction, but I think the main finite/infinite sticking point will remain the same whatever you try to do. In particular, if I understand your construction correctly, your use of a $\pm$ sign can be thought of as implementing the necessary bijection between one copy of $\mathbb N$ and two copies of $\mathbb N$.

By the way, a related question is to find an explicit bijection between $(0,1)$ and $(0,1) \times (0,1)$. Interleaving binary representations is the standard approach, but one must be careful about reals with two different binary representations. To fix this problem, disallow representations that end with repeating 0's, and break up a binary representation into blocks, where a block consists of a single 1, preceded by a (possibly empty) string of consecutive 0's. Then interleave blocks of digits instead of single digits. I think this construction may go back to Dedekind.

-
Here is a nice paper, "Was Cantor surprised?", showing the earlier works of Cantor on some related ideas: maa.org/sites/default/files/pdf/pubs/AMM-March11_Cantor.pdf – Amir Asghari Dec 23 '13 at 16:17
Do the interleaved blocks really go back to Dedekind? (I first saw this construction in the "Foundations" text by RL Wilder...) – Benjamin Dickman Oct 13 at 4:33
@BenjaminDickman : Yours could be a fresh MO question, perhaps... – Timothy Chow Oct 13 at 17:39
• A set of natural numbers can denote a sequence of natural numbers like {1,2,3} denotes 1,1,1 and {2,4,6,26} denotes 2,2,2,20.
• A sequence of natural numbers denotes a real number in a unique way using continued fraction.

For example N = {1,2,3,4,5,...} denotes the sequence 1,1,1,1,1,... which is the golden ratio.

-
This is indeed quick to write down and seems to be the kind of answer sought. You have written it down very neatly, too, but (and this isn't an attack on your answer) for me it is still more obvious that you can write reals in binary than the fact that "A sequence of natural numbers denotes a real number in a unique way using continued fraction." I don't see how one is "easier to define explicitly" than the other really. – Spencer Feb 25 '11 at 15:19
Rational numbers always have two continued fraction expansions (e.g. 1+1/(1+1/1) = 1+1/2) so the second bullet point is wrong. – François G. Dorais Feb 25 '11 at 15:27
François' objection can be fixed by adding a 1 to every finite sequence of naturals, or by adding 1 to the last term of any finite sequence of natural numbers. In the first case one gets a bijection between P(N) and non-negative reals, in the second case a bijection between P(N) and positive reals. Now one could reserve one element of N as a bit specifying the sign of the real, and by using the two different fixes to François' objection ensure that 0 is hit preceisely once. But maybe the resulting bijection doesn't qualify as that simple any more... – Marcos Cramer Feb 25 '11 at 15:47
...or just compose with log in the second case. – Kevin Ventullo Feb 25 '11 at 21:15
Yes, that's simpler. Thanks! – Marcos Cramer Feb 25 '11 at 22:17

a bijection using binary sequences:

case 1: For each finit subset of N a positive integer is choosen. E.g. by adding 1 to the integer which has in its binary representation the bits at position numbers contained in the subset set to 1. (LSB has position number 1)

case 2: N <--> 0.

case 3: N \ {n} <--> -n

case 4: The remaining subsets of N are represented as a string of infinite symbols. A symbol has value 1 when the symbol position number is element of the subset else it is 0. There are at least two 0's. Before the first 0 the string has k 1's. The substring behind the first 0 is used as a binary fraction for a real x. For subsets with even k the real k/2+x and for subsets with odd k the real -(k+1)/2+x is choosen.

(x < 1 as the fraction has at least one 0 and x > 0 and unique as due to case 1 the fraction has no infinite tail in 0's)

Case 4 is borrowed from Marcos Cramer and with the separation into finite and infinite subsets I followed Timothy Chow.

-
Please use LaTeX markup for formulas. – Stefan Kohl Oct 14 at 20:48

The idea to combine unary and binary representations seems interesting but I have problems with the bijection. E.g. I miss a real number for the binary sequence containing only 1s as each sequence defined in case 1 to 4 has at least one 0. Or I cannot see a real number for sequences like 11101111.... . This is not matching case 1 as it is not ending with 0s. It is also not case 2 or 3 as 0.1111...=1 is not possible for x-[x]. It is not case 4 as it does not start with 0. For me it looks like case 1 and 2 are for noninteger rationals and case 3 and 4 are for integers (as for integers x-[x]=0 has only one binary representation) and irrationals. But this is not fitting the idea mentioned below, as all integers except 0 have two binary representations but this two representations are not used to tell us the sign.

I like the continued fraction approch. But we have to say how to deal with the empty set in P(N) and when using log for positive continued fractions we have to point out how to get rid of the continued fraction with value 0.

I came up with the following:

Let z(n) = [n/2] cos(Pi n) with [x] is the integer part of x.

Map integers to subsets of N with less than 2 elements:

{} <--> 0

{a} <--> z(a+1)

Map non-integer rationals to other finit subsets of N with at least 2 elements:

{a, b, c, ..., u, v, w} <--> CF(z(a), b-a, c-b, ... ,v-u, w-v+1)

Map irrationals to infinite subsets of N:

{a, b, c, ...} <--> CF(z(a), b-a, c-b, ...)

with CF(.) denoting regular continued fractions with the last coefficient > 1.

-