Idempotent Map
   HOME

TheInfoList



OR:

Idempotence (, ) is the property of certain operations in mathematics and
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
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 mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathematics), fields, module (mathe ...
(in particular, in the theory of
projector A projector or image projector is an optical device that projects an image (or moving images) onto a surface, commonly a projection screen. Most projectors create an image by shining a light through a small transparent lens, but some newer types ...
s and
closure operator In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S : Closure operators are de ...
s) and
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
(in which it is connected to the property of
referential transparency In computer science, referential transparency and referential opacity are properties of parts of computer programs. An expression is called ''referentially transparent'' if it can be replaced with its corresponding value (and vice-versa) withou ...
). The term was introduced by American mathematician
Benjamin Peirce Benjamin Peirce (; April 4, 1809 – October 6, 1880) was an American mathematician who taught at Harvard University for approximately 50 years. He made contributions to celestial mechanics, statistics, number theory, algebra, and the philoso ...
in 1870 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 + '' potence'' (same + power).


Definition

An element x of a set S equipped with a binary operator \cdot is said to be ''idempotent'' under \cdot if : . The ''binary operation'' \cdot is said to be ''idempotent'' if : .


Examples

* In the
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...
(\mathbb, \times) of the
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...
s with multiplication, only 0 and 1 are idempotent. Indeed, and . * In the
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...
(\mathbb, +) of the
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...
s with addition, only 0 is idempotent. Indeed, . * In a
magma Magma () is the molten or semi-molten natural material from which all igneous rocks are formed. Magma is found beneath the surface of the Earth, and evidence of magmatism has also been discovered on other terrestrial planets and some natural sa ...
(M, \cdot), an
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
e or an
absorbing element In mathematics, an absorbing element (or annihilating element) is a special type of element of a set with respect to a binary operation on that set. The result of combining an absorbing element with any element of the set is the absorbing element i ...
a, if it exists, is idempotent. Indeed, and . * In a
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
(G, \cdot), the identity element e is the only idempotent element. Indeed, if x is an element of G such that , then and finally x=e by multiplying on the left by the
inverse element In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers. Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
of x. * In the monoids (\mathcal(E), \cup) and (\mathcal(E), \cap) of the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
\mathcal(E) of the set E with set union \cup and
set intersection In set theory, the intersection of two sets A and B, denoted by A \cap B, is the set containing all elements of A that also belong to B or equivalently, all elements of B that also belong to A. Notation and terminology Intersection is writt ...
\cap respectively, \cup and \cap are idempotent. Indeed, , and . * In the monoids (\, \vee) and (\, \wedge) of the
Boolean domain In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include ''false'' and ''true''. In logic, mathematics and theoretical computer science, a Boolean domain is usually written as ...
with
logical disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...
\vee and
logical conjunction In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents thi ...
\wedge respectively, \vee and \wedge are idempotent. Indeed, , and . * In a
Boolean ring In mathematics, a Boolean ring ''R'' is a ring for which ''x''2 = ''x'' for all ''x'' in ''R'', that is, a ring that consists only of idempotent elements. An example is the ring of integers modulo 2. Every Boolean ring gives rise to a Boolean al ...
, multiplication is idempotent. * In a
Tropical semiring In idempotent analysis, the tropical semiring is a semiring of extended real numbers with the operations of minimum (or maximum) and addition replacing the usual ("classical") operations of addition and multiplication, respectively. The tropical ...
, addition is idempotent. * In a ring of quadratic matrices, the
determinant In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if a ...
of an
idempotent matrix In linear algebra, an idempotent matrix is a matrix which, when multiplied by itself, yields itself. That is, the matrix A is idempotent if and only if A^2 = A. For this product A^2 to be defined, A must necessarily be a square matrix. Viewed thi ...
is either 0 or 1. If the determinant is 1, the matrix neccessarily is the identity matrix.


Idempotent functions

In the monoid (E^E, \circ) of the functions from a set E to itself (see set exponentiation) with function composition \circ, idempotent elements are the functions such that , that is such that (in other words, the image f(x) of each element x\in E is a fixed point of f). For example: * the absolute value is idempotent. Indeed, , that is ; * constant functions are idempotent; * the
identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
is 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 In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related ...
over the reals to itself is idempotent; * the closure and interior functions of the power set of a
topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called po ...
to itself are idempotent; * the
Kleene star In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics, it is more commonly known as the free monoid ...
and
Kleene plus In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics, it is more commonly known as the free monoid ...
functions of the power set of a monoid to itself are idempotent; * the idempotent
endomorphism In mathematics, an endomorphism is a morphism from a mathematical object to itself. An endomorphism that is also an isomorphism is an automorphism. For example, an endomorphism of a vector space is a linear map , and an endomorphism of a gr ...
s of a
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
are its projections. If the set E has n elements, we can partition it into k chosen fixed points and non-fixed points under f, and then k^ is the number of different idempotent functions. Hence, taking into account all possible partitions, : \sum_^n k^ is the total number of possible idempotent functions on the set. The
integer sequence In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers. An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...
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, ... . Neither the property of being idempotent nor that of being not is preserved under function composition. As an example for the former,
mod Mod, MOD or mods may refer to: Places * Modesto City–County Airport, Stanislaus County, California, US Arts, entertainment, and media Music * Mods (band), a Norwegian rock band * M.O.D. (Method of Destruction), a band from New York City, US ...
3 and g(x)=\max(x, 5) are both idempotent, but is not, although happens to be. As an example for the latter, the negation function \neg on the Boolean domain is not idempotent, but is. Similarly, unary negation of real numbers is not idempotent, but is. In both cases, the composition is simply the
identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
, which is idempotent.


Computer science meaning

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, the term ''idempotence'' may have a different meaning depending on the context in which it is applied: * in
imperative programming In computer science, imperative programming is a programming paradigm of software that uses statements that change a program's state. In much the same way that the imperative mood in natural languages expresses commands, an imperative program ...
, a subroutine with
side effects In medicine, a side effect is an effect, whether therapeutic or adverse, that is secondary to the one intended; although the term is predominantly employed to describe adverse effects, it can also apply to beneficial, but unintended, consequence ...
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 the definition; * in
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
, a
pure function In computer programming, a pure function is a function that has the following properties: # the function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference argume ...
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 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 In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases s ...
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. int x = 3; void read() void change() void sequence() int main() In the
Hypertext Transfer Protocol The Hypertext Transfer Protocol (HTTP) is an application layer protocol in the Internet protocol suite model for distributed, collaborative, hypermedia information systems. HTTP is the foundation of data communication for the World Wide Web, ...
(HTTP), idempotence and
safety Safety is the state of being "safe", the condition of being protected from harm or other danger. Safety can also refer to the control of recognized hazards in order to achieve an acceptable level of risk. Meanings There are two slightly dif ...
are the major attributes that separate 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.IETF
Hypertext Transfer Protocol (HTTP/1.1): Semantics and Content
. See also
HyperText Transfer Protocol The Hypertext Transfer Protocol (HTTP) is an application layer protocol in the Internet protocol suite model for distributed, collaborative, hypermedia information systems. HTTP is the foundation of data communication for the World Wide Web, ...
.
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 ''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. 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 In computer science, stream processing (also known as event stream processing, data stream processing, or distributed stream processing) is a programming paradigm which views data streams, or sequences of events in time, as the central input and o ...
, 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 In computer engineering, a load–store architecture is an instruction set architecture that divides instructions into two categories: memory access ( load and store between memory and registers) and ALU operations (which only occur between regis ...
, instructions that might possibly cause a
page fault In computing, a page fault (sometimes called PF or hard fault) is an exception that the memory management unit (MMU) raises when a process accesses a memory page without proper preparations. Accessing the page requires a mapping to be added t ...
are idempotent. So if a page fault occurs, the
operating system An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs. Time-sharing operating systems schedule tasks for efficient use of the system and may also i ...
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. When reformatting output, 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. In
service-oriented architecture In software engineering, service-oriented architecture (SOA) is an architectural style that focuses on discrete services instead of a monolithic design. By consequence, it is also applied in the field of software design where services are provide ...
(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 ways that finish much faster than starting all over from the beginning. For example, resuming a file transfer, synchronizing files, creating a
software build In software development, a build is the process of converting source code files into standalone software artifact(s) that can be run on a computer, or the result of doing so. Functions Building software is an end-to-end process that involves m ...
, installing an application and all of its dependencies with a
package manager A package manager or package-management system is a collection of software tools that automates the process of installing, upgrading, configuring, and removing computer programs for a computer in a consistent manner. A package manager deals wi ...
, etc.


Applied examples

Applied examples that many people could encounter in their day-to-day lives include
elevator An elevator or lift is a cable-assisted, hydraulic cylinder-assisted, or roller-track assisted machine that vertically transports people or freight between floors, levels, or decks of a building, vessel, or other structure. They a ...
call buttons and crosswalk buttons.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 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

*
Biordered set A biordered set (otherwise known as boset) is a mathematical object that occurs in the description of the structure of the set of idempotents in a semigroup. The set of idempotents in a semigroup is a biordered set and every biordered set is the s ...
*
Closure operator In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S : Closure operators are de ...
* Fixed point (mathematics) * Idempotent of a code *
Idempotent analysis In mathematical analysis, idempotent analysis is the study of idempotent semirings, such as the tropical semiring In idempotent analysis, the tropical semiring is a semiring of extended real numbers with the operations of minimum (or maximum) and ...
*
Idempotent matrix In linear algebra, an idempotent matrix is a matrix which, when multiplied by itself, yields itself. That is, the matrix A is idempotent if and only if A^2 = A. For this product A^2 to be defined, A must necessarily be a square matrix. Viewed thi ...
*
Idempotent relation In mathematics, an idempotent binary relation is a binary relation ''R'' on a set ''X'' (a subset of Cartesian product ''X'' × ''X'') for which the composition of relations ''R'' ∘ ''R'' is the same as ''R''. This notion g ...
a generalization of idempotence to binary relations * Involution (mathematics) *
Iterated function In mathematics, an iterated function is a function (that is, a function from some set to itself) which is obtained by composing another function with itself a certain number of times. The process of repeatedly applying the same function is ...
* List of matrices *
Nilpotent In mathematics, an element x of a ring R is called nilpotent if there exists some positive integer n, called the index (or sometimes the degree), such that x^n=0. The term was introduced by Benjamin Peirce in the context of his work on the cla ...
*
Pure function In computer programming, a pure function is a function that has the following properties: # the function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference argume ...
*
Referential transparency In computer science, referential transparency and referential opacity are properties of parts of computer programs. An expression is called ''referentially transparent'' if it can be replaced with its corresponding value (and vice-versa) withou ...


References


Further reading

*
idempotent
at the
Free On-line Dictionary of Computing The Free On-line Dictionary of Computing (FOLDOC) is an online, searchable, encyclopedic dictionary of computing subjects. History FOLDOC was founded in 1985 by Denis Howe and was hosted by Imperial College London. In May 2015, the site was up ...
* * * * * * p. 443 * Peirce, Benjamin
''Linear Associative Algebra''
1870. * {{citation , author1=Polcino Milies , ref={{harvid, Polcino, Sehgal, 2002 , last2=Sehgal , first2=Sudarshan K. , first=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 , page
127
, isbn=978-1-4020-0238-0 , mr=1896125 , doi= Properties of binary operations Algebraic properties of elements Closure operators Mathematical relations Theoretical computer science