• Definition: Let R be a binary relation on A. • R is reflexive if for all x ∈ A, (x,x) ∈ R. (Equivalently, for all x e A, x R x.) • R is symmetric if for all x,y ∈ A, (x,y) ∈ R implies (y,x) ∈ R. (Equivalently, for all x,y ∈ A, x R y implies that y R x.) • R is transitive if for all x,y,z ∈ A, (x,y) ∈ R and (y,z) ∈ R implies (x,z) ∈ R. (Equivalently, for all x,y,z ∈ A, x R y and y R z implies x R z.)10.2.2

Examples • Reflexive: The relation R on {1,2,3} given by R = {(1,1), (2,2), (2,3), (3,3)} is reflexive. (All loops are present.) • Symmetric: The relation R on {1,2,3} given by R = {(1,1), (1,2), (2,1), (1,3), (3,1)} is symmetric. (All paths are 2-way.) • Transitive: The relation R on {1,2,3} given by R = {(1,1), (1,2), (2,1), (2,2), (2,3), (1,3)} is transitive. (If I can get from one point to another in 2 steps, then I can get there in 1 step.)10.2.3

• Why is R = {(1,1), (2,2), (3,3)} not reflexive on {1,2,3,4}? Because (4,4) is missing. • Why is R = {(1,2), (2,1), (3,1)} not symmetric? Because (1,3) is missing. • Why is R = {(1,2), (2,3), (1,3), (2,1)} not transitive? Because (1,1) and (2,2) are missing. • Is {(1,1), (2,2), (3,3)} symmetric? transitive? Yes! Yes!10.2.4

• Definition: Let R be a binary relation on a set A. The transitive closure of R is the binary relation R t on A satisfying the following three properties: 1. R t is transitive; 2. R is a subset of R t ; 3. If S is any other transitive relation that contains R, then S contains R t . • In other words, the transitive closure of R is the smallest transitive relation containing R.10.2.5 Example of the Transitive Closure • Given the relation R on {1,2,3,4}, 1 2 4 3 its transitive closure is: 1 2 4 310.2.6

• Consider the Equality (=) relation on R: Equality is reflexive since for each x ∈ R, x = x. Equality is symmetric since for each x,y ∈ R, if x = y, then y = x. Equality is transitive since for each x,y,z ∈ R, if x = y and y = z, then x = z. • As a graph, the relation contains only loops, so symmetry and transitivity are vacuously satisfied!10.2.7 Properties of Congruence Mod p • Let p be an integer greater than 1, and consider the relation on Z given by: R = {(x,y) | x,y ∈ Z and x ≡ y mod p}. • When we say x ≡ y mod p, this means (x − y) = kp for some integer k. • Now, R is reflexive since (x − x) = 0 = 0p, for all integers x. • Moreover, R is symmetric, since if x ≡ y mod p, then (x − y) = kp, thus (y − x) = (−k)p, implying that y ≡ x mod p.10.2.8 Congruence Mod p (cont’d.) • Finally, R is transitive. Why? • Let x ≡ y mod p and y ≡ z mod p. This means there are integers k and j such that (x − y) = kp and (y − z) = jp. Hence, (x − z) = (x − y) + (y − z) = kp + jp = (k + j)p. Therefore, x ≡ z mod p.10.2.9

• Consider the Inequality (< or >) relation on R: Inequality is not reflexive since for no x ∈ R is it true that x < x.

x,y ∈ R, if x < y is true, then y < x is false. Inequality is transitive since for each x,y,z ∈ R, if x < y and y < z, then x < z. • Inequality is so pathelogically unsymmetric, that we define a special property to describe it.10.2.10

• Definition: A relation R on a set A is called anti- symmetric if (x,y) ∈ R and (y,x) ∈ R implies x = y. • This is equivalent to requiring that if x ≠ y and (x,y) ∈ R, then (y,x) ∉ R. (All streets are one- way.) • Example: R = {(1,1), (1,2), (3,2), (3,3)} is anti- symmetric. • Is every relation symmetric or anti-symmetric? • No! Consider R = {(1,2), (2,1), (1,3)}.