Demostrar la existencia de una función de ordenación

Question

Dejemos que $(X,\leq)$ sea un conjunto totalmente ordenado. Una ordenación para $f\in X^n$ es un elemento $g\in X^n$ satisfaciendo

(i) $g$ no es decreciente.

(ii) $ g=f\circ \sigma$ para alguna permutación $\sigma:\{1,\dots,n\}\to \{1,\dots,n\}$ .

Una función de clasificación para $X^n$ es una función $\Phi:X^n\to X^n$ tal que $\Phi(f)$ es un tipo para $f$ para cada $f\in X^n$ .

Me piden que demuestre que existe una función de ordenación para $X^n$ .

Mi intento:

Por inducción en $n$ . Si $n=1$ esto es trivial. Supongamos que existe una función de ordenación $\Phi:X^n\to X^n$ para algunos $n\geq 1$ .

Definir las funciones $\Gamma,\Delta:X^{n+1}\to X^{n+1}$ por $$\Gamma(f)=\bigg(\Phi[f|_{\{1,\dots,n\}}],f(n+1)\bigg)$$

$$\Delta(f)=f\circ \pi$$

donde $\pi:\{1,\dots,n+1\}\to \{1,\dots,n+1\}$ es la permutación definida por

$$\pi(i)=\begin{cases} i & \text{if } \quad i<i_0 \\ n+1 & \text{if } \quad i=i_0 \\ i-1 & \text{if } \quad i>i_0 \end{cases}$$

donde $i_0$ es el elemento más pequeño del conjunto $\big\{1\leq i\leq n:f(n+1)\leq f(i)\big\}$ si este conjunto no es vacío, y $i_0:=n+1$ de lo contrario.

Afirmo que $\Phi':=\Delta\circ \Gamma$ es una función de ordenación para $X^{n+1}$ . Desde $\Phi[f|_{\{1,\dots,n\}}]=f|_{\{1,\dots,n\}}\circ \sigma$ para alguna permutación $\sigma:\{1,\dots,n\}\to \{1,\dots,n\}$ vemos que $\Gamma(f)=f\circ \sigma'$ para alguna permutación $\sigma'$ . Entonces

$$\Phi'(f)=(\Delta\circ \Gamma) (f)=f\circ \sigma'\circ\pi$$ para la permutación $\sigma'\circ\pi$ . Al considerar los diferentes casos con respecto a $i_0$ también vemos que $i\leq j$ implica $\Phi'(f)(i)\leq \Phi'(f)(j)$ . Por lo tanto, $\Phi'(f)$ satisface (i) y (ii) para todos los $f\in X^{n+1}$ y por lo tanto es una función de ordenación para $ X^{n+1}$ .

¿Es esto correcto?

Muchas gracias por su ayuda

Answer 1

Por lo que veo parece correcto, sin embargo, no estoy del todo seguro ya que lo encuentro un poco enrevesado. Creo que la prueba se hace más concisa utilizando $\max$ en lugar del elemento más pequeño que sea mayor que $f(n+1)$ .

Dejemos que $[n]:=\{1,\dots,n\}$ y $\text{argmax}_n(f):=\max f^{-1}(\max\{f(i):i\in[n]\})$ para todos $n\in\mathbb{N}$ y $f\in X^n$ . Ahora, demostrando vía inducción: como escribiste, el caso base es trivial.

Supongamos que existe una función de ordenación $sort_n$ para $X^n$ para algunos $n\geq1$ . Para cada $f\in X^{n+1}$ definir $\pi_f:[n+1]\rightarrow[n+1]$ tal que $$\pi_f(k)=\begin{cases}n+1&\text{if }k=\text{argmax}_{n+1}(f)\\\text{argmax}_{n+1}(f)&\text{if }k=n+1\\k&\text{otherwise}\end{cases}$$ Además, por cada $f\in X^{n+1}:\exists\sigma_f:[n]\rightarrow[n]$ tal que $$sort_n(f|_{[n]})=f|_{[n]}\circ\sigma_f$$ Además, define para cada $\sigma:[n]\rightarrow[n]$ la única permutación $\sigma^*:[n+1]\rightarrow[n+1]$ tal que $\sigma^*|_{[n]}=\sigma$ .

Ahora defina $sort_{n+1}(f):X^{n+1}\rightarrow X^{n+1}$ tal que $$sort_{n+1}(f)=f\circ\pi_f\circ\sigma_{f\circ\pi_f}^*$$

(EDIT: como se ha señalado en los comentarios: Esto está bien definido ya que aunque la permutación $\sigma_{f\circ\pi_f}^*$ no es necesariamente única, las permutaciones sólo difieren si hay múltiples elementos iguales que pueden intercambiarse arbitrariamente entre sí, sin embargo, al intercambiar elementos iguales, el resultado sigue siendo el mismo).

Ahora, está claro que $sort_{n+1}(f)|_{[n]}=sort_n(f\circ\pi_f|_{[n]})$ para lo cual es claro, que es no decreciente vía hipótesis de inducción. También está claro que $sort_{n+1}(f)(n+1)$ es el máximo a través de la definición. Por lo tanto, el elemento completo es no decreciente. Y como las permutaciones son cerradas bajo composición, $sort_{n+1}$ es efectivamente una función de ordenación.