I'm well aware of the standard proof based on cardinality arithmetic to show that these two sets have the same cardinality and the question of defining a bijection between the two sets came up. I worked on it a little while and was wondering if there were any gaps, or a simpler method of coming up with such a bijection.

The main idea I had was to take a family of sequences indexed by the real numbers. So that each one of these sequences corresponds to a unique real number. Then I can map each one of these sequences to another number, by applying the binary function from $\mathbb R$ to $\{0,1\}$ and mapping the infinite binary sequence to a real number, use one of the standard bijections.

First let $E$ be a family of sequences indexed by the real numbers. Such that $E_{xi}\neq E_{yj}$ for all $x,y \in \mathbb R$ and $i,j \in \mathbb N$ also with the property that

$\mathbb R= \bigcup_{x \in \mathbb R, i \in \mathbb N} E_{xi}$.

What sort of theorems would I need to prove such a family existed, is it enough to note that the reals can be represented as a uncountable union of countably infinite sets?

Also let $P: 2^{\mathbb N} \rightarrow \mathbb R$ be you favorite bijection.

Now consider an element of $2^{\mathbb R}$ as a function $f: \mathbb R \rightarrow \{0,1\}$ and $g \in \mathbb{ R^R}$ in a similar manner. Then our bijection between the two sets will be the function $\Phi$ which maps $f$ to a function $g$, such that $g(x)=P(F(E_x))$ where $F$ applies $f$ to each element of the sequence $E_x$.

I'm fairly sure this is an onto and one-to-one function. The one-to-one property should follow because the sequences are disjoint, cover $\mathbb R$ and $P$ is a bijection. The onto argument is a little hazier, but it should be possible to recreate the function $f$, by first inverting each element with $P$ and then defining $f$ based on these sequences.


Once you have the bijection $P:2^\mathbb{N}\cong\mathbb{R}$, you can build your desired bijection as follows.

First, note that $\mathbb{N}\times 2^\mathbb{N}\cong 2^\mathbb{N}$, essentially by the bijection that associates $(n,A)$ with $\{n\}\cup (n+1+A)$, except that this will miss the empty set on the right, but we can fix this by composing with a map witnessing $2^\mathbb{N}-\{\varnothing\}\cong 2^\mathbb{N}$, such as shifting on a fixed countable subset.

Now simply observe that $$\mathbb{R}^\mathbb{R}\cong (2^\mathbb{N})^{(2^\mathbb{N})}\cong 2^{(\mathbb{N}\times 2^\mathbb{N})} \cong 2^{(2^\mathbb{N})} \cong 2^\mathbb{R}, $$

which provides the desired bijection. The first map is conjugation by $P$, simply composing with $P^{-1}$ and $P$ before and after; the second map is an easy exercise in parenthesis rearranging; the third map applies the observation above; and the final map applies $P$.

| cite | improve this answer | |
  • 16
    $\begingroup$ Right. You shouldn't think of cardinal arithmetic and finding bijections as somehow different mathematical activities: cardinal arithmetic is just a convenient way to write down a composition of certain standard bijections without explicitly giving them. (In fact, so is ordinary arithmetic!) $\endgroup$ – Qiaochu Yuan Feb 2 '11 at 13:50

A function $f:\mathbb R\rightarrow\mathbb R$ can be seen as a member of $\mathcal P(\mathbb R\times\mathbb R)$, which is just the so-called graph of the function, namely the set of all pairs $(x,y)$ such that $y=f(x)$. Since $$|\mathcal P(\mathbb R\times\mathbb R)|={|2^{\mathbb R\times\mathbb R}|}=|2^\mathbb R|$$ the result follows.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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