Definition:Iterated Binary Operation
Definition
Indexed Iteration
Let $\struct {G, *}$ be a magma.
Let $a, b \in \Z$ be integers.
Let $\closedint a b$ be the integer interval between $a$ and $b$.
Let $f: \closedint a b \to G$ be a mapping.
The indexed iteration of $*$ of $f$ from $a$ to $b$ is recursively defined and denoted:
- $\ds \prod_{k \mathop = a}^b \map f k = \begin {cases} \map f a & : b = a \\ \paren {\ds \prod_{k \mathop = a}^{b - 1} \map f k} * \map f b & : b > a \end {cases}$
For each ordered $n$-tuple $\tuple {a_1, a_2, \ldots, a_n} \in S^n$, the composite of $\tuple {a_1, a_2, \ldots, a_n}$ for $\oplus$ is the value at $\tuple {a_1, a_2, \ldots, a_n}$ of the $n$-ary operation defined by $\oplus$.
This composite is recursively defined and denoted:
| \(\ds \bigoplus_{k \mathop = 1}^n a_k\) | \(=\) | \(\ds \map {\oplus_n} {a_1, a_2, \ldots, a_n}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \begin {cases} a & : n = 1 \\ \map {\oplus_m} {a_1, \ldots, a_m} \oplus a_{m + 1} & : n = m + 1 \end {cases}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {\paren {\cdots \paren {\paren {a_1 \oplus a_2} \oplus a_3} \oplus \cdots} \oplus a_{n - 1} } \oplus a_n\) |
Iteration over Finite Set
Let $\struct {G, *}$ 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} \map f s$, is the indexed iteration of $*$ of the composition $f \circ g$ over $\N_{<n}$:
- $\displaystyle \prod_{s \mathop \in S} \map f s = \displaystyle \prod_{i \mathop = 0}^{n - 1} \map f {\map g i}$
Iteration over Set with Finite Support
Let $\struct {G, *}$ be a commutative monoid.
Let $S$ be a set.
Let $f: S \to G$ be a mapping.
Let the support $\map \supp f$ be finite.
The iteration of $*$ of $f$ over $S$, denoted $\ds \prod_{s \mathop \in S} \map f s$, is the iteration over the finite set $\map \supp f$ of $f$:
- $\ds \prod_{s \mathop \in S} \map f s = \prod_{s \mathop \in \map \supp f} \map 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
 | This page has been identified as a candidate for refactoring of medium complexity. Until this has been finished, please leave {{Refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code. |
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 $\closedint 1 n$ to $G$.
Thus the definition of indexed iterated binary operation includes the case of an ordered $n$-tuple.