Hint wanted: Any order-preserving $\phi:[m] \to [n]$ can be decomposed uniquely as composition of an injective and a surjective function

Question

Let $[n]=\{0,1,...,n\}$. I would like to show that that Any order-preserving (meaning if $i \leq j$, then $\phi(i) \leq \phi(j))$ $\phi:[m] \to [n]$ can be decomposed uniquely as composition of an injective and a surjective function, i.e. $\phi=\phi_1\phi_2$, where $\phi_1,\phi_2$ are order-preserving and $\phi_1:[k] \to [n]$ is injective, $\phi_2:[m] \to [k]$ is surjective (for some $k$). I have shown that this decomposition exists, but I have hard time showing that this decomposition is unique. Can anyone give me some hint? Thank you.

Answer 1

Let $\phi:[m]\rightarrow[n]$ be an order-preserving map. Write $\phi([m])=\{x_0<x_1<\ldots <x_k\}$; i.e. the elements $x_i\in [n]$ are the image of $\phi$, such that $x_i<x_j$ if $i<j$. Then there is a injective order-preserving map $\phi_1:[k]\rightarrow[n]$ given by $\phi(i)=x_i$, and a surjective map $\phi_2:[m]\rightarrow[k]$ defined by $\phi(i)=x_{\phi_2(i)}$. By construction, $\phi_1\circ \phi_2(i)=x_{\phi_2(i)}=\phi(i)$.

On the other hand, suppose that there is some other factorization $\phi=\phi_1'\circ\phi_2'$ such that $\phi_1':[m]\rightarrow[k']$ and $\phi_2':[k']\rightarrow[n]$ are order-preserving, $\phi_1'$ is injective and $\phi_2'$ is surjective. Then note that $k'+1=|\phi_1'([k'])|=|\phi([m])|=k+1$, so $k'=k$.

To prove $\phi_1=\phi_1'$ and $\phi_2=\phi_2'$, it suffices to consider the co-domain restricted maps $\phi:[m]\rightarrow \phi([m])$, $\phi_1,\phi_1':[k]\rightarrow \phi([m])$. In this context, $\phi_1,\phi_1'$ are injective and surjective, hence bijective. Furthermore, note that an bijective order-preserving map has an order-preserving inverse.

Then $\phi_1^{-1}\circ\phi_1':[k]\rightarrow[k]$ is an order-preserving bijection; this is only possible if $\phi_1^{-1}\circ\phi_1'=1_{[k]}$, hence $\phi_1=\phi_1'$. But then, $\phi_2=\phi_1^{-1}\circ \phi_1\circ\phi_2=\phi_1^{-1}\circ\phi_2=\phi_2'$