Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 7 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer
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.

share|cite|improve this answer
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}|$.

share|cite|improve this answer
Thanks Thomas ! – Q.matin Feb 3 '13 at 9:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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