Discrete Mathematics Lecture # 14 Types of Relations Reflexive Relation Let R be a relation on a set A. R is reflexive if, and only if, for all a A, (a, a) R. Or equivalently aRa. That is, each element of A is related to itself.

Remark R is not reflexive iff there is an element a in A such that (a, a) R. That is, some element a of A is not related to itself. Example Let A = {1, 2, 3, 4} and define relations R1,R2, R3, R4 on A as follows: 1. 2. 3. 4.

R1 = R2 = R3 = (4, 4)} R4 = {(1, 1), (3, 3), (2, 2), (4, 4)} {(1, 1), (1, 4), (2, 2), (3, 3), (4, 3)} {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), {(1, 3), (2, 2), (2, 4), (3, 1), (4, 4)} Solution 1. R1 is reflexive, since (a, a) R1 for all a A. 2.

R2 is not reflexive, because (4, 4) R2. 3. R3 is reflexive, since (a, a) R3 for all a A. 4. R4 is not reflexive, because (1, 1) R4, (3, 3) R4 Directed Graph of Reflexive Relation The directed graph of every reflexive relation includes an arrow from every point to the point itself. Solution R2 = {(1, 1), (1, 4), (2, 2), (3, 3), (4, 3)}

1 2 4 3 1 R1 is reflexive because at every point of the set A we have a loop in the graph. 2 4 3

R2 is not reflexive, as there is no loop at 4. 1 1 2 2 Solution R1 = {(1, 1), (3, 3), (2, 2), (4, 4)} 1 2 4

3 1 R1 is reflexive because at every point of the set A we have a loop in the graph. 2 4 3 R2 is not reflexive, as there is no loop at 4. 1

1 2 2 Solution R3 = {(1, 1), 1 2 4 3 1

R1 is reflexive because at every point of the set A we a loop graph. (1,have 2), (2,in the 1), (2, 2 4 3 2), (3, 3), (4, 4)} R2 is not reflexive, as there

is no loop at 4. 1 1 2 2 3 4 R3 is reflexive 3 4 R4 is not reflexive, as there are

no loops at 1and 3. 1 4 1 2 2 Solution 3 R1 is reflexive because at every point of the set A we R = {(1,

have a loop in the4graph. 4 3 3), (2, 2), (2, 4), (3, 1), (4, 4)} R2 is not reflexive, as there is no loop at 4. 1 1 2 2 3

4 R3 is reflexive 3 4 R4 is not reflexive, as there are no loops at 1and 3. Matrix Representation of Reflexive Relation Let A = {a1, a2, , an}. A Relation R on A is reflexive if and only if (ai, aj) R i=1,2, ,n. Accordingly,

R is reflexive if all the elements on the main diagonal of the matrix M representing R are equal to 1. Example The relation R = {(1,1), (1,3), (2,2), (3,2), (3,3)} on A = {1,2,3} represented by the following matrix M, is reflexive. Symmetric Relation Let R be a relation on a set A. R is symmetric if, and only if, for all a, b A, if (a, b) R then (b, a) R. That R

is, if aRb then bRa. is not symmetric iff there are elements a and b in A such that (a, b) R but (b, a) R. Example Let A = {1, 2, 3, 4} and define relations R1, R2, R3, and R4on A as follows. 1. 2. 3. 4. R1 R2 R3

R4 = = = = {(1, {(1, {(2, {(1, 1), 1), 2), 1), (1, (2,

(2, (2, 3), 2), 3), 2), (2, (3, (3, (3, 4), (3, 1), (4,2)} 3), (4, 4)} 4)} 3), (4, 3), (4, 4)} Solution

1. 2. 3. 4. Then R1 is symmetric. R2 is also symmetric we say it is vacuously true. R3 is not symmetric, because (2,3) R3 but (3,2) R3. R4 is not symmetric because (4,3) R4 but (3,4) R4. Directed Graph of Symmetric Relation For a symmetric directed graph whenever there is an arrow going from one point of the graph to a second, there is an arrow going from the second point back to the first.

Solution R1 = {(1, 1), (1, 3), (2, 4), (3, 1), (4,2)} 2 1 4 3 R1 is symmetric 1 2 4

R2 is symmetric 3 Solution R2 = {(1, 1), (3, 3), (2, 2), (4, 4)} 2 1 4 3 R1 is symmetric 1 2

4 R2 is symmetric 3 Solution R3 = {(2, 2), (2, 3), (3, 4)} 1 1 2 4 3 R3 is not symmetric since there are arrows from 2 to 3 and from 3 to 4 but not conversely

4 2 3 R4 is not symmetric since there is an arrow from 4 to but no arrow from 3 to 4 Solution R4= {(1, 1), (2, 2), (3, 3), (4, 3), (4, 4)} 1 1

2 4 3 R3 is not symmetric since there are arrows from 2 to 3 and from 3 to 4 but not conversely 4 2 3 R4 is not symmetric since there is an arrow from 4 to 3 but no arrow from 3 to 4

