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:
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.
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.
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].
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?