2
$\begingroup$

The original question is:

How many different equivalence relations can we define on the set $A = \{x,y,z\}$?

I illustrate my confusion in reaching a possible solution with 2 parts below:

Part (1): The possible partitions of set $A$ are:

a) $\{\{x\}, \{y\}, \{z\}\}$

b) $\{\{x\}, \{y, z\}\}$

c) $\{\{y\}, \{x, z\}\}$

d) $\{\{z\}, \{x, y\}\}$

e) $\{\{x, y, z\}\}$

Part (2): One possible equivalence relation is $\{(x,x), (y,y), (z,z)\}$.

My question is, how can I use something from Part (1) to get to Part (2)? There is clearly something integral to equivalence relations that I am missing. I know that an equivalence relation is transitive, symmetric, and reflexive, but how does part 2 show transitivity or symmetry?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Part $2$ shows transitivity and symmetry, since there are no cases to check. $\endgroup$ – астон вілла олоф мэллбэрг May 2 '17 at 1:15
  • $\begingroup$ @астонвіллаолофмэллбэрг what cases do you mean? $\endgroup$ – haxtar May 2 '17 at 1:18
  • $\begingroup$ See, symmetry says : whenever $(x,y) \in R$, $(y,x) \in R$. In the relation that you have, there are no $y \neq x$ such that $(x,y) \in R$, so the property is vacuously true. $\endgroup$ – астон вілла олоф мэллбэрг May 2 '17 at 1:30
2
$\begingroup$

There is a correspondence between partitions and equivalence relations.

To illustrate this, I'll give you a concrete example. Suppose $$A = \{ \rm USA, \ \rm France, \ \rm Germany, \ \rm UK \},$$ and suppose that we declare two countries to be "equivalent" if they are in the same continent. Then we can partition $A$ into two subsets: $$ A_{\rm North \ America} = \{ \rm USA \}, \ \ \ \ A_{\rm Europe} = \{ \rm France, \rm Germany, \rm UK \}.$$ Having partitioned the set in this way, it is clear that two countries are equivalent under the equivalence relation if and only if they are members of the same subset within the partition.

Now let's keep $A$ the same, but change the equivalence relation. Suppose we now decide to declare two countries to be "equivalent" if their people speak the same language. Then we can partition $A$ into three subsets: $$ A_{\rm English} = \{ \rm USA , \rm UK \}, \ \ \ \ A_{\rm French} = \{ \rm France \}, \ \ \ \ A_{\rm German} = \{ \rm Germany \}.$$ Again, two countries are equivalent under this equivalence relation iff they are members of the same subset within the partition.

In general, one can show that there is a one-to-one correspondence between equivalence relations and partitions. Given an equivalence relation, one can obtain a partition by grouping together elements that are equivalent under the equivalence relation. And conversely, given a partition, one can obtain an equivalence relation by declaring two elements equivalent iff they are members of the same subset within the partition.

So since there are five ways of partitioning your set, there must exist precisely five ways of defining equivalence relations on your set.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks @Kenny Wong. My question then for you is, if there is a correspondence between partitions and equivalence relations, then does this relation {(x,x), (y,y), (z,z)} correspond to partition a), as shown in the question above? $\endgroup$ – haxtar May 2 '17 at 1:55
  • 1
    $\begingroup$ Yes, that's exactly right. In the relation that you wrote down, $x$ is only equivalent to $x$, and $y$ is only equivalent to $y$, and $z$ is only equivalent to $z$. So if we are to partition $A$ by grouping together equivalent elements, the partition would be $\{ \{ x \}, \{ y \}, \{ z \} \}$. $\endgroup$ – Kenny Wong May 2 '17 at 2:00
  • 1
    $\begingroup$ To give you one more example: consider the partition $\{\{x \}, \{y, z \} \}$. Here, $x$ is only equivalent to itself, whereas $y$ and $z$ are equivalent to each other (as well as themselves). So the equivalence relation is $\{ (x,x), (y,y),(y,z),(z,y),(z,z) \}$. $\endgroup$ – Kenny Wong May 2 '17 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.