Idempotence (, ) is the property of certain
operations in
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 Applied science, practical discipli ...
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 groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...
(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 dete ...
s) and
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
(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
of a set
equipped with a binary operator
is said to be ''idempotent'' under
if
: .
The ''binary operation''
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.
Monoids ...
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 n ...
s with
multiplication
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
, 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.
Monoids ...
+) 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 n ...
s with
addition
Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...
, 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 ...
, 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 ...
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 ...
, 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 ...
, the identity element
is the only idempotent element. Indeed, if
is an element of
such that , then and finally
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
.
* In the monoids
and
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 po ...
of the set
with
set union
In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection. It is one of the fundamental operations through which sets can be combined and related to each other.
A refers to a union of ze ...
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 ...
respectively,
and
are idempotent. Indeed, , and .
* In the monoids
and
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 S ...
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 this ...
respectively,
and
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 s ...
, 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 and ...
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 this ...
is either 0 or 1. If the determinant is 1, the matrix neccessarily is the
identity matrix
In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere.
Terminology and notation
The identity matrix is often denoted by I_n, or simply by I if the size is immaterial o ...
.
Idempotent functions
In the monoid
of the functions from a set
to itself (see
set exponentiation) with
function composition
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
, idempotent elements are the functions such that , that is such that (in other words, the image
of each element
is a
fixed point of
). For example:
* the
absolute value
In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), an ...
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
A floor is the bottom surface of a room or vehicle. Floors vary from simple dirt in a cave to many layered surfaces made with modern technology. Floors may be stone, wood, bamboo, metal or any other material that can support the expected load ...
,
ceiling
A ceiling is an overhead interior surface that covers the upper limits of a room. It is not generally considered a structural element, but a finished surface concealing the underside of the roof structure or the floor of a story above. Ceilings ...
and
fractional part
The fractional part or decimal part of a non‐negative real number x is the excess beyond that number's integer part. If the latter is defined as the largest integer not greater than , called floor of or \lfloor x\rfloor, its fractional part can ...
functions are idempotent;
* the
subgroup generated function from the power set of a group to itself is idempotent;
* the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
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 relate ...
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 points ...
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 c ...
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 c ...
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 g ...
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
has
elements, we can partition it into
chosen fixed points and non-fixed points under
, and then
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
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
are both idempotent, but is not, although happens to be. 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. 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 Applied science, practical discipli ...
, 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 c ...
, a
subroutine
In computer programming, a function or subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed.
Functions may ...
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
A definition is a statement of the meaning of a term (a word, phrase, or other set of symbols). Definitions can be classified into two large categories: intensional definitions (which try to give the sense of a term), and extensional definitio ...
;
* in
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
, 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 argument ...
is idempotent if it is idempotent in the mathematical sense given in the
definition
A definition is a statement of the meaning of a term (a word, phrase, or other set of symbols). Definitions can be classified into two large categories: intensional definitions (which try to give the sense of a term), and extensional definitio ...
.
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 sp ...
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 risk management, the control of recognized hazards in order to achieve an acceptable level of risk.
Meanings
There are ...
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 to 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 in ...
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 wire rope, cable-assisted, hydraulic cylinder-assisted, or roller-track assisted machine that vertically transports people or freight between floors, levels, or deck (building), decks of a building, watercraft, ...
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 dete ...
*
Fixed point (mathematics)
A fixed point (sometimes shortened to fixpoint, also known as an invariant point) is a value that does not change under a given transformation. Specifically, in mathematics, a fixed point of a function is an element that is mapped to itself by th ...
*
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 this ...
*
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)
In mathematics, an involution, involutory function, or self-inverse function is a function that is its own inverse,
:
for all in the domain of . Equivalently, applying twice produces the original value.
General properties
Any involution i ...
*
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
This article lists some important classes of matrices used in mathematics, science and engineering. A matrix (plural matrices, or less commonly matrixes) is a rectangular array of numbers called ''entries''. Matrices have a long history of both st ...
*
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 class ...
*
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 argument ...
*
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 u ...
*
*
*
*
*
* 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