HOME

TheInfoList



OR:

In mathematics, an iterated binary operation is an extension of a
binary operation In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary op ...
on a set ''S'' to a function on finite
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
s of elements of ''S'' through repeated application. Common examples include the extension of the
addition Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or '' sum'' of ...
operation to the
summation In mathematics, summation is the addition of a sequence of any kind of numbers, called ''addends'' or ''summands''; the result is their ''sum'' or ''total''. Beside numbers, other types of values can be summed as well: functions, vectors, mat ...
operation, and the extension of the
multiplication Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being addi ...
operation to the
product Product may refer to: Business * Product (business), an item that serves as a solution to a specific consumer problem. * Product (project management), a deliverable or set of deliverables that contribute to a business solution Mathematics * Produ ...
operation. Other operations, e.g., the set-theoretic operations
union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''U ...
and
intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...
, are also often
iterated Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
, 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 :\sum,\ \prod,\ \bigcup, and \bigcap, respectively. More generally, iteration of a binary function is generally denoted by a slash: iteration of f over the sequence (a_, a_ \ldots, a_) is denoted by f / (a_, a_ \ldots, a_), following the notation for
reduce Reduction, reduced, or reduce may refer to: Science and technology Chemistry * Reduction (chemistry), part of a reduction-oxidation (redox) reaction in which atoms have their oxidation state changed. ** Organic redox reaction, a redox reacti ...
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 In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
, and whether the operator has
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures ...
s.


Definition

Denote by a''j'',''k'', with and , the finite sequence of length of elements of ''S'', with members (''a''i), for . Note that if , the sequence is empty. For , define a new function ''F''''l'' on finite nonempty sequences of elements of ''S'', where F_l(\mathbf_)= \begin a_0, &k=1\\ f(F_l(\mathbf_), a_), &k>1. \end Similarly, define F_r(\mathbf_) = \begin a_0, &k=1\\ f(a_0, F_r(\mathbf_)), &k>1. \end 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 In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids a ...
). If ''f'' is commutative and associative, then ''F'' can operate on any non-empty finite
multiset In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that ...
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 set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. ...
s. If ''S'' also is equipped with a
metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathema ...
or more generally with
topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing h ...
that is Hausdorff, so that the concept of a
limit of a sequence As the positive integer n becomes larger and larger, the value n\cdot \sin\left(\tfrac1\right) becomes arbitrarily close to 1. We say that "the limit of the sequence n\cdot \sin\left(\tfrac1\right) equals 1." In mathematics, the limi ...
is defined in ''S'', then an ''
infinite Infinite may refer to: Mathematics *Infinite set, a set that is not a finite set *Infinity, an abstract concept describing something without any limit Music * Infinite (group), a South Korean boy band *''Infinite'' (EP), debut EP of American m ...
iteration'' on a countable sequence in ''S'' is defined exactly when the corresponding sequence of finite iterations converges. Thus, e.g., if ''a''0, ''a''1, ''a''2, ''a''3, … is an infinite sequence of
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every r ...
s, then the
infinite product In mathematics, for a sequence of complex numbers ''a''1, ''a''2, ''a''3, ... the infinite product : \prod_^ a_n = a_1 a_2 a_3 \cdots is defined to be the limit of the partial products ''a''1''a''2...''a'n'' as ''n'' increases without bound ...
 \prod_^\infty a_i is defined, and equal to \lim\limits_\prod_^na_i, if and only if that limit exists.


Non-associative binary operation

The general, non-associative binary operation is given by a
magma Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma is found beneath the surface of the Earth, and evidence of magmatism has also been discovered on other terrestrial planets and some natural s ...
. The act of iterating on a non-associative binary operation may be represented as a
binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary tr ...
.


Notation

Iterated binary operations are used to represent an operation that will be repeated over a set subject to some constraints. Typically the lower bound of a restriction is written under the symbol, and the upper bound over the symbol, though they may also be written as superscripts and subscripts in compact notation. Interpolation is performed over positive
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
s from the lower to upper bound, to produce the set which will be substituted into the index (below denoted as ''i'') for the repeated operations. Common notations include the big Sigma ( repeated sum) and big Pi ( repeated product) notations. \sum_^ i = 0+1+2+ \dots + (n-1) \prod_^ i = 0 \times 1 \times 2 \times \dots \times (n-1) It is possible to specify set membership or other logical constraints in place of explicit indices, in order to implicitly specify which elements of a set shall be used: \sum_ x = x_1 + x_2 + x_3 + \dots + x_n Multiple conditions may be written either joined with a
logical and In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents this ...
or separately: \sum_ i = \sum_ i = 0 + 2 + 4 + \dots + n Less commonly, any
binary operator In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary o ...
such as
exclusive or Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , , ...
or
set union In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection. It is one of the fundamental operations through which sets can be combined and related to each other. A refers to a union of ze ...
may also be used. For example, if ''S'' is a set of logical
proposition In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, " meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the no ...
s: \bigwedge_{p \in S} p = p_1 \wedge p_2 \wedge \dots \wedge p_N which is true
iff In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicond ...
all of the elements of ''S'' are true.


See also

*
Continued fraction In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
*
Fold (higher-order function) In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the resu ...
*
Infinite product In mathematics, for a sequence of complex numbers ''a''1, ''a''2, ''a''3, ... the infinite product : \prod_^ a_n = a_1 a_2 a_3 \cdots is defined to be the limit of the partial products ''a''1''a''2...''a'n'' as ''n'' increases without bound ...
*
Infinite series In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, mat ...


References


External links


Bulk action




Binary operations