# Rarrange 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 for $n=4$ and $n=5$. Thank you!

-
Are you looking for a bijection for which that holds for all choices of $x_1\dots x_n$? – Omnomnomnom Jul 19 '13 at 3:05
Wow, this is much less easy for the real interval than the rational. – Kevin Carlson Jul 19 '13 at 3:09
@Omnomnomnom Yes,thanks – Next Jul 19 '13 at 3:12
Is this generally possible for finite/countable sets? It doesn't seem obvious that it should be – Omnomnomnom Jul 19 '13 at 3:19
Doesn't the Erdos-Szekeres theorem say this is impossible (even for the rationals) – deinst Jul 19 '13 at 4:07

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.

-

No need to bring in Ramsey theory! Given such a function $f$, consider the sequence $$f\left(1 - \tfrac{1}{2} \right), \left(1 - \tfrac{1}{3} \right), \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_3 < 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$.

-