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 generalizes that of an idempotent function to relations.

Definition

As a shorthand, the notation ''xRy'' indicates that a pair (''x'',''y'') belongs to a relation ''R''. The composition of relations ''R'' ∘ ''R'' is the relation ''S'' defined by setting ''xSz'' to be true for a pair of elements ''x'' and ''z'' in ''X'' whenever there exists ''y'' in ''X'' with ''xRy'' and ''yRz'' both true. ''R'' is idempotent if ''R'' = ''S''. Equivalently, relation ''R'' is idempotent if and only if the following two properties are true: *''R'' is a

transitive relation In mathematics, a relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each partial order as well as each equivalence relation needs to be transitive. Definition A ho ...

, meaning that ''R'' ∘ ''R'' ⊆ ''R''. Equivalently, in terms of individual elements, for every ''x'', ''y'', and ''z'' for which ''xRy'' and ''yRz'' are both true, ''xRz'' is also true. *''R'' ∘ ''R'' ⊇ ''R''. Equivalently, in terms of individual elements, for every ''x'' and ''z'' for which ''xRz'' is true, there exists ''y'' with ''xRy'' and ''yRz'' both true. Some authors call such an ''R'' a

dense relation In mathematics, a partial order or total order < on a set

X

is said to be dense if, for all

x

and

y

X< ...

. Because idempotence incorporates both transitivity and the second property above, it is a stronger property than transitivity.

Examples

For example, the relation < on the

rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...

s is idempotent. The strict ordering relation is transitive, and whenever two rational numbers ''x'' and ''z'' obey the relation ''x'' < ''z'' there necessarily exists another rational number ''y'' between them (for instance, their average) with ''x'' < ''y'' and ''y'' < ''z''. In contrast, the same ordering relation < on the

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

s is not idempotent. It is still transitive, but does not obey the second property of an idempotent relation. For instance, 1 < 2 but there does not exist any other integer ''y'' between 1 and 2. An outer product of logical vectors forms an idempotent relation. Such a relation may be contained in a more complex relation, in which case it is called a concept in that larger context. The description of relations in terms of their concepts is called formal concept analysis.

Uses

Idempotent relations have been used as an example to illustrate the application of Mechanized Formalisation of mathematics using the interactive theorem prover Isabelle/HOL. Besides checking the mathematical properties of finite idempotent relations, an algorithm for counting the number of idempotent relations has been derived in Isabelle/HOL. Idempotent relations defined on weakly countably compact spaces have also been shown to satisfy "condition Γ": that is, every nontrivial idempotent relation on such a space contains points

\langle x,x\rangle, \langle x,y\rangle,\langle y,y\rangle

for some

x,y

. This is used to show that certain subspaces of an uncountable

product Product may refer to: Business * Product (business), an item that serves as a solution to a specific consumer problem. * Product (project management), a deliverable or set of deliverables that contribute to a business solution Mathematics * Produ ...

of spaces, known as Mahavier products, cannot be

metrizable In topology and related areas of mathematics, a metrizable space is a topological space that is homeomorphic to a metric space. That is, a topological space (X, \mathcal) is said to be metrizable if there is a metric d : X \times X \to , \infty) s ...

when defined by a nontrivial idempotent relation.

Definition

Examples

Uses

References

Further reading