Idempotent relation
From Wikipedia, the free encyclopedia
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.[1][2] This notion generalizes that of an idempotent function to relations.
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.[3]
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.
