Hello everybody, today I'll be discussing a topic in Discrete Mathematical Structures, subject code 18CS36. In module 3, that is Relations and Functions, I'll be discussing a topic about Properties of Relations. Myself, Dr. Madhura.
Assistant Professor, Department of Mathematics, Sai Vidya Institute of Technology, Bengaluru. First, let us see the properties of relations one by one. Firstly, reflexive relation. A relation R on a set A is said to be reflexive if A, A belongs to R.
for every a belonging to the set A. That is, a is related to a for every element a belonging to the set A and R is not reflexive or it is said to be non-reflexive if there exists some element a belonging to the set A such that a comma a does not belong to the relation R. So, suppose the set A consists of the elements 1, 2, 3, 4, 5, etc.
Then every A, A, every element A, A should belong to the relation R. Like 1, 1, 2, 2, 3, 3, etc. Every element of the set A should belong to the relation R to say it is reflexive. And it is said to be not reflexive. If there exists some element A which belongs to the set A but A, A does not belong to the relation R.
Some of one of the element or two of the elements sometimes what happens from the set A, right? Those elements, the element or the ordered pair A, A need not belong to the relation R. In such cases, we say that it is non-reflexive.
Example, the symbols less than or equal to, equal to, greater than or equal to are all reflexive relations, whereas less than and greater than are not reflexive relations. This is one of the simple or basic examples for reflexive and not reflexive. As another example, I have taken of this. Suppose the set A equal to 1, 2, 3, 4, then r equal to the relation r which is given by 1 1 2 2 3 3 is not reflexive because we observe that the element 4 belong to the set A whereas 4 comma 4 does not belong to the relation r. So that is the reason this given relation 1 1 2 2 3 3 in ordered pairs it consists of is not reflexive.
Now, next see the next definition irreflexive. A relation R on a set A is said to be irreflexive if A comma A does not belong to R for every element A belonging to the set A. That is, no element of A is related to itself.
So, we have set A as say suppose 1, 2, 3, 4, etc. up to n. If every pair, ordered pair A, A does not belong to R, then we say that it is irreflexive relation. We'll note the following points.
A non-reflexive relation need not be irreflexive. So non-reflexive and irreflexive are totally different. When we say non-reflexive, it need not be irreflexive.
For irreflexive, every element A belonging to the set A, the ordered pair AA should not belong to the relation R. Whereas for not reflexive, any one element if it does not belong to the relation R also, we say it is not reflexive. Second point, a relation can be neither reflexive nor irreflexive.
So it can be neither reflexive nor irreflexive. Next, we will try to understand the definition for symmetric relation. A relation R on a set A is said to be symmetric whenever the ordered pair belongs to the relation R, belongs to relation R for every belonging to the set A. So if the ordered pair A, B belongs to the relation, then B, A should also belong to the relation R. For every A, B belonging to the set A.
If so, then we say such a relation is a symmetric relation. Now we will understand what is asymmetric relation. A relation R on a set A. is said to be asymmetric whenever a, b belongs to R, b, a does not belong to R for every a, b belonging to the set A.
So for every set A, for every elements a, b belonging to the set A, if a, b belongs to R and the reverse of it that is b, a does not belong to R, the relation R. Then we say such a relation is asymmetric. Now the next is about anti-symmetric relation.
A relation R on a set A is said to be anti-symmetric if whenever A, B belongs to R and B, A belongs to R, then A is equal to B. So whenever we observe any relation which has the form that a comma b belongs to r and b comma a belongs to r then a will be equal to b. This is one and the same as understanding any relation is said to be anti-symmetric. If a comma b belongs to r and a is not equal to b then b comma a does not belong to r. Then such a relation is called anti-symmetric relation.
Now let us note and understand the following points. Asymmetric and anti-symmetric relations are not one and the same. So asymmetric is different than the anti-symmetric. Here the condition imposes on A not equal to B.
A relation can neither be symmetric nor asymmetric. A relation can be neither symmetric nor anti-symmetric. Next, we will understand the definition for transitive relation. A relation R on a set A is said to be transitive if whenever the ordered pair A, B belongs to R and B, C belongs to R then A, C must also belong to R for every elements A, B, C belonging to the set A. I repeat and the easy example to understand for that is less than or equal to and greater than or equal to.
So let us understand how this is happening. The relation R is said to be transitive. If suppose two elements A, B belong to R and the element B, C also belong to R, then A, C should also belong to R to say that the relation R is transitive.
So a relation R is not transitive if there exists A, B, C belonging to the set A such that A, B belongs to relation R, B, C belongs to relation R but A, C does not belong to the relation R. So this is about transitive relation. Next, equivalence relation.
A relation R on a set A is said to be equivalent relation on A if it satisfies these three conditions. That is, the relation R should be reflexive, symmetric and transitive on the set A. So if these three conditions satisfy that the relation R is reflexive, symmetric and transitive on the set A, then we can conclude that the relation R is an equivalence relation. An example for that is the symbol equals. Equivalence classes.
Let R be an equivalence relation. on a set A and the element A belongs to the set A. Then the set of all those elements of A which are related to A by R is called equivalence class of A with respect to R and this equivalence class is usually denoted by R of A or simply within closed brackets we write down A or A complement. A bar we can write it as.
So R of A or the equivalence class of A is given by we read it in the words as equivalence class of A. So equivalence class of A is given by element X belonging to the set A such that X is related to A. X comma A belongs to R is same as saying X is related to A.
So let us try to read it once again and understand the definition. So we are collecting the set of all those elements of the set A, which are related to A by R, is called the equivalence class. All the elements that are related to the element A from the relation R, we are going to collect and those we are calling as X.
So all those elements we have to write down and That gives us together the equivalence class. Let us see an example to understand the same. Suppose the set A equal to 1, 2, 3 and relation R is defined as 1, 1, 1, 2, 2, 1, 2, 2, 3, 3. Then equivalence class of 1 equal to.
Let me explain how it is 1, 2. Observe from the relation R. If I want to write down the equivalence class of 1, I have to look into 1 is related to which all elements. So we observe here 1 is related to 1, correct? And then 1 is related to 2, that's all.
So we are taking all those elements of that X which is related to A. So we observe 1 is related to 1. That's why we write down 1 here. We observe that 2 is related to 1. We are looking forward for equivalence class of 1. So 2 is related to 1. So we are writing down the element 2 also. Similarly equivalence class of 2 is also 1 comma 2. It's because we observe 1 is related to the element 2 as well as 2 is related to the element 2. So equivalence class of 2 is 1, 2. And finally equivalence class of 3. We observe in the entire relation R, 3 is related to 3. So only 3 is related to 3. That's why equivalence class of 3 is only the element 3. So this is about equivalence class for us.
Next. We'll be seeing partition of a set. Partition of a set. Let A be a non-empty set. And suppose there exist non-empty subsets, A1, A2, A3, etc. up to A, K of the set A.
So A is partitioned or A is being split into two or more subsets. So they are all. non-empty subsets say denoted by a1, a2, a3 etc. up to ak such that the following two conditions hold. Conditions first one a is the union of a1, a2, a3 etc. up to ak that is a equal to a1 union, a2 union etc. up to ak.
So when you combine all those non-empty subsets, when you take the union of all those non-empty subsets A1 to Ak, you should get back A. That's the first condition. Secondly, any two of the subsets a1, a2, a3, etc. up to ak are disjoint. Any two of the subsets a1 to ak are disjoint.
When we say disjoint, it can be symbolically represented as intersection. So, we say ai intersection aj is equal to a null set. There is nothing common between those two sets. This is for i not equal to j.
Means you have to take any two subsets and say they are disjoint. So if these conditions are satisfied then we say that the set A is a partitioned. Then we say that the P Set P is a partition on A, where P is given by A1, A2, A3, etc. up to A, K. All the non-empty subsets that you consider together is put in the form of the set P. So, P is said to be the partition of A.
Also, A1, A2, A3, etc. up to A, K are called the blocks or the cells of the partition. I have just given a simple example of partition of a set with six blocks or cells which is shown as below. So this is the entire set A for us. It has been partitioned into A1, A2, A3, A4, A5, A6. Six partitions or blocks we have taken.
This is a simple example to understand what does a partition mean. So we'll be working problems on the same. Now we will see problems, problems on, problems on, properties of relations, problems on, properties of relations. First question, first question.
Let. Let the set A equal to 1, 2, 3, 4 and the relation R is given by relation R equal to 1, 3, 1, 1, 3, 1, 1, 2, 3, 3, 4, 4. Relation R is given for S. B. B. A relation on A.
B. A relation on A. Determine. Determine.
Whether. Whether. R is. Reflexive.
Reflexive. Irreflexive, symmetric, anti-symmetric or transitive. Transitive.
So we need to verify given the set A and the relation R that is set of ordered pairs for us, we need to verify whether the relation R is reflexive, irreflexive, symmetric, antisymmetric or transitive. So all of them are based on the definition. All of them are based on the definition of these.
So let us do one by one. So very firstly, solution, solution. So we have to check whether the relation R is reflexive or not. Is R reflexive?
Definition of reflexive says that if the set A has 1, 2, 3, 4 as the elements, then every pair, same pair, that is 1, 1, 2, 2, 3, 3, 4, 4 should belong to relation R. To say it is reflexive. We observe 1, 1 belong to The relation R, 3, 3 belongs to the relation R, 4, 4 belongs to relation R.
Whereas, a observation says that 2, 2 does not belong to the relation R. So it is not reflexive. Not reflexive.
R is not reflexive. It is always preferable to write down with the reason. R is not reflexive because 2,2 does not belong to R. 2,2 does not belong to the relation R.
So for any set A that consists of the elements, something like 1, 2, 3, 4. Every same element that is 1, 1, 2, 2, 3, 3, 4, 4 should belong to the relation R. Here 2, 2 does not belong to the relation R. That is why it is not reflexive.
Second one, we have to check whether it is irreflexive. Irreflexive. We recall the definition for irreflexive.
A relation R on a set A is said to be irreflexive. If for every element A belonging to the set A, A, A should not belong to R. A, A should not belong to the relation R.
So what is the conclusion? R is not irreflexive. It is not irreflexive because 1, 1, 3, 3. 113344 belongs to the relation R already.
Every same element 11, 22, 33, 44 should not belong to the relation R to say it is irreflexive. But here we observe 11, 33, 44 belongs to relation R. That is why it is not irreflexive. We will write down the same thing. R is not.
irreflexive because r is not irreflexive because 1 1 3 3 4 4 belong to the relational. Third one, third one is to talk about symmetric. We recall the definition for symmetric. It says that a relation R on a set A is said to be symmetric whenever A, B belongs to R, B, A also should belong to R.
So we will take elements like this. So suppose 1, 3 belongs to the relation R, then 3, 1 also should belong to the relation R. So it is satisfying for 1, 3, 3, 1. Let us check for any other elements.
Say I will check for 1, 2. So if 1, 2 belongs to the relation R, 2, 1 also should belong to relation R. But we observe 2, 1 does not belong to the relation R. That is why it is not symmetric.
We will write down the same thing along with the reason. R is not symmetric. R is not symmetric because 1,2 belongs to R but 2,1 does not belong to R. 2,1 does not belong to R.
So it is not symmetric. Then the fourth one is to verify whether it is anti-symmetric or not. We'll recall the definition for anti-symmetric. Anti-symmetric relation. So any relation R is said to be anti-symmetric if A, B belongs to R and A is not equal to B, then B, A should not belong to R.
should not belong to R. I repeat, if A, B belongs to R and A is not equal to B, A is not equal to B, then B, A should not belong to R, relation R. We observe it for the element 1, 3. So we observe that 1, B I am assuming as A, B. So we observe 1, 3 belongs to relation R and 1 is not equal to 3. A is not equal to the element B. Then according to the definition for anti-symmetric, B, A should not belong to R.
Whereas I observe 3, 1 is belonging to the relation R. 3,1 is belonging to the relation R. So it is not anti-symmetric. You have to verify that for every element that are existing on the set A. Correct?
So 1,3 belongs to R and 1 is not equal to 3. But 3,1 should not belong to R to say it is anti-symmetric. Whereas 3,1 is belonging to R and hence it is not anti-symmetric. We will just write on the same thing.
So r is not anti-symmetric. r is not anti-symmetric because 1,3 belongs to r and 1 is not equal to 3 but we see that 3,1 belongs to r. 3,1 belongs to R. That is why it is not anti-symmetric.
Fifth one or the last one, for R transitive, we have to check whether the relation R is transitive or not transitive. Let us recall the definition for transitive relation. Any relation R on a set A is said to be transitive if A, B belongs to R and B, C belongs to R, then A, C also must belong to R.
For every element A, B, C belonging to the set A, if A, B belongs to R and B, C belongs to the relation R, then we must have A, C also belonging to the relation R. Let us observe whether it is satisfied or not satisfied. We observe that We'll start with the first element only and check out the transitivity property. So we observe 1,3 belongs to relation R, 3,1 belongs to R, 1,3,3,1.
This implies 1,1 should belong to R. So 1,1 is belonging to R. For one ordered pair, when you verify like that, you cannot conclude it is transitive.
You have to check for every ordered pair of the relation R. Similarly, I'll check for this 1, 1, 1, 2. This is ending with 1, starting with 1. Similar to understanding of our composition property. So, 1, 1, 1, 2. 1, 1 belong to R.
1, 2 belong to R. So, 1, 2 belongs to R. Yes, it is also true.
I observe for another expression here. I have 3,1 belonging to relation R. 3,1 belongs to relation R.
1,2 belongs to relation R. This is ending with 1. This is starting with 1. So 3,1 belongs to R. 1,2 belongs to R. So 3,2 also should have been in R. 3,2 should also have been in relation R.
But 3,2 does not exist in the relation R. So we conclude R is not. transitive. So I write down the same thing.
R is not transitive. R is not transitive because 3 comma 1 belongs to R. 1 comma 2 belongs to R.
Bad. Right? This is ending with 1. This is starting with 1. So 3, 2 should have been in R. 3,2 is not existing in R.
That is why it is not transitive. If it is not satisfying for any one of such ordered pair, still we conclude it is not transitive. So this is all about. Now let us see second problem on equivalence relation. Second question.
Let A equal to 1, 2, 3, 4 and R be a relation on A given by R equal to 1, 1, 1, 2. 2, 1, 2, 2, 3, 4, 4, 3, 3, 3, 4, 4. This is the relation R for S. Given on A, verify, verify that R is an equivalence. relation.
Verify that r is an equivalence relation. Recall the property. When do we say r is an equivalence relation?
If r satisfies three properties. That is R is reflexive, R is symmetric and R is transitive. If all these three are satisfied, then we can conclude R is an equivalence relation. So let us see solution.
Solution. To prove. To prove R is reflexive, symmetric. And transitive.
So we have to prove these three conditions are satisfied in order to say R is an equivalence relation. So let us prove one by one. First one, in order to say R is reflexive, recall the definition. For every element of the set A, it is 1, 2, 3, 4. We should have in R the ordered pairs 1, 1, 2, 2, 3, 3, 4, 4. Let us check that.
So 1, 1 belongs to R, 2, 2 belongs to R, 3, 3 belongs to R and 4, 4 also belongs to R. Since for every element A belonging to the set A, A, A belongs to R, we can conclude that R is reflexive. We will write down the same thing.
1, 1, 2, 2, 3, 3, 4, 4 belongs to R. That is R. A, A belongs to R for every A belonging to the set A. Therefore, R is reflexive. Therefore, R is reflexive.
Second subpart we have to grow now is R is symmetric. We will recall the definition for symmetric property. If A, B belongs to R, then B, A also should belong to R. To say R is symmetric.
So we observe 1, 2 belongs to relation R. If 1, 2 belong to relation R, then 2, 1 also should belong to R. Which is true. Similarly, if 3, 4 belongs to the relation R, then 4, 3 also must belong to relation R, which is also satisfied. Correct?
1, 2, 2, 1, 3, 4, 4, 3. So if that A, B belongs to R, then BA also should belong to R. That is the definition for symmetric. So since it is satisfied for all the existing ordered pairs, that is 1, 2, 2, 1, 3, 4, 4, 3, we can conclude R is symmetric.
So let us quote the same reason and conclude. 1,2 belongs to R and 2,1 also belongs to R. Similarly, 3,4 belongs to relation R and 4,3 also we observe it belongs to relation R. That is according to definition it is of this form. If a, b belongs to R, we observe that b, a also belongs to relation R.
This is for all a, b belonging to the set A. Therefore, R is symmetric. Therefore, R is symmetric. Now, the last part that we have to prove is about transitivity.
So, let us either recall the definition for transitivity. If A, B belongs to R and B, C belongs to R, then A, C must also belong to the relation R. That's the definition for transitivity. So let us see whether it is satisfied or not.
1, 1, 1, 2 gives us 1, 2, which is there in R. Along with 1, 1, I cannot take any other. So I will stop for 1, 1. 1, 1 work is over. Then 1, 2, 2, 1. 1, 2, 2, 1 says 1, 1 must belong to R, which is happening. Similarly, 1, 2, 2, 2 says 1, 2 should belong to R.
Yes, it is true. Next, we take 2, 1. 2, 1, 1, 1 belongs to R. So, 2, 1 belongs to R.
2, 1, 1, 2 belongs to R which says 2, 2 also must belong to R which is true. 2, 1 work is over. Similarly, 2, 2, 2, 1 belongs to R. So, 2, 1 also belongs to R. Ending with 2, starting with 2 like that you have to search.
So 2, 2 work is over. 3, 4 belongs to R. 4, 4 belongs to R. So 3, 4 belongs to R. Similarly, 4, 3 belongs to R.
3, 4 belongs to R gives us 4, 4 belongs to R. And we also can verify 4, 3, 3. 3 belongs to R. So 4, 3 belongs to R. So like that if we observe every element it is satisfied correct.
If you want to observe for this also you can do 3 3 3 4 belongs to R so 3 4 belongs to R. 4 4 4 3 belongs to R so 4 3 also belongs to R. So for every element like that it is observed that if a b belongs to R and b c belongs to R a c also is belonging to R. So we can conclude R is transitive. So I'll just quote the same thing giving one or two examples like that.
1, 2, 2, 1 belongs to R implies 1, 1 also belongs to R. 2, 1, 1, 2 belongs to R implies 2, 2 belongs to R. Similarly, I can write down 4, 3. 3, 4 belongs to R. And this implies 4, 4 also belongs to R.
4, 4 belongs to R, etc. So, we can observe for many others also. So, this in general can be written as if A, B belongs to R and B, C belongs to R, we observe that A, C also belongs to R.
For all A, B, C, it belongs to the set A. Therefore, R is transitive. Now, since R is reflexive, symmetric and transitive, we can conclude that R is an equivalence relation.
R is an equivalence relation. So this is one simple problem that I took on equivalence relation. Next problem, third one.
For a fixed integer. For a fixed integer n greater than 1, prove that the relation congruent congruent modulo n is and equivalence relation on the set of all integers z. On the set of all integers z, we have to prove that the relation congruent modulo n is an equivalence relation.
So let's see the solution part. For any a, b belonging to the set of integers, a is congruent to b modulo n is same as saying if a minus b is a multiple of n. So when do we say a is congruent to b modulo n is?
If it satisfies the condition that a minus b is a multiple of n. We will write down that definition for modulo. For any a comma b belongs to z, a is congruent to b modulo n which is symbolically represented like this.
a is congruent to b mod n right this is the problem. Symbolical representation for modulo if a minus b is a multiple of n. If a minus b is a multiple of n, that is a minus b is equal to k into n for some k belonging to set of integers.
z represents the set of integers. So let us now relate it with a definition. We will relate it for congruent modular n on the relation r.
Let r be a relation. Let r be a relation on z. defined by, defined by a is related to b if and only if a is congruent to b more m.
We are trying to relate the we have to relate and write down the relation R now, correct? We need not rewrite it in defined form of it. So, we have to now correlate and write down the relation R on Z as A is related to B. Any element A, B belonging to the set A, A is related to B if and only if A is congruent to B mod N.
That is how we have defined the relation R. Now, in order to say congruent modulo n is equivalence relation, that is r is an equivalence relation, it has to satisfy three properties. There is reflexive, symmetric and transitive.
So let us prove one by one. First one. We consider for the ordered pair A belong A comma A.
We have to prove A comma A belongs to the relation R for every A belonging to the set A. So we have A minus A. A minus A is 0. Can it be written as a multiple of n like this?
0 into n we can write down, no? 0 into n is 0 itself. So, a minus a I took because I want to check for order pair a comma a belongs to R. For reflexive condition. For reflexive condition, I have to check a comma a belongs to relation R.
That's why I took a minus a. Alright, now this implies for us, this implies A is congruent to A mod N. Therefore, I can say A is related to A which implies R is reflexive. R is reflexive.
This was the first property what we have to prove. Second one, to prove for symmetric, let us assume that A is related to B. If A is related to B, then I can write down according to modulo definition, A is congruent to B mod n. This is same as writing a minus b is equal to kn.
When is a is congruent to b mod n? When a minus b is a multiple of n. When a minus b is a multiple of n, we can say a is congruent to b mod n. So that is why a congruent to b mod n, I can write it down as a minus b equal to k into n.
Now what I have to prove? I have to prove that I started with a is related to b and I have to arrive at b is related to a. So in order to arrive at b is related to a, we want b minus a in the left hand side.
So I take out a minus sign and push it to the RHS part. So what will be b minus a for me? So b minus a will be minus k into n.
Minus k into n. So this implies b is congruent to a mod n. Why we can write down like this is since k belongs to set of integers, minus k also belongs to the set of integers, set of integers. So we will be able to say that minus k also belongs to the set of integers and hence b is congruent to a mod n. So what is b congruent to a mod n says?
This is b is. related to A. B is related to A. So we started with A is related to B and now we have proved that B is related to A. So this implies for every A comma B belongings to Z, we have proved that A comma B belongs to R implies B comma A also belongs to R. Therefore R will be symmetric.
We will write down the same thing. Therefore, for every a, b belongings to z, if a, b belong, ordered pair a, b belongs to r, then b, a also belongs to r and thus r is symmetric, r is symmetric. Now the third property, what we have to prove the third one, we have to prove R is transitive. So when do we say R is transitive?
R is transitive if A, B belongs to R and B, C belongs to R, then A, C also belongs to relation R. So if this property is proved, we can say that it is transitive. So let us prove that. Third part of the problem.
Let us assume first A is related to B and B is related to C. So let us first prove that A is related to B and B is related to C. We are taking this for the third part that is to prove transitivity. So according to definition this is a is related to b means a is congruent to b mod n and similarly b is related to c means b is congruent to c mod n. Now from the definition of Modular, modulo n, we can write it down that.
What is the definition? We recall that from the previous one. We had already written here definition for a is congruent to b mod n if it satisfies a minus b is a multiple of n.
a minus b is a multiple of n. So we are trying to prove it. A minus B is a multiple of N.
So we can now take down A minus B is equal to say K1 into N. For reference, I'll keep this as equation 1. And B minus C is equal to K2 into N. k2 into n. This is for all k1, k2 belonging to set of integers z.
Now, what I have to prove? I have started with a is related to b and b is related to c. Since a is related to b and b is related to c, I have to prove that a is related to c. So, I have to take a and c terms. So, I will be considering this.
Equation 1 plus 2. When I do that, I'll get cancelled with b and I remain with a minus c only so that I'll be able to write a relation between a and c. So what we are implementing is equation 1 plus 2 we are implementing. So this gives us a minus c is equal to k1n plus k2n. So a minus c is equal to k2n. k1 plus k2 into n.
From this can we write down a is congruent to c modulo n. Can we write down like this? Yes, we can write down because k1 plus k2 also belongs to set of integers.
You have already taken k1 k2 belongs to set of integers. So, obviously there is some also belongs to. set of integers. So we can write down a minus c is congruent to k1 plus k2.
a minus c is equal to k1 plus k2 into n can be written as a is congruent to this is the symbol for congruency. a is congruent to c mod n. So from this we can write down a is related to c. Why we can write down like this?
When we took A is related to B, we are able to write down A is congruent to B mod N. In the same manner, when A is congruent to C mod N, you can say that A is related to C. So thus, we started with A related to B and B related to C and we arrived at A is related to C. So we can conclude R is transitive.
We will write down the same thing thus. a is related to b and b is related to c implies a is related to c for all a, b, c belonging to set of integers. This is one and the same as writing in our usual manner. a is related to b means a, b belongs to r.
This representation and this representation are one and the same. Similarly, B is related to R means I can write on. B is related to C means I can write on B, C belongs to R.
B, C belongs to R. So both these are one and the same. This is giving us A, C is belonging to R.
For all A, B, C belongs to the set of integers. Therefore, R is transitive. So, we have proved that R is symmetric, reflexive and transitive. Hence, we can conclude R is an equivalence relation.
R is an equivalence relation. So, what was our R here? We took the relation R as based on the congruency modulo n.
So, A is congruent to B modulo n or congruent modulo n is an equivalence relation. Therefore, congruent modulo n is an equivalence relation. Let us see next problem on partition on A, fourth one.
For the equivalence relation, for the equivalence relation, R is equal to, R is given for S, 1, 1, 1, 2, 2, 1, 2, 2, 3, 4. 4, 3, 3, 3, 4, 4 defined on the set A which is given by 1, 2, 3, 4 determine, determine the partition induced. Determine the partition induced. Right, first we will recall the definition for partition on the set A. So let us assume A is a non-empty set and there exist non-empty subsets A1, A2, A3 etc. to A, K on the set A such that it follows the following two conditions. The first condition is A should be the union of A1, A2, A3, etc. up to Ak.
And any two subsets that you consider among A1 to Ak should be disjoint. If so, then P equal to A1 to An is called the partition on A. So this was the definition what discussed in the theory part. Correct. So we'll have to find out the partition first.
So to find partition. It is purely based on the equivalence classes definition. So we have to find out equivalence class of every element of the set A. Set A consists of 1, 2, 3, 4. So for every element of the set A, we have to find out the equivalence class first.
So we will recall the equivalence class. Equivalence class of A is given by x belonging to the set a such that x is related to a such that x is related to a. So that's the definition for equivalence class no. So I'll just write down the same thing and then start the solution.
So we know that equivalence equivalence class classes on a on the set A with respect to R, with respect to R is given by, is given by, this is the symbol for equivalence of A. So equivalence of A is equal to X belonging to the set A such that X is related to A, X is related to A. So this we are going to grab from looking into the relation R, looking into the relation R for us, okay?
So let us find out equivalence relation of 1. So equivalence relation of 1 from the given relation R is, see observe 1 is related to 1, correct? We also observe that 2 is related to 1. You have to pick the element x from the set A such that x is related to that particular element A. Now my A value is 1. I have taken a as 1. So I have to choose that value of x from the relation r such that x is related to a. So I observe 1 is related to 1 and 2 is related to 1. So equivalence class of 1 is 1 comma 2, 1 comma 2. Next we will find out equivalence class of 2, equivalence class of 2. So we observe that 1 is related to 2 and 2 is related to 2. 1 is related to 2 as well as 2 is related to 2. So equivalence class of 2 is 1 comma 2. 1 comma 2. Next we will write down equivalence class of 3. Equivalence class of 3 we will write down. So we observe that 4 is related to 3 and 3 is related to 3. You are picking that value of x in such a way that x is related to a.
Here a value is 3 because you are finding equivalence class of 3. So 4 is related to 3 and 3 is related to 3. So 4 comma 3. 4 comma 3 or I can also write it down as 3 comma 4. Now finally equivalence class of 4 is equal to. We observe that I am finding equivalence class of 4. So I am observing that 3 is related to 4 and 4 is related to 4. 3 is related to 4, 4 is related to 4. So 3 comma 4 are the equivalence class of 4. Right? So, among all these, can I write down that only equivalence class of one is distinct and equivalence class of three, only these are distinct. Can we write down like that? Equivalence class of 1 and 3 are distinct.
No, 1 is having 1, 2. 3 is having 3, 4. See here, you need not take 1, 3 only. Instead of choosing 1 and 3, I can also choose 2, 3. Equivalence class of 2 and equivalence class of 3 are distinct. Or I can also choose 2, 4. Or I also I can choose 1, 4. So those are the different possibilities.
You have to choose distinct equivalence classes. All those distinct equivalence classes put in the form of a set gives you the partition set, right? You are going to get partition induced by writing down all the distinct equivalence classes together.
So therefore, partition, partition p is equal to 1. 3. This is one and the same as writing. It is one and the same as writing. You have one equivalence class of 1 is nothing but 1, 2 and equivalence class of 3 is nothing but 3, 4 is the partition of the given A induced by R.
Given set A induced by The relation. So for your better understanding, I'm just putting the next thing. We observe that.
Observe that. If you take A, A is nothing but 1, 2, 3, 4, which you can get by union of the equivalence classes. So when you take union of the equivalence classes, you are able to get the set 1, 2, 3, 4, which is nothing but the set A. Is it the first condition satisfying for partition? That's the first condition satisfying for partition, no.
It says that A is the union of A1, A2, A3, etc. up to A, K. Now any two disjoint subsets when you take, it should be null set. Then you take the second condition any two disjoint subsets even that should be equal to the null set. So both the conditions are getting satisfied.
So this is 1 comma 2 equivalence class of 1 and equivalence class of 3. 3 comma 4. When you club it, you are getting 1, 2, 3, 4, which is nothing but the set A itself. This is just for your understanding purpose, okay, that it is satisfying the partition. So, that is how we write down the partition definition, right?
So, next we will see another problem which is proving both. The equivalence relation on A cross A has been proved in that and then followed by equivalence classes we have to find out. And finally, the partition of A cross A induced by R is also formed.
So fifth question. Fifth question, let A equal to 1, 2, 3, 4, 5 define a relation R on A cross A by x1, y1 is related to x2, y2 if and only if x1 plus y1 is equal to x2 plus y2. x2 plus y2.
First problem, first part of the problem, verify that R is an equivalence relation on A cross A. R is an equivalence relation on A cross A. Second part of the problem is determine the equivalence classes. determine the equivalence classes 1, 3, 2, 4 and 1, 1. 1, 1. And the third part of the problem is to determine the partition of A cross A induced by R.
Determine the partition of A cross A induced by R. So I have tried to take up all the different varieties here so that one problem will get you a better idea on all the things that what we covered in the last set of problems. So let us see the solution. Solution.
So first part of the question is to prove that R is an equivalence relation. So we have to prove R is symmetric, reflexive and transitive in order to say it is equivalence relation. So first part to prove R is equivalence relation.
Correct? So we will prove one by one. A I will prove it for reflexive, B for symmetric and C for transitive. So for any x, y belonging to A cross A, we have x plus y is equal to x plus y.
This says that x, y is related to x, y. See here we are considering ordered pair to prove the reflexive symmetric and the transitivity property. So we have to take a ordered pair x, y which belongs to A cross A.
Recall the Cartesian product. We recall from the Cartesian product that A cross A is a set of all ordered pairs from the given set. Correct?
So, if I take X, Y as one such ordered pair and for reflexive I have to prove that it is equal to same element. So, X plus Y is equal to X plus Y. A comma A belongs to R I have to prove.
So, that is why X comma Y is related to X comma Y. So we have proved the first part of it. So this implies R is reflexive.
R is reflexive. Now in the B part, we have to prove R is symmetric. Symmetric. So I assume, I take any pair x1, y1 and x2, y2 belongs to A cross A. And prove the resultant.
For any... For any x1, y1, x2, y2 belongs to A cross A, let x1, y1 be related to x2, y2. x1, y1 is related to x2, y2 we assume and we have to prove for symmetric that x2, y2 is related to x1, y1.
That is what we prove for symmetric property, no? a, b belongs to R. We have to prove that b, a also belongs to R. That is symmetric property.
So here I have assumed for the ordered pair x1, y1 is related to x2, y2. I have to prove that x2, y2 is related to x1, y1. So this implies, this implies x1 plus y1 is equal to x2 plus y2.
Since x1 y1 is related to x2 y2, I can write down from the definition that it is x1 plus y1 is equal to x2 plus y2. Correct? This expression can in turn be written as x2 plus y2 is equal to x1 plus y1.
I just reversed the LHS to RHS, RHS to LHS. So this is one and the same as writing x2, y2 is related to x1, y1. x2, y2 is related to x1, y1. So, we started with x1, y1 is related to x2, y2 and we have proved x2, y2 is related to x1, y1. So, can I conclude that R is symmetric?
R is symmetric. R is symmetric. Now the third part of the problem is to prove transitivity. If I prove symmetric, reflexive and transitive, that gives me equivalence relation.
Correct? So thirdly, we have to prove that R is transitive. So I consider three ordered pairs.
Three ordered pairs. So for any, for any, x1, y1. x2, y2, x3, y3 belonging to A cross A, A cross A.
I'll just write down in the next page. So I can write down suppose suppose x1 y1 is related to x2 y2 and x2 y2 is related to x3 y3. So I have taken set of ordered pairs x1 y1 is related to x2 y2 and x2 y2 is related to x3 y3. Okay then from the definition definition I can write down what is our definition. Our definition is given that x1 plus y1 is equal to x2 plus y2.
Right so I can use the definition for this and write it down as x1 plus y1 is equal to x2 plus y2 and x2 plus y2 is equal to x3 plus y3, x3 plus y3. So can I club these two expressions and write it down as x1 plus y1 is equal to x3 plus y3. Because we observe that x2 plus y2, x2 plus y2.
Here the RHS is same as the LHS of the second expression. So I can equate x1 plus y1 is equal to x3 plus y3. Now is this one in the same as writing x1, y1, the ordered pair x1, y1 is related to x3, y3? Can I write so? x1, y1 is now related to x3, y3.
So this we started with x1 y1 related to x2 y2 and x2 y2 related to x3 y3 and we have arrived at x1 y1 is related to x3 y3 which proves the transitivity. Recall the definition for transitive relation if a is related to b and b is related to c then a is related to c correct that is the definition for transitive relation. transitive. Therefore, R is transitive.
Therefore, R is transitive. So, we proved that R is first part, A part. We proved R is reflexive.
Secondly, we proved R is symmetric. And now, we have proved R is transitive. Thus, we can conclude R is an equivalence relation. R is an equivalence relation. So this was our first part of the problem.
Now we will move on to second one. Second one, what is the second part? Determine the equivalence classes again in the form of ordered pairs.
So 1, 3, 2, 4, 1, 1. Okay, so I'll just write down the definition in this form. Just observe whether you can understand. So we have 1, 3. I will take for one of the ordered pair 1, 3. We can write down this in the form of definition as any ordered pair x, y I have to choose which belongs to A cross A such that x, y is related to 1, 3. x, y is related to 1, 3. So this is one in the same as writing 1, 3 can be written as x, y belonging to a cross a such that x plus y is equal to 1 plus 3 which is 4. This is what is our definition.
x1, y1 is related to x2, y2 from the definition. It says that x plus y is equal to 1 plus 3. If x1 y1 is related to x2 y2, then we can write down x1 plus y1 is equal to x2 plus y2. So same thing I have added x1 plus y1 in the left hand side is added is equal to x2 plus y2 right hand side has also added. So 1 plus 3 which is 4. So now I have to collect all those ordered pairs x comma y from the main set A cross A such that the sum sum sum is equal to 4. So that such that the sum of those x and y values is equal to 4. So let us choose those values from the set A.
Since set A is equal to 1, 2, 3, 4, 5. I have set of all ordered pairs that is A cross A carrying 1, 1, 1, 2, 1, 3, etc. 2, 2, 2, 1, 2, 3, etc. Like that up to 5, 5. This is A cross A for us. From that set, I am choosing sum equal to 4. So when can sum be equal to 4? It can be equal to 4 when I collect elements like 1, 3, 3, 1, 2, 2. Only when I choose elements like 1, 3, 3, 1 and 2, 2, the sum is 4 in each of these cases if you observe. So x, y, 1 plus 3. is 4, 3 comma 1. So, 3 plus 1 is 4, 2, 2, 2 plus 2 is 4. Only in these cases, sum is equal to 4. So, that is why equivalence class of 1 comma 3 is 1, 3, 3, 1, 2, 2. Now, similarly in this manner, we will find out for equivalence class of, what is the next sub question?
Equivalence class of 2, 4, equivalence class of 1, 1, we will find out. So equivalence class of 2, 4. So sum should be equal to 6. Correct? So x, y belonging to a cross a such that x plus y is equal to 2 plus 4 which is equal to 6. So let us grab all those values or the order pairs where the sum is equal to 6. So that can be. 1, 5, 5, 1. Immediately you can write on the reverse one. 2, 4, 4, 2. And then finally 3, 3. That's all known.
Similarly, the last one 1, 1. So this will be x, y belonging to a cross a such that x plus y should be equal to 1 plus 1 which is equal to 2. So this will be equal to, I will grab all the values, so sum will be 2. Is it only 1 comma 1? It will be only 1 comma 1. Sum should be equal to 2. So this is how you find out the equivalence classes of different pairs given for s. Now, the third part of the question.
Third one is to determine the partition of A cross A induced by R. So, in order to find the partition of A cross A induced by R, we have to find out the partition of all the equivalence classes. All the equivalence classes that exist for the given set A equal to 1, 2, 3, 4, 5. So, let us find out all the equivalence classes one by one.
Third part of the problem to determine to determine the partition to determine the partition induced by R we have to find we have to first find all the equivalence classes We have to first find all the equivalence classes of all elements x, y of a cross a with respect to r. With respect to r. So let us first find out the same thing. So just for reference, I will write down the set A here. Set A is given as 1, 2, 3, 4, 5. Okay.
So we will start with one by one equivalence classes. Equivalence classes are. Equivalence classes are.
So I'll write on first for 1 comma 1, 1 comma 1. It is just now we saw in the previous sub question, it is just 1, 1. Then coming on to 1 comma 2, sum should be equal to 3. According to definition, sum 2 plus 1, so sum should be equal to 3. So which all ordered pairs I can consider? 1 comma 2, 2 comma 1. 1 comma 2, 2 comma 1. So is this 1 in the same as writing equivalence class of 2 comma 1 also? 2 comma 1 also, no. So 1, 2 is same as equivalence class of 2, 1. Similar, because again here sum will be equal to 3, so that is why this will be the same for 2 comma 1 also. Then I consider 1 comma 3. 1 comma 3. So sum should be equal to 4. So I have 1 3 3 1 2 2 2 2. So again this is same as writing down equivalence class of 3 comma 1 as well as equivalence class of 2 comma 2. Now next I will consider 1 comma 4. 1, 4. So equivalence class of 1, 4 means sum should be equal to 5. 4 plus 1 or 1 plus 4, sum should be equal to 5. So we have ordered pairs 1, 4, 4, 1. Then we can take 2, 3, 3, 2. In each of these, if you observe, the sum is equal to 5. So is it one and the same as writing this is same as equivalence class of what 4 1 4 1 and it is same as equivalence class of 2 3 and this is same as equivalence class of 3 2 no 3 2 also right.
So next I will go with again equivalence class of next one. Next one I will take it as 1, 5. Sum should be equal to 6. So this is 1, 5, 5, 1, 3, 3. Then 2, 4, 4, 2. 2, 4, 4, 2. And is this equivalence class of this is same as writing equivalence class for. So this is equivalence class of another set of terms also, which is pi 1. 3 3 2 4 4 2. So when we took the sum as 6 it is in turn equivalence classes of 5 1 3 3 2 4 as well as 4 2 correct.
So next we will start with equivalence classes starting with 2. I took up 1 1 1 2 1 3 1 4 1 5 1 to 5 are the elements in the set A. Correct? So, 1, 2, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5 is done.
Next, we will go with 2. 2, 1. 2, 1 is same as this. We have already written here. 2, 1. So, sum is equal to 3. So, 2, 1 is 1 work is already over. 2, 2. 2, 2 sum should be equal to 4. So 2, 2 is also already taken care here.
Sum equal to 4. 2, 3 is also done here. 2, 4 is also taken considered here. So we are left with 2, 5. So starting with 225 is the equivalence class that we have to find some should be equal to seven, some should be equal to seven. So I will write down 25523443. So this is same as writing down equivalence class of another set of sets also, or pairs also, which is nothing but this is equivalence class of pi two. as well as for 3, 4 and for 4, 3. Now we will take starting with 2 all the terms are over.
So now we will consider the next one number starting with 3. So 3, 1. 3, 1 sum is 4 which is already considered here. 3, 2. 3, 2 sum is 5 which is also considered here. Then we have 3 3 3 3 is also considered here 3 4 3 4 is done 3 5 i have to do 3 5 sum should be 8 so 3 5 5 3 3 5 5 3 and then what else order pair we can write down sum should be 8 no so 4 comma 4 4 comma 4. this is in turn also the equivalence class of another set of terms for us which is nothing but 5 comma 3 as well as for 4 comma 4, 5 comma 3 as well as for 4 comma 4. So with 3 the work is over.
Now we will move on to equivalence class starting with 4. So 4 comma, let's see what I have to find out first. 4 comma 1, 4 comma 1 is same as 1 comma 4, so which is already done here. So we'll just put a tick mark. 4 1 is done. 4 2. 4 2 sum should be 6. 4 2 is also considered here.
4 2 also put a tick. 4 3 is done. 4 4 is done.
So I have to do 4 5. 4 comma 5 sum should be equal to 9. So I have to take 4 comma 5, 5 comma 4. That's all now. Sum equal to 9. That's all. So this is equal to. 5 comma 4 as well equivalence class of 5 comma 4 also.
Now starting with 5 let us see which one we have to do starting with 5. So observe 5 comma 1 is already considered 5 comma 1 is nothing but sum equal to 6 which is already considered 5 2 is considered 5 3 is considered 5 4 is considered. So I'll just put a tick here for your reference. 5 and 5, 2, 5, 3, 5, 4 equivalence classes are already done.
So I have to do 5, 5. 5, 5 sum is equal to 10. 10. So I have to consider sum equal to 10 means it is only 5, 5. Remember the set A consists of 1, 2, 3, 4, 5 only. So these are different equivalence classes for us. Now among all these, which are all distinct equivalence classes, We will consider them in the partition set P. So all the distinct equivalence classes put together gives you the partition P for you. So let us write down all those together.
So thus distinct equivalence classes put together. gives the partition, partition of A cross A induced by R. So partition P is equal to, we'll put them together, the equivalence classes which are distinct. If I say all the left hand terms which I considered are nothing but the distinct one, See right hand side I have written the repeated one.
So one two is same as two one equivalence class of two one. So when you want to write down the distinct or the different one, just we are taking the left hand terms and we are putting them together in the partition and easy to remember. So it is one one, one one, one two, one three, one four, one five. 1, 1, 1, 2, 1, 3. 1, 4, all the equivalence classes you have to write out.
Equivalence classes are in terms of the big brackets. So without brackets, you should not write, okay? So 1, 4 and then followed by 1, 5. And small brackets is to represent the ordered pairs, 1, 5. Then we have 2, 5. 2, 5, 3, 5, 4, 5, 5, 5. So we have 2, 5, 3, 5. 4, 5 and finally 5, 5. So this is the partition set of A cross A induced by the relation R. So observe the definition or the property of partition.
When you take A1 union, A2 union, A3 union etc like partitions when you take no, the union of all those gives you the A cross A. gives you the Cartesian product A cross A here and any two disjoint, any two sets when you consider that they are disjoint. Intersection between them is a null set. Intersection between any two of these sets when you consider it is a null set. So that's a definition for a Cartesian set.
So hope you have followed these problems on properties of relations. Thank you.