equivalence class of {2}
Answers
Step-by-step explanation:
Mathematics
Sign up
Log in
Questions Tags Users Badges Ask
Up vote
5
Down vote
Finding the equivalence classes of a relation R
discrete-mathematics elementary-set-theory logic equivalence-relations binary
Let A={0,1,2,3,4} and define a relation R on A as follows:
R={(0,0),(0,4),(1,1),(1,3),(2,2),(3,1),(3,3),(4,0),(4,4)}.
Find the distinct equivalence classes of R.
How do I solve this problem? What is an equivalence class? As I understand it so far, the equivalence class of a, is the set of all elements x in A such that x is related to a by R. What does this mean in my problems case?
Share Follow
asked
Apr 21 '15 at 2:14
Mark
79●22 gold badges●22 silver badges●33 bronze badges edited
Jun 12 '20 at 10:38
Community♦
1
2
By the way, the elements of a relation (e.g. R) are ordered pairs (e.g. (1,3)) rather than unordered pairs (e.g. {1,3}.) Although the mistake is not very confusing here because R is symmetric. – Trevor Wilson Apr 21 '15 at 3:22
great point @TrevorWilson good of you to mention that – void Jan 8 '18 at 11:52
Add a comment
4 Answers
order by
votes
Up vote
10
Down vote
The equivalence classes are {0,4},{1,3},{2}. to see this you should first check your relation is indeed an equivalence relation. After this find all the elements related to 0. Then pick the next smallest number not related to zero and find all the elements related to it and so on until you have processed each number.
Share Follow
answered
Apr 21 '15 at 3:10
Jorge
91.9k●1717 gold badges●113113 silver badges●224224 bronze badges
short and precise answer! +1 – void Jan 8 '18 at 11:59
Add a comment
Up vote
5
Down vote
Let ∼ be an equivalence relation (reflexive, symmetric, transitive) on a set S.
The equivalence class under ∼ of an element x∈S is the set of all y∈S such that x∼y. An equivalence relation will partition a set into equivalence classes; the quotient set S/∼ is the set of all equivalence classes of S under ∼.
At the extreme, we can have a relation where everything is equivalent (so there is only one equivalence class), or we could use the identity relation (in which case there is one equivalence class for every element of S). But typically we're interested in nontrivial equivalence relations, so we have multiple classes, some of which have multiple members.
As an example, the rational numbers Q are defined such that a/b=c/d if and only if ad=bc and bd≠0. This is an equivalence relation on Z×(Z∖{0}); here there are infinitely many equivalence classes each with infinitely many members.
Considering your example, we find that
(0,4)∈R, so 0 and 4 are in the same class;
(1,3)∈R, so 1 and 3 are in the same class;
(2,2)∈R, and since 2 does not occur in any other pairs in R, it is in a class by itself.
Of course, before I could assign classes as above, I had to check that R was indeed an equivalence relation, which it is.
Thus A/R={{0,4},{1,3},{2}} is the set of equivalence classes of A under R.
Share Follow
answered
Apr 21 '15 at 3:12
BenW
575●33 silver badges●99 bronze badges edited
Dec 3 '20 at 1:52
Community♦
1
Up vote
2
Down vote
The short answer to "what does this mean":
To say that x is related to y by R (also written xRy, especially if R is a symbol like "<") means that (x,y)∈R.
(Well, there may be some ambiguity about whether (x,y)∈R is read as "x is related to y by R" or "y is related to x by R", but it doesn't matter in this case because your relation R is symmetric.)
Share Follow
answered
Apr 21 '15 at 3:20
Trevor Wilson
16.1k●2828 silver badges●6464 bronze badges
Up vote
0
Down vote
Let ={0,1,2,3,4} and define a relation on as follows:
={(0,0),(0,4),(1,1),(1,3),(2,2),(3,1),(3,3),(4,0),(4,4)}. Find the distinct equivalence classes of .
These are actually really fun to do once you get the hang of them!
The way I think of equivalence classes given a set of ordered pairs as well as given a set A, is what is related to what. First, I start with 0, and ask myself, which ordered pairs in the set R are related to 0?
Here it goes! (think of equivalence class as x in an ordered pair y, and the equivalence class of x is what x is related to in the y value of the ordered pair)
[0]: 0 is related 0 and 0 is also related to 4, so the equivalence class of 0 is {0,4}. [2]: 2 is related to 2, so the equivalence class of 2 is simply {2}. [3]: 3 is related to 1, and 3 is also related to 3, so the equivalence class of 3 is {1,3}. [4]: 4 is related to 0, and 4 is also related to 4, so the equivalence class of 4 is {0,4}.
Notice that the equivalence class of 0 and 4 are the same, so we can say that [0]=[4], which says that there are only three equivalence classes on the relation R.
Share Follow
answered
Dec 7 '19 at 22:21
Joe
1
Your Answer
Body
Add picture
OR
Name
By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy