3
$\begingroup$

I am trying to prove the following result.

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

The first thing I'm trying to understand is the hint. If I am understanding it correctly, it says this. The rationals are dense in the reals, so I can always construct a sequence of rationals converging to any real. In fact, we can construct the reals as the limits of Cauchy sequences of rationals. So if I have two functions $f,g$ that send the rationals to the same points, it has to be the case that they send all the reals to the same points, so the function is ``uniquely determined'' by its outputs on the rationals, which we can safely enumerate as $q_1, \ldots, $ because they're countable. Is this right?

Formally, if $x \in \mathbb{R}$ and $(q_n) \to x$ where $q_n$ rational, we have by continuity of $f$ \begin{align*} f(x) = f\left(\lim\limits_{n \to \infty} q_n\right) = \lim\limits_{n \to \infty} f(q_n). \end{align*} Is this the right idea? Am I missing any formalism?

As for the actual proof, I only have an idea for how to prove that $|\mathbb{R}| = |C|$. I want to use the Schroeder-Bernstein theorem to construct injections in both directions and then conclude that there exists a bijection. I can write an injection from $\mathbb{R}$ to $C$ rather easily by mapping $c \in \mathbb{R}$ to the function $f(x) = c$ for all $x$, which is constant, hence continuous. In the opposite direction, I can enumerate the rationals $q_1, q_2, \ldots$ and map a continuous function $f$ to a sequence of its values $(f(q_1), f(q_2), \ldots)$, but that gives an injection to sequences of real numbers, $\mathbb{R}^{\mathbb{N}}$. I would need to then inject $\mathbb{R}^{\mathbb{N}}$ to $\mathbb{R}$ and compose injections to get an injection from $C$ to $\mathbb{R}$.

I do not have an idea for how to prove $|C| < |F|$. The notation is non-standard (since the cardinalities aren't finite), but I believe this typically means that there does not exist a surjection from $C$ to $F$, which makes sense, as intuitively there are plenty more total functions that aren't continuous. I considered a diagonal argument, but can't fully work out the details.

Any help, especially on this last part, would be very much appreciated.

$\endgroup$
1
  • $\begingroup$ The hint should be used as follows: the set of functions $A\to B$ has cardinality $|A|^{|B|}$. Now since a continuous function is fully determined by its values on the rational numbers (to prove), the set of continuous function on $\mathbb{R}$ will have cardinality $|\mathbb{Q}|^{|\mathbb{R}|}$ whereas the set of function on the real numbers has cardinality $|\mathbb{R}|^{|\mathbb{R}|}$. To prove that these two sets are of different cardinality use a cantor-type argument. $\endgroup$
    – b00n heT
    Commented Mar 9, 2021 at 7:27

2 Answers 2

4
$\begingroup$

What the determined by values on $\Bbb Q$ hint implies is that when two continuous real functions agree on $\Bbb Q$, they agree on $\Bbb R$.

So the map $r: C \to \Bbb R^{\Bbb Q}$ defined by $r(f)= f\restriction_{\Bbb Q}$ is 1-1. The right hand set is the set of all functions from $\Bbb Q$ to $\Bbb R$, as usual.

Let $\mathfrak{c}=|\Bbb R| = 2^{\aleph_0}$ then basic set theory (cardinal arithmetic) tells us

$$|C| \le | \Bbb R^{\Bbb Q} | = \mathfrak{c}^{\aleph_0} = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \times \aleph_0} = 2^{\aleph_0}= |\Bbb R|$$

As $|F| = \mathfrak{c}^{\mathfrak{c}} = 2^{\mathfrak{c}} > |\Bbb R|$ by Cantor's theorem, we're done: $\mathfrak{c} =|C| < |F|$.

$\endgroup$
1
  • $\begingroup$ Why is $(2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \times \aleph_0}$ in cardinal arithmetic? $\endgroup$
    – john
    Commented Jun 9, 2022 at 3:12
3
$\begingroup$

To inject $\Bbb R^{\Bbb N}\to\Bbb R$, I'd identify $\Bbb R$ with $\mathcal P(\Bbb N)$. But then how do we turn a sequence of subsets $A_1,A_2,\ldots $of $\Bbb N$ into a single subset of $\Bbb N$? Simply partition $\Bbb N$ in to infinitely many copies $2^n(2\Bbb N+1)$ of itself! So the sequence $A_1,A_2,\ldots$ maps to the set $A$ where $m\in A$ iff it can be written as $m=2^k(2l+1)$ and $l\in A_k$.


Assumes there is a surjection $f\colon\Bbb R\to F$. So for $x\in \Bbb R$, we have some function $f_x\in F$, which in particular itself maps $x$ to some real number $f_x(x)$. Define $g\colon \Bbb R\to \Bbb R$ as $g(x):=f_x(x)+1$. Then there is no $\xi\in\Bbb R$ with $g=f_\xi$, for that would imply $g(\xi)=f_\xi(\xi)$ as well as $g(\xi)=f_\xi(\xi)+1$.

$\endgroup$
1
  • $\begingroup$ What do you mean partition $\Bbb N$ into infinitely many copies $2^n(2\Bbb N+1)$ of itself? How does this partition look. Also I would like to say I dislike how ad-hoc this whole cardinality set theory seems to be. There seems to be no rhyme or reason to how people come up with results. But I guess this speaks to my ignorance on the subject. $\endgroup$
    – john
    Commented Jun 9, 2022 at 3:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .