Contents

Idempotent relation

Definition[edit]

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 zinX whenever there exists yinX 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 Radense relation.^[3]

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

Examples[edit]

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.

Anouter 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[edit]

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.^[4][5]

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 ${\displaystyle \langle x,x\rangle ,\langle x,y\rangle ,\langle y,y\rangle }$ for some ${\displaystyle x,y}$. 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.^[6]

References[edit]

Further reading[edit]

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Codes and automata. Encyclopedia of Mathematics and its Applications. Vol. 129. Cambridge: Cambridge University Press. p. 330. ISBN 978-0-521-88831-8. Zbl 1187.94001.