Idempotence
Idempotence (UK: /ˌɪdɛmˈpoʊtəns/,^{[1]} US: /ˌaɪdəm/)^{[2]} is the property of certain operations in mathematics and computer science whereby 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 operators) and functional programming (in which it is connected to the property of referential transparency).
The term was introduced by Benjamin Peirce^{[3]} 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).
Definition [ edit ]
An element x of a magma (M, •) is said to be idempotent if:^{[4]}^{[5]}
 x • x = x.
If all elements are idempotent with respect to •, then • is called idempotent. The formula ∀x, x • x = x is called the idempotency law for •.^{[6]}^{[7]}
Examples [ edit ]
 The natural number 1 is an idempotent element with respect to multiplication (since 1×1 = 1), and so is 0 (since 0×0 = 0), but no other natural number is (e.g. 2×2 = 2 does not hold). For the latter reason, multiplication of natural numbers is not an idempotent operation. More formally, in the monoid (ℕ, ×), idempotent elements are just 0 and 1.
 In a magma (M, •), an identity element e or an absorbing element a, if it exists, is idempotent. Indeed, e • e = e and a • a = a.
 In a group (G, •), the identity element e is the only idempotent element. Indeed, if x is an element of G such that x • x = x, then x • x = x • e and finally x = e by multiplying on the left by the inverse element of x.
 Taking the intersection x∩y of two sets x and y is an idempotent operation, since x∩x always equals x. This means that the idempotency law ∀x, x∩x = x is true. Similarly, taking the union of two sets is an idempotent operation. Formally, in the monoids (𝒫(E), ∪) and (𝒫(E), ∩) of the power set of the set E with the set union ∪ and set intersection ∩ respectively, all elements are idempotent; hence ∪ and ∩ are idempotent operations on 𝒫(E).
 In the monoids ({0, 1}, ∨) and ({0, 1}, ∧) of the Boolean domain with the logical disjunction ∨ and the logical conjunction ∧ respectively, all elements are idempotent.
 In a Boolean ring, multiplication is idempotent.
 In a Tropical semiring, addition is idempotent.
Idempotent functions [ edit ]
In the monoid (E^{E}, ∘) of the functions from a set E to itself with the function composition ∘, idempotent elements are the functions f: E → E such that f ∘ f = f, in other words such that for all x in E, f(f(x)) = f(x) (the image of each element in E is a fixed point of f). For example:
 Taking the absolute value abs(x)^{[8]} of an integer number x is an idempotent function for the following reason: abs(abs(x)) = abs(x) is true for each integer number x.^{[9]} This means that abs ∘ abs = abs^{[10]} holds, that is, abs is an idempotent element in the set of all functions (from integers to integers)^{[11]} with respect to function composition. Therefore, abs satisfies the above definition of an idempotent function.
Other examples include:
 the identity function is idempotent;
 constant functions are idempotent;
 the floor, ceiling and fractional part functions are idempotent;
 the subgroup generated function from the power set of a group to itself is idempotent;
 the convex hull function from the power set of an affine space over the reals to itself is idempotent;
 the closure and interior functions of the power set of a topological space to itself are idempotent;
 the Kleene star and Kleene plus functions of the power set of a monoid to itself are idempotent;
 the idempotent endomorphisms of a vector space are its projections.
