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 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, 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.

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 numbers 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 integers 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 [math]\displaystyle{ \langle x,x\rangle, \langle x,y\rangle,\langle y,y\rangle }[/math] for some [math]\displaystyle{ x,y }[/math]. This is used to show that certain subspaces of an uncountable product of spaces, known as Mahavier products, cannot be metrizable when defined by a nontrivial idempotent relation.

Further reading

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes and automata. Encyclopedia of Mathematics and its Applications. 129. Cambridge: Cambridge University Press. p. 330. ISBN 978-0-521-88831-8. http://www-igm.univ-mlv.fr/~berstel/LivreCodes/Codes.html.