Definition:Iterated Binary Operation

From ProofWiki
Jump to navigation Jump to search

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.


Also see