Chapter 1.2 - Set Theory and Relations PDF

60 Set Theory and Relations 19 1.2.1 Definition. E3 Let A and B be two non-empty sets, then every subset of A × B defines a relation from A to B and every relation from A to B is a subset of A × B. Let R  A  B and (a, b)  R. Then we say that a is related to b by the relation R and write it as a R...

60 Set Theory and Relations 19 1.2.1 Definition. E3 Let A and B be two non-empty sets, then every subset of A × B defines a relation from A to B and every relation from A to B is a subset of A × B. Let R  A  B and (a, b)  R. Then we say that a is related to b by the relation R and write it as a R b. If (a, b)  R , we write it as a R b. ID Example: Let A = {1, 2, 5, 8, 9}, B = {1, 3} we set a relation from A to B as: a R b iff a  b; a  A, b  B. Then R = {(1, 1)}, (1, 3), (2, 3)}  A × B U (1) Total number of relations : Let A and B be two non-empty finite sets consisting of m and n elements respectively. Then A × B consists of mn ordered pairs. So, total number of subset of A × B is 2mn. Since each subset of A × B defines relation from A to B, so total number of relations from A to B is 2mn. Among these 2mn relations the void relation  and the universal relation A × B are trivial relations from A to B. D YG (2) Domain and range of a relation : Let R be a relation from a set A to a set B. Then the set of all first components or coordinates of the ordered pairs belonging to R is called the domain of R, while the set of all second components or coordinates of the ordered pairs in R is called the range of R. Thus, Dom (R) = {a : (a, b)  R} and Range (R) = {b : (a, b)  R}. It is evident from the definition that the domain of a relation from A to B is a subset of A and its range is a subset of B. U (3) Relation on a set : Let A be a non-void set. Then, a relation from A to itself i.e. a subset of A × A is called a relation on set A. Let A = {1, 2, 3}. The total number of distinct relations that can be defined over A is ST Example: 1 (a) 2 9 Solution: (a) (b) 6 (c) 8 (d) None of these n( A  A)  n( A).n( A)  3  9 2 So, the total number of subsets of A  A is 2 9 and a subset of A  A is a relation over the set A. Example: 2 Let X  {1, 2, 3, 4, 5} and Y  {1, 3, 5, 7, 9}. Which of the following is/are relations from X to Y (a) R1  {(x, y)| y  2  x, x  X, y  Y } (b) R2  {(1,1), (2,1), (3, 3), (4, 3), (5, 5)} (c) R3  {(1,1), (1, 3)(3, 5), (3, 7), (5, 7)} (d) R4  {(1, 3), (2, 5), (2, 4), (7, 9)} Solution: (a,b,c) Example: 3 is R4 is not a relation from X to Y, because (7, 9)  R4 but (7, 9)  X  Y. Given two finite sets A and B such that n(A) = 2, n(B) = 3. Then total number of relations from A to B 20 Set Theory and Relations (a) 4 Solution: (c) (b) 8 (c) 64 (d) None of these Here n( A  B) = 2 × 3 = 6 Since every subset of A × B defines a relation from A to B, number of relation from A to B is equal to number of subsets of A  B  2 6  64 , which is given in (c). The relation R defined on the set of natural numbers as {(a, b) : a differs from b by 3}, is given by (a) {(1, 4, (2, 5), (3, 6),.....} (b) Solution: (b) {(4, 1), (5, 2), (6, 3),.....} R  {(a, b) : a, b  N , a  b  3} = {((n  3), n) : n  N}  {(4, 1), (5, 2), (6, 3).....} E3 1.2.2 Inverse Relation. (c){(1, 3), (2, 6), (3, 9),..} 60 Example: 4 Let A, B be two sets and let R be a relation from a set A to a set B. Then the inverse of R, denoted by R–1, is a relation from B to A and is defined by R 1  {(b, a) : (a, b)  R} Clearly (a, b)  R  (b, a)  R–1. Also, Dom (R) = Range (R 1 ) and Range (R) = Dom (R 1 ) Then, (i) R–1 = {(1, a), (3, a), (3, b), (3, c)} ID Example : Let A = {a, b, c}, B = {1, 2, 3} and R = {(a, 1), (a, 3), (b, 3), (c, 3)}. (ii) Dom (R) = {a, b, c} = Range (R 1 ) Let A = {1, 2, 3}, B = {1, 3, 5}. A relation R : A B is defined by R = {(1, 3), (1, 5), (2, 1)}. Then R 1 is D YG Example: 5 defined by U (iii) Range (R) = {1, 3} = Dom (R 1 ) (a) {(1,2), (3,1), (1,3), (1,5)} (b) 1 ,  R 1 {(1, 2), (3, 1), (2, 1)} (c) {(1, 2), (5, 1), (3, 1)}(d)  {(3, 1), (5, 1), (1, 2)}. Solution: (c) (x , y )  R  (y, x )  R Example: 6 The relation R is defined on the set of natural numbers as {(a, b) : a = 2b}. Then R 1 is given by (a) {(2, 1), (4, 2), (6, 3).....} (b) Solution: (b) {(1, 2), (2, 4), (3, 6)....} (c) R 1 is not defined (d) R = {(2, 1), (4, 2), (6, 3),......} So, R 1 = {(1, 2), (2, 4), (3, 6),.....}. U 1.2.3 Types of Relations. ST (1) Reflexive relation : A relation R on a set A is said to be reflexive if every element of A is related to itself. Thus, R is reflexive  (a, a)  R for all a  A. A relation R on a set A is not reflexive if there exists an element a  A such that (a, a)  R. Example: Let A = {1, 2, 3} and R = {(1, 1); (1, 3)} Then R is not reflexive since 3  A but (3, 3)  R Note :  The identity relation on a non-void set A is always reflexive relation on A. However, a reflexive relation on A is not necessarily the identity relation on A.  The universal relation on a non-void set A is reflexive. (2) Symmetric relation : A relation R on a set A is said to be a symmetric relation iff (a, b)  R  (b, a)  R for all a, b  A Set Theory and Relations 21 aRb  bRa for all a, b  A. i.e. it should be noted that R is symmetric iff R 1  R Note :  The identity and the universal relations on a non-void set are symmetric relations. 60  A relation R on a set A is not a symmetric relation if there are at least two elements a, b  A such that (a, b)  R but (b, a)  R.  A reflexive relation on a set A is not necessarily symmetric. E3 (3) Anti-symmetric relation : Let A be any set. A relation R on set A is said to be an antisymmetric relation iff (a, b)  R and (b, a)  R  a = b for all a, b  A. Thus, if a  b then a may be related to b or b may be related to a, but never both. Example: Let N be the set of natural numbers. A relation R  N  N is defined by xRy iff x divides y(i.e., x/y). Note :  The identity relation on a set A is an anti-symmetric relation. The universal relation on a set A containing at least two elements is not anti- U  ID Then x R y, y R x  x divides y, y divides x  x  y symmetric, because if a  b are in A, then a is related to b and b is related to a under the universal relation will imply that a = b but a  b. D YG  The set {(a, a) : a  A}  D is called the diagonal line of A  A. Then “the relation R in A is antisymmetric iff R  R 1  D ”. (4) Transitive relation : Let A be any set. A relation R on set A is said to be a transitive relation iff (a, b)  R and (b, c)  R  (a, c)  R for all a, b, c  A i.e., aRb and bRc  aRc for all a, b, c  A. U In other words, if a is related to b, b is related to c, then a is related to c. Transitivity fails only when there exists a, b, c such that a R b, b R c but a R c. ST Example: Consider the set A = {1, 2, 3} and the relations R1  {(1, 2), (1, 3)} ; R 2 = {(1, 2)}; R 3 = {(1, 1)}; R 4 = {(1, 2), (2, 1), (1, 1)} Then R 1 , R 2 , R 3 are transitive while R 4 is not transitive since in R 4 , (2, 1)  R 4 ;(1, 2)  R 4 but (2, 2)  R4. Note :  The identity and the universal relations on a non-void sets are transitive.  The relation ‘is congruent to’ on the set T of all triangles in a plane is a transitive relation. (5) Identity relation : Let A be a set. Then the relation IA = {(a, a) : a  A} on A is called the identity relation on A. 22 Set Theory and Relations In other words, a relation IA on A is called the identity relation if every element of A is related to itself only. Every identity relation will be reflexive, symmetric and transitive. Example: On the set = {1, 2, 3}, R = {(1, 1), (2, 2), (3, 3)} is the identity relation on A. Note :  It is interesting to note that every identity relation is reflexive but every reflexive 60 relation need not be an identity relation. Also, identity relation is reflexive, symmetric and transitive. (6) Equivalence relation : A relation R on a set A is said to be an equivalence relation on A (i) It is reflexive i.e. (a, a)  R for all a  A E3 iff (ii) It is symmetric i.e. (a, b)  R  (b, a)  R, for all a, b  A ID (iii) It is transitive i.e. (a, b)  R and (b, c)  R  (a, c)  R for all a, b, c  A. Note :  Congruence modulo (m) : Let m be an arbitrary but fixed integer. Two integers a U and b are said to be congruence modulo m if a  b is divisible by m and we write a  b (mod m). Thus a  b (mod m)  a  b is divisible by m. For example, 18  3 (mod 5) because 18 – 3 = 15 which is divisible by 5. Similarly, 3  13 (mod 2) because 3 – 13 = –10 which D YG is divisible by 2. But 25  2 (mod 4) because 4 is not a divisor of 25 – 3 = 22. The relation “Congruence modulo m” is an equivalence relation. Important Tips If R and S are two equivalence relations on a set A , then R  S is also an equivalence relation on A.  The union of two equivalence relations on a set is not necessarily an equivalence relation on the set.  The inverse of an equivalence relation is an equivalence relation. U  1.2.4 Equivalence Classes of an Equivalence Relation. ST Let R be equivalence relation in A(  ). Let a  A. Then the equivalence class of a, denoted by [a] or {a} is defined as the set of all those points of A which are related to a under the relation R. Thus [a] = {x  A : x R a}. It is easy to see that (1) b  [a]  a  [b] (2) b  [a]  [a]  [b] (3) Two equivalence classes are either disjoint or identical. As an example we consider a very important equivalence relation x  y(mod n) iff n divides (x  y ), n is a fixed positive integer. Consider n  5. Then = {x : x  0 (mod 5)} = {5p : p  Z} = { 0,  5,  10 ,  15 ,.....} Set Theory and Relations 23 = {x : x  1(mod 5)}  {x : x  1  5 k , k  Z}  {5 k  1 : k  Z}  {1, 6, 11,.......,  4 ,  9,.....}. One can easily see that there are only 5 distinct equivalence classes viz. , , , and , when n = 5. Given the relation R = {(1, 2), (2, 3)} on the set A = {1, 2, 3}, the minimum number of ordered pairs which when added to R make it an equivalence relation is (a) 5 Solution: (c) (b) 6 (c) 7 R is reflexive if it contains (1, 1), (2, 2), (3, 3) (d) 8 E3  (1, 2)  R, (2, 3)  R 60 Example: 7  R is symmetric if (2, 1), (3, 2)  R. Now, R  {(1, 1), (2, 2), (3, 3), (2, 1), (3, 2), (2, 3), (1, 2)} R will be transitive if (3, 1); (1, 3)  R. Thus, R becomes an equivalence relation by adding (1, 1) (2, 2) (3, 3) (2, 1) (3,2) (1, 3) (3, 1). Hence, the total number of ordered pairs is 7. The relation R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (1, 3)} on set A = {1, 2, 3} is (a) Reflexive but not symmetric transitive (c) Symmetric and Transitive (b) Reflexive (d) Neither but not symmetric U nor transitive ID Example: 8 Since (1, 1); (2, 2); (3, 3)  R therefore R is reflexive. (1, 2)  R but (2, 1)  R, therefore R is not symmetric. It can be easily seen that R is transitive. Example: 9 Let R be the relation on the set R of all real numbers defined by a R b iff | a  b |  1. Then R is D YG Solution: (a) (a) Reflexive and Symmetric (b) Solution: (a) Symmetric only (c) Transitive only (d) | a  a|  0  1 a R a  a  R  R is reflexive, Again a R b  | a  b |  1 | b  a|  1  bRa  R is symmetric, Again 1R 1 1 1 and R1 but 1 2 2 2 U  R is not anti-symmetric Further, 1 R 2 and 2 R 3 but 1 R 3 ST [ | 1  3 |  2  1 ]  R is not transitive. Example: 10 The relation "less than" in the set of natural numbers is [UPSEAT 1994, 98; AMU 1999] (a) Only symmetric Solution: (b) (b) Only transitive (c) Only reflexive (d) Equivalence relation Since x  y, y  z  x  z  x, y, z  N  x R y, yR z  x R z ,  Relation is transitive ,  x  y does not give y  x ,  Relation is not symmetric. Since x  x does not hold, hence relation is not reflexive. Example: 11 With reference to a universal set, the inclusion of a subset in another, is relation, which is (a) Symmetric only (b) Equivalence relation (c) Reflexive only (d) None of these 24 Set Theory and Relations Solution: (d) Since A  A  relation '  ' is reflexive. Since A  B, B  C  A  C  relation '  ' is transitive. But A  B,  B  A ,  Relation is not symmetric. (a) Anti-symmetric Solution: (c) (b) Reflexive (c) Symmetric Given A = {2, 4, 6, 8} R = {(2, 4)(4, 2) (4, 6) (6, 4)} Let P  {(x , y )| x 2  y 2  1, x , y  R}. Then P is (a) Reflexive Solution: (b) Obviously, the (b) Symmetric relation is not x y 1 y  x 1. 2 Example: 14 Then R is 2 and transitive but it is symmetric, because Let R be a relation on the set N of natural numbers defined by nRm  n is a factor of m (i.e., n|m). (a) Reflexive and symmetric symmetric (c) Equivalence (b) Transitive and (d) Reflexive, transitive but not symmetric Since n | n for all n  N , therefore R is reflexive. Since 2 | 6 but 6 | 2 , therefore R is not symmetric. D YG Solution: (d) reflexive (d) Anti-symmetric ID 2 (c) Transitive U 2 (d) Transitive E3 (a, b)  R  (b, a)  R and also R 1  R. Hence R is symmetric. Example: 13 60 Let A  {2, 4, 6, 8}. A relation R on A is defined by R  {(2, 4), (4, 2), (4, 6), (6, 4)}. Then R is Example: 12 Let n R m and m R p  n|m and m|p  n|p  nRp. So R is transitive. Example: 15 pairs in R is Let R be an equivalence relation on a finite set A having n elements. Then the number of ordered (a) Less than n Solution: (b) ordered pairs. Let N denote the set of all natural numbers and R be the relation on N  N defined by (a, b) R (c, d) if ad (b  c)  bc (a  d ), then R is [Roorkee 1995] (b) Reflexive only (c) Transitive only ST (a) Symmetric only relation Solution: (d) Less than or equal to n(d) Since R is an equivalence relation on set A, therefore (a, a)  R for all a  A. Hence, R has at least n U Example: 16 (b) Greater than or equal to n (c) For (a, b), (c, d)  N × N (a, b)R(c, d)  ad(b  c)  bc(a  d) Reflexive: Since ab(b  a) = ba(a  b)ab  N ,  (a, b)R(a, b) ,  R is reflexive. Symmetric: For (a, b), (c, d)  N  N , let (a, b)R(c, d)  ad (b  c)  bc (a  d )  bc (a  d )  ad (b  c)  cb(d  a)  da(c  b)  (c, d)R(a, b)  R is symmetric Transitive: For (a, b), (c, d), (e, f )  N  N, Let (a, b)R(c, d), (c, d)R(e, f )  ad (b  c)  bc (a  d ) , cf (d  e )  de (c  f ) (d) An equivalence Set Theory and Relations 25  adb  adc  bca  bcd.....(i) cfd  cfe  dec  def and.......(ii) (i) × ef  (ii) × ab gives, adbef  adcef  cfdab  cfeab = bcaef  bcdef  decab  defab  adcf (b  e )  bcde (a  f )  af (b  e )  be (a  f )  (a, b)R (e, f ).  R is transitive. Hence R is an equivalence relation. For real numbers x and y, we write x Ry  x  y  2 is an irrational number. Then the relation R is (a) Reflexive Solution: (a) (b) Symmetric (c) Transitive For any x  R, we have x  x  2  2 an irrational number. 2 R1 but 1 R 2 , R is not transitive also because but 2 R 2 2. Example: 18 (d) None of these E3  xRx for all x. So, R is reflexive. R is not symmetric, because 60 Example: 17 2 R 1 and 1R 2 2 Let X be a family of sets and R be a relation on X defined by ‘A is disjoint from B’. Then R is (b) Symmetric (c) Anti-symmetric (d) Transitive ID (a) Reflexive Solution: (b) Clearly, the relation is symmetric but it is neither reflexive nor transitive. Example: 19 Let R and S be two non-void relations on a set A. Which of the following statements is false (b) R and S are transitive  R  S is transitive (c) R and S are symmetric  R  S is symmetric (d) R and S are reflexive  R  S is reflexive U Solution: (a) (a) R and S are transitive  R  S is transitive Let A  {1, 2, 3} and R = {(1, 1), (1, 2)}, S = {(2, 2) (2, 3)} be transitive relations on A. D YG Then R  S = {(1, 1); (1, 2); (2, 2); (2, 3)} Obviously, R  S is not transitive. Since (1, 2)  R  S and (2, 3)  R  S but (1, 3)  R  S. Example: 20 Solution: (c) The solution set of 8 x  6(mod 14 ), x  Z , are (a)  (b)  8 x  6  14 P(P  Z)  x  1 (c)  (d)   [14 P  6 ] , x  Z 8 1 (7 P  3) 4  x = 6, 13, 20, 27, 34, 41, 48,....... U x =  Solution set = {6, 20, 34, 48,.....}  {13, 27, 41,......} = . ST Where , are equivalence classes of 6 and 13 respectively. 1.2.5 Composition of Relations. Let R and S be two relations from sets A to B and B to C respectively. Then we can define a relation SoR from A to C such that (a, c)  SoR   b  B such that (a, b)  R and (b, c)  S. This relation is called the composition of R and S. For example, if A = {1, 2, 3}, B = {a, b, c, d}, C = {p, q, r, s} be three sets such that R = {(1, a), (2, c), (1, c), (2, d)} is a relation from A to B and S = {(a, s), (b, q), (c, r)} is a relation from B to C. Then SoR is a relation from A to C given by SoR = {(1, s) (2, r) (1, r)} In this case RoS does not exist. 26 Set Theory and Relations In general RoS  SoR. Also (SoR)–1 = R–1oS–1. If R is a relation from a set A to a set B and S is a relation from B to a set C, then the relation SoR (a) Is from A to C (b) Is from C to A (c) Does not exist Solution: (a) It is obvious. Example: 22 If R  A  B and S  B  C be two relations, then (SoR )1  (a) S 1 oR 1 (b) R 1 oS 1 (c) SoR (d) None of these 60 Example: 21 (d) RoS It is obvious. Example: 23 If R be a relation < from A = {1,2, 3, 4} to B = {1, 3, 5} i.e., (a, b)  R  a  b, then RoR 1 is (a) {(1, 3), (1, 5), (2, 3), (2, 5), (3, 5), (4, 5)} (b) {(3, 1) (5, 1), (3, 2), (5, 2), (5, 3), (5, 4)} ID (c) {(3, 3), (3, 5), (5, 3), (5, 5)} (d) {(3, 3) (3, 4), (4, 5)} Solution: (c) E3 Solution: (b) We have, R = {(1, 3); (1, 5); (2, 3); (2, 5); (3, 5); (4, 5)} R 1  {(3, 1), (5, 1), (3, 2), (5, 2); (5, 3); (5, 4)} Solution: (a) Let a relation R be defined by R = {(4, 5); (1, 4); (4, 6); (7, 6); (3, 7)} then R 1oR is D YG Example: 24 U Hence RoR 1 = {(3, 3); (3, 5); (5, 3); (5, 5)} (a) {(1, 1), (4, 4), (4, 7), (7, 4), (7, 7), (3, 3)} (b) {(1, 1), (4, 4), (7, 7), (3, 3)} (c) {(1, 5), (1, 6), (3, 6)} (d) None of these We first find R 1 , we have R 1  {(5, 4 ); (4 , 1); (6, 4 ); (6, 7); (7, 3)} we now obtain the elements of R 1 oR we first pick the element of R and then of R 1. Since (4, 5)  R and (5, 4 )  R 1 , we have (4 , 4 )  R 1 oR Similarly, (1, 4 )  R, (4 , 1)  R 1  (1, 1)  R 1 oR (4 , 6)  R, (6, 7)  R 1  (4 , 7)  R 1 oR (7, 6)  R, (6, 4 )  R 1  (7, 4 )  R 1 oR , (7, 6)  R, (6, 7)  R 1  (7, 7)  R 1 oR U (4 , 6)  R, (6, 4 )  R 1  (4 , 4 )  R 1 oR , ST (3, 7)  R, (7, 3)  R 1  (3, 3)  R 1 oR , Hence R 1 oR  {(1, 1); (4, 4); (4, 7); (7, 4), (7, 7); (3, 3)}. 1.2.6 Axiomatic Definitions of the Set of Natural Numbers (Peano's Axioms). The set N of natural numbers (N = {1, 2, 3, 4......}) is a set satisfying the following axioms (known as peano's axioms) (1) N is not empty. (2) There exist an injective (one-one) map S : N N given by S (n)  n  , where n  is the immediate successor of n in N i.e., n  1  n . (3) The successor mapping S is not surjective (onto). Set Theory and Relations 27 (4) If M  N such that, (i) M contains an element which is not the successor of any element in N, and (ii) m  M  m   M , then M  N This is called the axiom of induction. We denote the unique element which is not the successor 60 of any element is 1. Also, we get 1   2, 2   3. Note :  Addition in N is defined as, E3 n  1  n n  m   (n  m) n.1  n ST U D YG U n.m   n.m  n ID  Multiplication in N is defined by,