# Cardinality of set of real continuous functions

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 deﬁned 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?

• The result that you’ve found here is correct: there are $\mathfrak c=|\Bbb R|$ continuous real-valued functions on $[0,1]$. I find it hard to believe that Ó Searcóid made such an egregious error; could you quote exactly what he says? Apr 21, 2013 at 0:05
• This is from page 268 (first edition): "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 deﬁned on $[0 , 1]$ is of a greater cardinality than $\mathbb R$, and that there are sets of greater and greater cardinality." Apr 21, 2013 at 0:29
• (Brian's comment and mine refer to a different version of the question, merged with this one as duplicate. The question was prompted by a claim in "Metric spaces", by Mícheál Ó Searcóid, where it is claimed that there are more continuous functions on $[0,1]$ than real numbers.) Apr 21, 2013 at 1:43
• Sorry to bring up an old question like that but I want to ask this. When we say the set of all $\mathbb{R\to R}$ continuous functions does that contain partial functions as well? for example does it contain a continuous function from $[0,1] \to \mathbb{R}$ ? Jul 8, 2015 at 22:11
• This question was asked on the first day on Math.SE, but was recently closed for not giving enough context etc. I have edited the question to improve it, basing the context on a question which was merged with it. (I've also used the above comments, to make the question clearer.) Jun 17, 2020 at 16:12

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.

• +1 Nice. Since the rational points are dense, this determines the function. - This is the trickiest claim in the argument, enough to count as a lacuna. It might make a good further question "Can there be two distinct, continuous functions that are equal at all rationals?" Jul 22, 2010 at 12:31
• @Kaestur: it works for countably many reals, which I think is all that was intended. Jul 22, 2010 at 12:32
• By popular demand, math.stackexchange.com/questions/505/… Jul 22, 2010 at 16:53
• @CharlesStewart That question doesn't make sense since $\mathbb{R}$ is a Hausdorff space (cf Stephen Willard's General Topology) Apr 28, 2019 at 17:10
• @Akerbeltz - The question Charles Stewart created does make sense, as you can tell from the (as of now) 52 upvotes and multiple good answers. What you mean is that the answer is "no" because $\mathbb{R}$ is Hausdorff. As none of the current answers make the connection to Hausdorffness explicit, perhaps you can add another good answer! Jun 23, 2020 at 16:16

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

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

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

• How does seperableness prove it?
– john
Jun 8 at 8:13

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

• Note that if $f\not=g$, then they will not agree in all of $\mathbb{Q}$ $-$ according to the quoted result from Willard's General Topology $-$. So $F(f)\not=F(g)$ Apr 28, 2019 at 17:39

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

• It seems that you claim that there are only $\mathfrak c$ functions from $\mathbb R$ to $\mathbb R$. This is not true; see here. The cardinality of the sets of all functions $\mathbb R\to\mathbb R$ is $\mathfrak c^{\mathfrak c} = 2^{\mathfrak c}$. Sep 3, 2014 at 11:27
• 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$. - Try this assuming $\mathbb{R}$ is a set with two elements. Mar 1, 2017 at 14:59