# Definition:Iterated Binary Operation

## Contents

## Indexed Iteration

Let $\left({G, *}\right)$ be a magma.

Let $a, b \in \Z$ be integers.

Let $\left[{a \,.\,.\, b}\right]$ be the integer interval between $a$ and $b$.

Let $f : \left[{a \,.\,.\, b}\right] \to G$ be a mapping.

### Nondegenerate case

Let $a\leq b$

The **indexed iteration of $*$ of $f$ from $a$ to $b$** is recursively defined and denoted:

- $\displaystyle \prod_{k \mathop = a}^b f(k) = \begin{cases} f(a) & : b = a \\ \left( \displaystyle \prod_{k \mathop = a}^{b-1} f(k) \right) * f(b) & : b > a\end{cases}$

For each ordered $n$-tuple $\left({a_1, a_2, \ldots, a_n}\right) \in S^n$, the **composite** of $\left({a_1, a_2, \ldots, a_n}\right)$ for $\oplus$ is the value at $\left({a_1, a_2, \ldots, a_n}\right)$ of the $n$-ary operation defined by $\oplus$.

This **composite** is recursively defined and denoted:

\(\displaystyle \displaystyle \bigoplus_{k \mathop = 1}^n a_k\) | \(=\) | \(\displaystyle \oplus_n \left({a_1, a_2, \ldots, a_n}\right)\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \begin{cases} a & : n = 1 \\ \oplus_m \left({a_1, \ldots, a_m}\right) \oplus a_{m+1} & : n = m + 1 \end{cases}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \left({\left({\cdots \left({\left({a_1 \oplus a_2}\right) \oplus a_3}\right) \oplus \cdots}\right) \oplus a_{n-1} }\right) \oplus a_n\) |

### Degenerate case

Let $(G, *)$ be a unitary magma with identity $e$.

Let $a,b \in \Z$ be integers with $a<b$.

Then $\displaystyle\prod_{i=a}^b f(i) = e$.

## Induced n-ary Operation

Let $(G, \oplus)$ be a magma.

Let $n\geq 1$ be a natural number.

Let $G^n$ be the $n$th cartesian power of $G$.

The **$n$-ary operation induced by $\oplus$** is the $n$-ary operation $\oplus_n : G^n \to G$ defined as:

- $\oplus_n (f) = \displaystyle \bigoplus_{i \mathop = 1}^n f(i)$

where $\bigoplus$ denotes indexed iteration of $f$ from $1$ to $n$.

### Induced nullary operation

Let $(G, \oplus)$ be a unital magma with identity $e$.

The **$0$-ary operation induced by $\oplus$** is the nullary operation equal to the element $e$.

## Iteration over Finite Set

Let $\left({G, *}\right)$ be a commutative semigroup.

Let $S$ be a finite non-empty set.

Let $f: S \to G$ be a mapping.

Let $n \in \N$ be the cardinality of $S$.

Let $g: \N_{< n} \to S$ be a bijection, where $\N_{< n}$ is an initial segment of the natural numbers.

The **iteration of $*$ of $f$ over $S$**, denoted $\displaystyle \prod_{s \mathop \in S} f \left({s}\right)$, is the indexed iteration of $*$ of the composition $f \circ g$ over $\N_{< n}$:

- $\displaystyle \prod_{s \mathop \in S} f \left({s}\right) = \displaystyle \prod_{i \mathop = 0}^{n - 1} f \left({g \left({i}\right)}\right)$

### Commutative Monoid

Let $G$ be a commutative monoid.

Let $S$ be a non-empty set.

Let $f : S \to G$ be a mapping

## Iteration over Set with Finite Support

Let $(G, *)$ be a commutative monoid.

Let $S$ be a set.

Let $f : S \to G$ be a mapping.

Let the support $\operatorname{Supp}f$ be finite.

The **iteration of $*$ of $f$ over $S$**, denoted $\displaystyle\prod_{s\mathop\in S} f(s)$, is the iteration over the finite set $\operatorname{Supp} f$ of $f$:

- $\displaystyle\prod_{s\mathop\in S} f(s) = \displaystyle\prod_{s \mathop\in \operatorname{Supp}f} f(s)$

## Also denoted as

Depending on the notation that is used for the binary operation, alternative notations for the **iterated operation** are often seen:

- $+$ becomes $\sum$
- $\cap$ becomes $\bigcap$
- $*$ and $\cdot$ may become $\prod$
- $\oplus$ becomes $\bigoplus$

and so on.

## Note

Let $n\in\N$ be a natural number.

Note that an ordered $n$-tuple of elements of $G$ is by definition a mapping from the integer interval $\left[{1 \,.\,.\, n}\right]$ to $G$.

Thus the definition of indexed iterated binary operation includes the case of an ordered $n$-tuple.