7
$\begingroup$

Let $\eta>0$. Does there exist a countable collection $\mathcal{F}$ of real-valued functions on $\mathbb{R}$ such that the following properties are equivalent?

  • $x - y > \eta$
  • for all $f\in\mathcal{F}$, $f(x)>f(y)$

I can make it work for an uncountable collection of functions, but I believe it is false for the countable case.

I have tried showing that there does not exist a finite collection with the desired property, but there was a flaw in my argument. I asked a question here to check if a certain statement is true, but it turns out there is a counterexample, so this invalidates my proof for the finite case.

  • 1
    Just a point to be made, sometimes thing exist only in infinite domains. Namely, there are no finite models of a certain theory. The best and simplest example, methinks, is dense linear orders. The minimal model is (\mathbb Q,<).2012-03-27

3 Answers 3

7

The hole that Dejan pointed out in Francis' attempt can be plugged by instead defining

$g(x)=\begin{cases}x&x\le0\;,\\x-\eta&x\gt0\;.\end{cases}$

Then $x-y\gt\eta$ still implies $f(x)\gt f(y)$, and for $0\lt x-y\le\eta$ there is always a rational between $x$ and $y$ and the corresponding $f_n$ has $f_n(x)\le f_n(y)$; for $x-y\le0$ "most" $f_n$ will do.

[Update:]

Perhaps somewhat surprisingly, it turns out that the minimal number of functions in $\mathcal F$ is three. Building on Robert's answer, define

$g(x)=x+2\left(\left\lfloor\frac{x+1}3\right\rfloor-\left\lfloor\frac{x+2}3\right\rfloor\right)(x-\lfloor x\rfloor) - 2\left(\left\lfloor\frac{x+1}3\right\rfloor-\left\lfloor\frac{x}3\right\rfloor\right)\;.$

(Here's a plot.) Then $\{f_0,f_1,f_2\}$ with $f_k=g(2x/\eta+k)$ is a collection of real-valued functions that satisfies the condition, for reasons analogous to the ones given by Robert.

To see that two functions are not enough, assume that $\mathcal F=\{f_1,f_2\}$ is a collection of two functions satisfying the condition. Call $f$ a witness for an (ordered) pair $\def\pair#1#2{\langle #1,#2\rangle}\pair yx$ if $f(x)\le f(y)$. The condition requires that there be a witness in $\mathcal F$ for every pair $\pair yx$ with $x-y\le\eta$.

If $f$ is a witness for $\pair{x-\eta}{x}$, it cannot also be a witness for $\pair{x}{x+\eta}$, since the condition requires $f(x+\eta)\gt f(x-\eta)$ for all $f\in\mathcal F$. Thus $f_1$ and $f_2$ must alternate in being witnesses for $\pair{x+k\eta}{x+(k+1)\eta}$ for $k\in\mathbb Z$. Assume without loss of generality that $f_1$ is a witness for $\pair0\eta$ and $\pair{2\eta}{3\eta}$. Then $f_1(\eta)\le f_1(0)\lt f_1(3\eta/2)\lt f_1(3\eta)\le f_1(2\eta)$, so $f_1$ is not a witness for $\pair{\eta}{3\eta/2}$ or $\pair{3\eta/2}{2\eta}$. Thus $f_2$ is a witness for these pairs, so $f_2(\eta)\ge f_2(3\eta/2)\ge f_2(2\eta)$. But then $f_2(\eta/2)\lt f_2(2\eta)\le f_2(3\eta/2)\le f_2(\eta)\lt f_2(5\eta/2)$, so $f_2$ is a witness for neither $\pair{\eta/2}{3\eta/2}$ nor $\pair{3\eta/2}{5\eta/2}$, in contradiction to the earlier conclusion that $f_1$ and $f_2$ alternate in being witnesses for $\pair{\eta/2+k\eta}{\eta/2+(k+1)\eta}$ for $k\in\mathbb Z$.

  • 1
    @jor$i$ki: Beautiful! Thanks for notifying me.2012-03-28
4

Consider the functions f_r(x) = \cases{ x & for $x \le r$\cr 2r-x & for $r < x \le r + \eta/2$\cr x - \eta & for $x > r + \eta/2$\cr } Note that $f_r(x+\eta) \ge f_r(x)$, with equality iff $r-\eta/2 \le x \le r$, and $f_r(x+t) > f_r(x)$ if $t > \eta$. If $x \le y$ and $r > y$ we have $f_r(x) \le f_r(y)$, while if $y \le x \le y+\eta$ we have $f_r(x) \le f_r(y)$ if $(x,y)$ is in the closed diamond-shaped region with vertices at $(r,r), (r+\eta/2,r+\eta/2),(r+\eta,r),(r+\eta/2,r-\eta/2)$. So we can take ${\cal F} = \{ f_{j \eta/2}: j \in {\mathbb Z}\}$.

  • 2
    Your construction led me in the right direction to find a minimal $\mathcal F$; see my answer.2012-03-28
0

Let $g$ be the function such that $g(x)=x$ if $x\leq0$, and $g(x)=0$ if $0, and $g(x)=x-\eta$ if $x \geq \eta$. Let $q_n$ a bijection between $\mathbb{N}$ and $\mathbb{Q}$. The set $\mathcal{F}$ is $\{ f_n| n \in \mathbb{N}\}$ with $f_n(x)=g(x+q_n)$.

  • 2
    @francis-jamet: Your answer can be salvaged; see mine.2012-03-27