Cardinality of set of real continuous functions

Question

I believe that the set of all $\mathbb{R\to R}$ continuous functions is $\mathfrak c$, the cardinality of the continuum. However, I read in the book "Metric spaces" by Ó Searcóid that set of all $[0, 1]\to\mathbb{R}$ continuous functions is greater than $\mathfrak c$:

"It is demonstrated in many textbooks that $\mathbb{Q}$ is countable, that $\mathbb{R}$ is uncountable, that every non-degenerate interval is uncountable, that the collection of continuous functions defined on $[0,1]$ is of a greater cardinality than $\mathbb{R}$, and that there are sets of greater and greater cardinality."

I understand that (via composition with the continuous function $\tan$ or $\arctan$) these sets of continuous functions have the same cardinality. Therefore, which claim is correct, and how do I prove this?

Answer 1

The cardinality is at least that of the continuum because every real number corresponds to a constant function. The cardinality is at most that of the continuum because the set of real continuous functions injects into the sequence space $\mathbb R^N$ by mapping each continuous function to its values on all the rational points. Since the rational points are dense, this determines the function.

The Schroeder-Bernstein theorem now implies the cardinality is precisely that of the continuum.

Note that then the set of sequences of reals is also of the same cardinality as the reals. This is because if we have a sequence of binary representations $.a_1a_2..., .b_1b_2..., .c_1c_2...$, we can splice them together via $.a_1 b_1 a_2 c_1 b_2 a_3...$ so that a sequence of reals can be encoded by one real number.

Answer 2

Suppose $f:\mathbb R\to\mathbb R$ is a continuous function. Let $x\in\mathbb R$. Then there is a sequence of rational numbers $(q_n)_{n=1}^\infty$ that converges to $x$. Continuity of $f$ means that $$\lim_{n\to\infty}f(q_n) = f(\lim_{n\to\infty}q_n)=f(x).$$ This means that the values of $f$ at rational numbers already determine $f$. In other words, the mapping $\Phi:C(\mathbb R,\mathbb R)\to \mathbb R^{\mathbb Q}$, defined by $\Phi(f)=f|_{\mathbb Q}$, where $f|_{\mathbb Q}:\mathbb Q\to\mathbb R$ is the restriction of $f$ to $\mathbb Q$, is an injection. (Which implies that $|C(\mathbb R,\mathbb R)|<|\mathbb R^{\mathbb Q}|$). Here, $C(\mathbb R,\mathbb R)$ denotes the set of all continuous functions from $\mathbb R$ to $\mathbb R$, as usual.

Now, cardinal arithmetic tells us that $|\mathbb R^{\mathbb Q}| = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}=|\mathbb R|$. (Namely, $(a^b)^c=a^{b\cdot c}$ holds for cardinal numbers.)

Answer 3

On the one hand it is clear that the set of all the continuous functions from $\mathbb{R}$ to $\mathbb{R}$, which shall be denoted by $\mathcal{C}^0$, is such that:

$$|\mathbb{R}|\le|\mathcal{C}^0|$$

(because for each $r\in \mathbb{R}$, simply we consider the constant function $f_r:\mathbb{R}\longrightarrow\mathbb{R}$ defined by: for each $x\in \mathbb{R},\;f_r(x)=r$. Obviously, the assignation $r\longmapsto f_r$ is injective).

On the other hand, we know that $\mathbb{R}$ is a Hausdorff space, so if $f,g\in\mathcal{C}^0$ are two continuous functions such that they agree in the (dense) subset of the rational numbers, then $f=g$ (cf Stephen Willard, General Topology, 1970, Addison Wesley, page 89, 13.14).

This allows us to consider the function $F:\mathcal{C}^0\longrightarrow ^\mathbb{Q}\mathbb{R}$ defined by: for each $f\in\mathcal{C}^0,\;F(f)=f|_\mathbb{Q}$ (where $^\mathbb{Q}\mathbb{R}$ denotes the set of all the functions from $\mathbb{Q}$ to $\mathbb{R}$).

From the previous comment, it is clear that $F$ is then an injective function, therefore:

$$|\mathcal{C}^0|\le|^\mathbb{Q}\mathbb{R}|={\big(2^{\aleph_0}\big)}^{\aleph_0}=2^{\aleph_0\times\aleph_0}=2^{\aleph_0}=|\mathbb{R}|$$

From the Cantor-Bernstein theorem we conclude that $|\mathcal{C}^0|=|\mathbb{R}|$.

Answer 4

Let $x$ be any real number; there is a sequence $\langle q_n:n\in\Bbb N\rangle$ of rational numbers converging to $x$. If $f$ is continuous, then $f(x)=\lim_{n\to\infty}f(q_n)$, so $f(x)$ is completely determined by the values $f(q_n)$ for $n\in\Bbb N$ and hence by $f\upharpoonright\Bbb Q$.

---

