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
    I'm not understanding the question. If you have an uncountable family of functions with this property, any countable (or finite) subset will also have that property, since the property does not contain an "there exists $f\in\mathcal{F}$"2012-03-27
  • 2
    @Desiato: the family suggested by francis-jamet will work if instead of one function for each $q_n\in\mathbb Q$ you modify it to contain one such function for each $r\in\mathbb R$. But it becomes uncountable this way.2012-03-27
  • 4
    @Desiato: What you wrote would be right if the bullet points were conditions on $\mathcal F$; but the condition is that these two statements be equivalent.2012-03-27
  • 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$.

  • 0
    Thanks! Do you know if it is possible for a finite collection of functions?2012-03-27
  • 1
    @DDB: It does seem to be possible, with quite a small number of functions.2012-03-28
  • 1
    This is one of the most exciting things I have seen in a very long time. I wish I could upvote more. (Both the question and this answer.)2012-03-28
  • 3
    @Dejan: Then you may be interested in the update, in which I show that the minimal number of functions in $\mathcal F$ is three.2012-03-28
  • 1
    @joriki: 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)$.

  • 3
    What about $x=\pi+\eta$ and $y=\pi$? Then $x-y=\eta$, despite the fact that $f(x)>f(y)$ for every $f$ in your family ...2012-03-27
  • 0
    Yes, you are right...2012-03-27
  • 2
    @francis-jamet: Your answer can be salvaged; see mine.2012-03-27