# Cardinality of the set of continuous functions versus set of all functions

Let $$F$$ denote the set of all functions $$f: \mathbb{R} \to \mathbb{R}$$, and let $$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}$$.

I've done some searching on this website about this proof and almost every answer seems to involve arithmetic of infinite cardinals, but this is not something I am familiar with, so I am hoping there is a proof that doesn't require it, even if it's longer and has more moving parts.

Here is a sketch of what I have so far.

By the Cantor-Schroeder Bernstein theorem, we can prove $$|\mathbb{R}| = |C|$$ by finding injections $$f: \mathbb{R} \to C$$ and $$g: C \to \mathbb{R}$$. For $$f$$, we can take $$c \mapsto f(x) = c$$, the constant function, which is of course continuous (take $$\delta = \epsilon$$). For $$g$$, we enumerate the rationals (which are countable), $$q_1, \ldots,$$ and map a function $$f$$ to the sequence $$(f(q_1), f(q_2), \ldots)$$. This map is injective because a continuous function from $$\mathbb{R}$$ to $$\mathbb{R}$$ is uniquely determined by how it acts on the rationals (by density). If I could prove that the reals have the same cardinality as the sequences of reals, I can compose injections to conclude that, by Schroeder Bernstein, $$|\mathbb{R}| = |C|$$.

I don't know how to prove that $$|C| < |F|$$. I believe the definition of a strictly larger cardinality is that there is an injection from $$C$$ to $$F$$ but not surjection. (Is this correct?) If $$so$$, I can definitely inject $$C$$ into $$F$$ by the identity function. I would need only show there is no surjection from $$C$$ to $$F$$, which I don't know how to do.

To finish your argument for the first part I’m going to assume that you know that $$|\Bbb R|=|\wp(\Bbb N)|=\left|\{0,1\}^{\Bbb N}\right|$$, and that $$|\Bbb N\times\Bbb N|=|\Bbb N|$$. Thus,

$$\left|\Bbb R^{\Bbb N}\right|=\left|\left(\{0,1\}^{\Bbb N}\right)^{\Bbb N}\right|=\left|\{0,1\}^{\Bbb N\times\Bbb N}\right|=\left|\{0,1\}^{\Bbb N}\right|=|\Bbb R|\,.\tag{1}$$

To rephrase that in terms of mappings, let $$f:\Bbb R\to\{0,1\}^{\Bbb N}$$ be a bijection. Then

$$g:\Bbb R^{\Bbb N}\to\left(\{0,1\}^{\Bbb N}\right)^{\Bbb N}:\langle x_n:n\in\Bbb N\rangle\mapsto\langle f(x_n):n\in\Bbb N\rangle$$

is a bijection, establishing the first equality in $$(1)$$. The second follows from the general result that for sets $$A,B$$, and $$C$$ there is a bijection between $$\left(A^B\right)^C$$ and $$A^{B\times C}$$; it’s a little messy to write down the details, but it’s not too hard and is a good exercise. The third follows easily from the existence of a bijection between $$\Bbb N\times\Bbb N$$ and $$\Bbb N$$, and I’ll leave that one to you.

For the inequality note that each $$A\subseteq\Bbb R$$ has an indicator (characteristic) function

$$\chi_A:\Bbb R\to\Bbb R:x\mapsto\begin{cases} 1,&\text{if }x\in A\\ 0,&\text{if }x\notin A\,. \end{cases}$$

The map from $$\wp(\Bbb R)$$ to $$\Bbb R^{\Bbb R}$$ that takes $$A$$ to $$\chi_A$$ is easily seen to be injective, so $$|\wp(\Bbb R)|\le\left|\Bbb R^{\Bbb R}\right|$$. (In fact they are equal, but you don’t need that.) Finally, Cantor’s theorem says that $$|\Bbb R|<|\wp(\Bbb R)|$$, so $$|\Bbb R|<\left|\Bbb R^{\Bbb R}\right|$$.

The cardinality of the set of all functions $$f:\mathbb{R} \to \mathbb{R}$$ is simply $$|\mathbb{R}|^{|\mathbb{R}|}$$ which by cardinal arithmetic can be looked at as $$2^{| \mathbb{R}|}$$ or denoted as $$2^{\mathfrak{c}}$$, $$\mathfrak{c}$$ being the cardinality of the continuum.

Now concerning the cardinality of the set of all continuous functions from $$\mathbb{R}$$ to $$\mathbb{R}$$, we must be careful. let's use the fact that $$\mathbb{Q}$$ is dense in $$\mathbb{R}$$. Let's go ahead and apply the Cantor-Schroder-bernstein theorem as you tried to.

1. The cardinality of the set of all continuous functions is at least that of the continuum $$\frak{c}$$ since we can associate injectively to each constant function a real number.

2. The cardinality of the set of all continuous functions is at most that of the continuum $$\mathfrak{c}$$ since we can inject this set into the set $$\mathbb{R}^{\mathbb{N}}$$. Essentially one associates to each continuous function its values on all the rational points (infinite sequence of integers).

3. Since $$\mathbb{Q}$$ is dense in $$\mathbb{R}$$ this uniquely determines the continuous function.

Hence nay the Bernstein-Cantor-Schroder theorem, $$|\{f: f:\mathbb{R} \to \mathbb{R} \text{ is continuous}\}|=\mathfrak{c}$$