Idempotence

Idempotence IPA: /ˌaɪdɨmˈpoʊtənts/ describes the property of operations in mathematics and computer science which yield the same result after the operation is applied multiple times. The concept of idempotence arises in a number of places in abstract algebra (in particular, in the theory of projectors, closure operators and functional programming, in which it is connected to the property of referential transparency).

There are two main definitions of idempotence in use:

• Given a binary operation, an idempotent element (or simply an idempotent) is something which when multiplied by (or for a function, composed with) itself, gives itself as a result. For example, the only two real numbers which are idempotent under multiplication are 0 and 1.
• A unary operation is idempotent if, whenever it is applied twice to any element, it gives the same result as if it were applied once. For example, the greatest integer function is idempotent as a function from the set of real numbers to the set of integers. This "unary operation definition" is in fact a special case of the "binary operation definition", see below.

Formal definitions

Binary operation

If S is a set with a binary operation * on it, then an element s of S is said to be idempotent (with respect to *) if

s * s = s.

In particular, any identity element is idempotent. If every element of S is idempotent, then the binary operation * is said to be idempotent. For example, the operations of set union and set intersection are both idempotent.

Unary operation

If f is a unary operation, i.e. a map f from some set X into itself, then f is idempotent if, for all x in X,

f(f(x)) = f(x).

This is equivalent to say that f o f = f, using function composition denoted by "o". Thus an idempotent unary operation on X is an idempotent element of the set X^X of all functions from X into itself, with respect to the binary operation "o", in the sense of the previous definition.

In particular, the identity function f(x) = x is idempotent, and any constant function f(x) = c is idempotent as well.

Common examples

Computer Science

Main article: Referential transparency (computer science)

In computer science, the term idempotent is used to describe method or subroutine calls which can safely be called multiple times, as invoking the procedure a single time or multiple times results in the system maintaining the same state i.e. after the method call all variables have the same value as they did before.

Example: Looking up some customer's name and address are typically idempotent, since the system will not change state based on this. However, placing an order for a car for the customer is not, since running the method/call several times will lead to several orders being placed, and therefore the state of the system being changed to reflect this.

Functions

As mentioned above, the identity map and the constant maps are always idempotent maps. Less trivial examples are the absolute value function of a real or complex argument, and the floor function of a real argument.

The function which 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.

Idempotent ring elements

An idempotent element of a ring is, by definition, an element which is idempotent with respect to the ring's multiplication. One may define a partial order on the idempotents of a ring as follows: if e and f are idempotents, we write e ≤ f iff ef = fe = e. With respect to this order, 0 is the smallest and 1 the largest idempotent.

Two idempotents e and f are called orthogonal if ef = fe = 0. In this case, e + f is also idempotent, and we have e ≤ e + f and f ≤ e + f.

If e is idempotent in the ring R, then so is f = 1 − e; e and f are orthogonal.

If e is idempotent in the ring R, then eRe is again a ring, with multiplicative identity e.

An idempotent e in R is called central if ex = xe for all x in R. In this case, Re is a ring with multiplicative identity e. The central idempotents of R are closely related to the decompositions of R as a direct sum of rings. If R is the direct sum of the rings R₁,...,R_n, then the identity elements of the rings R_i are central idempotents in R, pairwise orthogonal, and their sum is 1. Conversely, given central idempotents e₁,...,e_n in R which are pairwise orthogonal and have sum 1, then R is the direct sum of the rings Re₁,...,Re_n. So in particular, every central idempotent e in R gives rise to a decomposition of R as a direct sum of Re and R(1 − e).

Any idempotent e which is different from 0 and 1 is a zero divisor (because e(1 − e) = 0). This shows that integral domains and division rings don't have such idempotents. Local rings 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.

A ring in which all elements are idempotent is called a boolean ring. It can be shown that in every such ring, multiplication is commutative, and every element is its own additive inverse.

Relation with involutions

If e is an idempotent, then Failed to parse (Missing texvc executable; please see math/README to configure.): 1-2e

is an involution.

If T is an involution, then Failed to parse (Missing texvc executable; please see math/README to configure.): \frac{1}{2}(1-T)

is an idempotent,

and these are inverse: thus if 2 is invertible in a ring, idempotents and involutions are equivalent.

Further, if T is an involution, then Failed to parse (Missing texvc executable; please see math/README to configure.): \frac{1}{2}(1-T)

and Failed to parse (Missing texvc executable; please see math/README to configure.): \frac{1}{2}(1+T)
are orthogonal idempotents, corresponding to e and Failed to parse (Missing texvc executable; please see math/README to configure.): 1-e

.

Numerical examples

One may consider the ring of integers mod n, where n is squarefree. 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 division ring, so it's 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 Failed to parse (Missing texvc executable; please see math/README to configure.): 2^m

idempotents.

We can check this for the integers mod 6. Since 6 has 2 factors (2 and 3) it should have Failed to parse (Missing texvc executable; please see math/README to configure.): 2^2

idempotents.

     0 = 0^2 = 0^3 = etc (mod 6)
     1 = 1^2 = 1^3 = etc (mod 6)
     3 = 3^2 = 3^3 = etc (mod 6)
     4 = 4^2 = 4^3 = etc (mod 6)

Other examples

Idempotent operations can be found in Boolean algebra as well.

In linear algebra, projections are idempotent. In fact, they are defined as idempotent linear maps.

An idempotent semiring is a semiring whose addition (not multiplication) is idempotent.

There are idempotent matrices.

See also

• Fixed point (mathematics)
• Nilpotent
• List of matrices
• Referential transparency
• Superidempotency
• Subidempotencycs:Idempotence

de:Idempotenz et:Idempotentsus es:Idempotente fr:Idempotence it:Idempotenza nl:Idempotentie ja:冪等 pl:Idempotentność pt:Idempotente ru:Идемпотентный элемент sr:Идемпотенција th:นิจพล fi:Idempotenssi