Matrix Representation of Symmetric Relation Let A = {a1, a2, , an}. A relation R on A is symmetric if and only if for all ai, aj A, if (ai, aj) R then (aj, ai)R. Accordingly, R is symmetric if the elements in the ith row are the same as the elements in the ith column of the matrix M representing R. More Mt

precisely, M is a symmetric matrix.i.e. M = Example The on relation R = {(1,3), (2,2), (3,1), (3,3)} A = {1,2,3} represented by the following matrix M is symmetric. Transitive Relation Let R be a relation on a set A.R is transitive if and only if for all a, b, c A, if (a, b) R and (b, c) R then (a, c) R. That

is, if aRb and bRc then aRc. In words, if any one element is related to a second and that second element is related to a third, then the first is related to the third. Note that the first, second and third elements need not to be distinct. Remark R is not transitive iff there are elements a, b, c in A such that

If (a,b) R and (b,c) R but (a,c) R. Example Let A = {1, 2, 3, 4} and define relations R1, R2 and R3 on A as follows: 1. 2. 3. R1 = {(1, 1), (1, 2), (1, 3), (2, 3)} R2 = {(1, 2), (1, 4), (2, 3), (3, 4)} R3 = {(2, 1), (2, 4), (2, 3), (3,4)}

Solution 1. Then R1 is transitive because (1, 1), (1, 2) are in R then to be transitive relation (1,2) must be there and it belongs to R Similarly for other order pairs. 2. R2 is not transitive since (1,2) and (2,3) R2 but (1,3) R2. 3. R3 is transitive. DIRECTED GRAPH OF A TRANSITIVE RELATION

For a transitive directed graph, whenever there is an arrow going from one point to the second, and from the second to the third, there is an arrow going directly from the first to the third. Example Let R2 1. 2. 3. A = {1, 2, 3, 4} and define relations R1, and R3 on A by the directed graphs: R1 = {(1, 1), (1, 2), (1, 3), (2, 3)} R2 = {(1, 2), (1, 4), (2, 3), (3, 4)}

R3 = {(2, 1), (2, 4), (2, 3), (3,4)} Solution R1 = {(1, 1), (1, 2), (1, 3), (2, 3)} 1 1 2 4 4 3 R1 is transitive 1 4

2 3 R2 is not transitive since there is an arrow from 1 to 2 and from 2 to 3 but no arrow from 1 to 3 directly 2 3 Solution R2 = {(1, 2), (1, 4), (2, 3), (3, 4)} 1 1

2 4 4 3 R1 is transitive 1 4 2 2 3

R2 is not transitive since there is an arrow from 1 to 2 and from 2 to 3 but no arrow from 1 to 3 directly 1 1 2 Solution R3 = {(2, 1), (2, 4), (2, 3), (3,4)} 4 3 R1 is transitive

4 3 R3 is transitive 3 R2 is not transitive since there an arrow from 1 to 2 and from to 3 but no arrow from 1 to 3 directly 2 1 4 2

Exercise Let A = {1, 2, 3, 4} and define the null relation and universal relation A A on A. Test these relations for reflexive, symmetric and transitive properties. Solution Reflexive: 1. 2. is not reflexive since (1,1), (2,2), (3,3), (4,4) . A A is reflexive since (a,a) A A for all a A. Solution Symmetric

For the null relation on A to be symmetric, it must satisfy the implication: if (a,b) then (a, b) . Since (a, b) is never true, the implication is vacuously true or true by default. Hence is symmetric. 2. The universal relation A A is symmetric, for it contains all ordered pairs of elements of A. Thus, if (a, b) A A then (b, a) A A for all a, b in A. 1. Solution Transitive 1. The null relation on A is transitive, because the implication. if (a, b) and (b, c) then (a, c) is true by default,

since the condition (a, b) is always false. 2. The universal relation A A is transitive for it contains all ordered pairs of elements of A. Accordingly, if (a, b) A A and (b, c) A A then (a, c) A A as well. Exercise Let A = {0, 1, 2} and R = {(0,2), (1,1), (2,0)} be a relation on A. 1. 2. Is R reflexive? Symmetric? Transitive? Which ordered pairs are needed in R to make it a reflexive and transitive relation.

Solution R is not reflexive, since 0 A but (0, 0) R and also 2 A but (2, 2) R. R is clearly symmetric. R is not transitive, since (0, 2) & (2, 0) R but (0, 0) R. 1. For R to be reflexive, it must contain ordered pairs (0,0) and (2,2). For R to be transitive, we note (0,2) and (2,0) but (0,0) R. Also (2,0) and (0,2) R but (2,2)R. 2. Hence (0,0) and (2,2). Are needed in R to make it a transitive relation.

Exercise Define a relation L on the set of real numbers R be defined as follows: for all x, y R, x L y x < y. 1. Is L reflexive? 2. Is L symmetric? 3. Is L transitive? Solution 1. L is not reflexive, because x < x for any real number x. (e.g. 1 < 1) 2.

