Proof of Existence and Uniqueness of Iterates of a Binary Operation

Fix the set $X$ and the binary operation $\ast$. For $n\in\mathbb{N}$ let $P(n)$ be the assertion: for every map $a:[n]\to X$ there is exactly one map $\sigma:[n]\to X$ satisfying the two displayed conditions of the statement for that $n$. Let $A$ be the set of all $n\in\mathbb{N}$ for which $P(n)$ holds. We show $A=\mathbb{N}$ by Principle of Induction for the Natural Numbers.

We use throughout the following facts about initial segments and the order on $\mathbb{N}$: $1\in[n]$ for every $n$, $[1]=\{1\}$, and $[S(n)]=[n]\cup\{S(n)\}$ with $S(n)\notin[n]$, by claims 1, 2 and 3 of Basic Properties of Initial Segments of the Natural Numbers; and $m<S(m)$ together with the transitivity of the order, by claims 5 and 1 of Properties of the Order on the Natural Numbers. In particular, if $S(m)\in[n]$, that is $S(m)\le n$, then $m<S(m)\le n$ gives $m\le n$, so $m\in[n]$.

Base case. Let $a:[1]\to X$. Since $[1]=\{1\}$, a map $\sigma:[1]\to X$ is determined by the single value $\sigma(1)$, and the first condition says exactly that this value is $a_{1}$. The second condition is vacuous: if $S(m)\in[1]=\{1\}$ then $S(m)=1$, contradicting the requirement in the definition of the natural numbers that $1$ is not a successor. Hence there is exactly one such $\sigma$, and $1\in A$.

Induction step. Suppose $n\in A$, and let $a:[S(n)]\to X$ be given. Write $a'$ for the restriction of $a$ to $[n]$, which is defined because $[n]\subseteq[S(n)]$. By $P(n)$ there is exactly one map $\sigma':[n]\to X$ with $\sigma'(1)=a_{1}$ and $\sigma'(S(m))=\sigma'(m)\ast a_{S(m)}$ for every $m$ with $S(m)\in[n]$.

Existence. Since $[S(n)]=[n]\cup\{S(n)\}$ and $S(n)\notin[n]$, there is a well-defined map $\sigma:[S(n)]\to X$ given by

where $\sigma'(n)$ is defined because $n\in[n]$. As $1\in[n]$ we get $\sigma(1)=\sigma'(1)=a_{1}$. Now let $m\in\mathbb{N}$ with $S(m)\in[S(n)]$. Then either $S(m)\in[n]$ or $S(m)=S(n)$. In the first case $m\in[n]$ as noted above, so

In the second case $m=n$ by the injectivity of $S$, and

Thus $\sigma$ satisfies both conditions for $S(n)$.

Uniqueness. Let $\tau:[S(n)]\to X$ also satisfy both conditions for $S(n)$, and let $\tau'$ be its restriction to $[n]$. Then $\tau'(1)=\tau(1)=a_{1}$. If $m$ satisfies $S(m)\in[n]$, then also $S(m)\in[S(n)]$ and $m\in[n]$, so

Hence $\tau'$ satisfies the two conditions for $n$, and the uniqueness part of $P(n)$ gives $\tau'=\sigma'$. Finally $S(n)\in[S(n)]$ and

Since $[S(n)]=[n]\cup\{S(n)\}$, we conclude $\tau=\sigma$. Therefore $P(S(n))$ holds and $S(n)\in A$.

By the principle of induction, $A=\mathbb{N}$, which is the assertion of the lemma.