# Cardinality of $\mathbb{R}^\mathbb{R}$ by diagonal argument

I want to prove that the set of all real functions $\mathbb{R}^\mathbb{R}$ has a higher cardinality than the real numbers $\mathbb R$, by Cantor's diagonal argument.

I'm having difficulties with approaching this problem.

What I'm looking for is a hint in the right direction.

I've seen an example where it is shown that the power set $2^S$ of a countable set $S$ is uncountable, by the diagonal argument.

• Hint: the powerset can be identified with the set of functions into $\{0,1\}$. – Tobias Kildetoft Mar 9 '16 at 20:22
• Hold on guys, that's enough for now; I'm working on it. – Mussé Redi Mar 9 '16 at 20:35

HINT: Let $\varphi:\Bbb R\to\Bbb R^{\Bbb R}$ be any function. Now define $f_\varphi:\Bbb R\to\Bbb R$ by $f_\varphi(x)=\big(\varphi(x)\big)(x)+1$. If that’s not quite enough of a hint, look at the spoiler-protected question below.

Is $f_\varphi$ in the range of $\varphi$?

A rough outline of the proof.

Consider a subset $U$ of $\mathbb R ^\mathbb R$. It can be defined by a sequence of characteristic functions $s_i$.

Now, consider a subset $T$ of $\mathbb R$. It can be defined by a single characteristic function $\chi_j$.

It is clear that a one-to-one correspondence between $U$ and $T$ is not possible; because a map $\chi_j \mapsto s_i$ can never be surjective.

Hence, $\mathbb R ^\mathbb R$ has a higher cardinality than $\mathbb R$.