Idempotent relation


In mathematics, an idempotent binary relation is a binary relation R on a set X for which the composition of relations RR 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 belongs to a relation R.
The composition of relations RR 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:
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 z between them 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 for some. 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.