Prove that $(f\circ g)(1)\leq (f\circ g)(2)\leq \cdots\leq (f\circ g)(n)$ for some $g$.

Question

Let $n\in\Bbb N$. Prove that for every function $ f: J_n \to \Bbb R $, there exists a bijective function $ g: J_n \to J_n $ such that $$(f\circ g)(1)\leq (f\circ g)(2)\leq \cdots\leq (f\circ g)(n).$$

Note: $J_n=\{1,2,3,\ldots,n\}.$

I try to prove that by induction.

For $n=1$, there's nothing to do.

For $n=2$, We have to show that for every function $ f: J_2 \to \Bbb R $, there exists a function $ g: J_2 \to J_2 $ such that $$ (f \circ g) (1) \leq (f \circ g) ( 2). $$ Let's fix the function $ f: J_2 \to \Bbb R $ given by $ f (1) = r_1 $ and $ f (2) = r_2 $, where $ r_1, r_2 \in \Bbb R $. Without loss of generality, let's take $ r_2 \leq r_1 $, then we can define the function $ g: J_2 \to J_2 $ as $ g (1) = 2 $ and $ g (2) = 1 $. And we would have that $ f (g (1)) = f (2) = r_2 $ and $ f (g (2)) = f (1) = r_1 $ and clearly what we want is fulfilled.

Some help for the inductive step would be appreciated, I really don't know how to do that part.

Answer 1

Not sure that induction is required here. Denote $f_i = f(i)$ and order the $\{f_i\}$:

$$f_{i_1} \le f_{i_2} \le \dots \le f_{i_n}.$$

Let $g \in \mathfrak S_n$ be the permutation defined by $g(j) = i_j$ for $j \in J_n$.

You're done as $(f \circ g)(j) = f(g(j)) = f(i_j) =f_{i_j}$.

Answer 2

How to use induction

How to take the induction step $n\to n+1$: You already know that for $f:J_{n+1}\to\mathbb{R}$ there exists $g':J_n\to J_n$ s.t. $f(g'(i)) \leq f(g'(j)) $ for $i\leq j\leq n$ (but not for $n+1$). You now have an additional element $f(n+1)$.

As you can sort your elements there exists an index $i\leq n$ s.t. $f(g'(i))\leq f(n+1)\leq f(g'(i+1))$.

You new $g:J_{n+1}\to J_{n+1}$ is now defined as $$ g(j) = \begin{cases}g'(j) \text{ for } j \leq i \\ n+1 \text{ for } j = i+1 \\ g'(j-1) \text{ for } j\geq i +1 \end{cases} $$

More complex solution

You don't necessarily need induction. You could just generalize your solution for $n=2$ as follows:

Take $f:J_n\to \mathbb{R}$ saying $f(i) = r_i$. Let's sort these values $r_1,...,r_n$ ascending. Use the set $A_j$ to get the values which are $\geq$ than the first $j$ elements: $$ A_1 = \{r_1,...,r_n\} \\ A_j = A_{j-1} \setminus\min_{r_k\in A_{j-1}} r_k \text{ for } j\geq 2 $$ E.g. for $n=3$ and $r_2 \leq r_3\leq r_1$ we will get $A_1=\{r_1,r_2,r_3\},A_2=\{r_3,r_1\},A_3=\{r_1\}$.

We can then define $g$ as follows: \begin{align} g: J_n&\to J_n \\ j &\mapsto\text{arg}\min_{r_k\in A_j} r_k \end{align} This function will sort the $a_i$ so that everything works out. In above example we would have $g(1)=2,g(2)=3,g(3)=1$ so in total we would have $$ f(g(1))=r_2 \leq f(g(2))=r_3 \leq f(g(3)) = r_1 $$