Let $n, m \in \mathbb N$ and also let $n \leq m$, we define the set: $$\text{Inc}(n,m): = \{f: \{1,...,n\} \to \{1,...,m\} \mid f \text{ strictly increasing}\}.$$
I am trying to prove (for $n<m$ I think) that such increasing functions on a subset of the integers satisfy the following property:
$$ \text{Inc}(n,m) = \text{Inc}(m-1, m) \circ \text{Inc}(n, m-1)$$ Where the circle denotes composition of maps.
One direction was of course easy, namely composition of two increasing functions is again increasing. If $fg \in \text{Inc}(m-1, m) \circ \text{Inc}(n, m-1)$, for $f \in \text{Inc}(m-1, m)$ and $g \in \text{Inc}(n, m-1)$. First $g$ maps the set $\{1, \dots, n\}$ to the set $\{1, \dots, m-1\}$, for $n<m$. Then $f$ maps from the set $\{1, \dots, m-1\}$ to the set $\{1, \dots, m\}$. We see that the domain and range are as desired. We also see both functions are increasing therefore their composition is as well. We then have that $fg \in \text{Inc}(n,m) $.
I was having trouble breaking an increasing function up into two maps, the other way around. So given $h \in \text{Inc}(n,m) $, find some decomposition $h= s \circ t$ such that each map lies in the respective set. $$t: \{1, \dots, n\} \to \{ 1, \dots , m-1\}.$$ $$s: \{ 1, \dots , m-1\} \to\{ 1, \dots , m\}.$$ I was think about letting the first one just be $h$ piecewise until a certain point and then let the second one be linear up to where that one stops, something like:
$$t(i):= \begin{cases} h(i) & \text{ if } i \leq n-1 \\ \dots & \text{ if } i=n \end{cases}. $$ $$s(i):= \begin{cases} i & \text{ if } i < t(n) \\ h(i) & \text{ if } i \geq t(n) \end{cases}.$$
This does not quite work out as $h(i)$ might not be defined for some values and I cannot find a good spot to connect the two, any suggestions?
Let $j\in \{1, \dots, n \}$ such that $h(j) >j$. If such a $j$ does not exist, we know that $h$ must be the natural embedding and this means that $\forall i \in \{ 1, \dots, n\}$ we have $h(i)=i$. In this case we may decompose $h=s\circ t$ where: $$t(i)=i \quad \forall i \in \{ 1, \dots, n\}$$ $$s(i)=i, \quad \forall i \in \{ 1, \dots, m-1\}.$$ Clearly these functions are increasing and their composition gives $h$ hence $h \in \text{Inc}(m-1, m) \circ \text{Inc}(n, m-1)$.
Suppose now such a smallest $j$ exists such that $h(j)>j$. Since this is the smallest $j$ we also know that before this index occurs we must have $h(i)=i$, as $h$ is an increasing function. We define $t: \{1, \dots, n\} \to \{ 1, \dots , m-1\}$ as follows: $$t(i):= \begin{cases} h(i) & \text{ if } i <j \\ h(i)-1 & \text{ if } i \geq j \end{cases} .$$ Next we define $s: \{1, \dots, m-1\} \to \{ 1, \dots , m\}$ $$s(i):= \begin{cases} i & \text{ if } i < k(n) \\ i+1 & \text{ if } i \geq k(n) \end{cases} .$$ Again we claim that $h= s\circ t$. Observe if $i < j$ we have : $s(t(i)) = s(i) = i = h(i)$ if $i \geq j: s(t(i)) = s(t(i)) = s(h(i)-1) = h(i) - 1 + 1=h(i)$ since $h(i)-1 \geq h(j)-1.$ One can now argue that $s$ and $t$ are both increasing functions.