Idempotence

From Wikipedia, the free encyclopedia

For the concept in matrix algebra, see Idempotent matrix.

Idempotence (// -dəm--təns^{[citation needed]}) is the property of certain operations in mathematics and computer science, that 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 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 algebras 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 operation (or function) is idempotent if, whenever it is applied twice to any value, it gives the same result as if it were applied once; i.e., ƒ(ƒ(x)) ≡ ƒ(x). For example, the absolute value function, where abs(abs(x)) ≡ abs(x).
A binary operation is idempotent if, whenever it is applied to two equal values, it gives that value as the result. For example, the function giving the maximum value of two equal 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 that value as the result. For example, the number 1 is an idempotent of multiplication: 1 × 1 = 1.

Definitions

Unary operation

A unary operation , that is, a map from some set into itself, is called idempotent if, for all in ,

$f\!\left(f\!\left(x\right)\right) = f\!\left(x\right)$ .

In particular, the identity function $\text{id}_S$ , defined by $\text{id}_S\left(x\right) = x$ , is idempotent, as is the constant function , where is an element of , defined by $K_c\left(x\right) = c$ .

An important class of idempotent functions is given by projections in a vector space. An example of a projection is the function $\pi_{xy}$ defined by $\pi_{xy}\left(x, y, z\right) = \left(x, y, 0\right)$ , which projects an arbitrary point in 3D space to a point on the -plane, where the third coordinate () is equal to 0.

A unary operation $f\colon S \to S$ is idempotent if it maps each element of to a fixed point of . We can partition a set with elements into chosen fixed points and non-fixed points, and then $k^{n-k}$ is the number of different idempotent functions. Hence, taking into account all possible partitions,

$\sum_{k=0}^n {n \choose k} k^{n-k}$

is the total number of possible idempotent functions on the set. The integer sequence of the number of idempotent functions as given by the sum above for $n = \left\{0, 1, 2, \dots\right\}$ starts with $1, 1, 3, 10, 41, 196, 1057, 6322, 41393, \dots$ . (sequence A000248 in OEIS)

Neither the property of being idempotent nor that of being not is preserved under composition of unary functions.² As an example for the former, f(x) = x mod 3 and g(x) = max(x,5) are both idempotent, but f∘g is not,³ although g∘f happens to be.⁴ As an example for the latter, the negation function ¬ on truth values isn't idempotent, but ¬∘¬ is.

Idempotent elements and binary operations

Main article: Idempotent element

Given a binary operation $\bigstar$ on a set , an element is said to be idempotent (with respect to $\bigstar$ ) if:

$x \,\bigstar\, x = x$ .

In particular an identity element of $\bigstar$ , if it exists, is idempotent with respect to the operation $\bigstar$ . The binary operation itself is called idempotent if every element of is idempotent. That is, for all $x \in S$ when $\in$ denotes set membership:

$x \,\bigstar\, 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.

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 ∘ f = f, using the binary operation of function composition 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 with respect to the function composition operation ∘ on functions from S to S.

Common examples

Functions

As mentioned above, the identity map and the constant maps are always idempotent maps. The absolute value function of a real or complex argument, and the floor function of a real argument are idempotent. The function that assigns to every subset of some topological space the closure of is idempotent on the power set $\mathcal{P}\left(X\right)$ of . 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 numbers $3, 6, 8, 8, \text{and }10$ . The average $\frac{\sum_1^n x_n}{n} \,\forall x_n$ is $\frac{3 + 6 + 8 + 8 + 10}{5} = \frac{35}{5} = 7$ . Subtracting 7 from every number in the list yields $\left(-4\right), \left(-1\right), 1, 1, 3$ . The average $\frac{\sum_1^n x_n}{n} \,\forall x_n$ of that list is $\frac{\left(-4\right) + \left(-1\right) + 1 + 1 +3}{5} = \frac{0}{5} = 0$ . Subtracting 0 from every number in that list yields the same list.

Formal languages

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

Idempotent ring elements

Main article: Idempotent element

An idempotent element of a ring is, by definition, an element that is idempotent for the ring's multiplication.⁵ That is, an element a is idempotent precisely when a² = a.

Idempotent elements of rings yield direct decompositions of modules, and play a role in describing other homological properties of the ring. While "idempotent" usually refers to the multiplication operation of a ring, there are rings in which both operations are idempotent: Boolean algebras are such an example.

Other examples

In Boolean algebra, both the logical and and the logical or operations are idempotent. This implies that every element of Boolean algebra is idempotent with respect to both of these operations. Specifically, $x \wedge x = x$ and $x \vee x = x$ for all . In linear algebra, projections are idempotent. In fact, the projections of a vector space are exactly the idempotent elements of the ring of linear transformations of the vector space. After fixing a basis, it can be shown that the matrix of a projection with respect to this basis is an idempotent matrix. An idempotent semiring (also sometimes called a dioid) is a semiring whose addition (not multiplication) is idempotent. If both operations of the semiring are idempotent, then the semiring is called doubly idempotent.⁶

Computer science meaning

In computer science, 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 methods 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 has the property f(f(x)) = f(x) for any value 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.

Examples

Looking up some customer's name and address in a database 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.

Applied examples

Applied examples that many people could encounter in their day-to-day lives include elevator call buttons and crosswalk buttons.¹⁰ The initial activation of the button moves the system into a requesting state, until the request is satisfied. Subsequent activations of the button between the initial activation and the request being satisfied have no effect.

References

Jump up ^ Polcino & Sehgal (2002), p. 127.
Jump up ^ If f and g commute, i.e. if f∘g = g∘f, then idempotency of both f and g implies that of f∘g, since f∘g ∘ f∘g = f∘f ∘ g∘g = f ∘ g, using the associativity of composition.
Jump up ^ e.g. f(g(7)) = f(7) = 1, but f(g(1)) = f(5) = 2 ≠ 1
Jump up ^ also showing that commutation of f and g is not a necessary condition for idempotency preservation
Jump up ^ See Hazewinkel et al. (2004), p. 2.
Jump up ^ Gondran & Minoux. Graphs, dioids and semirings. Springer, 2008, p. 34
Jump up ^ Rodriguez, Alex. "RESTful Web services: The basics". IBM developerWorks. IBM. Retrieved 24 April 2013.
Jump up ^ http://foldoc.org/idempotent
^ Jump up to: ^a ^b IETF, Hypertext Transfer Protocol (HTTP/1.1): Semantics and Content. See also HyperText Transfer Protocol.
Jump up ^ http://web.archive.org/web/20110523081716/http://www.nclabor.com/elevator/geartrac.pdf For example, this design specification includes detailed algorithm for when elevator cars will respond to subsequent calls for service

Idempotence - Wikipedia, the free encyclopedia