If the set E has n elements, we can partition it into k chosen fixed points and n − k nonfixed points under f, and then k^{n−k} is the number of different idempotent functions. Hence, taking into account all possible partitions,
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 = 0, 1, 2, 3, 4, 5, 6, 7, 8, … starts with 1, 1, 3, 10, 41, 196, 1057, 6322, 41393, … (sequence A000248 in the OEIS).
Neither the property of being idempotent nor that of being not is preserved under function composition.^{[12]} 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,^{[13]} although g ∘ f happens to be.^{[14]} As an example for the latter, the negation function ¬ on the Boolean domain is not idempotent, but ¬ ∘ ¬ is. Similarly, unary negation −( ) of real numbers is not idempotent, but −( ) ∘ −( ) is.
Computer science meaning [ edit ]
In computer science, the term idempotence may have a different meaning depending on the context in which it is applied:
 in imperative programming, a subroutine with side effects is idempotent if the system state remains the same after one or several calls, in other words if the function from the system state space to itself associated to the subroutine is idempotent in the mathematical sense given in the definition;
 in functional programming, a pure function is idempotent if it is idempotent in the mathematical sense given in the definition.
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 nonidempotent operations, the algorithm may have to keep track of whether the operation was already performed or not.
Computer science examples [ edit ]
A function looking up a customer's name and address in a database is typically idempotent, since this will not cause the database to change. Similarly, changing a customer's address to XYZ is typically idempotent, because the final address will be the same no matter how many times XYZ is submitted. However, placing an order for a cart for the customer is typically not idempotent, since running the 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 should be implemented in an idempotent manner according to the standard, but POST need not be.^{[15]} 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 and deleting a given set of content are each usually idempotent as long as the request specifies a location or identifier that uniquely identifies that resource and only that resource again in the future. The PUT and DELETE operations with unique identifiers reduce to the simple case of assignment to an immutable variable of either a value or the nullvalue, respectively, and are idempotent for the same reason; the end result is always the same as the result of the initial execution, even if the response differs.^{[16]}
Violation of the unique identification requirement in storage or deletion typically causes violation of idempotence. For example, storing or deleting a given set of content without specifying a unique identifier: POST requests, which do not need to be idempotent, often do not contain unique identifiers, so the creation of the identifier is delegated to the receiving system which then creates a corresponding new record. Similarly, PUT and DELETE requests with nonspecific criteria may result in different outcomes depending on the state of the system  for example, a request to delete the most recent record. In each case, subsequent executions will further modify the state of the system, so they are not idempotent.
In Event stream processing, idempotence refers to the ability of a system to produce the same outcome, even if the same file, event or message is received more than once.
In a loadstore 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 reexecute the faulted instruction. In a processor where such instructions are not idempotent, dealing with page faults is much more complex.^{[citation needed]}
When reformatting output, prettyprinting is expected to be idempotent. In other words, if the output is already "pretty", there should be nothing to do for the prettyprinter.^{[citation needed]}
In serviceoriented architecture (SOA), a multiplestep orchestration process composed entirely of idempotent steps can be replayed without sideeffects if any part of that process fails.
Applied examples [ edit ]
Applied examples that many people could encounter in their daytoday lives include elevator call buttons and crosswalk buttons.^{[17]} 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, unless the system is designed to adjust the time for satisfying the request based on the number of activations.
See also [ edit ]
 Closure operator
 Fixed point (mathematics)
 Idempotent of a code
 Nilpotent
 Idempotent matrix
 Idempotent relation — a generalization of idempotence to binary relations
 List of matrices
 Pure function
 Referential transparency
 Iterated function
 Biordered set
 Involution (mathematics)
References [ edit ]
 ^ "idempotence". Oxford English Dictionary (3rd ed.). Oxford University Press. 2010.
 ^ "idempotent". MerriamWebster. Archived from the original on 20161019.
 ^ Polcino & Sehgal (2002), p. 127.

^
Valenza, Robert (2012). Linear Algebra: An Introduction to Abstract Mathematics. Berlin: Springer Science & Business Media. p. 22. ISBN 9781461209010.
An element s of a magma such that ss = s is called idempotent.

^
Doneddu, Alfred (1976). Polynômes et algèbre linéaire (in French). Paris: Vuibert. p. 180.
Soit M un magma, noté multiplicativement. On nomme idempotent de M tout élément a de M tel que a^{2} = a.
 ^ George Grätzer (2003). General Lattice Theory. Basel: Birkhäuser. Here: Sect.1.2, p.5.
 ^ Garrett Birkhoff (1967). Lattice Theory. Colloquium Publications. 25. Providence: Am. Math. Soc.. Here: Sect.I.5, p.8.
 ^ A more common notation for this is , but it is harder to read when expressions are nested.
 ^ In fact, this equation holds for all rational, real and even complex numbers, too.
 ^ This is an equation between functions. Two functions are equal if their domains and ranges agree, and their output values agree on their whole domain.
 ^ This set of functions is formally denoted as ℤ^{ℤ}.
 ^ 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
 ^ IETF, Hypertext Transfer Protocol (HTTP/1.1): Semantics and Content Archived 20140608 at the Wayback Machine. See also HyperText Transfer Protocol.

^
"Idempotent Methods". Hypertext Transfer Protocol (HTTP/1.1): Semantics and Content. sec. 4.2.2. doi:10.17487/RFC7231. RFC 7231.
It knows that repeating the request will have the same intended effect, even if the original request succeeded, though the response might differ.
 ^ https://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
Further reading [ edit ]
Look up idempotence in Wiktionary, the free dictionary. 
Wikibooks has more on the topic of: Idempotence 
Wikiversity has learning resources about Portal:Computer Science 
 “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 9780894646324, MR 1150975
 Gunawardena, Jeremy (1998), "An introduction to idempotency" (PDF), in Gunawardena, Jeremy (ed.), Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994, Cambridge: Cambridge University Press, pp. 1–49, Zbl 0898.16032
 Hazewinkel, Michiel, ed. (2001) [1994], "Idempotent", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 9781556080104
 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 9781402026904, MR 2106764
 Lam, T. Y. (2001), A first course in noncommutative rings, Graduate Texts in Mathematics, 131 (2 ed.), New York: SpringerVerlag, pp. xx+385, doi:10.1007/9781441986160, ISBN 9780387951836, MR 1838439
 Lang, Serge (1993), Algebra (Third ed.), Reading, Mass.: AddisonWesley, ISBN 9780201555400, 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, doi:10.1007/9789401004053, ISBN 9781402002380, MR 1896125