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.

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.

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.

Updated April 04, 2018 02:20 AM

Updated October 29, 2017 19:20 PM

- Serverfault Query
- Superuser Query
- Ubuntu Query
- Webapps Query
- Webmasters Query
- Programmers Query
- Dba Query
- Drupal Query
- Wordpress Query
- Magento Query
- Joomla Query
- Android Query
- Apple Query
- Game Query
- Gaming Query
- Blender Query
- Ux Query
- Cooking Query
- Photo Query
- Stats Query
- Math Query
- Diy Query
- Gis Query
- Tex Query
- Meta Query
- Electronics Query
- Stackoverflow Query
- Bitcoin Query
- Ethereum Query