Cover of set in $\mathbb{R}$ with linear functions

54 Views Asked by At

Let $f_1,...,f_N$ be non-degenerate linear functions on $\mathbb{R} \to \mathbb{R}$. Is it possible to create an infinite and well ordered set $S \subset \mathbb{R}$ so that

$$f_i(S) \subset \bigcup_{j \ne i} f_j(S)$$ For all $i$ from $1$ to $N$. Here $f_i(S)$ denotes the image of $S$ under $f_i$. For $N=2$ it's not possible assuming well ordering, but possible if you just want countably infinite points. I have no idea how to tackle even $N=3$.

I should include that by linear, I mean $f_i(x) = a_ix+b_i$ for some $a_i,b_i \in \mathbb{R^+}$. I guess affine is more correct here.

There are cases where this is possible, ($2x,2x+1,4x,x+1$ on $\mathbb{N}$) but when is it possible?

1

There are 1 best solutions below

2
On BEST ANSWER

If such $S$ exists, there is a smallest element $s$ in $S$, consider min$\{f_i(s)\}$, there must be at least two index achieving minimum.

Claim: It is possible if and only if there is not a single point that all $f_i$ passthrough.

only if part:

just remove $s$ from $S$, the rest must also satisfy condition, hence smallest of that set is also coordinate of a intersection point, but there is only one intersection point.

if part:

Choose $s$ such that min$\{f_i(s)\}$ can be achieved for at least two index.

Let $S_0 = \{s\}$, define $S_n$ by induction, $S_n = \{x | f_i(x) = f_j(t) \text{ for some }i \ne j, t \in S_{n-1} \text{ and } x > t\}$.

Then $|S_n| < N^2 \cdot |S_{n-1}|$, $|S_n|$ is finite.

Next we prove $S = \cup_n S_n$ is well ordered.

Otherwise there is a decreasing sequence $\{x_l\}$, assume it has limit $x_0$ and is the smallest possible.

Take subsequence of $x$ such that $|x_k - x_m| < \epsilon /M$, where $\epsilon$ is minimum distance from an intersection point to lines not passing that point.

For some $i,j$ there is a subsequence of $x$ (indexed by $l$) and sequence $\{t_l\}$ in $S$ satisfy $f_i(x_l) = f_j(t_l)$ and $x_l > t_l$. Then $\text{ lim } x_l \ge \text{ lim } t_l$ must be equal since $x_0$ is the smallest. $f_i(x_0) = f_j(x_0)$ hence $x_0$ is coordinate of intersection point of $f_i$ and $f_j$.

Every $x_l$ can be traced back(those elements in $S$ used in its definition) to some line not passing that intersection point(since eventually trace to $s$ which is smaller than $x_0$).

By taking a subsequence, we can assume all trace back to the same line, meaning $f_i(t_l) = f_k(y_l)$ and $y_l$, $t_l$ are consecutive elements in tracing back sequence of $x_l$ satisfying $t_l > x_0 > y_l$.

$x_0 - y_l = (t_l - y_l) - (t_l - x_0) > (\epsilon - \epsilon/M) - 0$ this makes sequence $y$ has a smaller limit, its limit $y_0$ is in $S$ hence in some $S_n$, but $f_i(x_0) = f_k(y_0)$ indicates $x_0$ is in $S_{n+1}$, contradicts assumption on $x_0$.

Finally, we need $S$ is infinite. Only need to show it is infinite for case $N=3$, which is quite obvious.