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 ter ...
(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 typ ...
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 tha ...
(in which it is connected to the property of
referential transparency).
The term was introduced by American mathematician
Benjamin Peirce 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.
Monoid ...
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
Multiplication (often denoted by the Multiplication sign, cross symbol , by the mid-line #Notation and terminology, dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four Elementary arithmetic, elementary Op ...
, 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 ...
+) 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
Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or '' sum'' ...
, 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 natura ...
, an
identity element or an
absorbing element , if it exists, is idempotent. Indeed, and .
* In a
group , 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 of
.
* In the monoids
and
of the
power set 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 respectively,
and
are idempotent. Indeed, , and .
* In the monoids
and
of the
Boolean domain 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 ...
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 ...
respectively,
and
are idempotent. Indeed, , and .
* In a
Boolean ring, multiplication is idempotent.
* In a
Tropical semiring, 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 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 or ...
.
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), ...
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 ca ...
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 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 poin ...
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
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 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 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 ...
, 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, consequenc ...
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 definiti ...
;
* 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 tha ...
, 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 ar ...
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 definiti ...
.
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 ...
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 We ...
(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 di ...
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 We ...
. 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, 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
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 daemon (computing), services for computer programs.
Time-sharing operating systems scheduler (computing), schedule tasks for ef ...
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 provid ...
(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 ...
, installing an application and all of its dependencies with a
package manager, 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 ...
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 ...
*
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)
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. The lack of an additive inverse in the semiring is compensated somewhat by the idempotent rule A \oplus A = A.
References
*
...
*
Idempotent matrix
*
Idempotent relation 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
*
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 cl ...
*
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 ar ...
*
Referential transparency
References
Further reading
*
idempotent at the
Free On-line Dictionary of Computing
*
*
*
*
*
* 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