# 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
@Hagrid: The $y$’s were copied and pasted during an earlier version of the answer, and I forgot to fix them; I’ve done so now. If $x$ is irrational, we know that we must have $\varphi^-(x)\le f(x)\le\varphi^+(x)$ in order for $f$ to be non-decreasing, so the choices for $f(x)$ are the $|[\varphi^-(x),\varphi^+(x)]|$ real numbers in the interval $[\varphi^-(x),\varphi^+(x)]$. This number is either $1$ or $2^\omega$, depending on whether $\varphi^-(x)=\varphi^+(x)$ or not. –  Brian M. Scott Jan 14 '13 at 19:02
It's easier to show there are at least $2^{\aleph_0}$ such that functions by using the map: $r\mapsto x+r$ or $r\mapsto r\cdot x$ (for $r>1$). –  Asaf Karagila Jan 14 '13 at 19:03
@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
@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