In the previous section, we saw identity element and inverse element. In this section, we will see some miscellaneous examples.
Solved example 17.41
If R1 and R2 are equivalence relations in a set A, show that R1∩R2 is also an equivalence relation.
Solution:
Let us assume that, the set A = {a1, a2, a3, a4, . . . , an}
Part (i): Proving that, the intersection is reflexive.
1. R1 is an equivalence relation in set A.
• So all reflexive pairs like (a1,a1), (a2,a2), (a3,a3), . . .(an,an) will be present in the set R1.
2. R2 is also an equivalence relation in set A.
• So all reflexive pairs like (a1,a1), (a2,a2), (a3,a3), . . .(an,an) will be present in the set R2 also.
3. The same reflexive pairs are present in both R1 and R2.
• So those reflexive pairs will be present in R1∩R2 also.
Therefore, R1∩R2 is reflexive.
Part (ii): Proving that, the intersection is symmetric.
1. Suppose that, a random pair (a3,a7) is present in the intersection.
♦ Then this (a3,a7) will be present in the set R1.
♦ This (a3,a7) will be present in the set R2 also.
2. (a3,a7) is present in R1.
• But R1 is an equivalence relation. So the symmetric pair (a7,a3) will be present in R1.
3. (a3,a7) is present in R2.
• But R2 is an equivalence relation. So the symmetric pair (a7,a3) will be present in R2.
4. From (2) and (3), we see that:
(a7,a3) is present in both R1 and R2.
5. From (1) and (4) we see that:
The symmetric pairs (a3,a7) and (a7,a3) are present in the intersection.
6. In this way, all symmetric pairs will be present in the intersection.
So the intersection is a symmetric relation.
Part (iii): Proving that, the intersection is transitive.
1. Suppose that, two random pairs (a3,a7) and (a7,a2) are present in the intersection.
♦ Then these two pairs will be present in R1.
♦ These two pairs will be present in R2 also.
2. (a3,a7) and (a7,a2) are present in R1.
• But R1 is a symmetric relation. So the transitive pair (a3,a2) will be present in R1.
3. (a3,a7) and (a7,a2) are present in R2.
• But R2 is a symmetric relation. So the transitive pair (a3,a2) will be present in R2.
4. From (2) and (3), we see that:
• (a3,a2) will be present in both R1 and R2.
• So it will be present in the intersection also.
5. From (1) and (4),we see that:
• The intersection contains (a3,a7), (a7,a2) and (a3,a2)
Therefore, the intersection is transitive.
◼ From parts (i), (ii) and (iii), we see that, the intersection is reflexive, symmetric and transitive. So the intersection is an equivalence relation.
Solved example 17.42
Let R be the relation on set A of ordered pairs of positive integers defined by (x,y)R(u,v) if and only if xv = yu. Show that R is an equivalence relation.
Solution:
1. Set A is a set of ordered pairs.
• Each of those ordered pairs will contain +ve integers.
For example: (3,5), (1,2), (7,11) etc.,
2. The given relation is on A.
• That means, we need to consider the set A × A
• Each element in A × A will be a pair of ordered pairs.
For example: [(11,3),(5,4)], [(7,5),(8,2)], [(14,8),(9,3)] etc.,
• In general, we can write:
Each element in A × A will be a pair of ordered pairs in the form [(x,y),(u,v)]
3. The set R will contain those elements from A × A, which satisfy the condition: xv = yu.
• We need to prove that R is an equivalence relation.
4. First we check whether R is reflexive.
(i) If R is reflexive, then a possible random element in R is: [(a3,a7),(a3,a7)].
(ii) Let us check whether this element satisfies the condition xv = yu.
• Here, x = u = a3 and y = v = a7
• We can write:
xv = a3 a7 and yu = a7 a3 = a3 a7
(iii) We see that xv = yu.
• So all reflexive elements are eligible to be included in R.
Therefore, R is a reflexive relation.
5. Next we check whether R is symmetric.
(i) Suppose that a random element [(a3,a7),(a2,a9)] is present in R.
• It's symmetric element is [(a2,a9),(a3,a7)]. Is this symmetric element present in R? Let us check.
(ii) [(a3,a7),(a2,a9)] is present in R.
• That means, this element satisfies the condition: xv = yu
• That means, a3 a9 = a7 a2.
(iii) If the symmetric element is to be present in R, it must also satisfy the condition xv = yu.
• That means, a2 a7 must be equal to a9 a3.
• From (ii), we see that, they are indeed equal.
(iv) So we can write:
• If [(a3,a7),(a2,a9)] is present in R, then the symmetric element [(a2,a9),(a3,a7)] will also be present in R.
• So all symmetric elements are eligible to be included in R.
Therefore, R is a symmetric relation.
6. Finally, we check whether R is transitive.
(i) Suppose that two random elements [(a3,a7),(a2,a9)] and [(a2,a9),(a8,a11)] are present in R.
• Then the transitive element is [(a3,a7),(a8,a11)]. Is this transitive element present in R? Let us check.
(ii) [(a3,a7),(a2,a9)] is present in R.
• That means, this element satisfies the condition: xv = yu
• That means, a3 a9 = a7 a2.
(iii) Similarly, [(a2,a9),(a8,a11)] is present in R.
• That means, this element satisfies the condition: xv = yu
• That means, a2 a11 = a9 a8.
(iv) If the transitive element written in (i) is to be present in R, then it should also satisfy the condition xv = yu.
• That means, a3 a11 must be equal to a7 a8
• That means, $\frac{a_3}{a_7}~\text{must be equal to}~\frac{a_8}{a_{11}}$
(v) From (ii) we get: $\frac{a_3}{a_7}~=~\frac{a_2}{a_9}$
(vi) From (iii) we get: $\frac{a_2}{a_9}~=~\frac{a_8}{a_{11}}$
(vii) Combining the results in (v) and (vi), we get:
$\frac{a_2}{a_9}~=~\frac{a_8}{a_{11}}~=~\frac{a_3}{a_7}$
• So the condition mentioned in (iv) is satisfied.
(vii) That means, all transitive elements will be present in R.
Therefore, R is a transitive relation.
◼ Based on the above 6 steps, we see that, R is reflexive, symmetric and transitive. So R is an equivalence relation.
Solved example 17.43
Let X = {1,2,3,4,5,6,7,8,9}. Let R1 be a relation in X given by R1 = {(x,y): x-y is divisible by 3} and R2 be another relation on X given by R2 ={(x,y): {x,y}⊂{1,4,7} or {x,y}⊂{2,5,8} or {x,y}⊂{3,6,9}}. Show that R1 = R2.
Solution:
1. We can write set R1 easily. Ordered pairs like (1,4), (4,1), (5,8), are some of the elements of R1.
• But in this problem, we do not have to write the elements of R1. We just need to know the nature of the elements. We see that, for all those elements, (x-y) will be divisible by 3.
2. Next we consider R2
(i) Any ordered pair (x,y) for which, {x,y} is a subset of {1,4,7}, will be an element of R2.
(ii) Any ordered pair (x,y) for which, {x,y} is a subset of {2,5,8}, will be an element of R2.
(iii) Any ordered pair (x,y) for which, {x,y} is a subset of {3,6,9}, will be an element of R2.
3. Consider the sets {1,4,7}.
•
We can take any two elements from this set. The difference between those two elements will be divisible by 3.
•
Similar is the case with the other two sets {2,5,8} and {3,6,9}
•
Union of the three sets will give X.
•
So R1 will be a subset of R2
4. While writing the ordered pairs of R2, we see that, difference between the members of each ordered pair is divisible by 3.
•
So R2 will be a subset of R1.
5. Now we can compare the results.
♦ In (3), we see that: R1 ⊂ R2.
♦ In (4), we see that: R2 ⊂ R1.
•
So we can write: R1 = R2
Solved example 17.44
Let f: X→Y be a function. Define a relation R in X given by R = {(a,b): f(a) = f(b)}. Examine whether R is an equivalence relation or not.
Solution:
1. Let X = {x1, x2, x3, . . . } and Y = {y1, y2, y3, . . .}
2. Then a possible example set for f is {(x1, y5), (x2, y8), (x3, y11), . . .}
• This means:
♦ When x1 is the input, the function f gives y5 as the output.
♦ When x2 is the input, the function f gives y8 as the output.
♦ When x3 is the input, the function f gives y11 as the output.
so on . . .
3. Now we can write the set R.
• Set R will contain ordered pairs of the form (a,b).
• Consider any one ordered pair (a,b). That ordered pair is eligible to be in R because, f(a) = f(b).
• So both a and b will be from set X. This is because, all inputs of f are taken from X.
4. So R is a relation on X.
• That means, the elements of R are taken from the set X×X.
• So a random ordered pair taken from R will be (x5,x9)
• This ordered pair is eligible to be in R because, f(x5) = f(x9)
5. Now we check whether R is reflexive.
• A possible random element in X×X is (x5,x5)
• This element will satisfy the condition f(a) = f(b).
This is because, f(x5) = f(x5)
• So all reflexive pairs will be present in R.
Therefore, R is reflexive.
6. Next we check whether R is symmetric.
• If a random pair (x5,x9) is present in R, then the symmetric pair (x9,x5) will also be present in R.
This is because:
f(x5) = f(x9) ⇒ f(x9) = f(x5)
• So all symmetric pairs will be present in R.
Therefore, R is symmetric.
7. Finally we check whether R is transitive.
• Consider two random pairs from R: (x5,x9) and (x9,x2)
• Will the transitive pair (x5,x2) be present in R?
• Since both (x5,x9) and (x9,x2) are present in R, we can write:
f(x5) = f(x9) = f(x2)
• So it is clear that, the transitive pair (x5,x2) will be present in R
Therefore, R is transitive.
◼ Since R is reflexive, symmetric and, transitive, it is an equivalence relation.
Solved example 17.45
Determine which of the following binary operations on the set N are associative and which are commutative.
$(a)~a * b = 1 ~ \forall ~ a,b \in N~~~~~(b)~a * b = \frac{a+b}{2} ~ \forall ~ a,b \in N$
Solution:
Part (i):
1. Checking whether commutative or not.
• For an operation to be commutative, the condition which should be satisfied is:
(a∗b) = (b∗a)
• For our present case, a and b should be natural numbers.
• It is given that, if we perform the operation '*' between any two natural numbers a and b, then the result will be 1.
• So the same operation between b and a will also give 1.
• That means, (a∗b) = (b∗a)
• So the given ∗ is a commutative binary operation.
2. Checking whether associative or not.
• For an operation to be associative, the condition which should be satisfied is:
(a∗b)∗c = a∗(b∗c)
• For our present case, a, b and c should be natural numbers.
• First we calculate (a∗b)∗c:
(a ∗ b) = 1
So (a∗b)∗c = (1∗c) = 1
• Next we calculate a∗(b∗c):
(b ∗ c) = 1
So a∗(b∗c) = (a∗1) = 1
• We see that: (a∗b)∗c = a∗(b∗c)
So the given ∗ is an associative binary operation.
◼ Based on the above 2 steps, we can write:
The given ∗ is both commutative and associative.
Part (ii):
1. Checking whether commutative or not.
• For an operation to be commutative, the condition which should be satisfied is:
(a∗b) = (b∗a)
• For our present case, a and b should be natural numbers.
• For any two natural numbers, $\frac{a+b}{2}$ will be equal to $\frac{b+a}{2}$ .
• That means, (a∗b) = (b∗a)
• So the given ∗ is a commutative binary operation.
2. Checking whether associative or not.
• For an operation to be associative, the condition which should be satisfied is:
(a∗b)∗c = a∗(b∗c)
• For our present case, a, b and c should be natural numbers.
• First we calculate (a∗b)∗c:
$(a*b)~=~\frac{a+b}{2}$
$\text{So}~(a*b)*c~=~\left(\frac{a+b}{2}\right) * c~=~\frac{\frac{a+b}{2}~+~c}{2}~=~\frac{a+b+2c}{4}$
• Next we calculate a∗(b∗c):
$(b*c)~=~\frac{b+c}{2}$
$\text{So}~a*(b*c)~=~a * \left(\frac{b+c}{2}\right)~=~\frac{a~+~\frac{b+c}{2}}{2}~=~\frac{2a+b+c}{4}$
• We see that: (a∗b)∗c ≠ a∗(b∗c)
So the given ∗ is not an associative binary operation.
◼ Based on the above 2 steps, we can write:
The given ∗ is commutative but not associative.
Solved example 17.46
Find the number of all one-one functions from set A = {1,2,3} to itself.
Solution:
1. Take any one element from the domain. It can be mapped to the codomain in 3 different ways.
2. Take a second element from the domain. It can be mapped to the codomain in 2 ways. This is because, the way chosen in step 1 should not be repeated. For example, (1,2) and (2,2) cannot be selected. Then it would not be a one-one function.
3. Take the third element from the domain. It can be mapped to the codomain in one way.
4. So the total number of ways = 3 × 2 × 1 = 3! = 6
In the next section,we will see a few more solved examples.
No comments:
Post a Comment