# Cardinality of the set of increasing real functions

Could you show me how to "calculate" the cardinality of the set of increasing (not necessarily strictly) functions $\ f: \mathbb{R} \rightarrow \mathbb{R}$ ?

• Hint: an increasing function has only countably many discontinuities. – Chris Eagle Jan 14 '13 at 17:27

There are only $|\Bbb R|=2^\omega$ such functions.

Let $\varphi:\Bbb Q\to\Bbb R$ be non-decreasing. There are only $|\Bbb R|^{|\Bbb Q|}=\left(2^\omega\right)^\omega=2^\omega$ functions from $\Bbb Q$ to $\Bbb R$, and it’s easy to see that there are at least $|\Bbb R|=2^\omega$that are non-decreasing, so there are $2^\omega$ such functions $\varphi$. If $f:\Bbb R\to\Bbb R$ is non-decreasing, then $f\upharpoonright\Bbb Q$ is one of these $2^\omega$ functions, so we’d like to know how many non-decreasing functions from $\Bbb R$ to $\Bbb R$ restrict to a given non-decreasing $\varphi:\Bbb Q\to\Bbb R$.

Let $\varphi:\Bbb Q\to\Bbb R$ be non-decreasing, and suppose that $f:\Bbb R\to\Bbb R$ is non-decreasing and restricts to $\varphi$ on $\Bbb Q$. For each irrational $x$ let

$$\varphi^-(x)=\sup_{q\in\Bbb Q\cap(\leftarrow,x)}\varphi(q)$$

and

$$\varphi^+(x)=\inf_{q\in\Bbb Q\cap(x,\to)}\varphi(q)\;;$$

then $\varphi^-(x)\le f(x)\le \varphi^+(x)$. If $\varphi^-(x)=\varphi^+(x)$, then there is only one way to define $f(x)$. Otherwise, there are $\left|\big[\varphi^-(x),\varphi^+(x)\big]\right|=2^\omega$ choices for $f(x)$.

Let $$C=\left\{x\in\Bbb R\setminus\Bbb Q:\big(\varphi^-(x),\varphi^+(x)\big)\ne\varnothing\right\}\;;$$ the intervals $\big(\varphi^-(x),\varphi^+(x)\big)$ for $x\in C$ are pairwise disjoint, so there are at most countably many of them. Thus, $f(x)$ is completely determined by $\varphi$ except on the countable set $C$, and for each $x\in C$ there are $2^\omega$ possible values for $f(x)$, so there are at most $\left(2^\omega\right)^\omega=2^\omega$ possible non-decreasing functions $f:\Bbb R\to\Bbb R$ such that $f\upharpoonright\Bbb Q=\varphi$.

Putting the pieces together, we see that there are at most $2^\omega\cdot2^\omega=2^\omega$ non-decreasing functions $f:\Bbb R\to\Bbb R$, and the constant functions already show that there are at least that many.

• Thank you. Could you explain, however, why there are $\left|\big[\varphi^-(x),\varphi^+(x)\big]\right|$ choices for $f$, for irrational $x$ and why there's a change of notation in $\big(\varphi^-(y),\varphi^+(y)\big)$ ? – Hagrid Jan 14 '13 at 18:57
• @Anna: Show that if two of those intervals overlapp, $\varphi$ is not non-decreasing. Remember, their overlap will be a whole open interval. – Brian M. Scott Jan 14 '13 at 19:06
• @Asaf: Those are easier than the $2^\omega$ constant functions from $\Bbb R$ to $\Bbb R$? – Brian M. Scott Jan 14 '13 at 19:07
• @Asaf: They’re non-decreasing, which is what the question is about: see ‘not necessarily strictly’ in the question statement. – Brian M. Scott Jan 14 '13 at 19:15
• @Anna: You just need that if $x_1<x_2$, then $\varphi^+(x_1)\le\varphi^-(x_2)$. Suppose that $\varphi^-(x_2)<\varphi^+(x_1)$; then there is a $q\in\Bbb Q$ such that $q<x_1$ and $\varphi(q)>\varphi^+(x_2)$, and then there is a $p\in\Bbb Q$ such that $p>x_2$ and $\varphi(p)<\varphi(q)$, contradicting the hypothesis that $\varphi$ is non-decreasing. Here I’m using properties of the $\sup$ and $\inf$. – Brian M. Scott Jan 14 '13 at 19:34

Any nondecreasing function is Borel measureable, but there are only $$\mathbf{R}$$ many Borel measureable functions.