HOME

TheInfoList




In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, an iterated binary operation is an extension of a
binary operation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
on a set ''S'' to a
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
on finite
sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

sequence
s of elements of ''S'' through repeated application. Common examples include the extension of the
addition Addition (usually signified by the plus symbol The plus and minus signs, and , are mathematical symbol A mathematical symbol is a figure or a combination of figures that is used to represent a mathematical object A mathematical object is an ...

addition
operation to the
summation In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

summation
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 arithmetic, elementary Operation (mathematics), mathematical operations ...

multiplication
operation to the product operation. Other operations, e.g., the set theoretic operations union and
intersection The line (purple) in two points (red). The disk (yellow) intersects the line in the line segment between the two red points. In mathematics, the intersection of two or more objects is another, usually "smaller" object. Intuitively, the inter ...
, 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 :\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 Reduce is a general-purpose computer algebra system geared towards applications in physics. The development of the Reduce computer algebra system was started in the 1960s by Anthony C. Hearn. Since then, many scientists from all over the world have ...
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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
, and whether the operator has
identity element In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...
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 In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathemati ...
). If ''f'' is
commutative In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
and associative, then ''F'' can operate on any non-empty finite
multiset In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
s. If ''S'' also is equipped with a
metric METRIC (Mapping EvapoTranspiration at high Resolution with Internalized Calibration) is a computer model Computer simulation is the process of mathematical modelling, performed on a computer, which is designed to predict the behaviour of or th ...
or more generally with
topology In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities ...

topology
that is
Hausdorff
Hausdorff
, so that the concept of a
limit of a sequence As the positive integer An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. ...
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 (band), a South Korean boy band *''Infinite'' (EP), debut EP of American musi ...

infinite
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 Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s, then the
infinite product In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no genera ...
 \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 rock Igneous rock (derived from the Latin word ''ignis'' meaning fire), or magmatic rock, is one of the three main The three types of rocks, rock types, the others ...
. The act of iterating on a non-associative binary operation may be represented as a
binary tree In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...

binary tree
.


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 (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
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. 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. Common notations include the big Sigma (
repeated sum
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) Though binary operators including but not limited to
exclusive or Exclusive or or exclusive disjunction is a Logical connective, logical operation that is true if and only if its arguments differ (one is true, the other is false). It is Table of logic symbols, symbolized by the prefix operator J and by the ...
and
set union In set theory Set theory is the branch of that studies , which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of , is mostly concerned with those that ...

set union
may be used. Let ''S'' be a set of sets \bigcup_ s_i= s_1 \cup s_2 \cup \dots \cup s_N. Let ''S'' be a set of logical
proposition In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, lab ...
s \bigoplus_ s_i= s_1 \oplus s_2 \oplus \dots \oplus s_N. Let ''S'' be a set of
multivector In multilinear algebra, a multivector, sometimes called Clifford number, is an element of the exterior algebra of a vector space . This algebra is graded algebra, graded, associative algebra, associative and alternating algebra, alternating, and ...
s in a
Clifford algebra In mathematics, a Clifford algebra is an algebra over a field, algebra generated by a vector space with a quadratic form, and is a Unital algebra, unital associative algebra. As algebra over a field, ''K''-algebras, they generalize the real nu ...
/
geometric algebra In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
\bigwedge_ s_i= s_1 \wedge s_2 \wedge \dots \wedge s_N, \prod_ s_i= s_1 s_2 \dots s_N. Note how in the above, no upper bound is used, because it suffices to express that the elements s_i are elements of the set ''S''. It is also to produce a repeated operation given a number of constraint joined by a
conjunction (and)
conjunction (and)
, for example: \sum_ i = 0 + 2 + 4 + \dots + n, which may also be denoted \sum_{\stackrel{i \in 2\N}{i \leq n i = 0 + 2 + 4 + \dots + n.


See also

*
Continued fraction In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
*
Fold (higher-order function)In functional programming In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), f ...
*
Infinite product In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no genera ...
*
Infinite series In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...


References


External links


Bulk action




Binary operations