View source for Idempotence

{{Short description|Property of operations}}
{{For|the concepts in algebra|Idempotent (ring theory)|Idempotent matrix}}
[[File:On Off - Zał Wył (3086204137).jpg|thumb|''On''/''Off'' buttons of a train's [[destination sign]] control panel. Pressing the ''On'' button (green) is an idempotent operation, since it has the same effect whether done once or multiple times. Likewise, pressing ''Off'' is idempotent.]]
'''Idempotence''' ({{IPAc-en|UK|,|ɪ|d|ɛ|m|ˈ|p|əʊ|t|ən|s}},<ref>{{cite dictionary |title=idempotence |dictionary=[[Oxford English Dictionary]] |url=http://www.oed.com/view/Entry/273873 |date=2010 |edition= 3rd|publisher=Oxford University Press }}</ref> {{IPAc-en|US|ˈ|aɪ|d|ə|m|-}})<ref>{{cite dictionary |title=idempotent |url=http://www.merriam-webster.com/dictionary/idempotent |dictionary=[[Merriam-Webster]] |url-status=live |archive-url=https://web.archive.org/web/20161019143953/http://www.merriam-webster.com/dictionary/idempotent |archive-date=2016-10-19 }}</ref> is the property of certain [[operation (mathematics)|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 [[projector (linear algebra)|projector]]s and [[closure operator]]s) and [[functional programming]] (in which it is connected to the property of [[referential transparency]]).

The term was introduced by American mathematician [[Benjamin Peirce]] in 1870<ref>Original manuscript of 1870 lecture before National Academy of Sciences (Washington, DC, USA):  Peirce, Benjamin (1870) [https://books.google.com/books?id=HqQKAAAAYAAJ&pg=PA16 "Linear associative algebra"]  From pages 16–17:  "When an expression which is raised to the square or any higher power vanishes,  it may be called ''nilpotent''; but when raised to a square or higher power it gives itself as the result, it may be called ''idempotent''.<br> 
The defining equation of nilpotent and idempotent expressions are respectively A<sup>n</sup> = 0 and A<sup>n</sup> = A; but with reference to idempotent expressions, it will always be assumed that they are of the form A<sup>n</sup> = A unless it be otherwise distinctly stated."
*Printed:  {{cite journal |last1=Peirce |first1=Benjamin |title=Linear associative algebra |journal=American Journal of Mathematics |date=1881 |volume=4 |issue=1 |pages=97–229 |doi=10.2307/2369153 |jstor=2369153 |url=https://babel.hathitrust.org/cgi/pt?id=uc1.$b772370&seq=107|url-access=subscription }}  See p. 104.
*Reprinted:  {{cite book |last1=Peirce |first1=Benjamin |title=Linear Associative Algebra |date=1882 |publisher=D. Van Nostrand |location=New York, New York, USA |page=8 |url=https://ia903403.us.archive.org/33/items/linearassocalgeb00pierrich/linearassocalgeb00pierrich_bw.pdf}}</ref>{{sfn|Polcino|Sehgal|2002|p=[https://books.google.com/books?id=7m9P9hM4pCQC&q=Idempotence&pg=PA127 127]}} 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 {{wikt-lang|la|idem}} + ''[[wikt:potence|potence]]'' (same + power).

== Definition ==
An element <math>x</math> of a set <math>S</math> equipped with a [[binary operator]] <math>\cdot</math> is said to be ''idempotent'' under <math>\cdot</math> if<ref>{{cite book |last=Valenza |first=Robert |date=2012 |title=Linear Algebra: An Introduction to Abstract Mathematics |url=https://books.google.com/books?id=7x8MCAAAQBAJ |location=Berlin |publisher=Springer Science & Business Media |page=22 |isbn=9781461209010 |quote=An element ''s'' of a magma such that ''ss'' = ''s'' is called ''idempotent''.}}</ref><ref>{{cite book |last=Doneddu |first=Alfred |date=1976 |title=Polynômes et algèbre linéaire |url=https://books.google.com/books?id=5Ry7AAAAIAAJ |language=fr |location=Paris |publisher=Vuibert |page=180 |quote=Soit ''M'' un magma, noté multiplicativement. On nomme idempotent de ''M'' tout élément ''a'' de ''M'' tel que ''a''<sup>2</sup> = ''a''.}}</ref>
: {{nowrap|1=<math>x\cdot x=x</math>}}.
The ''binary operation'' <math>\cdot</math> is said to be ''idempotent'' if<ref>{{cite book | author=George Grätzer | title=General Lattice Theory | url=https://archive.org/details/generallatticeth0000grat | url-access=registration | location=Basel | publisher=Birkhäuser | year=2003 | isbn=978-3-7643-6996-5 }} Here: Sect.1.2, p.5.</ref><ref>{{cite book | author=Garrett Birkhoff | title=Lattice Theory | location=Providence | publisher=Am. Math. Soc. | series=Colloquium Publications | volume=25 | year=1967 }}. Here: Sect.I.5, p.8.</ref>
: {{nowrap|1=<math>x\cdot x=x</math> for all <math>x\in S</math>}}.

== Examples ==
* In the [[monoid]] <math>(\mathbb{N}, \times)</math> of the [[natural number]]s with [[multiplication]], only <math>0</math> and <math>1</math> are idempotent. Indeed, {{nowrap|1=<math>0\times 0 = 0</math>}} and {{nowrap|1=<math>1\times 1=1</math>}}.
* In the [[monoid]] <math>(\mathbb{N}, +)</math> of the [[natural number]]s with [[addition]], only <math>0</math> is idempotent. Indeed, {{nowrap|1=0 + 0 = 0}}.
* In a [[Magma (algebra)|magma]] <math>(M, \cdot)</math>, an [[identity element]] <math>e</math> or an [[absorbing element]] <math>a</math>, if it exists, is idempotent. Indeed, {{nowrap|1=<math>e\cdot e=e</math>}} and {{nowrap|1=<math>a\cdot a=a</math>}}.
* In a [[Group (mathematics)|group]] <math>(G, \cdot)</math>, the identity element <math>e</math> is the only idempotent element. Indeed, if <math>x</math> is an element of <math>G</math> such that {{nowrap|1=<math>x\cdot x=x</math>}}, then {{nowrap|1=<math>x\cdot x=x\cdot e</math>}} and finally <math>x=e</math> by multiplying on the left by the [[inverse element]] of <math>x</math>.
* In the monoids <math>(\mathcal{P}(E), \cup)</math> and <math>(\mathcal{P}(E), \cap)</math> of the [[power set]] <math>\mathcal{P}(E)</math> of the set <math>E</math> with [[Union (set theory)|set union]] <math>\cup</math> and [[Intersection (set theory)|set intersection]] <math>\cap</math> respectively, <math>\cup</math> and <math>\cap</math> are idempotent. Indeed, {{nowrap|1=<math>x\cup x=x</math> for all <math>x\in \mathcal{P}(E)</math>}}, and {{nowrap|1=<math>x\cap x=x</math> for all <math>x\in \mathcal{P}(E)</math>}}.
* In the monoids <math>(\{0, 1\}, \vee)</math> and <math>(\{0, 1\}, \wedge)</math> of the [[Boolean domain]] with [[logical disjunction]] <math>\vee</math> and [[logical conjunction]] <math>\wedge</math> respectively, <math>\vee</math> and <math>\wedge</math> are idempotent. Indeed, {{nowrap|1=<math>x\vee x=x</math> for all <math>x\in \{0, 1\}</math>}}, and {{nowrap|1=<math>x\wedge x=x</math> for all <math>x\in \{0, 1\}</math>}}.
* In a [[GCD domain]] (for instance in <math>\mathbb{Z}</math>), the operations of [[greatest common divisor|GCD]] and [[least common multiple|LCM]] are idempotent.
* In a [[Boolean ring]], multiplication is idempotent.
* In a [[Tropical semiring]], addition is idempotent.
* In a [[Matrix_ring|ring of quadratic matrices]], the [[determinant]] of an [[idempotent matrix]] is either 0 or 1. If the determinant is 1, the matrix necessarily is the [[identity matrix]].<ref>{{Cite journal |last=Balmaceda |first=Jose Maria |title=Idempotents in Certain Matrix Rings Over Polynomial Rings |url=https://dergipark.org.tr/tr/pub/ieja/issue/50849/662942 |journal=International Electronic Journal of Algebra |doi=10.24330/IEJA.662942|doi-access=free }}</ref>

===Idempotent functions===
In the monoid <math>(E^E, \circ)</math> of the functions from a set <math>E</math> to itself (see [[Function_(mathematics)#Set_exponentiation|set exponentiation]]) with [[function composition]] <math>\circ</math>, idempotent elements are the functions {{nowrap|<math>f\colon E\to E</math>}} such that {{nowrap|1=<math>f\circ f = f</math>}},{{efn |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.}} that is such that {{nowrap|1=<math>f(f(x))=f(x)</math> for all <math>x\in E</math>}} (in other words, the image <math>f(x)</math> of each element <math>x\in E</math> is a [[Fixed point (mathematics)|fixed point]] of <math>f</math>). For example:
* the [[absolute value]] is idempotent. Indeed, {{nowrap|1=<math>\operatorname{abs}\circ \operatorname{abs}=\operatorname{abs}</math>}}, that is {{nowrap|1=<math>\operatorname{abs}(\operatorname{abs}(x))=\operatorname{abs}(x)</math> for all <math>x</math>}};
* [[Constant function|constant]] functions are idempotent;
* the [[identity function]] is idempotent;
* the [[Floor and ceiling functions|floor]], [[Floor and ceiling functions|ceiling]] and [[fractional part]] functions are idempotent;
* the real part function <math>\mathrm{Re}(z)</math> of a [[complex number]], is idempotent.
* the [[Generating set of a group|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 [[Real number|reals]] to itself is idempotent;
* the [[Closure (topology)|closure]] and [[Interior (topology)|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 [[endomorphism]]s of a [[vector space]] are its [[Projection (linear algebra)|projections]].

If the set <math>E</math> has <math>n</math> elements, we can partition it into <math>k</math> chosen fixed points and {{nowrap|<math>n-k</math>}} non-fixed points under <math>f</math>, and then <math>k^{n-k}</math> is the number of different idempotent functions. Hence, taking into account all possible partitions,
: <math>\sum_{k=0}^n {n \choose k} k^{n-k}</math>
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, ... {{OEIS|A000248}}.

Neither the property of being idempotent nor that of being not is preserved under function composition.{{efn |If <math>f</math> and <math>g</math> commute under composition (i.e. if {{nowrap|1=<math>f\circ g=g\circ f</math>}}) then idempotency of both <math>f</math> and <math>g</math> implies that of {{nowrap|<math>f\circ g</math>}}, since {{nowrap|1=<math>(f\circ g)\circ (f\circ g)=f\circ (g\circ f)\circ g=f\circ (f\circ g)\circ g=(f\circ f)\circ (g\circ g)=f\circ g</math>}}, using the associativity of composition.}} As an example for the former, {{nowrap|1=<math>f(x)=x</math>}} [[modular arithmetic|mod]] 3 and <math>g(x)=\max(x, 5)</math> are both idempotent, but {{nowrap|<math>f\circ g</math>}} is not,{{efn |e.g. <math>f(g(7))=f(7)=1</math>, but <math>f(g(1))=f(5)=2\neq 1</math>}} although {{nowrap|<math>g\circ f</math>}} happens to be.{{efn |Also showing that commutation of <math>f</math> and <math>g</math> is not a [[necessary condition]] for idempotency preservation.}} As an example for the latter, the negation function <math>\neg</math> on the Boolean domain is not idempotent, but {{nowrap|<math>\neg\circ\neg</math>}} is. Similarly, unary negation {{nowrap|<math>-(\cdot)</math>}} of real numbers is not idempotent, but  {{nowrap|<math>-(\cdot)\circ -(\cdot)</math>}} is. In both cases, the composition is simply the [[identity function]], which is idempotent.

== Computer science meaning ==
{{See also|Referential transparency|Reentrant (subroutine)|Stable sort|Command query separation}}
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 effect (computer science)|side effects]] is idempotent if multiple calls to the subroutine have the same effect on the system state as a single call, in other words if the function from the system state space to itself associated with the subroutine is idempotent in the mathematical sense given in [[#Definition|the definition]];
* in [[functional programming]], a [[pure function]] is idempotent if it is idempotent in the mathematical sense given in [[#Definition|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 non-idempotent operations, the algorithm may have to keep track of whether the operation was already performed or not.

=== Computer science examples ===
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, a request for changing a customer's address to XYZ is typically idempotent, because the final address will be the same no matter how many times the request is submitted. However, a customer request for placing an order is typically not idempotent since multiple requests will lead to multiple orders being placed. A request for canceling a particular order is idempotent because no matter how many requests are made the order remains canceled.

A sequence of idempotent subroutines where at least one subroutine is different from the others, however, is not necessarily idempotent if a later subroutine in the sequence changes a value that an earlier subroutine depends on—''idempotence is not closed under sequential composition''. For example, suppose the initial value of a variable is 3 and there is a subroutine 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 the step changing the 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.<!-- {{Citation needed|date=December 2017}} please discuss this on talk page before reinstating -->
<syntaxhighlight lang=c>
int x = 3;
void inspect() { printf("%d\n", x); }
void change() { x = 5; }
void sequence() { inspect(); change(); inspect(); }

int main() {
  sequence();  // prints "3\n5\n"
  sequence();  // prints "5\n5\n"
  return 0;
}
</syntaxhighlight>

In the [[Hypertext Transfer Protocol]] (HTTP), idempotence and [[Hypertext Transfer Protocol#Safe methods|safety]] are the major attributes that separate [[Hypertext Transfer Protocol#Request methods|HTTP methods]]. Of the major HTTP methods, GET, PUT, and DELETE should be implemented in an idempotent manner according to the standard, but POST doesn't need to be.<ref name="httpStd-methods">IETF, [http://tools.ietf.org/html/rfc7231#section-4.2.2 Hypertext Transfer Protocol (HTTP/1.1): Semantics and Content] {{webarchive|url=https://web.archive.org/web/20140608213403/http://tools.ietf.org/html/rfc7231 |date=2014-06-08 }}.  See also [[Hypertext Transfer Protocol|HyperText Transfer Protocol]].</ref> GET retrieves the state of a resource; PUT updates the state of a resource; and DELETE deletes a resource. As in the example above, reading data usually has no side effects, so it is idempotent (in fact [[wiktionary:nullipotent|''nullipotent'']]). Updating and deleting a given data are each usually idempotent as long as the request uniquely identifies the resource and only that resource again in the future. PUT and DELETE with unique identifiers reduce to the simple case of assignment to a variable of either a value or the null-value, 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.<ref>{{cite IETF|title=Hypertext Transfer Protocol (HTTP/1.1): Semantics and Content |rfc=7231 |section=4.2.2 |sectionname=Idempotent Methods |quote=It knows that repeating the request will have the same intended effect, even if the original request succeeded, though the response might differ.}}</ref>

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 [[load–store architecture]], instructions that might possibly cause a [[page fault]] are idempotent. So if a page fault occurs, the [[operating system]] 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.<ref>
[[John Ousterhout]].
[https://web.stanford.edu/~ouster/cgi-bin/cs140-spring14/lecture.php?topic=paging "Demand Paging"].
</ref><ref>
Marc A. de Kruijf.
[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.259.7708&rep=rep1&type=pdf "Compiler construction of idempotent regions and applications in architecture design"].
2012.
p. 10.
</ref>

When reformatting output, [[prettyprint|pretty-printing]] is expected to be idempotent. In other words, if the output is already "pretty", there should be nothing to do for the pretty-printer.{{Citation needed|date=March 2017}}

In [[service-oriented architecture]] (SOA), a multiple-step orchestration process composed entirely of idempotent steps can be replayed without side-effects if any part of that process fails.

Many operations that are idempotent often have ways to "resume" a process if it is interrupted{{snd}} ways that finish much faster than starting all over from the beginning. For example, [[upload#Resumability of file transfers|resuming a file transfer]], 
[[rsync|synchronizing files]],  creating a [[software build]], installing an application and all of its dependencies with a [[package manager]], etc.

== Applied examples ==
[[File:Colección de hombres cruzando.JPG|thumb|A typical crosswalk button is an example of an idempotent system.]]
Applied examples that many people could encounter in their day-to-day lives include [[elevator]] call buttons and [[crosswalk button]]s.<ref>{{cite web |url=http://www.nclabor.com/elevator/geartrac.pdf |title=Geared Traction Passenger Elevator Specification Guide Information/Instructions |work=NC Department Of Labor, Elevator Bureau |year=2002 |archive-url=https://web.archive.org/web/20110523081716/http://www.nclabor.com/elevator/geartrac.pdf |archive-date=2011-05-23 |url-status=dead}} For example, this design specification includes detailed algorithm for when elevator cars will respond to subsequent calls for service</ref> 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.

Similarly, the elevator "close" button may be pressed many times to the same effect as once, since the doors close on a fixed  schedule – unless the "open" button is pressed. The "open" button is not idempotent, because each press adds further delay.

== See also ==
* [[Biordered set]]
* [[Closure operator]]
* [[Fixed point (mathematics)]]
* [[Idempotent of a code]]
* [[Idempotent analysis]]
* [[Idempotent matrix]]
* [[Idempotent relation]]{{snd}} a generalization of idempotence to binary relations
* [[Idempotent (ring theory)]]
* [[Involution (mathematics)]]
* [[Iterated function]]
* [[List of matrices]]
* [[Nilpotent]]
* [[Pure function]]
* [[Referential transparency]]

== Notes ==
{{Notelist}}

== References ==
{{Reflist |30em}}

== Further reading ==
{{Refbegin |30em}}
*{{citation
 |author=Goodearl, K. R.
 |title=von Neumann regular rings
 |edition=2
 |publisher=Robert E. Krieger Publishing Co. Inc.
 |place=Malabar, FL
 |year=1991
 |pages=xviii+412
 |isbn=978-0-89464-632-4
 |mr=1150975}}
* {{citation | last=Gunawardena | first=Jeremy | chapter=An introduction to idempotency | zbl=0898.16032 | editor1-last=Gunawardena | editor1-first=Jeremy | title=Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994 | location=Cambridge | publisher=[[Cambridge University Press]] | pages=1–49 | year=1998 | chapter-url=http://www.hpl.hp.com/techreports/96/HPL-BRIMS-96-24.pdf }}
* {{springer|title=Idempotent|id=p/i050080}}
*{{citation
 |author1=Hazewinkel, Michiel
 |author-link=Hazewinkel, Michiel
 |author2=Gubareni, Nadiya
 |author3=Kirichenko, V. V.
 |title=Algebras, rings and modules. vol. 1
 |series=Mathematics and its Applications
 |volume=575
 |publisher=Kluwer Academic Publishers
 |place=Dordrecht
 |year=2004
 |pages=xii+380
 |isbn=978-1-4020-2690-4
 |mr=2106764}}
*{{citation
 |author=Lam, T. Y.
 |title=A first course in noncommutative rings
 |series=Graduate Texts in Mathematics
 |volume=131
 |edition=2
 |publisher=Springer-Verlag
 |place=New York
 |year=2001
 |pages=xx+385
 |isbn=978-0-387-95183-6
 |mr=1838439
 |doi=10.1007/978-1-4419-8616-0}}
* {{Lang Algebra|edition=3}} p.&nbsp;443
* Peirce, Benjamin. [http://legacy-www.math.harvard.edu/history/peirce_algebra/ ''Linear Associative Algebra''] 1870.
* {{citation |last1=Polcino Milies |ref={{harvid|Polcino|Sehgal|2002}} |last2=Sehgal |first2=Sudarshan K. |first1=César |title=An Introduction to Group Rings |series=Algebras and Applications |url=https://books.google.com/books?id=7m9P9hM4pCQC&q=Idempotence&pg=PA127 |volume=1 |publisher=Kluwer Academic Publishers |place= |year=2002 |pages=[https://books.google.com/books?id=7m9P9hM4pCQC&q=Idempotence&pg=PA127 127] |isbn=978-1-4020-0238-0 |mr=1896125 |doi=}}
{{Refend}}

==External links==
{{Wikibooks}}
{{Wikiversity |Portal:Computer Science}}
* "[http://foldoc.org/idempotent idempotent]" at the [[Free On-line Dictionary of Computing]]

{{Subject bar |auto=0 |wikt=idempotence |portal1=Mathematics }}

[[Category:Properties of binary operations]]
[[Category:Algebraic properties of elements]]
[[Category:Closure operators]]
[[Category:Mathematical relations]]
[[Category:Theoretical computer science]]