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

Each result cited below is universally quantified over the data in its own statement, and is applied to the data named where it is cited.

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 induction from $1$ on $\mathbb{N}$, The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §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})$, by the recursion clause for $\ast$ on $X$ and for $\diamond$ on $Y$. If the claim holds for $n$ and $a:[n+1]\to X$, then by the recursion clause, applied to $\ast$ on $X$ and, in the last step, to $\diamond$ on $Y$, 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 (here $1\le n+1$, and $j+n=n+j$). 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$, where $n+(m+1)=(n+m)+1$ by associativity of addition, written $n+m+1$, 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 the other $k\in[n]$, those with $k\ge j$ by totality of the order; this is a map by Maps Defined by Cases §cases with $P(k)$ the property $k<j$, both values lying in $X$ because $k\in[n]\subseteq[n+1]$ and $k+1\in[n+1]$ for $k\in[n]$, by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §inclusion, Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §segment and the compatibility of addition with the order (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §laws). 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 the other $k\in[n]$, those with $k\ge j$ by totality of the order, which is a well-order and hence a total order by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §order and Well-Orders on a Set §well-order (if $k\le j$ but not $k<j$, then $k=j$ by Arithmetic and Order of the Natural Numbers §partial-order); this is a map by Maps Defined by Cases §cases with $P(k)$ the property $k<j$, as $k\in[n+1]$ and $k+1\in[n+1]$ for every $k\in[n]$. 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)=k<j\le l<l+1=\rho(l)$ whenever $k<j\le l$, where $l<l+1$ by Arithmetic and Order of the Natural Numbers §successor, so $\rho(k)<\rho(l)$ by Arithmetic and Order of the Natural Numbers §partial-order. 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. If $i<j$, then $i<n+1$ by Arithmetic and Order of the Natural Numbers §partial-order, as $j\le n+1$; hence $i\le n$, since otherwise $n<i<n+1$ by Arithmetic and Order of the Natural Numbers §trichotomy, contradicting Arithmetic and Order of the Natural Numbers §successor; so $i\in[n]$ and $i=\rho(i)$. If $i>j$, then $i\neq1$, because $1\le j$ as $1$ is the least natural number by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §order, and $j<1\le j$ is impossible by Arithmetic and Order of the Natural Numbers §partial-order and Arithmetic and Order of the Natural Numbers §trichotomy; 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)$; here $j\le l$, since otherwise $l<j<l+1$ by trichotomy, contradicting Arithmetic and Order of the Natural Numbers §successor, and $l\le n$, since $l+1=i\le n+1$ and addition is compatible with the order by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §laws. 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.