Prove that $(f\circ g)(1)\leq (f\circ g)(2)\leq \cdots\leq (f\circ g)(n)$ for some $g$. 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.
 A: 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}$.
A: 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
$$
