Suppose I have two order-preserving, surjective maps $s \colon [m] \to [n] $ and $s' \colon [m'] \to [n]$. I need to show that there exists some $l \in \mathbb{N}$ and order-preserving, surjective maps $t \colon [l] \to [m]$ and $t' \colon [l] \to [m']$ such that $s \circ t = s' \circ t'$. What's the quickest way to prove this?
I have a vague idea that it might involve the maps $\sigma_{i}^{n} \colon \left[n+1\right] \to \left[n\right]$ that are given by $$\sigma_{i}^{n}\left(j\right) = \begin{cases} j & \text{if } 0 \leq j \leq i \\ j-1 & \text{if } i+1 \leq j \leq n+1 \end{cases}$$. That is, start by writing $s$ and $s'$ as composites of the $\sigma^{n}_{i}$. But this seems way too tedious and I'm getting lost in the indices.
Another vague idea I have is to make a list of how many times each entry in $[n]$ is hit by $s$ and $s'$ and to construct an order-preserving surjective map $[l] \to [n]$ so that the hits of each entry in $[n]$ under the newly constructed map is the sum of hits under $s$ and under $s'$ (maybe we need to subtract one from the total). But then, I need to construct $t$ and $t'$ such that this newly constructed map is equal to the composites $s \circ t = s' \circ t'$. Again, getting lost in the weeds at this point.
I'd ideally like a clean, category theoretic argument (without resorting to multiple cases and indices) but I'm not sure this is possible since the maps involved are probably not unique. Any help appreciated!
It helps to look at this from a different perspective. Given an order-preserving surjective map $f:[m]\to [n]$, consider the list $[f(1),f(2),\dots,f(m)]$. This will look something like $$ [1,1,1,1,2,2,3,4,5,5,5] $$ This can be written more succinctly as $$ \text{four $1$'s, two $2$'s, one $3$, one $4$, three $5$'s}, $$ or even more succinctly as $$ (\text{four, two, one, one, three})=(4,2,1,1,3) $$ That is, order-preserving surjective maps $[m]\to[n]$ are in bijection with compositions of $m$ with $n$ parts.
You want to find $t$ and $t'$ so that $s\circ t=s'\circ t'$. Since every order-preserving surjective map can be written as a composition of the maps $\sigma^r_k$ for various choices of $r$ and $k$, it helps to understand how the composition for $s$ relates to the composition for $s\circ \sigma_{k}^{n+1}$.
Let's look at some examples, using the same $f$ from before:
If you think about these examples enough, you can see that the composition for $f\circ \sigma_k^{n+1}$ is given by incrementing one of the parts of the composition for $f$. Furthermore, by appropriately choosing $k$, you can choose to increment any of the parts in this fashion. I will refer to this operation as inflation.
Since $t$ can be written as a composition of $\sigma^r_k$ for various $r$ and $k$, finding $t$ and $t'$ for which $s\circ t=s'\circ t'$ is equivalent to finding two series of inflations, one applied to the composition for $s$, the other applied to the composition for $s'$, such that the resulting compositions are equal. This is doable with the following very simple procedure. Suppose $s$ has composition $(a_1,a_2,\dots,a_n)$ and $s'$ has composition $(b_1,b_2,\dots,b_n)$. For each $i\in \{1,\dots,n\}$, look at $a_i$ and $b_i$. If $a_i<b_i$, then inflate $a_i$ until it equals $b_i$, and if $a_i\ge b_i$, then inflate $b_i$ until it equals $a_i$.