partition and equivalence relation's classes

Question

My question concerns the definitions more than semantics.

That is, a family of sets $P$ is a partition of $X$ if the following conditions hold:

1. $P$ doesn't contain the empty set;
2. union of all $P$'s sets gives $X$;
3. elements of $P$ are pairwise disjoint.

Now for an equivalence relation $R$ over $X$, its classes are defined as:

• $\forall x\in X,$ $c_R(x)=\{y \mid (x,y) \in R\}$

My question is: why is the family of equivalence classes over $R$ a partition of $X$?

Why it shouldn't be: because we can have a relation $R$ and a set $X$ such that: $ \exists x,y \in X, c_R(x)\cap c_R(y)\ne \emptyset$ which violates the condition 3. in the definition of a partition.

EDIT

I am convinced that every two classes of an equivalence relation are either disjoint or equal. But I still have a problem with the definition of equivalence classes:

So since we have a class for each element, we can have equal classes and so non pairwise disjoint.

unless family word in the family of equivalence classes over a relation $R$ on a set $X$ is a partition of $X$ refers to unique classes.

Answer 1

Hint: if $c_R(x)\cap c_R(y)\neq\emptyset$ then $c_R(x)=c_R(y)$ (it is an immediate consequence of transitivity)

Answer 2

When you talk about the equivalence classes of a relation on a set:

• if you violate (1), i.e. $\emptyset \in P$, you have an invalid relation
• if you violate (2), either the union of class elements has something which is not in the original set (which means you have an invalid relation since it is defined on things outside the set of interest) or the set has something not in the union of equivalence classes (which invalidates the relation being an equivalence relation)
• if you violate (3), 2 equivalence classes contain the same item $x$, then your equivalence classes just collide into the same class because the equivalence relation is transitive, and if $a \ne x$ is in the first class and $b \ne x$ in the second, since $R$ is transitive you have $(a,x)$ and $(x,b)$ imply $(a,b)$ and classes collapse.

Answer 3

Every $x$ is in its own $c_R(x)$, which is a member of the set of classes. So that takes care of 1 and 2. It uses reflexivity of $R$.

If $c_R(x)=c_R(y)$ as sets, this is equivalent to $(x,y) \in R$.

Proof: Suppose $c_R(x)=c_R(y)$. Then in particular $y \in c_R(y)$ as $(y,y) \in R$ so $y \in c_R(x)$ which by definition means $(x,y) \in R$.

Suppose $(x,y) \in R$. Let $z \in c_R(x)$ so that $(x,z) \in R$. We also have that $(z,x) \in R$ by symmetry, and then $(z,x),(x,y) \in R$ allows us to say that $(z,y) \in R$ so that $z \in c_R(y)$, and we've shown $c_R(x) \subseteq c_R(y)$ and the reverse inclusion is similar.

Also, if two classes $c_R(x), c_R(y)$ intersect, they are equal; this follows from the previous: if $z$ is in the intersection, $(x,z) \in R, (z,y) \in R$ and so $(x,y) \in R$ and so equal classes..

Answer 4

Let $R$ be an equivalence relation on non empty set $X$. Let's denote class of $p\in X$ by $cl(p)$. For any $x,y \in X$. We can have only two cases:

Case (1): $(x,y)\notin R$
If $a\in cl(x)\cap cl (y) $, then $ (x,a)\in R, (a,y)\in R$ and hence $(x,y)\in R$ (as R is equivalence relation). This is a contradiction and hence $ cl(x)\cap cl(y)=\phi$

Case (2): $(x,y)\in R$
For any $b\in cl(x)$, we have $(b,x)\in R$ and also $(x,y)\in R$ and hence by transitivity of $R$, we have $(b,y)\in R$ and hence $b\in cl(y)$. Thus $cl(x)\in cl (y)$. Similarly, $cl(y)\in cl(x)$ and hence $cl(x)=cl(y)$

Note that any two equivalent classes of an equivalent relation are either equal or disjoint.

Proof: Let's consider two equivalent classes $cl(x)$ and $cl(y)$ such that $cl(x)\cap cl(y)\ne \phi$. Hence, $\exists a\in X$ such that $a\in cl(x)\cap cl(y)$. This implies that $(x,a)\in R$ and $(a,y)\in R\implies (x,y)\in R$ (by transitivity of $R$) and hence by case (2) above, $cl(x)=cl(y)$. Thus two equivalence classes of $R$ are either equal or disjoint!

Now for any $x\in X$, we have $x\in cl (x)\subseteq X$. Hence, $cl(x)$ is non empty. [Condition 1 is satisfied]

Any two classes of $R$ are either pairwise disjoint or equal. From here, you can show that they form a partition. Can you take it from here?