Idempotence

From Wikipedia, the free encyclopedia

Idempotence (pronounced /ˌaɪdɨmˈpoʊtəns/) describes the property of operations in mathematics and computer science which means that multiple applications of the operation do not change the result. The concept of idempotence arises in a number of places in abstract algebra (in particular, in the theory of projectors and closure operators) 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 power.

There are several meanings of idempotence, depending on what the concept is applied to:

• A unary operation (or function) is called 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 value function is idempotent as a function from the set of real numbers to the set of real numbers: abs(abs (x)) = abs(x). Occasionally in functional analysis, a different definition is used: a unary operation is called idempotent if, whenever it is applied twice to any value, it gives the original value. For example, the complex conjugation of a number is considered an idempotent operation.
• A binary operation is called 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: max(x, x) = x.
• 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 multiplication: 1 × 1 = 1.

Contents 1 Definitions 1.1 Unary operation 1.2 Binary operation 1.3 Connections 2 Common examples 2.1 Functions 2.2 Formal languages 2.3 Idempotent ring elements 2.3.1 Relation with involutions 2.3.2 Numerical examples 2.4 Other examples 3 In computing 4 See also 5 Notes 6 References

[edit] Definitions

[edit] Unary operation

A unary operation 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 id_S, defined by id_S(x) = x, is idempotent, as is the constant function K_c, where c is an element of S, defined by K_c(x) = c.

An important class of idempotent functions is given by projections in a vector space. An example of a projection is the function π_xy defined by π_xy(x, y, z) = (x, y, 0), 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 f : S → S is idempotent if it maps all elements of S to fixed points. 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,…^[1]

[edit] Binary operation

A binary operation ★ on a set S is called idempotent if, for all x in S,

x★x = x.

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,

x★x = x.

In particular, an identity element of ★ is idempotent for the operation.

[edit] 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, f(f(x)) = f(x) for x in the domain of f, can equivalently be rewritten as f o f = f, using the binary operation of function composition denoted by "o". 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 o on functions from S to S.

[edit] Common examples

[edit] Functions

As mentioned above, the identity map and the constant maps are always idempotent maps. 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.

[edit] Formal languages

The Kleene star and Kleene plus operators used to express repetition in formal languages are idempotent.

[edit] 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 a and b are idempotents, we write a ≤ b if and only if ab = ba = a. With respect to this order, 0 is the smallest and 1 the largest idempotent.

Two idempotents a and b are called orthogonal if ab = ba = 0. In this case, a + b is also idempotent, and we have a ≤ a + b and b ≤ a + b.

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.

An idempotent a in R is called central if ax = xa for all x in R. In this case, Ra is a ring with multiplicative identity a. 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 a₁,...,a_n in R which are pairwise orthogonal and have sum 1, then R is the direct sum of the rings Ra₁,...,Ra_n. So in particular, every central idempotent a in R gives rise to a decomposition of R as a direct sum of Ra and R(1 − a).

Any idempotent a which is different from 0 and 1 is a zero divisor (because a(1 − a) = 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.

[edit] Relation with involutions

If a is an idempotent, then 1 − 2a 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 1 − a.

[edit] 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 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 2^m idempotents.

We can check this for the integers mod 6. Since 6 has 2 factors (2 and 3) it should have 2² idempotents.

0 = 0² = 0³ = etc (mod 6)

1 = 1² = 1³ = etc (mod 6)

3 = 3² = 3³ = etc (mod 6)

4 = 4² = 4³ = etc (mod 6)

[edit] 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. By choosing a basis, any projection gives an idempotent matrix.

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

[edit] In computing

In computer science, the term idempotent is used to describe methods or subroutine calls that can safely be called multiple times, as invoking the procedure a single time or multiple times has the same result; i.e., after any number of method calls all variables have the same value as they did after the first call.

Example: Looking up some customer's name and address in a database are typically idempotent, since this will not cause the database to change. Placing an order for a car for the customer is not idempotent, since running the method/call several times will lead to several orders being placed, and therefore the state of the database being changed to reflect this. Canceling an order is idempotent, because the order remains canceled no matter how many requests are made.

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.

[edit] See also

• Closure operator
• Fixed point (mathematics)
• Idempotent of a code
• Nilpotent
• List of matrices
• Referential transparency (computer science)
• Superidempotency
• Subidempotency
• Iterated function
• Biordered set

[edit] Notes

[edit] References

This article needs additional citations for verification. Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (October 2008)

• Page 443 of Lang, Serge (1993), Algebra (Third ed.), Reading, Mass.: Addison-Wesley Pub. Co., ISBN 978-0-201-55540-0