Idempotence (, ) is the property of certain
operations
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Man ...
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 whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of places in
abstract algebra (in particular, in the theory of
projectors and
closure operators) and
functional programming (in which it is connected to the property of
referential transparency).
The term was introduced by 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 of the
natural numbers 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 +) of the
natural numbers 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 , 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 and
logical conjunction 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 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 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 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 over the
reals to itself is idempotent;
* the
closure and
interior
Interior may refer to:
Arts and media
* ''Interior'' (Degas) (also known as ''The Rape''), painting by Edgar Degas
* ''Interior'' (play), 1895 play by Belgian playwright Maurice Maeterlinck
* ''The Interior'' (novel), by Lisa See
* Interior de ...
functions of the power set of a
topological space to itself are idempotent;
* the
Kleene star and
Kleene plus functions of the power set of a monoid to itself are idempotent;
* the idempotent
endomorphisms of a
vector space are its
projections.
If the set
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, which is idempotent.
Computer science meaning
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
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 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, a
pure function 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 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 (HTTP), idempotence and
safety 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. 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 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.
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 (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, 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 call buttons and
crosswalk button
A pedestrian crossing (or crosswalk in American English) is a place designated for pedestrians to cross a road, street or avenue. The term "pedestrian crossing" is also used in the Vienna and Geneva Conventions, both of which pertain to road si ...
s.
[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
*
Closure operator
*
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
In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detecti ...
*
Idempotent analysis
*
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
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
*
Pure function
*
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