4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Goldstern
    Commented Dec 7, 2012 at 11:26
  • $\begingroup$ 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! $\endgroup$ Commented Dec 7, 2012 at 19:41

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Amazing... When I wrote my answer, I thought that this particular family is very uncanonical. $\endgroup$
    – Goldstern
    Commented Dec 7, 2012 at 11:46
  • 2
    $\begingroup$ It becomes a little more canonical because the OP already mentioned logarithms. $\endgroup$ Commented Dec 7, 2012 at 11:53
  • $\begingroup$ This is perfect! (Especially with Goldstern's reminder below containing some elementary real analysis.) Thank you! $\endgroup$ Commented Dec 7, 2012 at 19:39
7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This was super helpful as well. Thanks! $\endgroup$ Commented Dec 7, 2012 at 19:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .