Iterated binary operation

From Quire, the open reference·Repeated application of an operation to a sequence·3 min read

In mathematics, an iterated binary operation is an extension of a binary operation on a set S to a function on finite sequences of elements of S through repeated application.^[1] Common examples include the extension of the addition operation to the summation operation, and the extension of the multiplication operation to the product operation. Other operations, e.g., the set-theoretic operations union and intersection, are also often iterated, but the iterations are not given separate names. In print, summation and product are represented by special symbols; but other iterated operators often are denoted by larger variants of the symbol for the ordinary binary operator. Thus, the iterations of the four operations mentioned above are denoted

${\displaystyle \sum ,\ \prod ,\ \bigcup ,}$ and ${\displaystyle \bigcap }$ , respectively.

More generally, iteration of a binary function is generally denoted by a slash: iteration of ${\displaystyle f}$ over the sequence ${\displaystyle (a_{1},a_{2}\ldots ,a_{n})}$ is denoted by ${\displaystyle f/(a_{1},a_{2}\ldots ,a_{n})}$ , following the notation for reduce in Bird–Meertens formalism.

In general, there is more than one way to extend a binary operation to operate on finite sequences, depending on whether the operator is associative, and whether the operator has identity elements.

Definition#edit

Denote by a_j,k, with j ≥ 0 and k ≥ j, the finite sequence of length k − j of elements of S, with members (a_i), for j ≤ i < k. Note that if k = j, the sequence is empty.

For f : S × S → S, define a new function F_l on finite nonempty sequences of elements of S, where ${\displaystyle F_{l}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(F_{l}(\mathbf {a} _{0,k-1}),a_{k-1}),&k>1.\end{cases$

Similarly, define ${\displaystyle F_{r}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(a_{0},F_{r}(\mathbf {a} _{1,k})),&k>1.\end{cases$

If f has a unique left identity e, the definition of F_l can be modified to operate on empty sequences by defining the value of F_l on an empty sequence to be e (the previous base case on sequences of length 1 becomes redundant). Similarly, F_r can be modified to operate on empty sequences if f has a unique right identity.

If f is associative, then F_l equals F_r, and we can simply write F. Moreover, if an identity element e exists, then it is unique (see Monoid).

If f is commutative and associative, then F can operate on any non-empty finite multiset by applying it to an arbitrary enumeration of the multiset. If f moreover has an identity element e, then this is defined to be the value of F on an empty multiset. If f is idempotent, then the above definitions can be extended to finite sets.

If S also is equipped with a metric or more generally with topology that is Hausdorff, so that the concept of a limit of a sequence is defined in S, then an infinite iteration on a countable sequence in S is defined exactly when the corresponding sequence of finite iterations converges. Thus, e.g., if a₀, a₁, a₂, a₃, … is an infinite sequence of real numbers, then the infinite product ${\textstyle \prod _{i=0}^{\infty }a_{i$ is defined, and equal to ${\textstyle \lim \limits _{n\to \infty }\prod _{i=0}^{n}a_{i},}$ if and only if that limit exists.

Non-associative binary operation#edit

The general, non-associative binary operation is given by a magma. The act of iterating on a non-associative binary operation may be represented as a binary tree.

Basic iterated operations#edit

Iterated operations
Area of mathematics	Sum				Product
Area of mathematics	Name	Operation	Definition	Symbol	Name	Operation	Definition	Symbol
Arithmetic	Summation	Addition	Sum of numbers	${\displaystyle \sum }$	Iterated product	Multiplication	Product of numbers	${\displaystyle \prod }$
Set theory	Union of a sequence of sets	Set union	All elements of sets	${\displaystyle \bigcup }$	Intersection of a sequence of sets	Set intersection	Common elements	${\displaystyle \bigcap }$
Logic	Existential quantifier	Disjunction	Disjunction of statements	${\displaystyle \bigvee }$	Universal quantifier	Conjunction	Conjunction of statements	${\displaystyle \bigwedge }$
Divisibility theory	Least common multiple	Least common multiple	The smallest number that is a multiple of all the terms	${\displaystyle \operatorname {lcm} }$	Greatest common divisor	Greatest common divisor	The greatest number that is a divisor of all the terms	${\displaystyle \gcd }$
Category theory	Coproduct	Disjoint union	Coproduct of objects	${\displaystyle \coprod }$	Product	Cartesian product	Product of objects	${\displaystyle \prod }$

Notation#edit

The iterated binary operation is written as:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k$

Meaning of symbols:

Symbol	Meaning
${\displaystyle \bigstar }$	Iterated binary operation symbol
${\displaystyle k}$	Index variable
${\displaystyle k=1}$	Lower bound
${\displaystyle k=n}$ or ${\displaystyle n}$	Upper bound
${\displaystyle a_{k$	k-th element

Example:

${\displaystyle \mathop {\bigstar } _{k=1}^{4}a_{k}=\mathop {\bigstar } _{k=1}^{k=4}a_{k}=a_{1}\star a_{2}\star a_{3}\star a_{4$

General form:

${\displaystyle \mathop {\bigstar } _{k\in K}a_{k$

Restricted form:

${\displaystyle \mathop {\bigstar } _{1\leq k\leq n \atop k\equiv 0{\pmod {2a_{k$

Infinite version:

${\displaystyle \mathop {\bigstar } _{k=1}^{\infty }a_{k}=\mathop {\bigstar } _{k=1}^{k\to \infty }a_{k$

Properties#edit

Let ${\displaystyle (S,\star )}$ be a structure with associative operation ${\displaystyle \star }$ :

Single element:

${\displaystyle \mathop {\bigstar } _{k=n}^{n}a_{k}=a_{n$

Expansion:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=a_{1}\star a_{2}\star \dots \star a_{n$

Recursion:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=\left(\mathop {\bigstar } _{k=1}^{n-1}a_{k}\right)\star a_{n$

Right recursion:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=a_{1}\star \left(\mathop {\bigstar } _{k=2}^{n}a_{k}\right)}$

Splitting:

${\displaystyle \left(\mathop {\bigstar } _{k=1}^{m}a_{k}\right)\star \left(\mathop {\bigstar } _{k=m+1}^{n}a_{k}\right)=\mathop {\bigstar } _{k=1}^{n}a_{k$

Permutation invariance:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=\mathop {\bigstar } _{k=1}^{n}a_{\sigma (k)$

Empty product (monoid):

${\displaystyle \mathop {\bigstar } _{k=1}^{0}a_{k}=e}$

Idempotence:

if ${\displaystyle a\star a=a}$ , then ${\displaystyle \mathop {\bigstar } _{k=1}^{n}a=a}$

Constant sequence:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a=a\star \cdots \star a}$

Identity element and empty set#edit

If ${\displaystyle (S,\star ,e)}$ is a monoid, then:

Empty product = identity element
Empty sum = 0 (in arithmetic monoids)

Computer science#edit

In functional programming, iterated binary operations correspond to higher-order functions such as fold or reduce.

References#edit

^ Saunders MacLane (1971). Categories for the Working Mathematician. New York: Springer-Verlag. p. 142. ISBN 0387900357.

External links#edit

Bulk action
Parallel prefix operation Archived 2013-06-03 at the Wayback Machine
Nuprl iterated binary operations Archived 2016-03-03 at the Wayback Machine

Categories Binary operations

This article is mirrored from “Iterated binary operation” on English Wikipedia, revision 1370193624, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1370193624 · just now