Proof of Iterated Operations: Recursion, Splitting, Reordering, Termwise Combination and Homomorphisms

For a map $a$ from a set containing $[p]$ to $X$, $\mathop{\ast}\limits_{k=1}^{p}a_{k}$ is the iterated operation of $a|_{[p]}$ by Iterated Operations: Finite Sums and Finite Products §restriction; this is how the induction hypotheses below are applied to restrictions. Each induction runs over the set of those $n\in\mathbb{N}$ (or $m\in\mathbb{N}$) for which the claim in question holds for all data of the stated kind, and concludes by Arithmetic and Order of the Natural Numbers §induction.

Recursion. Let $p\in\mathbb{N}$, let $a:[p]\to X$, and let $s:[p]\to X$ be the map of Iterating a Binary Operation along a Finite List §existence for $a$, so that $\mathop{\ast}\limits_{k=1}^{p}a_{k}=s(p)$ by Iterated Operations: Finite Sums and Finite Products §iterated. Let $q\in[p]$. Then $[q]\subseteq[p]$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §inclusion, and $s|_{[q]}$ satisfies $s(1)=a_{1}$ and $s(k+1)=s(k)\ast a_{k+1}$ for every $k\in[q]$ with $k<q$, since such $k$ satisfy $k<p$. By the uniqueness in Iterating a Binary Operation along a Finite List §existence for $a|_{[q]}$, $s|_{[q]}$ is the map for $a|_{[q]}$, so $\mathop{\ast}\limits_{k=1}^{q}a_{k}=s(q)$. Taking $p=n$ and $q=1$, which lies in $[n]$ since $1\le n$, gives $\mathop{\ast}\limits_{k=1}^{1}a_{k}=s(1)=a_{1}$ for every $a:[n]\to X$. Taking $p=n+1$ and $q=n$, which lies in $[n+1]$ since $n<n+1$, gives for every $a:[n+1]\to X$

$$\mathop{\ast}\limits_{k=1}^{n+1}a_{k}=s(n+1)=s(n)\ast a_{n+1}=\Big(\mathop{\ast}\limits_{k=1}^{n}a_{k}\Big)\ast a_{n+1}.$$

Homomorphism. We induct on $n$. For $n=1$ both sides equal $\varphi(a_{1})$. If the claim holds for $n$ and $a:[n+1]\to X$, then by the recursion clause, the hypothesis on $\varphi$ and the induction hypothesis for $a|_{[n]}$,

$$\varphi\Big(\mathop{\ast}\limits_{k=1}^{n+1}a_{k}\Big)=\varphi\Big(\mathop{\ast}\limits_{k=1}^{n}a_{k}\Big)\diamond\varphi(a_{n+1})=\Big(\mathop{\diamond}\limits_{k=1}^{n}\varphi(a_{k})\Big)\diamond\varphi(a_{n+1})=\mathop{\diamond}\limits_{k=1}^{n+1}\varphi(a_{k}).$$

Splitting. Fix $n$ and induct on $m$; for $a:[n+m]\to X$ and $j\in[m]$ we have $n+j\in[n+m]$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §shift and Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §split. For $m=1$, the recursion clause gives $\mathop{\ast}\limits_{j=1}^{1}a_{n+j}=a_{n+1}$ and $\mathop{\ast}\limits_{k=1}^{n+1}a_{k}=\Big(\mathop{\ast}\limits_{k=1}^{n}a_{k}\Big)\ast a_{n+1}$. If the claim holds for $m$ and $a:[n+m+1]\to X$, write $P=\mathop{\ast}\limits_{k=1}^{n}a_{k}$ and $Q=\mathop{\ast}\limits_{j=1}^{m}a_{n+j}$. By the recursion clause, the induction hypothesis for $a|_{[n+m]}$, associativity, and the recursion clause for the map $j\mapsto a_{n+j}$ on $[m+1]$,

$$\mathop{\ast}\limits_{k=1}^{n+m+1}a_{k}=\Big(\mathop{\ast}\limits_{k=1}^{n+m}a_{k}\Big)\ast a_{n+m+1}=(P\ast Q)\ast a_{n+m+1}=P\ast(Q\ast a_{n+m+1})=P\ast\Big(\mathop{\ast}\limits_{j=1}^{m+1}a_{n+j}\Big).$$

Moving one term to the end. Let $\ast$ be associative and commutative. For $c:[n+1]\to X$ and $j\in[n+1]$ let $c^{(j)}:[n]\to X$ be given by $c^{(j)}_{k}=c_{k}$ for $k<j$ and $c^{(j)}_{k}=c_{k+1}$ for $k\ge j$. We show by induction on $n$ that

