-1
$\begingroup$

This question already has an answer here:

When I search about the cardinality of real number set in Wiki (http://en.wikipedia.org/wiki/Cardinality_of_the_continuum)

I found: By the Cantor–Bernstein–Schroeder theorem we conclude that $c=|P(\mathbb{N})|=2^{\aleph_0}$

And the Cantor–Bernstein–Schroeder state that if $A\preceq B$ and $B\preceq A$, then $A \sim B$.

How can I use it to prove that $c=|P(\mathbb{N})|=2^{\aleph_0}$. How to create a bijection function mapping $P(\mathbb{N})$ onto $\mathbb{R}$?

$\endgroup$

marked as duplicate by Asaf Karagila, azimut, awllower, Potato, Ayman Hourieh Jun 30 '13 at 9:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ @Ink True. Misread the question. $\endgroup$ – Arthur Jun 30 '13 at 7:32
  • 3
    $\begingroup$ Do you mean a bijection from $\mathcal{P}(\mathbb{N})$ to $\mathbb{R}$? Because by Cantor, $\left | \mathbb{N} \right | < \left | \mathbb{R} \right |$. $\endgroup$ – Ryan Sullivant Jun 30 '13 at 7:33
  • 2
    $\begingroup$ You can’t find a bijection from $\Bbb N$ onto $\wp(\Bbb N)$: $|\wp(\Bbb N)|>|\Bbb N|$. $\endgroup$ – Brian M. Scott Jun 30 '13 at 7:35
  • 2
    $\begingroup$ Also, see here: mathoverflow.net/questions/56633/… . A bijection might not be as easy to produce as you would like, but nevertheless as you pointed out, by Schroder-Bernstein $\left| 2^{\aleph_0} \right| = \left| \mathbb{R} \right|$ $\endgroup$ – Ryan Sullivant Jun 30 '13 at 7:44
  • $\begingroup$ Oh I make a mistake, I mean $P(\mathbb{N})$ to $\mathbb{R}$ $\endgroup$ – Y.H. Chan Jun 30 '13 at 8:39
2
$\begingroup$

Proof by Cantor-Bernstein-Schroder. To use Cantor-Bernstein-Schroder, you only need to find an injection from $\mathbb{R}$ to $P(\mathbb{N})$ and vice-versa. This is fairly easy to do. For the $\mathbb{R}$ to $P(\mathbb{N})$ direction, we work as follows. It is easy to show that $\mathbb{R}$ is equipollent to $(0, 1)$. I give an explicit bijection below. Using such a bijection, first map $\mathbb{R}$ to $(0, 1)$. Now, we exploit the following fact: the subsets of $\mathbb{N}$ can be put into one-to-one correspondence with (finite and infinite) binary strings that do not end in zeroes as follows.

  1. Write out the elements of $\mathbb{N}$ in their usual order.
  2. Cross out the elements of the subset.
  3. Below each element of $\mathbb{N}$, write a “0” if it is not crossed out, and a “1” if it is.
  4. Read out the resulting binary string, and chop off trailing zeroes (I.e. what happens when the set is finite).

(The empty set maps to the empty string $\epsilon$.)

Reversing this rule gives a mapping from such strings to subsets. Then, map $(0, 1)$ injectively into $P(\mathbb{N})$ by binary-expanding each member of $(0, 1)$, minding to use a consistent conevntion of whether to take the terminating or "11111..."-ending expansion when applicable, taking the fractional part, and then chopping off any trailing zeroes and applying the above rule in reverse to get a subset of $\mathbb{N}$. This gives an injection from $\mathbb{R}$ to $P(\mathbb{N})$. Now, for an injection going the other way. Map all infinite members of $P(\mathbb{N})$ into $(0, 1)$ using the inverse of the map just given. Then map all finite members by interpreting their binary strings as integers after appending a leading 1. These integers will be 1 or more, hence won't conflict with anything in $(0, 1)$.

This shows $\mathbb{R}$ and $P(\mathbb{N})$ are equipollent by the Cantor-Bernstein-Schroder Theorem.

But you also asked for something else: an explicit bijection from $\mathbb{R}$ to $P(\mathbb{N})$. We can do this too.

Proof by Explicit Construction. We can build up a bijection $f: \mathbb{R} → P(\mathbb{N})$ in stages, as follows. The first step is to construct one from $[0, 1)$ to $P(\mathbb{N})$. Call it $\beta$. We exploit the fact that a subset of $\mathbb{N}$ can be encoded as a binary string without trailing zeroes that we just mentioned.

Expand a real in $[0, 1)$ in binary. Exclude the set of reals whose binary terminates (or can be represented as a repeating binary ending in “111111....”). Take the fractional parts of the binary expansions of these reals and map them to subsets of $\mathbb{N}$ via the procedure just discussed.

The next stage is to fill in the reals we just excluded. We cannot simply use the natural correspondence of these reals to their binary expansions, for their binary expansions are not unique. Instead, we can do something like this. Let such a real be expanded as $0.a_1a_2...a_n$, $a_n = 1$. Then, let the rational that said binary represents be given by $\frac{p}{2^n}$, $p = a_1 2^{n-1} + a_2 2^{n-2} + … + 2a_{n-1} + a_n$. Now for the trick. Do not map the real $\frac{p}{2^n}$ to the binary $a_1a_2...a_n$ and corresponding subset. Instead, map $\frac{p}{2^{n+1}}$ to this binary, and map $\frac{p + 2^n}{2^{n+1}}$ to the binary $a_1a_2...a_{n-1}011111....$ and its corresponding subset. Map 0 to the null set, and map $1/2$ to $\mathbb{N}$. That this last mapping puts the terminating-binary members of $[0, 1)$ in one-to-one correspondence with the remaining subsets of $\mathbb{N}$ should be easy to see: each such terminating-binary rational can be represented as $\frac{p}{2^n}$ for an odd, unique $p$ and unique $n > 0$ with $p < 2^n$. All odd $p$ are represented. For each $n > 1$, all values for $p$ from $1$ to $2^n – 1$ are given a binary string/subset. The case where $n = 1$ is taken care of by special case, as is $0$. So every such rational is given a unique string, and every string a unique such rational.

This completes the construction of bijection $\beta$. We now consider the construction of bijection $Б: (0, 1) \rightarrow [0, 1)$. Such a bijection can be constructed in a number of ways. One way is as follows. When $x \le 1/2$, let $Б(x) = 1/2 – x$. This maps $(0, 1/2]$ to $[0, 1/2)$. When $x > 1/2$ (so is in $(1/2, 1)$ ), let $Б(x) = \frac{Б(2x – 1)}{2} + \frac{1}{2}$. $2x – 1$ stretches $(1/2, 1)$ to $(0, 1)$. $Б$ then is called upon to recursively map $(0, 1)$ to $[0, 1)$. Dividing by 2 shrinks $[0, 1)$ to $[0, 1/2)$. Adding $\frac{1}{2}$ translates $[0, 1/2)$ to $[1/2, 1)$, the missing interval. Note that each of these steps is reversible, so $Б$ is indeed bijective.

Finally, we need a bijection from $\mathbb{R}$ to $(0, 1)$. This is the simplest of all. Call this bijection $b$. We can use something like

$$b(x) = \frac{\mathrm{arccot}(x)}{\pi}$$.

Or

$$b(x) = \frac{\tanh(x) + 1}{2}$$

or any other sigmoid function ranging in $(0, 1)$. Then,

$$f = \beta \circ Б \circ b$$

is a bijection from $\mathbb{R}$ to $P(\mathbb{N})$. Thus we prove by explicit construction that $\mathbb{R}$ and $P(\mathbb{N})$ are equipollent.

So, it is definitely true that

$$2^{\aleph_0} = \mathfrak{c}$$

.

$\endgroup$

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