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 you show me how to "calculate" the cardinality of the set of increasing (not necessarily strictly) functions $\ f: \mathbb{R} \rightarrow \mathbb{R}$ ?

share|improve this question
4  
Hint: an increasing function has only countably many discontinuities. –  Chris Eagle Jan 14 '13 at 17:27
add comment

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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
1  
@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
1  
@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
show 7 more comments

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.