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

  • 6
    $\begingroup$ Hint: an increasing function has only countably many discontinuities. $\endgroup$ – 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)$$


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

  • $\begingroup$ 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)$ ? $\endgroup$ – Hagrid Jan 14 '13 at 18:57
  • 1
    $\begingroup$ @Anna: Show that if two of those intervals overlapp, $\varphi$ is not non-decreasing. Remember, their overlap will be a whole open interval. $\endgroup$ – Brian M. Scott Jan 14 '13 at 19:06
  • 1
    $\begingroup$ @Asaf: Those are easier than the $2^\omega$ constant functions from $\Bbb R$ to $\Bbb R$? $\endgroup$ – Brian M. Scott Jan 14 '13 at 19:07
  • 1
    $\begingroup$ @Asaf: They’re non-decreasing, which is what the question is about: see ‘not necessarily strictly’ in the question statement. $\endgroup$ – Brian M. Scott Jan 14 '13 at 19:15
  • 1
    $\begingroup$ @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$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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