Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The set of all $\mathbb{R\to R}$ continuous functions is $\mathfrak c$. How to show that? Is there any bijection between $\mathbb R^n$ and the set of continuous functions?

share|improve this question
    
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? –  Brian M. Scott Apr 21 '13 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 defined on $[0 , 1]$ is of a greater cardinality than $\mathbb R$, and that there are sets of greater and greater cardinality." –  Andres Caicedo Apr 21 '13 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.) –  Andres Caicedo Apr 21 '13 at 1:43

6 Answers 6

up vote 38 down vote accepted

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

share|improve this answer
    
Good answer, but your last statement does not work for infinite sequences. –  Larry Wang Jul 22 '10 at 12:27
5  
+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?" –  Charles Stewart Jul 22 '10 at 12:31
    
@Kaestur: it works for countably many reals, which I think is all that was intended. –  Charles Stewart Jul 22 '10 at 12:32
    
@Charles: Fair enough. +1 from me. –  Larry Wang Jul 22 '10 at 13:19
1  
By popular demand, math.stackexchange.com/questions/505/… –  Charles Stewart Jul 22 '10 at 16:53

The cardinality of your set is at least $2^{\aleph_0} = \frak{c}$ because every real number corresponds to a constant function.

The cardinality is at most $\frak{c}$ because the set of real continuous functions injects into the sequence space $R^{N}$ by mapping each continuous function to its values on all the rational points. Since the rational points are dense in $\mathbb{R}$, this determines the function.

  • Without resorting to epsilon-delta; arguments: Let $f$ and $g$ be continuous real functions and $f(x) = g(x)$ for all rational $x$. For any real number $c$ (in particular, an irrational $c$), there exists a Cauchy sequence of rational numbers such that $\lim_{n \to \infty}x_{n}=c$. Since $f$ and $g$ are continuous, $\lim_{n \to \infty}f({x_{n}})=f({c})$ and $\lim_{n \to \infty}g({x_{n}})=g({c})$. Since $x_n$ is rational, $f(x_n) = g(x_n)$ for all $n$, so the two limits must be equal and so $f(c) = g(c)$ for all real $c$.

The Schroeder-Bernstein theorem now implies the cardinality is precisely that of the continuum: Let $k$ be the cardinality of your set. We have shown that $k \ge \frak{c},$ and that $k \le \frak{c}$. By Schroeder-Bernstein's Theorem, $k = \frak{c}$.

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.

See also this post on Cardinality of the set of all real functions of real values, not necessarily continuous. In this case, given we are interested in the cardinality of real-valued continuous functions, we have that $$|\mathbb R^{\mathbb Q}| = |\mathbb{R}^{\mathbb{N}}|= (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}=|\mathbb R|=\frak{c}.$$

Here's a nice site that provides a tutorial on cardinal arithmetic.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
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}$. –  Martin Sleziak Sep 3 at 11:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.