$$\mathop{\ast}\limits_{k=1}^{n+1}c_{k}=\Big(\mathop{\ast}\limits_{k=1}^{n}c^{(j)}_{k}\Big)\ast c_{j}.\qquad(\dagger)$$

If $j=n+1$, then $c^{(j)}=c|_{[n]}$ and $(\dagger)$ is the recursion clause; this covers $j=2$ when $n=1$. For $n=1$ and $j=1$, $c^{(1)}_{1}=c_{2}$ and $c_{1}\ast c_{2}=c_{2}\ast c_{1}$ by commutativity. Suppose $(\dagger)$ holds for $n$, and let $c:[n+2]\to X$ and $j\in[n+1]$ (the case $j=n+2$ being done). Put $d=c|_{[n+1]}$. Then $c^{(j)}|_{[n]}=d^{(j)}$ and $c^{(j)}_{n+1}=c_{n+2}$, because $n+1\ge j$. Writing $D=\mathop{\ast}\limits_{k=1}^{n}d^{(j)}_{k}$, the recursion clause, the induction hypothesis for $d$ (note $d_{j}=c_{j}$), then associativity and commutativity, then associativity again, and finally the recursion clause for $c^{(j)}$ on $[n+1]$ give

$$\mathop{\ast}\limits_{k=1}^{n+2}c_{k}=\Big(\mathop{\ast}\limits_{k=1}^{n+1}c_{k}\Big)\ast c_{n+2}=(D\ast c_{j})\ast c_{n+2}=D\ast(c_{n+2}\ast c_{j})=(D\ast c_{n+2})\ast c_{j}=\Big(\mathop{\ast}\limits_{k=1}^{n+1}c^{(j)}_{k}\Big)\ast c_{j}.$$

Reordering. We induct on $n$. For $n=1$, $[1]=\{1\}$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §segment, so $\sigma(1)=1$. Suppose the claim holds for $n$, and let $a:[n+1]\to X$, $\sigma:[n+1]\to[n+1]$ be a bijection, and $j=\sigma^{-1}(n+1)$. Let $\rho:[n]\to[n+1]$ be given by $\rho(k)=k$ for $k<j$ and $\rho(k)=k+1$ for $k\ge j$. Then $\rho$ is injective: it is clearly injective on $\{k\in[n]:k<j\}$ and on $\{k\in[n]:k\ge j\}$, and $\rho(k)<j<\rho(l)$ whenever $k<j\le l$. Its image is $[n+1]\setminus\{j\}$: $j$ is not a value, and every $i\in[n+1]$ with $i\ne j$ is a value, since $i=\rho(i)$ if $i<j$, while if $i>j$ then $i\neq1$, so $i=l+1$ for some $l\in\mathbb{N}$ by Arithmetic and Order of the Natural Numbers §predecessor, with $j\le l\le n$ and $i=\rho(l)$. Since $\sigma$ maps $[n+1]\setminus\{j\}$ bijectively onto $[n+1]\setminus\{n+1\}=[n]$ (by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §successor), $\tau=\sigma\circ\rho$ is a bijection $[n]\to[n]$. For $b=a\circ\sigma$, i.e. $b_{k}=a_{\sigma(k)}$, we have $b^{(j)}_{k}=a_{\tau(k)}$ for $k\in[n]$ and $b_{j}=a_{n+1}$. By $(\dagger)$, the induction hypothesis for $a|_{[n]}$ and $\tau$, and the recursion clause,

$$\mathop{\ast}\limits_{k=1}^{n+1}a_{\sigma(k)}=\Big(\mathop{\ast}\limits_{k=1}^{n}a_{\tau(k)}\Big)\ast a_{n+1}=\Big(\mathop{\ast}\limits_{k=1}^{n}a_{k}\Big)\ast a_{n+1}=\mathop{\ast}\limits_{k=1}^{n+1}a_{k}.$$

Termwise. We induct on $n$. For $n=1$ both sides equal $a_{1}\ast b_{1}$. If the claim holds for $n$ and $a,b:[n+1]\to X$, write $A=\mathop{\ast}\limits_{k=1}^{n}a_{k}$ and $B=\mathop{\ast}\limits_{k=1}^{n}b_{k}$. By the recursion clause and the induction hypothesis the left side for $n+1$ is $(A\ast B)\ast(a_{n+1}\ast b_{n+1})$. By associativity and commutativity this equals

$$A\ast\big((B\ast a_{n+1})\ast b_{n+1}\big)=A\ast\big((a_{n+1}\ast B)\ast b_{n+1}\big)=A\ast\big(a_{n+1}\ast(B\ast b_{n+1})\big)=(A\ast a_{n+1})\ast(B\ast b_{n+1}),$$

which is the right side for $n+1$ by the recursion clause.