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.[1][2] This notion generalizes that of an idempotent function to relations.
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 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[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.
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[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 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.[6]
References[edit]
- ^ Florian Kammüller, J. W. Sanders (2004). Idempotent Relation in Isabelle/HOL (PDF) (Technical report). TU Berlin. p. 27. 2004-04. Archived from the original (PDF) on 2014-05-12. Retrieved 2014-05-10. Here:p.3
- ^ Florian Kammüller (2011). "Mechanical Analysis of Finite Idempotent Relations" (PDF). Fundamenta Informaticae. 107: 43–65. doi:10.3233/FI-2011-392.
- ^ Gunter Schmidt (2011) Relational Mathematics, page 212, Cambridge University Press ISBN 978-0-521-76268-7
- ^ Florian Kammüller (2006). "Number of idempotent relations on n labeled elements". The On-Line Encyclopedia of Integer Sequences (A12137).
- ^ Florian Kammüller (2008). Counting Idempotent Relations (PDF) (Technical report). TU Berlin. p. 27. 2008-15.
- ^ Clontz, Steven; Varagona, Scott (2018). "Mahavier Products, Idempotent Relations, and Condition Γ". arXiv:1805.06827 [math.GN].
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.