Idempotence (// EYE-dəm-POH-təns) 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.
- 1 Definitions
- 2 Common examples
- 3 Computer science meaning
- 4 Applied examples
- 5 See also
- 6 References
- 7 Further reading
- 8 External links
A unary operation , that is, a map from some set into itself, is called idempotent if, for all in ,
An important class of idempotent functions is given by projections in a vector space. An example of a projection is the function defined by , 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 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 is the number of different idempotent functions. Hence, taking into account all possible partitions,
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
Given a binary operation on a set , an element is said to be idempotent (with respect to ) if:
In particular an identity element of , if it exists, is idempotent with respect to the operation . The binary operation itself is called idempotent if every element of is idempotent. That is, for all when denotes set membership:
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.
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 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 . The average is . Subtracting 7 from every number in the list yields . The average of that list is . Subtracting 0 from every number in that list yields the same list.
Idempotent ring elements
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.
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, and 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.
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 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.
- Closure operator
- Fixed point (mathematics)
- Idempotent of a code
- Idempotent matrix
- Idempotent relation — a generalization of idempotence to binary relations
- List of matrices
- Pure function
- Referential transparency (computer science)
- Iterated function
- Biordered set
- Involution (mathematics)
- Polcino & Sehgal (2002), p. 127.
- 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.
- e.g. f(g(7)) = f(7) = 1, but f(g(1)) = f(5) = 2 ≠ 1
- also showing that commutation of f and g is not a necessary condition for idempotency preservation
- See Hazewinkel et al. (2004), p. 2.
- Gondran & Minoux. Graphs, dioids and semirings. Springer, 2008, p. 34
- Rodriguez, Alex. "RESTful Web services: The basics". IBM developerWorks. IBM. Retrieved 24 April 2013.
- IETF, Hypertext Transfer Protocol (HTTP/1.1): Semantics and Content. See also HyperText Transfer Protocol.
- 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
- “idempotent” at FOLDOC
- Goodearl, K. R. (1991), von Neumann regular rings (2 ed.), Malabar, FL: Robert E. Krieger Publishing Co. Inc., pp. xviii+412, ISBN 0-89464-632-X, MR 1150975 (93m:16006)
- Gunawardena, Jeremy (1998), "An introduction to idempotency", in Gunawardena, Jeremy, Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994 (PDF), Cambridge: Cambridge University Press, pp. 1–49, Zbl 0898.16032
- Hazewinkel, Michiel; Gubareni, Nadiya; Kirichenko, V. V. (2004), Algebras, rings and modules. vol. 1, Mathematics and its Applications 575, Dordrecht: Kluwer Academic Publishers, pp. xii+380, ISBN 1-4020-2690-0, MR 2106764 (2006a:16001)
- Lam, T. Y. (2001), A first course in noncommutative rings, Graduate Texts in Mathematics 131 (2 ed.), New York: Springer-Verlag, pp. xx+385, ISBN 0-387-95183-0, MR 1838439 (2002c:16001)
- Lang, Serge (1993), Algebra (Third ed.), Reading, Mass.: Addison-Wesley Pub. Co., ISBN 978-0-201-55540-0, Zbl 0848.13001 p. 443
- Peirce, Benjamin. Linear Associative Algebra 1870.
- Polcino Milies, César; Sehgal, Sudarshan K. (2002), An introduction to group rings, Algebras and Applications 1, Dordrecht: Kluwer Academic Publishers, pp. xii+371, ISBN 1-4020-0238-6, MR 1896125 (2003b:16026)
|Look up idempotence in Wiktionary, the free dictionary.|
- Hazewinkel, Michiel, ed. (2001), "Idempotent", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
|Wikibooks has more on the topic of: Idempotence|
|Wikiversity has learning materials about Portal:Computer Science|