For the cardinality part of the argument I’m going to follow the outline that you gave in the question; depending on what you know about cardinal arithmetic, there may be substantially shorter arguments. I’m also going to arrange the argument to use some techniques that are useful more generally, again perhaps at the expense of brevity.

I’m assuming that you know that $|\Bbb Q|=|\Bbb N|$ and hence that there is a bijection $\varphi:\Bbb Q\to\Bbb N$. This easily yields a bijection $\Phi:\Bbb R^{\Bbb N}\to\Bbb R^{\Bbb Q}$: if $f:\Bbb N\to\Bbb R$, then $$\Phi(f):\Bbb Q\to\Bbb R:q\mapsto f\big(\varphi(q)\big)\;,$$ i.e., $\Phi(f)=f\circ\varphi$. (I leave it to you to check that $\Phi$ is a bijection.)

Now define a map $$N:\Bbb R\to\wp(\Bbb N):x\mapsto\{\varphi(q):q\in\Bbb Q\text{ and }q\le x\}\;;$$

clearly $N$ is injective (one-to-one), and $N(x)$ is infinite for each $x\in\Bbb R$. Thus, we may write $$N(x)=\{n_x(k):k\in\Bbb N\}\;,$$ where $n_x(k)<n_x(k+1)$ for each $k\in\Bbb N$. This is nothing more complicated than listing $N(x)$ in increasing order, but it lets us define the sequence $\nu(x)=\langle n_x(k):k\in\Bbb N\rangle\in\Bbb N^{\Bbb N}$. We now have a map

$$\nu:\Bbb R\to\Bbb N^{\Bbb N}:x\mapsto\nu(x)=\langle n_x(k):k\in\Bbb N\rangle\;,$$

and it’s not hard to check that $\nu$ is injective. On the other hand, the map that takes a sequence $\langle n_k:k\in\Bbb N\rangle\in\Bbb N^{\Bbb N}$ to the real number whose continued fraction expansion is $$[n_0;n_1+1,n_2+1,n_3+1,\ldots]$$ is an injection from $\Bbb N^{\Bbb N}$ to $\Bbb R$ (in fact to $\Bbb R\setminus\Bbb Q$), so by the Cantor-Schröder-Bernstein theorem there is a bijection between $\Bbb R$ and $\Bbb N^{\Bbb N}$. (I write $n_k+1$ in the continued fraction expansion, because my $\Bbb N$ includes $0$.)

Clearly, then, there is a bijection between $\Bbb R^{\Bbb N}$ and $\left(\Bbb N^{\Bbb N}\right)^{\Bbb N}$. To finish off the argument along the lines that you sketched in your question, carry out the following steps.

• Find a bijection between $\left(\Bbb N^{\Bbb N}\right)^{\Bbb N}$ and $\Bbb N^{\Bbb N\times\Bbb N}$. (More generally, for any sets $A,B$, and $C$ there is a bijection between $\left(A^B\right)^C$ and $A^{B\times C}$; this fact is often useful and is well worth knowing.

• In the same way that I found a bijection between $\Bbb R^{\Bbb N}$ and $\Bbb R^{\Bbb Q}$, show that there is a bijection between $\Bbb N^{\Bbb N}$ and $\Bbb N^{\Bbb N\times\Bbb N}$.

• Conclude that there is a bijection between $\Bbb R^{\Bbb N}$ and $\Bbb N^{\Bbb N}$ and hence between $\Bbb R^{\Bbb N}$ and $\Bbb R$.

Answer 5

It is at least $c$, since all constant functions are continuous. Now consider the fact that $\mathbb{R}$ is separable.

Answer 6

I have a somewhat simple answer to this question. It is not as elaborate as the other but perhaps it will add some intuition.

let's look at the number of functions from $\mathbb R^n \to \mathbb R$.

For every element in $\mathbb R^n$ we need to choose a corresponding image in $\mathbb R$. There are $c$ elements in $\mathbb R$, and so if there are $\alpha$ elements in $\mathbb R^n$, there are $\alpha c$ functions (not continuous! just functions) from $\mathbb R^n \to \mathbb R$.

Let's find alpha: For the first element in an $n$ vector we have $c$ choices, for the second one $c$ choices, for the third one $c$ choices etc...overall $c^n=c$ choices.

So overall there are $c^{n+1}=c$ functions from $\mathbb R^n \to \mathbb R$.

since the continuous functions are a subset of this set, there are AT MOST $c$ continuous functions.

Now let's look at the function $f(x)=\xi ||x||_2$ where $\xi$ is some real number, $x$ is an $n$ vector, and $||x||_2$ is the euclidean norm of the vector $x$.

This function $f$ is continuous no matter which $\xi$ we pick. We have $c$ options to choose from, and so the set of continuous functions includes all the functions of the form $f(x)=\xi ||x||_2$ and so it is AT LEAST $c$.

Since it is at most $c$, and at least $c$, the conclusion is that it is exactly $c$.