L is not symmetric, because for all x, y R, if x < y then y < x (e.g. 0 < 1 but 1 < 0) 3. L is transitive, because for all, x, y, z R, if x < y and y < z, then x < z. (by transitive law of order of real numbers). Exercise Define a relation R on the set of positive integers Z+ as follows: for all a, b Z+, a R b iff a b is odd. Determine whether the relation is 1. reflexive 2. symmetric 3. transitive

Solution Firstly, recall that the product of two positive integers is odd if and only if both of them are odd. Reflexive R is not reflexive, because 2 Z+ but 2 R 2 for 2 2 = 4 which is not odd. Symmetric R is symmetric, because if a R b then a b is odd or equivalently b a is odd ( b a = a b) b R a.

Solution Transitive R is transitive, because if a R b then a b is odd both a and b are odd. Also bRc means b c is odd both b and c are odd. Now if aRb and bRc, then all of a, b, c are odd and so a c is odd. Consequently aRc. Exercise Let

D be the divides relation on Z defined as: for all m, n Z, m D n m|n Determine whether D is reflexive, symmetric or transitive. Justify your answer. Solution Reflexive Let m Z, since every integer divides itself so m|m m Z therefore m D m m Z Accordingly D is reflexive

Solution Symmetric Let m, n Z and suppose m D n. By definition of D, this means m|n (i.e.= an integer) Clearly, then it is not necessary that = an integer. Accordingly, if m D n then n D m, m, n Z Hence D is not symmetric.

Solution Transitive Let m, n, p Z and suppose m D n and n D p. Now m D n m|n = an integer. Also n D p n|p = an integer. We note p =m p * n n = (an int) * (an int)

m = an int m|p and so mDp Thus if mDn and nDp then mDp m, n, p Z Hence D is transitive. Exercise Let A be the set of people living in the world today. A binary relation R is defined on A as follows: for all p, q A, pRq p has the same first name as q. Determine whether the relation R is reflexive, symmetric and/or transitive.

Solution Reflexive Since every person has the same first name as his/her self. Hence for all p A, pRp. Thus, R is reflexive. Symmetric: Let p, q A and suppose pRq. p has the same first name as q. q has the same first name as p. q R p Thus if pRq then qRp p,q A. R is symmetric.

Solution Transitive Let p, q, s A and suppose p R q and qRr. Now pRq p has the same first name as q and qRr q has the same first name as r. Consequently, p has the same first name as r. pRr Thus, if pRq and qRs then pRr, p, q, r A. Hence R is transitive

Equivalence Relation Let A be a non-empty set and R a binary relation on A. R is an equivalence relation if, and only if, R is reflexive, symmetric, and transitive. Example Let A = {1, 2, 3, 4} and R = {(1,1), (2,2), (2,4), (3,3), (4,2), (4,4)} be a binary relation on A. Note that R is reflexive, symmetric and transitive, hence an equivalence relation. Congruences Let

m and n be integers and d be a positive integer. The notation m n (mod d) means that d | (m n) {d divides m minus n} There exists an integer k such that (m n) = d k Example 1. 2. 3. 4.

Is Is Is Is 22 1(mod 3)? 5 +10 (mod 3)? 7 7 (mod 3)? 14 4 (mod 3)? Solution 1. Since 22-1 = 21 = 37. Hence 3|(22-1), and so 22 1 (mod 3) 2. Since 5 10 = - 15 = 3 (-5), Hence 3|((-5)-10), and so - 5 10 (mod 3) 3.

Since 7 7 = 0 = 3 0 Hence 3|(7-7), and so 7 7 (mod 3) 4. Since 14 4 = 10, and 3 / 10 because 10 3 k for any integer k. Hence 14 4 (mod 3). Exercise Define a relation R on the set of all integers Z as follows: for all integers m and n, m R n m n (mod 3) Prove that R is an equivalence relation.

Solution R R is reflexive. is reflexive iff for all m Z, m R m. By definition of R, this means that For all m Z, m m (mod 3) Since m m = 0 = 3 0. Hence 3|(m-m), and so m m (mod 3) mRm R is reflexive. Solution R is symmetric.

R is symmetric iff for all m, n Z if m R n then n R m. Now mRn mn (mod 3) 3|(m-n) m-n = 3k, for some integer k. n m = 3(-k), -k Z 3|(n-m) n m (mod 3) nRm

Hence R is symmetric. Solution R is transitive R is transitive iff for all m, n, p Z, if mRn and nRp then mRp Now mRn and nRp means m n (mod 3) and n p (mod 3) 3|(m-n) and 3|(n-p) (m-n) = 3r and (n-p) = 3s for some r, s Z Adding these two equations, we get,

(m n) + (n p) = 3 r + 3 s m p = 3 (r + s),where r + s Z 3|(m p) m p (mod 3) m Rp Hence R is transitive.R being reflexive, symmetric and transitive, is an equivalence relation.