Distinct equivalence classes and induced relations

by zack cook   Last Updated August 14, 2019 06:20 AM

I have a question regarding identifying the distinct equivalence classes of a relation in a specific problem. The problem reads

Let B = {0,1,2,3,4} and let {0},{1,3,4},{2} be a partition of B that induces a relation Q.
Find the distinct equivalence classes of Q.

I believe I am understanding the question and what it is asking. Where I run into trouble is what to do with the given partition and how to use it to find the distinct equivalence classes.



Answers 2


The equivalence relation associated the partition is $x\sim y$ iff x and y are in the same part of the partition. And the partition generated by that equivalence relation is exactly the original partition.

The moral of the story is that there is a one-to-one correspondence between partitions of B and equivalence relations over B.

Matthew Daly
Matthew Daly
August 14, 2019 06:09 AM

The partition induces the relation $Q\subset B\times B$ in the following way. We say that $(x,y) \in Q$ (for $x,y\in B$) if there exists a set $S$ in your partition such that $x,y\in S$.

This is reflexive since trivially any element $x\in B$ is contained in some set of the partition by virtue of it being a partition and hence $(x,x)\in Q$, so we have reflexivity.

This is symmetric since if $(x,y)\in Q$ then by definition that means that there exists a set $S$ of the partition such that $x\in S$ and $y\in S$. But then $(y,x)\in Q$, so we have symmetry.

This is transitive since if $(x,y)\in Q$ and $(y,z)\in Q$ then we have that there exist sets $S$ and $T$ such that $x,y\in S$ and $y,z\in T$. But by definition of a partition, if $y\in S$ and $y\in T$ then $S=T$, so $x,z\in S$ and hence $(x,z)\in Q$, so we have transitivity.

OK, so now that we have made it clear exactly how a partition induces an equivalence relation, we may ask what the equivalence classes of this equivalence relations are. Well, we say that two elements $x,y\in B$ are in the same equivalence class $[x]=[y]$ if and only if $(x,y)\in Q$. But $(x,y)\in Q$ if and only if $x$ and $y$ are elements of the same set of the partition, and so the equivalence class of any element $[x]$ is just the set of the partition that it belongs to. Every set of the partition contains an element and hence maps into an equivalence class, and two elements belong to the same equivalence class iff they belong to the same set of the partition -- I hope this makes it clear, the equivalence classes are the sets of the partition.

Jack Crawford
Jack Crawford
August 14, 2019 06:16 AM

Related Questions


Updated August 25, 2017 21:20 PM

Updated March 16, 2017 00:20 AM

Updated June 12, 2017 20:20 PM