Definition:Iterated Binary Operation over Finite Set

From ProofWiki
Jump to navigation Jump to search


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}$

Commutative Monoid

Let $G$ be a commutative monoid.

Let $S$ be a non-empty set.

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

Also known as

The iterated binary operation over a finite set can be referred to as the summation over a finite set.

Also see

Special cases