MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\Bbb{R}^{+}\_{0}$ be the set of non-negative real numbers and $\Bbb{R}^{+}$be the set of positive reals. Let us say that a function $f \colon \Bbb{R}^{+}\_{0} \to \Bbb{R}^{+}\_{0}$ is eventually sublinear if $\ \forall r \in \Bbb{R}^{+} \ \exists x_0 \in \Bbb{R}^{+} \colon \forall x \geq x_0, f(x) < rx$. Let $S$ be the set of non-decreasing, eventually sublinear functions (we require no continuity). We define an equivalence relation on $S$: $f \sim g$ if and only if $f$ and $g$ are eventually boundedly close, i.e., $\exists K>0\ \exists x_0 \in \Bbb{R}^{+} \colon \forall x \geq x_0, |f(x)-g(x)| < K$. Denote the set of equivalence classes of $S$ under $\sim$ by $\ T$.

Question 1: What is the cardinality of $\ T$?

Question 2: Does this cardinality change if we drop the requirement that the functions are non-decreasing? What if the co-domain becomes $\Bbb{R}$?

Looking at the set of pairwise non-equivalent sublinear functions $\{f(x) = r*ln(x) \mid r \in \Bbb{R}\}$ shows that $|T|$ must be at least as big as the cardinality of the reals, $\beth_1$. Also, $|T|$ can be no bigger than the cardinality of all functions from $\Bbb{R}$ to $\Bbb{R}$, which is $\beth_2$, the cardinality of the power set of the reals. So there seem to be three options:

Option 1: ZFC proves $|T| = \beth_1$.

Option 2: ZFC proves $|T| = \beth_2$.

Option 3: This question is independent from ZFC (but perhaps not independent from ZFC + Generalized CH?).

Different proof ideas involving explicit bounds or forcing are failing me. So does anyone know of an answer and a proof? Thanks.

share|cite|improve this question
Could you give some motivation for your question? Note that there are only continuum many nondecreasing functions. (Also, note that a priori there are many other possibilities for a cardinal number to be between $\aleph_0$ and $\beth_2$, such as $\aleph_1$; however, experience shows that the answer to naive questions about cardinality is almost always $\aleph_0$ or $2^{\aleph_0}$, when separable spaces are involved. – Goldstern Dec 7 '12 at 11:26
I don't really remember the "motivation" right now. It came from a fellow graduate student's research in geometry group theory, but she is the sort to walk into a room, drop this sort of problem down without context, and then leave. I was interested in it independently as a toy problem (and because I like infinite cardinality counting problems). If this doesn't answer her original question, I'll come back! Thanks again! – Charlie Cunningham Dec 7 '12 at 19:41
up vote 7 down vote accepted

There are only $\beth_1$ non-decreasing functions from $\mathbb R_0^+$ to itself, because such a function is determined by its values on a dense set plus information about its countably many discontinuities. So the answer to Question 1 is $\beth_1$. For Question 2, the answer is $\beth_2$. Take any proper nonempty subset $A$ of the unit interval (there are $\beth_2$ of these), and consider the function $f_A$ that agrees with the natural logarithm at points whose fractional part is in $A$ and is identically 0 at all other points. No two of these functions are boundedly close.

share|cite|improve this answer
Amazing... When I wrote my answer, I thought that this particular family is very uncanonical. – Goldstern Dec 7 '12 at 11:46
It becomes a little more canonical because the OP already mentioned logarithms. – Andreas Blass Dec 7 '12 at 11:53
This is perfect! (Especially with Goldstern's reminder below containing some elementary real analysis.) Thank you! – Charlie Cunningham Dec 7 '12 at 19:39

(EDIT: I was busy writing this answer when Andreas Blass already submitted his answer. No need to read this answer, it is surprisingly similar to Andreas' answer.)

Every function $f: \mathbb R_0^+\to \mathbb R_0^+$ is completely determined by its restriction to $\mathbb Q \cup D(f)$, where $D(f)$ is the set of points where $f$ is not continuous. If $f$ satisfies $x\le y \Rightarrow f(x) \le f(y)$, then $D(f)$ is countable since the intervals $(\lim_{x\to a-} f(x), \lim_{x\to a+} f(x))$ are disjoint for $a\in D(f)$. So the number of nondecreasing functions is $\beth_1=2^{\aleph_0}$.

If the functions are not required to be nondecreasing, then there are $\beth_2 = 2^{\beth_1}$ equivalence classes, which can be seen as follows:

For every set $A \subseteq (0,1)$ define $f_A$ by $f_A(n+x) = \log(n)$ if $x\in A$, $n\in \mathbb N$. Let $f_A(n+x) = 0$ for $x\in [0,1]\setminus A$.

share|cite|improve this answer
This was super helpful as well. Thanks! – Charlie Cunningham Dec 7 '12 at 19:38

Your Answer


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.