Idempotence
Encyclopedia
Idempotence is the property of certain operations in mathematics
and computer science
, that they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of places in abstract algebra
(in particular, in the theory of projectors and closure operator
s) and functional programming
(in which it is connected to the property of referential transparency).
The term was introduced by Benjamin Peirce
in the context of elements of an algebra that remain invariant when raised to a positive integer power, and literally means "(the quality of having) the same power", from idem + potence (same + power).
There are several meanings of idempotence, depending on what the concept is applied to:
f, that is, a map from some set S into itself, is called idempotent if, for all x in S,
In particular, the identity function
idS, defined by , is idempotent, as is the constant function
Kc, where c is an element of S, defined by .
An important class of idempotent functions is given by projection
s in a vector space
. An example of a projection is the function πxy defined by , which projects an arbitrary point in 3D space to a point on the x–y-plane
, where the third coordinate (z) is equal to 0.
A unary operation is idempotent if it maps all elements of S to fixed point
s. For a set with n elements there are
idempotent functions, where
is the number of idempotent functions with exactly k fixed points. The integer sequence
of the number of idempotent functions as given by the sum above starts with 1, 1, 3, 10, 41, 196, 1057, 6322, 41393, ...
★ on a set S is called idempotent if, for all x in S,
For example, the operations of set union
and set intersection
are both idempotent, as are logical conjunction
and logical disjunction
, and, in general, the meet
and join operations of a lattice
.
An element x of S is called idempotent for ★ if, for that element,
In particular, an identity element
of ★ is idempotent for the operation.
function of a real
or complex
argument, and the floor function
of a real argument are idempotent.
The function that assigns to every subset U of some topological space
X the closure
of U is idempotent on the power set of X. It is an example of a closure operator
; all closure operators are idempotent functions.
The operation of subtracting the average of a list of numbers from every number in the list is idempotent. For example, consider the list . The average is 7. Subtracting 7 from every number in the list yields . The average of that list is 0. Subtracting 0 from every number in that list yields the same list.
and Kleene plus operators used to express repetition in formal languages
are idempotent.
is, by definition, an element which is idempotent with respect to the ring's multiplication. That is, r2 = r.
A short list of important notions defined with idempotents includes:
Any non-trivial idempotent a is a zero divisor
(because a(1 − a) = 0). This shows that integral domains and division ring
s don't have such idempotents. Local ring
s also don't have such idempotents, but for a different reason. The only idempotent contained in the Jacobson radical
of a ring is 0. There is a catenoid
of idempotents in the coquaternion
ring.
s. If M is an R module and E=EndR(M) is its ring of endomorphisms, then A⊕B=M if and only if there is a unique idempotent e in E such that A=e(M) and B=(1−e)(M). Clearly then, M is directly indecomposable if and only if 0 and 1 are the only idempotents in E.
In the case when M=R, End(R)=R, and so A⊕B=R as right modules if and only if there exists a unique idempotent e such that eR=A and (1−e)R=B. Thus every module direct summand of R is generated by an idempotent. The ring R can be written as e1R⊕e2R⊕...⊕enR with each ei a local idempotent if and only if R is a semiperfect ring
.
If a is a central idempotent, then the corner ring aRa=Ra is a ring with multiplicative identity a. Just as idempotents determine the direct decompositions of R as a module, the central idempotents of R determine the decompositions of R as a direct sum
of rings. If R is the direct sum of the rings R1,...,Rn, then the identity elements of the rings Ri are central idempotents in R, pairwise orthogonal, and their sum is 1. Conversely, given central idempotents a1,...,an in R which are pairwise orthogonal and have sum 1, then R is the direct sum of the rings Ra1, …, Ran. So in particular, every central idempotent a in R gives rise to a decomposition of R as a direct sum of the corner rings aRa and (1 − a)R(1 − a). As a result, a ring R is directly indecomposable as a ring if and only if the identity 1 is centrally primitive.
Working inductively, one can attempt to decompose 1 into a sum of centrally primitive elements. If 1 is centrally primitive, we are done. If not, it is a sum of central orthogonal idempotents, which in turn are primitive or sums of more central idempotents, and so on. The problem that may occur is that this may continue without end, producing an infinite family of central orthogonal idempotents. The condition "R does not contain infinite sets of central orthogonal idempotents" is a type of finiteness condition on the ring. It can be achieved in many ways, such as requiring the ring to be right Noetherian
. If a decomposition R=c1R⊕c2R⊕...⊕cnR exists with each ci a centrally primitive idempotent, then R is a direct sum of the corner rings ciRci, each of which is ring irreducible.
as an R module. Idempotents always lift modulo nil ideal
s and rings for which R/I is I-adically complete.
Lifting is most important when I=J(R), the Jacobson radical
of R. Yet another characterization of semiperfect rings is that they are semilocal rings whose idempotents lift modulo J(R).
ab = ba = a. With respect to this order, 0 is the smallest and 1 the largest idempotent. For orthogonal idempotents a and b, a + b is also idempotent, and we have a ≤ a + b and b ≤ a + b. The atoms of this partial order are precisely the primitive idempotents.
When the above partial order is restricted to the central idempotents of R, a lattice structure can be given. For two central idempotents e and f the complement ¬e=1−e and the join and meet
are given by
and
The ordering now becomes simply e≤f if and only if eR⊆fR, and the join and meet satisfy (e∨f)R=eR+fR and (e∧f)R=eR∩fR=(eR)(fR). It is shown in that if R is von Neumann regular and right self-injective, then the lattice is a complete lattice
.
is an involution.
If b is an involution, then
is an idempotent,
and these are inverse: thus if 2 is invertible in a ring, idempotents and involutions are equivalent.
Further, if b is an involution, then
and 
are orthogonal idempotents, corresponding to a and 
.
. By the Chinese Remainder Theorem
, this ring factors into the direct product of rings of integers mod p. Now each of these factors is a field, so it is clear that the only idempotents will be 0 and 1. That is, each factor has 2 idempotents. So if there are m factors, there will be 2m idempotents.
We can check this for the integers mod 6, R=Z/6Z. Since 6 has 2 factors (2 and 3) it should have 22 idempotents.
This also demonstrates the decomposition properties: because 3+4=1 (mod 6), there is a ring decomposition 3Z/6Z⊕4Z/6Z. In 3Z/6Z the identity is 3+6Z and in 4Z/6Z the identity is 4+6Z.
In linear algebra
, projection
s are idempotent. In fact, they are defined as idempotent linear maps. By choosing a basis
, any projection gives an idempotent matrix.
An idempotent semiring is a semiring whose addition (not multiplication) is idempotent.
, the term idempotent is used more comprehensively to describe an operation that will produce the same results if executed once or multiple times. This may have a different meaning depending on the context in which it is applied. In the case of method
s or subroutine
calls with side effects
, for instance, it means that the modified state remains the same after the first call. In functional programming
, though, an idempotent function is one that preserves the property f(f(x)) = f(x).
This is a very useful property in many situations, as it means that an operation can be repeated or retried as often as necessary without causing unintended effects. With non-idempotent operations, the algorithm may have to keep track of whether the operation was already performed or not.
Stronger is nullipotent, meaning that the results are the same if executed zero or multiple times, which is synonymous with "no side effects".
are typically idempotent (in fact nullipotent), since this will not cause the database to change. Similarly, changing a customer's address is typically idempotent, because the final address will be the same no matter how many times it is submitted. However, placing an order for a car for the customer is typically not idempotent, since running the method/call several times will lead to several orders being placed. Canceling an order is idempotent, because the order remains canceled no matter how many requests are made.
A composition of idempotent methods or subroutines, however, is not necessarily idempotent if a later method in the sequence changes a value that an earlier method depends on – idempotence is not closed under composition. For example, suppose the initial value of a variable is 3 and there is a sequence that reads the variable, then changes it to 5, and then reads it again. Each step in the sequence is idempotent: both steps reading the variable have no side effects and changing a variable to 5 will always have the same effect no matter how many times it is executed. Nonetheless, executing the entire sequence once produces the output (3, 5), but executing it a second time produces the output (5, 5), so the sequence is not idempotent.
In the HyperText Transfer Protocol (HTTP)
, idempotence and safety are the major attributes that separate HTTP verbs. Of the major HTTP verbs, GET, PUT, and DELETE are idempotent (if implemented according to the standard), but POST is not. These verbs represent very abstract operations in computer science: GET retrieves a resource; PUT stores content at a resource; and DELETE eliminates a resource. As in the example above, reading data usually has no side effects, so it is idempotent (in fact nullipotent). Storing a given set of content is usually idempotent, as the final value stored remains the same after each execution. And deleting something is generally idempotent, as the end result is always the absence of the thing deleted.
In Event Stream Processing
, idempotence refers to the ability of a system to produce the same outcome, even if an event or message is received more than once.
In a load-store architecture, instructions that might possibly cause a page fault
are idempotent. So if a page fault occurs, the OS can load the page from disk and then simply re-execute the faulted instruction.
In a processor where such instructions are not idempotent, dealing with page faults is much more complex.
The notion of idempotence at the end of a chain of operations was applied to so-called "desired-outcome" functions in the widely used configuration management software Cfengine
in 1993, changing the industry approach to datacenter automation by bringing "self-healing" by simple repetition with a predictable outcome.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, that they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of places in abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
(in particular, in the theory of projectors and closure operator
Closure operator
In mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....
s) and functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
(in which it is connected to the property of referential transparency).
The term was introduced by Benjamin Peirce
Benjamin Peirce
Benjamin Peirce was an American mathematician who taught at Harvard University for approximately 50 years. He made contributions to celestial mechanics, statistics, number theory, algebra, and the philosophy of mathematics....
in the context of elements of an algebra that remain invariant when raised to a positive integer power, and literally means "(the quality of having) the same power", from idem + potence (same + power).
There are several meanings of idempotence, depending on what the concept is applied to:
- A unary operationUnary operationIn mathematics, a unary operation is an operation with only one operand, i.e. a single input. Specifically, it is a functionf:\ A\to Awhere A is a set. In this case f is called a unary operation on A....
(or functionFunction (mathematics)In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
) is idempotent if, whenever it is applied twice to any value, it gives the same result as if it were applied once. For example, the absolute valueAbsolute valueIn mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...
: . - A binary operationBinary operationIn mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
is idempotent if, whenever it is applied to two equal values, it gives that value as the result. For example, the operation giving the maximum value of two values is idempotent: . - Given a binary operation, an idempotent element (or simply an idempotent) for the operation is a value for which the operation, when given that value for both of its operands, gives the value as the result. For example, the number 1 is an idempotent of multiplicationMultiplicationMultiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
: .
Unary operation
A unary operationUnary operation
In mathematics, a unary operation is an operation with only one operand, i.e. a single input. Specifically, it is a functionf:\ A\to Awhere A is a set. In this case f is called a unary operation on A....
f, that is, a map from some set S into itself, is called idempotent if, for all x in S,
- f(f(x)) = f(x).
In particular, the identity function
Identity function
In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...
idS, defined by , is idempotent, as is the constant function
Constant function
In mathematics, a constant function is a function whose values do not vary and thus are constant. For example the function f = 4 is constant since f maps any value to 4...
Kc, where c is an element of S, defined by .
An important class of idempotent functions is given by projection
Projection (linear algebra)
In linear algebra and functional analysis, a projection is a linear transformation P from a vector space to itself such that P2 = P. It leaves its image unchanged....
s in a vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
. An example of a projection is the function πxy defined by , which projects an arbitrary point in 3D space to a point on the x–y-plane
Plane (mathematics)
In mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...
, where the third coordinate (z) is equal to 0.
A unary operation is idempotent if it maps all elements of S to fixed point
Fixed point (mathematics)
In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...
s. For a set with n elements there are
idempotent functions, where
is the number of idempotent functions with exactly k fixed points. The integer sequence
Integer sequence
In mathematics, an integer sequence is a sequence of integers.An integer sequence may be specified explicitly by giving a formula for its nth term, or implicitly by giving a relationship between its terms...
of the number of idempotent functions as given by the sum above starts with 1, 1, 3, 10, 41, 196, 1057, 6322, 41393, ...
Binary operation
A binary operationBinary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
★ on a set S is called idempotent if, for all x in S,
- x ★ x = x.
For example, the operations of set union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
and set intersection
Intersection (set theory)
In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
are both idempotent, as are logical conjunction
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
and logical disjunction
Logical disjunction
In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
, and, in general, the meet
Meet (mathematics)
In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...
and join operations of a lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
.
An element x of S is called idempotent for ★ if, for that element,
- x ★ x = x.
In particular, an identity element
Identity element
In mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
of ★ is idempotent for the operation.
Connections
The connections between the three notions are as follows.- The statement that the binary operation ★ on a set S is idempotent, is equivalent to the statement that every element of S is idempotent for ★.
- The defining property of unary idempotence, for x in the domain of f, can equivalently be rewritten as , using the binary operation of function compositionFunction compositionIn mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
denoted by ∘. Thus, the statement that f is an idempotent unary operation on S is equivalent to the statement that f is an idempotent element for the operation ∘ on functions from S to S.
Functions
As mentioned above, the identity map and the constant maps are always idempotent maps. The absolute valueAbsolute value
In mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...
function of a real
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
or complex
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
argument, and the floor function
Floor function
In mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following integer, respectively...
of a real argument are idempotent.
The function that assigns to every subset U of some topological space
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
X the closure
Closure (topology)
In mathematics, the closure of a subset S in a topological space consists of all points in S plus the limit points of S. Intuitively, these are all the points that are "near" S. A point which is in the closure of S is a point of closure of S...
of U is idempotent on the power set of X. It is an example of a closure operator
Closure operator
In mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....
; all closure operators are idempotent functions.
The operation of subtracting the average of a list of numbers from every number in the list is idempotent. For example, consider the list . The average is 7. Subtracting 7 from every number in the list yields . The average of that list is 0. Subtracting 0 from every number in that list yields the same list.
Formal languages
The Kleene starKleene star
In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...
and Kleene plus operators used to express repetition in formal languages
Formal grammar
A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
are idempotent.
Idempotent ring elements
An idempotent element of a ringRing (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
is, by definition, an element which is idempotent with respect to the ring's multiplication. That is, r2 = r.
A short list of important notions defined with idempotents includes:
- A ring in which all elements are idempotent is called a Boolean ringBoolean ringIn mathematics, a Boolean ring R is a ring for which x2 = x for all x in R; that is, R consists only of idempotent elements....
. It can be shown that in every such ring, multiplication is commutative, and every element is its own additive inverseAdditive inverseIn mathematics, the additive inverse, or opposite, of a number a is the number that, when added to a, yields zero.The additive inverse of a is denoted −a....
. - Two idempotents a and b are called orthogonal if ab = ba = 0. If a is idempotent in the ring R, then so is b = 1 − a; a and b are orthogonal.
- If a is idempotent in the ring R, then aRa is again a ring, with multiplicative identity a. The ring aRa is often referred to as a corner ring of R. The corner ring arises naturally since the ring of endomorphisms
. - An idempotent a in R is called a central idempotent if ax = xa for all x in R. A ring in which all idempotents are central is called an Abelian ring. Such rings need not be commutative.
- A trivial idempotent is one of the elements 0 and 1.
- A primitive idempotent is an idempotent a such that aR is directly indecomposable.
- A local idempotent is an idempotent a such that aRa is a local ringLocal ringIn abstract algebra, more particularly in ring theory, local rings are certain rings that are comparatively simple, and serve to describe what is called "local behaviour", in the sense of functions defined on varieties or manifolds, or of algebraic number fields examined at a particular place, or...
. This implies that aR is directly indecomposable, so local idempotents are also primitive. - A right irreducible idempotent is an idempotent a for which aR is a simple module. By Schur's lemmaSchur's lemmaIn mathematics, Schur's lemma is an elementary but extremely useful statement in representation theory of groups and algebras. In the group case it says that if M and N are two finite-dimensional irreducible representations...
, End(aR)=aRa is a division ring, and hence is a local ring, so right (and left) irreducible idempotents are local. - A centrally primitive idempotent is a central idempotent a that cannot be written as the sum of two nonzero orthogonal central idempotents.
- An idempotent e+I in the quotient ring R/I is said to lift modulo I if there is an idempotent f in R such that f+I=e+I.
Any non-trivial idempotent a is a zero divisor
Zero divisor
In abstract algebra, a nonzero element a of a ring is a left zero divisor if there exists a nonzero b such that ab = 0. Similarly, a nonzero element a of a ring is a right zero divisor if there exists a nonzero c such that ca = 0. An element that is both a left and a right zero divisor is simply...
(because a(1 − a) = 0). This shows that integral domains and division ring
Division ring
In abstract algebra, a division ring, also called a skew field, is a ring in which division is possible. Specifically, it is a non-trivial ring in which every non-zero element a has a multiplicative inverse, i.e., an element x with...
s don't have such idempotents. Local ring
Local ring
In abstract algebra, more particularly in ring theory, local rings are certain rings that are comparatively simple, and serve to describe what is called "local behaviour", in the sense of functions defined on varieties or manifolds, or of algebraic number fields examined at a particular place, or...
s also don't have such idempotents, but for a different reason. The only idempotent contained in the Jacobson radical
Jacobson radical
In mathematics, more specifically ring theory, a branch of abstract algebra, the Jacobson radical of a ring R is an ideal which consists of those elements in R which annihilate all simple right R-modules. It happens that substituting "left" in place of "right" in the definition yields the same...
of a ring is 0. There is a catenoid
Catenoid
A catenoid is a three-dimensional surface made by rotating a catenary curve about its directrix. Not counting the plane, it is the first minimal surface to be discovered. It was found and proved to be minimal by Leonhard Euler in 1744. Early work on the subject was published also by Jean Baptiste...
of idempotents in the coquaternion
Coquaternion
In abstract algebra, the split-quaternions or coquaternions are elements of a 4-dimensional associative algebra introduced by James Cockle in 1849 under the latter name. Like the quaternions introduced by Hamilton in 1843, they form a four dimensional real vector space equipped with a...
ring.
Role in decompositions
The idempotents of R have an important connection to decompositon of R moduleModule
Module or modular may refer to the concept of modularity. It may also refer to:-Computing and engineering:* Modular design, the engineering discipline of designing complex devices using separately designed sub-components...
s. If M is an R module and E=EndR(M) is its ring of endomorphisms, then A⊕B=M if and only if there is a unique idempotent e in E such that A=e(M) and B=(1−e)(M). Clearly then, M is directly indecomposable if and only if 0 and 1 are the only idempotents in E.
In the case when M=R, End(R)=R, and so A⊕B=R as right modules if and only if there exists a unique idempotent e such that eR=A and (1−e)R=B. Thus every module direct summand of R is generated by an idempotent. The ring R can be written as e1R⊕e2R⊕...⊕enR with each ei a local idempotent if and only if R is a semiperfect ring
Semiperfect ring
In abstract algebra, a semiperfect ring is a ring over which every finitely generated left module has a projective cover. This property is left right symmetric.- Definition :Let R be ring...
.
If a is a central idempotent, then the corner ring aRa=Ra is a ring with multiplicative identity a. Just as idempotents determine the direct decompositions of R as a module, the central idempotents of R determine the decompositions of R as a direct sum
Direct sum of modules
In abstract algebra, the direct sum is a construction which combines several modules into a new, larger module. The result of the direct summation of modules is the "smallest general" module which contains the given modules as submodules...
of rings. If R is the direct sum of the rings R1,...,Rn, then the identity elements of the rings Ri are central idempotents in R, pairwise orthogonal, and their sum is 1. Conversely, given central idempotents a1,...,an in R which are pairwise orthogonal and have sum 1, then R is the direct sum of the rings Ra1, …, Ran. So in particular, every central idempotent a in R gives rise to a decomposition of R as a direct sum of the corner rings aRa and (1 − a)R(1 − a). As a result, a ring R is directly indecomposable as a ring if and only if the identity 1 is centrally primitive.
Working inductively, one can attempt to decompose 1 into a sum of centrally primitive elements. If 1 is centrally primitive, we are done. If not, it is a sum of central orthogonal idempotents, which in turn are primitive or sums of more central idempotents, and so on. The problem that may occur is that this may continue without end, producing an infinite family of central orthogonal idempotents. The condition "R does not contain infinite sets of central orthogonal idempotents" is a type of finiteness condition on the ring. It can be achieved in many ways, such as requiring the ring to be right Noetherian
Noetherian ring
In mathematics, more specifically in the area of modern algebra known as ring theory, a Noetherian ring, named after Emmy Noether, is a ring in which every non-empty set of ideals has a maximal element...
. If a decomposition R=c1R⊕c2R⊕...⊕cnR exists with each ci a centrally primitive idempotent, then R is a direct sum of the corner rings ciRci, each of which is ring irreducible.
Category of R modules
Lifting idempotents also has major consequences for the category of R modules. All idempotents lift modulo I if and only if every R direct summand of R/I has a projective coverProjective cover
In the branch of abstract mathematics called category theory, a projective cover of an object X is in a sense the best approximation of X by a projective object P. Projective covers are the dual of injective envelopes.- Definition :...
as an R module. Idempotents always lift modulo nil ideal
Nil ideal
In mathematics, more specifically ring theory, an ideal of a ring is said to be a nil ideal if each of its elements is nilpotent. The nilradical of a commutative ring is an example of a nil ideal; in fact, it is the ideal of the ring maximal with respect to the property of being nil...
s and rings for which R/I is I-adically complete.
Lifting is most important when I=J(R), the Jacobson radical
Jacobson radical
In mathematics, more specifically ring theory, a branch of abstract algebra, the Jacobson radical of a ring R is an ideal which consists of those elements in R which annihilate all simple right R-modules. It happens that substituting "left" in place of "right" in the definition yields the same...
of R. Yet another characterization of semiperfect rings is that they are semilocal rings whose idempotents lift modulo J(R).
Lattice of ideals
One may define a partial order on the idempotents of a ring as follows: if a and b are idempotents, we write a ≤ b if and only ifIf and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
ab = ba = a. With respect to this order, 0 is the smallest and 1 the largest idempotent. For orthogonal idempotents a and b, a + b is also idempotent, and we have a ≤ a + b and b ≤ a + b. The atoms of this partial order are precisely the primitive idempotents.
When the above partial order is restricted to the central idempotents of R, a lattice structure can be given. For two central idempotents e and f the complement ¬e=1−e and the join and meet
Join and meet
In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...
are given by
- e ∨ f = e + f − ef
and
- e ∧ f = ef.
The ordering now becomes simply e≤f if and only if eR⊆fR, and the join and meet satisfy (e∨f)R=eR+fR and (e∧f)R=eR∩fR=(eR)(fR). It is shown in that if R is von Neumann regular and right self-injective, then the lattice is a complete lattice
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
.
Relation with involutions
If a is an idempotent, then is an involution.If b is an involution, then
is an idempotent,and these are inverse: thus if 2 is invertible in a ring, idempotents and involutions are equivalent.
Further, if b is an involution, then
and are orthogonal idempotents, corresponding to a and .Numerical examples
One may consider the ring of integers mod n, where n is squarefreeSquare-free integer
In mathematics, a square-free, or quadratfrei, integer is one divisible by no perfect square, except 1. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32...
. By the Chinese Remainder Theorem
Chinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
, this ring factors into the direct product of rings of integers mod p. Now each of these factors is a field, so it is clear that the only idempotents will be 0 and 1. That is, each factor has 2 idempotents. So if there are m factors, there will be 2m idempotents.
We can check this for the integers mod 6, R=Z/6Z. Since 6 has 2 factors (2 and 3) it should have 22 idempotents.
- 0 = 02 = 03 = etc (mod 6)
- 1 = 12 = 13 = etc (mod 6)
- 3 = 32 = 33 = etc (mod 6)
- 4 = 42 = 43 = etc (mod 6)
This also demonstrates the decomposition properties: because 3+4=1 (mod 6), there is a ring decomposition 3Z/6Z⊕4Z/6Z. In 3Z/6Z the identity is 3+6Z and in 4Z/6Z the identity is 4+6Z.
Other examples
Idempotent operations can be found in Boolean algebra as well.In linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
, projection
Projection (linear algebra)
In linear algebra and functional analysis, a projection is a linear transformation P from a vector space to itself such that P2 = P. It leaves its image unchanged....
s are idempotent. In fact, they are defined as idempotent linear maps. By choosing a basis
Basis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
, any projection gives an idempotent matrix.
An idempotent semiring is a semiring whose addition (not multiplication) is idempotent.
Computer science meaning
In computer scienceComputer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the term idempotent is used more comprehensively to describe an operation that will produce the same results if executed once or multiple times. This may have a different meaning depending on the context in which it is applied. In the case of method
Method (computer science)
In object-oriented programming, a method is a subroutine associated with a class. Methods define the behavior to be exhibited by instances of the associated class at program run time...
s or subroutine
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
calls with side effects
Side effect (computer science)
In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...
, for instance, it means that the modified state remains the same after the first call. In functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
, though, an idempotent function is one that preserves the property f(f(x)) = f(x).
This is a very useful property in many situations, as it means that an operation can be repeated or retried as often as necessary without causing unintended effects. With non-idempotent operations, the algorithm may have to keep track of whether the operation was already performed or not.
Stronger is nullipotent, meaning that the results are the same if executed zero or multiple times, which is synonymous with "no side effects".
Examples
Looking up some customer's name and address in a databaseDatabase
A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
are typically idempotent (in fact nullipotent), since this will not cause the database to change. Similarly, changing a customer's address is typically idempotent, because the final address will be the same no matter how many times it is submitted. However, placing an order for a car for the customer is typically not idempotent, since running the method/call several times will lead to several orders being placed. Canceling an order is idempotent, because the order remains canceled no matter how many requests are made.
A composition of idempotent methods or subroutines, however, is not necessarily idempotent if a later method in the sequence changes a value that an earlier method depends on – idempotence is not closed under composition. For example, suppose the initial value of a variable is 3 and there is a sequence that reads the variable, then changes it to 5, and then reads it again. Each step in the sequence is idempotent: both steps reading the variable have no side effects and changing a variable to 5 will always have the same effect no matter how many times it is executed. Nonetheless, executing the entire sequence once produces the output (3, 5), but executing it a second time produces the output (5, 5), so the sequence is not idempotent.
In the HyperText Transfer Protocol (HTTP)
Hypertext Transfer Protocol
The Hypertext Transfer Protocol is a networking protocol for distributed, collaborative, hypermedia information systems. HTTP is the foundation of data communication for the World Wide Web....
, idempotence and safety are the major attributes that separate HTTP verbs. Of the major HTTP verbs, GET, PUT, and DELETE are idempotent (if implemented according to the standard), but POST is not. These verbs represent very abstract operations in computer science: GET retrieves a resource; PUT stores content at a resource; and DELETE eliminates a resource. As in the example above, reading data usually has no side effects, so it is idempotent (in fact nullipotent). Storing a given set of content is usually idempotent, as the final value stored remains the same after each execution. And deleting something is generally idempotent, as the end result is always the absence of the thing deleted.
In Event Stream Processing
Event Stream Processing
Event stream processing, or ESP, is a set of technologies designed to assist the construction of event-driven information systems. ESP technologies include event visualization, event databases, event-driven middleware, and event processing languages, or complex event processing...
, idempotence refers to the ability of a system to produce the same outcome, even if an event or message is received more than once.
In a load-store architecture, instructions that might possibly cause a page fault
Page fault
A page fault is a trap to the software raised by the hardware when a program accesses a page that is mapped in the virtual address space, but not loaded in physical memory. In the typical case the operating system tries to handle the page fault by making the required page accessible at a location...
are idempotent. So if a page fault occurs, the OS can load the page from disk and then simply re-execute the faulted instruction.
In a processor where such instructions are not idempotent, dealing with page faults is much more complex.
The notion of idempotence at the end of a chain of operations was applied to so-called "desired-outcome" functions in the widely used configuration management software Cfengine
Cfengine
CFEngine is a popular open source configuration managementsystem, written by Mark Burgess.Its primary function is to provide automated configuration and...
in 1993, changing the industry approach to datacenter automation by bringing "self-healing" by simple repetition with a predictable outcome.
See also
- Closure operatorClosure operatorIn mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....
- Fixed point (mathematics)Fixed point (mathematics)In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...
- Idempotent of a code
- NilpotentNilpotentIn mathematics, an element x of a ring R is called nilpotent if there exists some positive integer n such that xn = 0....
- Idempotent matrixIdempotent matrixIn algebra, an idempotent matrix is a matrix which, when multiplied by itself, yields itself. That is, the matrix M is idempotent if and only if MM = M...
- List of matrices
- Pure functionPure functionIn computer programming, a function may be described as pure if both these statements about the function hold:# The function always evaluates the same result value given the same argument value...
- Referential transparency (computer science)
- Iterated functionIterated functionIn mathematics, an iterated function is a function which is composed with itself, possibly ad infinitum, in a process called iteration. In this process, starting from some initial value, the result of applying a given function is fed again in the function as input, and this process is repeated...
- Biordered setBiordered setA biordered set is a mathematical object that occurs in the description of the structure of the set of idempotents in a semigroup. The concept and the terminology were developed by K S S Nambooripad of Kerala, India, in the early 1970s....
- Involution (mathematics)