2
$\begingroup$

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.

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

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$?

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

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.