# Proofs involving the cardinality of the set of continuous functions

I am trying to prove the following result.

Let $$F$$ denote the set of all functions $$f: \mathbb{R} \to \mathbb{R}$$ and $$C \subset F$$ denote the subset of all continuous functions. Prove that $$|\mathbb{R}| = |C| < |F|$$. (Hint: use the fact that a continuous function on $$\mathbb{R}$$ is determined by its values on the rational numbers $$\mathbb{Q} \subset \mathbb{R}$$.)

The first thing I'm trying to understand is the hint. If I am understanding it correctly, it says this. The rationals are dense in the reals, so I can always construct a sequence of rationals converging to any real. In fact, we can construct the reals as the limits of Cauchy sequences of rationals. So if I have two functions $$f,g$$ that send the rationals to the same points, it has to be the case that they send all the reals to the same points, so the function is uniquely determined'' by its outputs on the rationals, which we can safely enumerate as $$q_1, \ldots,$$ because they're countable. Is this right?

Formally, if $$x \in \mathbb{R}$$ and $$(q_n) \to x$$ where $$q_n$$ rational, we have by continuity of $$f$$ \begin{align*} f(x) = f\left(\lim\limits_{n \to \infty} q_n\right) = \lim\limits_{n \to \infty} f(q_n). \end{align*} Is this the right idea? Am I missing any formalism?

As for the actual proof, I only have an idea for how to prove that $$|\mathbb{R}| = |C|$$. I want to use the Schroeder-Bernstein theorem to construct injections in both directions and then conclude that there exists a bijection. I can write an injection from $$\mathbb{R}$$ to $$C$$ rather easily by mapping $$c \in \mathbb{R}$$ to the function $$f(x) = c$$ for all $$x$$, which is constant, hence continuous. In the opposite direction, I can enumerate the rationals $$q_1, q_2, \ldots$$ and map a continuous function $$f$$ to a sequence of its values $$(f(q_1), f(q_2), \ldots)$$, but that gives an injection to sequences of real numbers, $$\mathbb{R}^{\mathbb{N}}$$. I would need to then inject $$\mathbb{R}^{\mathbb{N}}$$ to $$\mathbb{R}$$ and compose injections to get an injection from $$C$$ to $$\mathbb{R}$$.

I do not have an idea for how to prove $$|C| < |F|$$. The notation is non-standard (since the cardinalities aren't finite), but I believe this typically means that there does not exist a surjection from $$C$$ to $$F$$, which makes sense, as intuitively there are plenty more total functions that aren't continuous. I considered a diagonal argument, but can't fully work out the details.

Any help, especially on this last part, would be very much appreciated.

• The hint should be used as follows: the set of functions $A\to B$ has cardinality $|A|^{|B|}$. Now since a continuous function is fully determined by its values on the rational numbers (to prove), the set of continuous function on $\mathbb{R}$ will have cardinality $|\mathbb{Q}|^{|\mathbb{R}|}$ whereas the set of function on the real numbers has cardinality $|\mathbb{R}|^{|\mathbb{R}|}$. To prove that these two sets are of different cardinality use a cantor-type argument. Commented Mar 9, 2021 at 7:27

What the determined by values on $$\Bbb Q$$ hint implies is that when two continuous real functions agree on $$\Bbb Q$$, they agree on $$\Bbb R$$.

So the map $$r: C \to \Bbb R^{\Bbb Q}$$ defined by $$r(f)= f\restriction_{\Bbb Q}$$ is 1-1. The right hand set is the set of all functions from $$\Bbb Q$$ to $$\Bbb R$$, as usual.

Let $$\mathfrak{c}=|\Bbb R| = 2^{\aleph_0}$$ then basic set theory (cardinal arithmetic) tells us

$$|C| \le | \Bbb R^{\Bbb Q} | = \mathfrak{c}^{\aleph_0} = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \times \aleph_0} = 2^{\aleph_0}= |\Bbb R|$$

As $$|F| = \mathfrak{c}^{\mathfrak{c}} = 2^{\mathfrak{c}} > |\Bbb R|$$ by Cantor's theorem, we're done: $$\mathfrak{c} =|C| < |F|$$.

• Why is $(2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \times \aleph_0}$ in cardinal arithmetic?
– john
Commented Jun 9, 2022 at 3:12

To inject $$\Bbb R^{\Bbb N}\to\Bbb R$$, I'd identify $$\Bbb R$$ with $$\mathcal P(\Bbb N)$$. But then how do we turn a sequence of subsets $$A_1,A_2,\ldots$$of $$\Bbb N$$ into a single subset of $$\Bbb N$$? Simply partition $$\Bbb N$$ in to infinitely many copies $$2^n(2\Bbb N+1)$$ of itself! So the sequence $$A_1,A_2,\ldots$$ maps to the set $$A$$ where $$m\in A$$ iff it can be written as $$m=2^k(2l+1)$$ and $$l\in A_k$$.

Assumes there is a surjection $$f\colon\Bbb R\to F$$. So for $$x\in \Bbb R$$, we have some function $$f_x\in F$$, which in particular itself maps $$x$$ to some real number $$f_x(x)$$. Define $$g\colon \Bbb R\to \Bbb R$$ as $$g(x):=f_x(x)+1$$. Then there is no $$\xi\in\Bbb R$$ with $$g=f_\xi$$, for that would imply $$g(\xi)=f_\xi(\xi)$$ as well as $$g(\xi)=f_\xi(\xi)+1$$.

• What do you mean partition $\Bbb N$ into infinitely many copies $2^n(2\Bbb N+1)$ of itself? How does this partition look. Also I would like to say I dislike how ad-hoc this whole cardinality set theory seems to be. There seems to be no rhyme or reason to how people come up with results. But I guess this speaks to my ignorance on the subject.
– john
Commented Jun 9, 2022 at 3:03