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.

Could somebody explain to me how to prove that the cardinality of all real continuous functions is $c$ ?

The first problem is that I don't know how to show that each real continuous function $f: X \rightarrow Y$ is uniquely determined by its values for $x \in Q $.

Secondly, how to show that $R^Q \sim R^N \sim R$ ?

Thank you.

share|improve this question

3 Answers 3

up vote 13 down vote accepted

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
    
Excellent answer amWhy! –  Sami Ben Romdhane Feb 3 at 17: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.)

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

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.