Properties of Relations
I often want a list of properties that can obtain for two-place relations and don’t have a good place to look them up. Here is an ongoing list.
First, some notation. Consider a relation R on a (possibly infinite) set X. That is:
R: X→X
Equivalence Properties
A relation R is an equivalence relation if and only if R is reflexive, symmetric, and transitive.
R is reflexive iff ∀x∈X(Rxx)
R is symmetric iff ∀x,y∈X(Rxy → Ryx)
R is transitive iff ∀x,y,z∈X((Rxy ∧ Ryz) → Rxz)
Each of these properties also has variants:
R is irreflexive iff ∀x∈X(¬Rxx)
R is quasi-reflexive iff ∀x,y∈X(Rxy → (Rxx ∧ Ryy))
R is antisymmetric iff ∀x,y∈X((Rxy ∧ Ryx) → x=y)
R is antitransitive iff ∀x,y,z∈X((Rxy ∧ Ryz) → ¬Rxz)
Other Properties
R is connected iff ∀x,y∈X(Rxy ∨ Ryx)
R is right Euclidean iff ∀x,y,z∈X((Rxy ∧ Rxz) → Ryz)
R is left Euclidean iff ∀x,y,z∈X((Ryx ∧ Rzx) → Ryz)