# Bijective function between $\mathbb R$ and $\mathbb R^\mathbb R$

Let $F=\{\text{all functions}\ f:\mathbb{R} \rightarrow \mathbb{R}\}$. Then $\nexists$ a bijection $\alpha: \mathbb{R}\rightarrow F$.

Why is this the case? I do not know why?

-
Are you familiar with cardinal arithmetic? – Git Gud Feb 3 '13 at 8:45
@GitGud No, unfortunately, I am not : ( – Q.matin Feb 3 '13 at 8:47
@GitGud What course do you start learning cardinality? Because I hear that all the time. I am taking real analysis now. – Q.matin Feb 3 '13 at 8:49
Usually in Discrete Mathematics and Elementary Set Theory. – Git Gud Feb 3 '13 at 8:51

Assume there is a surjection $G:\mathbb R \to F$. Construct a function $h:\mathbb R \to \mathbb R$ as follows. $h(x)=1+[G(x)](x)$. Since $h\in F$ and $G$ is surjective it follows that there is some $y\in \mathbb R$ such that $G(y)=h$. But then $h(y)=1+[G(y)](y)=1 + h(y)$ which is nonsense. So, no surjection $G$ can exist and thus no bijections.

-
Why exactly is it nonsense? Why is it not in the range? Also, why do you have an extra $(x)$ at the end in $h(x)=1+[G(x)](x)$? – Q.matin Feb 3 '13 at 9:09
how can it be that h(y)=1+h(y)??? – Ittay Weiss Feb 3 '13 at 9:11
Ohhh I see now! Thanks a lot Ittay! I also liked your use of the word "nonsense". Makes a strong point. Thanks again! – Q.matin Feb 3 '13 at 9:13
you are welcome :) – Ittay Weiss Feb 3 '13 at 9:51

Consider $S=\{1_A:A\subset \mathbb{R}\}$, ($1_A$ is characteristic function.)

Then $S\subset F$ and $S\approx \mathcal{P}(\mathbb{R})$ Because $A\mapsto 1_A$ is bijection.

-
Thanks Tetori ! – Q.matin Feb 3 '13 at 9:16

This can be proved by diagonalization. If we have a map $\alpha : \mathbb{R} \to F$, then define a function $g : \mathbb{R} \to \mathbb{R}$ by $g(x) = \alpha(x)(x) + 1$. Then $g$ is not in the range of $\alpha$. So no map $\alpha : \mathbb{R} \to F$ can be surjective.

-
Why is it not in the range? – Q.matin Feb 3 '13 at 9:10
Suppose $g = \alpha(y)$ for some $y \in \mathbb{R}$. Then $g(y) = \alpha(y)(y)$. But we know from the definition of $g$ that $g(y) = \alpha(y)(y)+1$. – Ted Feb 3 '13 at 9:22
I see now. Thanks a lot Ted ! I wish I can have top two accepted answers. – Q.matin Feb 3 '13 at 9:24

First of all, $2^{\mathbb{R}}=\{\text{all functions }f:\mathbb{R}\to \{0,1\}\}$ has the same cardinality as the powerset of reals, i.e. $P(\mathbb{R})$. A bijection can be established by identifying each subset of $\mathbb{R}$ with its indicator function. It is known that $|P(\mathbb{R})|>|\mathbb{R}|$, i.e. there exists no one-to-one from $2^{\mathbb{R}}$ to $\mathbb{R}$. Now since you can identify $2^{\mathbb{R}}$ bijectively with a subset of $F$ (in the obvious way), then a bijection from $F$ to $\mathbb{R}$ would yield a contradiction, as its restriction to $2^{\mathbb{R}}$ would be a one-to-one map from $2^{\mathbb{R}}$ to $\mathbb{R}$, implying that $|P(\mathbb{R})|\leq |\mathbb{R}|$.

-
Thanks Thomas ! – Q.matin Feb 3 '13 at 9:16