Applications: Mathematical Proofs and Automated Reasoning 5.2.5 239 Special binary relations Definition 201 A binary relation R ⊆ X is called: • • • • • • • • • • • • • reflexive if it satisfies ∀x(xRx); irreflexive if it satisfies ∀x¬(xRx), that is, if X − R is reflexive; serial if it satisfies ∀x∃y (xRy ); functional if it satisfies ∀x∃!y (xRy ), where ∃!y means “there exists a unique y ;” symmetric if it satisfies ∀x∀y (xRy → yRx); asymmetric if it satisfies ∀x∀y (xRy → ¬yRx); antisymmetric if it satisfies ∀x∀y (xRy ∧ yRx → x = y ); connected if it satisfies ∀x∀y (xRy ∨ yRx ∨ x = y ); transitive if it satisfies ∀x∀y ∀z ((xRy ∧ yRz ) → xRz ); an equivalence relation if it is reflexive, symmetric, and transitive; euclidean if it satisfies ∀x∀y ∀z ((xRy ∧ xRz ) → yRz ); a pre-order (or quasi-order) if it is reflexive and transitive; a partial order if it is reflexive, transitive, and antisymmetric, that is, an antisymmetric pre-order; • a strict partial order if it is irreflexive and transitive; • a linear order (or total order) if it is a connected partial order; or • a strict linear order (or strict total order) if it is a connected strict partial order Proposition 202 For any set X and binary relation R ⊆ X : (a) R is reflexive iff EX ⊆ R; (b) R is symmetric iff R−1 ⊆ R iff R−1 = R; (c) R is asymmetric iff R−1 ∩ R = ∅; (d) R is antisymmetric iff R−1 ∩ R ⊆ EX ; (e) R is connected iff R ∪ R−1 ∪ EX = X ; (f) R is transitive iff R2 ⊆ R Functions can be regarded as special type of relations by means of their graphs: the graph of a function f : A → B can be defined as the binary relation Gf ⊆ A × B where Gf = {(a, f (a)) | a ∈ A} A relation R ⊆ A × B is therefore functional iff it is the graph of a function from A to B (exercise) Let R ⊆ X × X be a binary relation on a set X Then • the reflexive closure of R is the smallest by inclusion reflexive binary relation Rref on X such that R ⊆ Rref ; • the symmetric closure of R is the smallest by inclusion symmetric binary relation Rsym on X such that R ⊆ Rsym ; and • the transitive closure of R is the smallest by inclusion transitive binary relation Rtran on X such that R ⊆ Rtran As an exercise, show that each of these closures always exists