Relations

Sets & Relations RELATIONS ORDERED PAIR A pair of objects listed in a specific order is called Ex.1 If A = {1, 2} and B = {3, 4}, then find A × B. an ordered pair. It is written by listing the two objects Sol. A × B = {(1, 3), (1, 4), (2, 3), (2, 4)} in specific order separating them by a comma abd Ex.2 Let A and B be two non-empty sets having elements in common, then prove that A × B and enclosing the pair in parantheses. B × A have n2 elements in common. In the ordered pair (a, b), a is called the first element Sol. We have (A × B)  (C × D) = (A  C)× (B  D) and b is called the second element. On replacing C by B and D by A, we get Two ordered pairs are set to be equal if their  (A × B)  (B × A) = (A  B) × (B  A) corresponding elements are equal. i.e. It is given that AB has n elements so (a, b) = (c, d) if a = c and b = d. (A  B) × (B  A) has n2 elements But (A × B)  (B × A) = (A  B) × (B  A) CARTESIAN PRODUCT  (A × B)  (B × A) has n 2 elements The set of all possible ordered pairs (a, b), where a Hence A × B and B × A have n2 elements in  A and b  B i.e. {(a, b) ; a  A and b  B} common. is called the cartesian product of A to B and is denoted by A × B. RELATION A × B = {(a, b) : a  A and b  B} A relation R from set A to B (R : A  B) is a = {(a1, b1),(a1, b2),(a2, b1),(a2, b2),(a3, b1),(a3, b2)} correspondence between set A to set B by which If set A = {a1, a2, a3} and B = {b1, b2} then some or more elements of A are associated with A × B and B × A can be written as : some or more elements of B. A × B = {(a, b) : a  A and b  B and Therefore a relation R from A to B is a subset of B × A = {(b, a) ; b  B and a  A} A × B. Thus, R is a relation from A to B  R  A × Clearly A × B  B × A until A and B are equal B. The subsets is derived by describing a relationship between the first element and the second element of Note : ordered pairs in A × B e.g. if A = {1, 2, 3, 4, 5, 6, 7, 1. If number of elements in A : n(A) = m and 8} and B = {1, 2, 3, 4, 5} and R = {(a, b) : a = b2, n(B) = n then number of elements in (A × B) = m × n a  A, b  B} then R = {(1, 1), (4, 2), 2. Since A × B contains all such ordered pairs of the (9, 3)}. Here a R b  1 R 1, 4 R 2, 9 R 3. type (a, b) such that a  A & b  B, that means it includes all possibilities in which the elements of set NOTE : A can be related with the elements of set B. Therefore, (i) If a is related to b then symbolically it is written as a A × B is termed as largest possible relation defined R b where a is pre-image and b is image from set A to set B, also known as universal relation (ii) If a is not related to b then symbolically it is written from A to B. as a R/ b. Similarly A × B × C = {(a, b, c) : a  A, b  B, (iii) Let A and B be two non-empty finite sets consisting c  C} is called ordered triplet. of m and n elements respectively. Then A × B consists of mn ordered pairs. So total number of subsets of A × B i.e. number of relations from A to B is 2mn. (iv) A relation R from A to A is called a relation on A. Sets & Relations Sol. Under relation R, we have 3R2, 5R2, 5R4, 7R4 and 7R6 Ex.3 If the number of elements in A is m and number of element in B is n then find (i) The number of elements in the power set of A × B. (ii) number of relation defined from A to B Sol. (i) Since n(A) = m; n(B) = n then n(A × B ) = mn So number of subsets of A × B = 2mn  n (P(A × B)) = 2mn (ii) number of relation defined from A to B = 2mn Any relation which can be defined from set A to set B will be subset of A × B  A × B is largest possible relation A  B no. of relation from A  B = no. of subsets of set (A × B)  i.e.R = {(3, 2), (5, 2), (5, 4), (7, 2), (7, 4), (7, 6)}  Dom (R) = {3, 5, 7} and range (R) = {2, 4, 6} Ex.5 Let A = {2, 3, 4, 5, 6, 7, 8, 9}. Let R be the relation on A defined by {(x, y) : x  A, y  A and x divides y}. Find domain and range of R. Sol. The relation R is R = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)} Domain of R = {2, 3, 4, 5, 6, 7, 8, 9} = A Range of R = {2, 3, 4, 5, 6, 7, 8, 9} = A Ex.6 Let R be the relation on the set N of natural numbers defined by R : {(x, y)} : x + 3y = 12 x  N, y  N} Find DOMAIN, CO-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 of coordinates of the ordered pairs belonging to R is called to domain of R, while the set of all second components of corrdinates of the ordered pairs in R is called the range of R. Thus, Domain (R) = {a : (a, b)  R}, (i) R (ii) Domain of R (iii) Range of R Sol. (i) We have, x + 3y =12  x = 12 – 3y Putting y = 1, 2, 3, we get x = 9, 6, 3 respectively For y = 4, we get x = 0  N. Also for y > 4, x  N  R = {(9, 1), (6, 2), (3, 3)} (ii) Domain of R = {9, 6, 3} (iii) Range of R = {1, 2, 3} Co-domain (R) = B 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 Co-domain (B). INVERSE OF A RELATION Let A, B be two sets and let R be a relation from a set A to 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, Ex.4 Let A = {1, 3, 5, 7} and B = {2, 4, 6, 8} be two sets and let R be a relation from A to B defined by the phrase "(x, y)  R  x > y". Find relation R and its domain and range. Dom of R = Range of R–1 and Range of R = Dom of R–1 Sets & Relations (ii) Universal relation : Let A be a set. Then A × A  A × A and so it is a relation on A. This relation is called the universal relation on A. Ex.7 Let A be the set of first ten natural numbers and let R be a relation on A defined by (iii) Identity relation : Let A be a set. Then the relation (x, y)  R  x + 2y = 10 i.e., IA = {(a, a) : a  A} on A is called the identity relation R = {(x, y) : x  A, y  A and x + 2y = 10}. on A. In other words, a relation IA on A is called the Express R and R–1 as sets of ordered pairs. identity relation if every element of A is related to Determine also : itself only. (i) Domains of R and R–1 (iv) Reflexive relation : A relation R on a set A is said (ii) Range of R and R –1 Sol. We have (x, y)  R  x + 2y = 10  y = 10  x , x, 2 yA where A = {1,2,3,4,5,6,7,8,9,10} Now, x = 1  y = 10  1 9   A 2 2 This shows that 1 is not related to any element in A. Similarly we can observe that 3, 5, 7, 9 and 10 are not related to any element of a under the defined relation. Further we find that 10  2 2 10  4 for x = 4, y = 2 10  6 for x = 6, y = 2 10  8 for x = 8, y = 2 for x = 2, y = = 4  A  (2, 4)  R = 3  A  (4, 3) R = 2  A  (6, 2)  R = 1  A  (8, 1)  R Thus R = {(2, 4), (4, 3), (6, 2), (8, 1)}  R –1 = {(4, 2), (3, 4), (2, 6), (1, 8)} Clearly, Dom (R) = {2, 4, 6, 8} = Range (R–1) and Range (R) = {4, 3, 2, 1} = Dom (R–1) to be reflexive if every element of A is related to itself. Thus, R on a set A is not reflexive if there exists an element a  A such that (a, a)  R. Note : Every identity relation is reflexive but every reflexive relation in not identity. (v) 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. i.e. a R b  b R a for all a, b  A. (vi) Transitive relation : Let A be any set. A relation R on 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. a R b and b R c  a R c for all a, b, c  A Note : (i) Every null relation is a symmetric and transitive relation. (ii) Every singleton relation is a transitive relation. (iii) Universal and identity relations are reflexive, symmetric as well as transitive. (iv) Anti-symmetric Relation TYPES OF RELATIONS In this section we intend to define various types of relations on a given set A. (i) Void relation : Let A be a set. Then   A × A and so it is a relation on A. This relation is called the void or empty relation on A. 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 e.g. Relations “being subset of ”; “is greater than or equal to” and “identity relation on any set A” are antisymmetric relations. (v) Equivalence relation : A relation R on a set A is said to be an equivalence relation on A iff Sets & Relations (iii) Let (T1, T2)  R and (T2, T3)  R  T1 is congruent to T2 (i) it is reflexive i.e. (a, a)  R for all a  A  T1 is congruent to T3 (ii) it is symmetric i.e. (a, b)  R  (b, a)  R for all a, b  A  (iii) it is transitive i.e. (a, b)  R and (b, c)  R  (a, c)  R for all a, b  A and T2 is congruent to T3  (T1, T3)  R R is transitive Hence R is an equivalence relation. Ex.12 Show that the relation R in R defined as R = {(a, b) : a  b} is transitive. Sol. Let (a, b)  R and (b, c)  R Ex.8 Which of the following are identity relations on set A = {1, 2, 3}. R1 = {(1, 1), (2, 2)}, R2 = {(1, 1), (2, 2), (3, 3), (1, 3)}, R3 = {(1, 1), (2, 2), (3, 3)}. Sol. The relation R3 is idenity relation on set A.  (a  b) and b  c  a  c  (a, c)  R Hence R is transitive. Ex.13 Show that the relation R in the set {1, 2, 3} given by R = {(1, 2), (2, 1)} is symmetric. Sol. Let (a, b)  R [ (1, 2)  R] (b, a)  R [ (2, 1)  R] R1 is not identity relation on set A as (3, 3)  R1.  R2 is not identity relation on set A as (1, 3)  R2 Hence R is symmetric. Ex.9 Which of the following are reflexive relations on set Ex.14 If X = {x1, x2, x3} and y = (x1, x2, x3,x4,x5} A = {1, 2, 3}. then find which is a reflexive relation of the following : R = {(1, 1), (2, 2), (3, 3), (1, 3), (2, 1)}, 1 R2 = {(1, 1), (3, 3), (2, 1), (3, 2)}. (a) R1 : {(x 1, x1), (x2, x2) Sol. R1 is a reflexive relation on set A. (b) R1 : {(x1, x1), (x2, x2), (x3, x 3) R2 is not a reflexive relation on A because 2  A but (2, 2)  R2. Ex.10 Prove that on the set N of natural numbers, the relation R defined by x R y  x is less than y is transitive. Sol. Because for any x, y, z  N x < y and y < z  x < z  x R y and y R z  x R z. so R is transitive. (c) R3 : {(x1, x1), (x2, x2),(x3, x3),(x1, x3),(x2, x4) (d) R3 : {(x1, x1), (x2, x2),(x3, x3),(x4, x4) Ex.11 Let T be the set of all triangles in a plane with R a relation in T given by R = {(T1 , T2) : T1 is congruent to T2}. Show that R is an equivalence relation. Sol. Since a relation R in T is said to be an equivalenece relation if R is reflexive, symmetric and transitive. (i) Since every triangle is congruent to itself  R is reflexive (ii) (T1 , T2)  R  T1 is congruent to T2  T2 is congruent to T1 Hence R is symmetric  (T2, T1)  R Sol. (a) non-reflexive because (x3, x3)  R1 (b) Reflexive (c) Reflexive (d) non-reflexive because x4  X Ex.15 If x = {a, b, c} and y = {a, b, c, d, e, f} then find which of the following relation is symmetric relation : R1 : { } i.e. void relation R2 : {(a, b)} R3 : {(a, b), (b, a)(a, c)(c, a)(a, a)} Sol. R1 is symmetric relation because it has no element in it. R 2 is not symmetric because (b, a)  R 2 & R3 is symmetric. Ex.16 If x = {a, b, c} and y = (a, b, c, d, e} then which of the following are transitive relation. (a) R 1 = { } (b) R2 = {(a, a)} Sets & Relations Sol. (a) R1 is transitive relation because it is null relation. (b) R2 is transitive relation because all singleton relations are transitive. (c) R3 = {(a, a}.(c, d)} (c) R3 is transitive relation (d) R4 = {(a, b), (b, c)(a, c),(a, a), (c, a)} (d) R4 is also transitive relation