The cardinality of $\{f\subseteq\mathbb R^2\mid f\colon\mathbb{R\to R}\text{ is a function}\}$ is strictly greater than the cardinality of $\mathbb R$

Question

I have a weird problem. Let's define $\mathcal{F}=\{f\subseteq \mathbb{R}^2\mid f:\mathbb{R}\rightarrow\mathbb{R}\text{ is a function}\}$.
I'm trying to prove that there does not exist a surjection $g:\mathbb{R}\twoheadrightarrow \mathcal{F}$.
I'm completely stumped, though. I tried modifying Cantor's diagonal argument, but that didn't lead anywhere because, well, $\mathbb{R}$ is uncountable. Next, I tried doing something with Cantor's theorem, because it was the only thing I could find that proved that a surjection of something wasn't possible. That didn't work either. Is there anything that could point me in the right direction here?

Answer 1

Suppose that a surjection $g$ exists.

We can now consider a function $f\in \mathcal F$ such that $f(x)\neq (g(x))(x)$ for every $x\in \mathbb R$. One possible way to do this is by choosing $f$ so that $f(x)=(g(x))(x)+1$ . This is a contradiction as clearly $f\neq g(x)$ for every $x$ as $f$ and $g(x)$ take on different values at $x$.

Notice this is basically cantor's diagonal argument.

---

If you want to use cantor's argument directly you can notice that $\mathbb R^\mathbb R \supseteq {\{0,1\}}^\mathbb R\cong 2^\mathbb R$

Answer 2

You were trying to reduce "it"(?) to Cantor's theorem.

You can also do that by looking at the functions $\chi_A(x)=1$ if $x\in A$ and $=0$ if $x\notin A$, for $A\subset \mathbb{R}$.

This gives you an injection from $P(\mathbb{R})$ to $\mathcal{F}$.

Therefore $|\mathcal{F}|\geq |P(\mathbb{R})|>|\mathbb{R}|$.

Both your approaches were viable.

Answer 3

Cantors argument doesn't require countability.

All it need is if $h: X \to Y$ is function and we can construct a $y \in Y$ so the $h_x \ne y$ for any $x\in X$ then $f$ can not be surjective.

The kicker comes if the $y \in Y$ are individually things with same cardinality of $|y| = |X|$ we can make a $y_x \ne (h_x)_x$ so $y \ne h(x)$ for any $x \in X$.

And functions are a perfect situation to do that. Jorge Fernandez's answer is a good example how to do that:

If we have a function: $h: \mathbb R \to F$ then if we can define $f$ so that $f\ne h_x$ for any $x \in \mathbb R$ then $h$ is not surjective. We can do this by defining $f(x) \ne h_x(x)$. That way $f\ne h_x$ for any $x$. And we can do this but defining $f(x) = h_x(x) + 1$

Answer 4

There is more real numbers than two: $$|\mathbb R|>2$$ so there is not less functions $\mathbb R\to\mathbb R$ than functions $\mathbb R\to\{0,1\}$: $$\left|\mathbb R ^ \mathbb R\right| \ge \left|\{0,1\} ^ \mathbb R\right|$$

And each function from the $\mathbb R\to\{0,1\}$ family identifies (i.e. is a characteristic function of) some subset of reals. By the Cantor's theorem we know that each set – $\mathbb R$ among them – has strictly more subsets than elements: $$\left|2^\mathbb R\right| > |\mathbb R|$$ hence $$\left|\mathbb R ^ \mathbb R\right| \gt \left|\mathbb R\right|$$