A relation R:A→A is the same as a digraph with vertices A.
Reflexivity: R is reflexive when ?x∈A.xRx Every vertex in R has a self-loop.Irreflexivity: R is irreflexive when NOT[?x∈A.xRx] There are no self-loops in R.Symmetry: R is symmetric when ?x,y∈A.xRy implies yRx If there is an edge from x to y in R, then there is an edge back from y to x as well.Asymmetry: R is asymmetric when ?x,y∈A.xRy implies not(yRx) There is at most one directed edge between any two vertices in R, and there are no self-loops.Antisymmetry: R is antisymmetric when ?x≠y∈A.xRy implies not(yRx) There is at most one directed edge between any two distinct vertices, but there may be self-loopsTransitivity: R is transitive when ?x,y,z∈A.(xRy AND yRz) implies xRz If there is a positive length path from u to v, then there is an edge from u to v.Linear: R is linear when ?x≠y∈A.(xRy OR yRx) Given any two vertices in R, there is an edge in one direction or the other between them. For any finite, nonempty set of vertices of R, there is a directed path going through exactly these vertices.Strict Partial Order R is a strict partial order iff R is transitive and irreflexive iff R is transitive and asymmetric iff it is the positive length walk relation of a DAG.Weak Partial Order R is a weak partial order iff R is transitive and anti-symmetric and reflexive iff R is the walk relation of a DAG.Equivalence Relation R is an equivalence relation iff R is reflexive, symmetric and transitive iff R equals the in-the-same-block-relation for some partition of domain(R).
Reference
[1] Lehman E, Leighton F H, Meyer A R. Mathematics for Computer Science[J]. 2015.
