# 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.

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}$$.

• Thank you very much for answering. I appreciated Jun 7, 2021 at 22:05

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$$

• Thank you very much for the reply. One question, regarding the $g$ function. What do you mean by $\ text {arg}$ that part I didn't understand. Jun 7, 2021 at 22:04
• That means the argument of the minimum. If $a_s$ is the minimum, arg min would have the value $s$. This is necessary to get the index for the function $g$ Jun 8, 2021 at 5:49