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.

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.

share|improve this question
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}$" –  Desiato Mar 27 '12 at 21:07
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. –  Dejan Govc Mar 27 '12 at 21:11
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. –  joriki Mar 27 '12 at 21:13
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,<)$. –  Asaf Karagila Mar 27 '12 at 23:44
add comment

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer
1  
+1. Very elegant. –  Dejan Govc Mar 27 '12 at 22:42
1  
@DDB: It does seem to be possible, with quite a small number of functions. –  joriki Mar 28 '12 at 0:50
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.) –  Dejan Govc Mar 28 '12 at 1:02
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. –  joriki Mar 28 '12 at 8:38
1  
@joriki: Beautiful! Thanks for notifying me. –  Dejan Govc Mar 28 '12 at 11:37
show 1 more comment

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}\}$.

share|improve this answer
2  
Your construction led me in the right direction to find a minimal $\mathcal F$; see my answer. –  joriki Mar 28 '12 at 8:40
add comment

Let $g$ be the function such that $g(x)=x$ if $x\leq0$, and $g(x)=0$ if $0<x<\eta$, 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)$.

share|improve this answer
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 ... –  Dejan Govc Mar 27 '12 at 20:48
    
Yes, you are right... –  francis-jamet Mar 27 '12 at 20:57
2  
@francis-jamet: Your answer can be salvaged; see mine. –  joriki Mar 27 '12 at 22:37
add comment

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.