Rearrange all the real numbers between $0$ and $1$

Can we rearrange all the real numbers between $0$ and $1$, denote $f(x):(0,1) \rightarrow (0,1)$ (a bijection), such that for $$\forall 0<x_1<x_2<\dots<x_n<1,$$ neither $$f(x_1) <f(x_2) <\dots <f(x_n)$$ nor $$f(x_1)>f(x_2)>\dots>f(x_n)$$ can be hold $(n>3)$?

I'd like to see an answer in particular for $n=4$ and $n=5$.

Solution 1:

As deinst's link has spectacularly shown, there is a direct link between the question of finding a suitable bijection (per your criteria) and Ramsey theory. Let's start by answering the question on finite sets:

Let $X=\{x_1,\dots ,x_N\}\subset \mathbb R$ with $x_i<x_{i+1}$ be a set of cardinality $N\in\mathbb N$, and let $f:X\to X$ be a bijection. Let $G_f$ be the graph defined as follows:

Draw one node for each $x_i$. For any $i< j$ from $1$ to $N$, we draw an edge $e_{ij}$. If $f(x_i)<f(x_j)$, color the edge red. If $f(x_i)>f(x_j)$, color the edge blue.

Our condition is that neither $$ f(x_{i_1}) <f(x_{i_2}) <\dots <f(x_{i_n}) $$ nor $$ f(x_{i_1}) >f(x_{i_2}) >\dots >f(x_{i_n}) $$ is true for any increasing selection of indices $i_k$. This condition holds iff $G_f$ has no monochromatic complete subgraph on $n$ nodes. Thus, for a given $X$, we only can find a suitable $f$ when $N<R(N,N)$.

With that in mind, Ramsey theory gives us the following results:

• if $n=3$, we can only find a suitable $f$ if $N<6$
• if $n=4$, we can only find a suitable $f$ if $N<18$
• if $n=5$, we can only find a suitable $f$ if $N<49$
• if $n=6$, we can only find a suitable $f$ if $N<165$

and so on and so forth, following the diagonal entries of this table.

Finally, as was pointed out in the comments: for any $X$ of non-finite cardinality, the Infinite Ramsey's Theorem tells us that we can find infinitely many (increasing) $i_k$ so that

$$ f(x_{i_1}) <f(x_{i_2}) <\dots <f(x_{i_k})<\dots $$ or $$ f(x_{i_1}) >f(x_{i_2}) >\dots >f(x_{i_k})>\dots $$

Note: although every bijection has a corresponding graph, not every possible graph on the $N$ nodes as defined above corresponds to a possible bijection $f:X\to X$. However, there may be a bijection for every graph up to isomorphism. At any rate, it is not clear to me whether, for example, we can find a bijection $f$ on an $X$ containing $5$ elements that will satisfy the condition for $n=3$.

After some investigation, it turns out that there is no suitable bijection on a set of $5$ elements. The conditions I gave above on the number of elements in a set are thus necessary but insufficient to establish the existence of a suitable bijection.

Solution 2:

No need to bring in Ramsey theory! Given such a function $f$, consider the sequence $$ f\left(1 - \tfrac{1}{2} \right),\; f\left(1 - \tfrac{1}{3} \right),\; f\left(1 - \tfrac{1}{4} \right), \ldots $$ As any sequence in $\mathbb{R}$ has a monotone subsequence, there exists an increasing sequence of real numbers $x_i$, $0 < x_1 < x_2 < x_3 < \cdots$, such that $$ f(x_1) \le f(x_2) \le f(x_3) \le \cdots \text{ or } f(x_1) \ge f(x_2) \ge f(x_3) \ge \cdots $$ and since $f$ is a bijection, equality cannot hold, i.e. $$ f(x_1) < f(x_2) < f(x_3) < \cdots \text{ or } f(x_1) > f(x_2) > f(x_3) > \cdots $$ so the rearrangement you ask for is impossible for any $n$.