Show that either $[x] = [y]$ or $[x]$ and $[y]$ are disjoint?

243 Views Asked by At

An equivalence class $[x]_R$ is defined by $[x]_R = [y ∈ X : xRy]$.

In this proof I'm supposed to start by assuming $[x]$ and $[y]$ are not disjoint. Therefore, there is some element $z$ that is in $[x]$ and $[y]$, so $z ∈ [x]$ and $z ∈ [y]$.

From this point on I'm a bit unsure about what I can and can't do, but here is my attempt:

Suppose there is an element $w$ that is also in $[x]$. I want to show that if it is in $[x]$ then it must also be in $[y]$. Because $w$ is in $[x]$, it is true that $xRw$ (where $R$ is an equivalence relation). The same can be said with $z$, so we also have $xRz$. So, because $xRw$ is the same as $wRx$ because the relation is symmetric, we have $wRxRz$, which means we have $wRz$ because the relation is transitive.

So, because $z ∈ [y]$, $zRy$ is true. So then $wRzRy$, meaning $wRy$, which means $w ∈ [y]$. Therefore $[x]$ is a subset of $[y]$.

Then I would do this again, but start with an element in $[y]$ and find that it is also in $[x]$, which would prove $[x] = [y]$ by containment.

Would this be valid to show that $[x] = [y]$ when $[x]$ and $[y]$ are not disjoint?

1

There are 1 best solutions below

0
On

A little more concisely:

Suppose $[x]\cap [y] \neq \emptyset$. Let $z\in [x]\cap [y]$.

By definition, $xRz$ and $yRz$. Thus $zRy$ by symmetry, so $xRy$ by transitivity, and $yRx$ by symmetry.

It follows that $[x]\subseteq[y]$: Suppose $w\in [x]$. Then $xRw$, so $wRx$ by symmetry. Because $xRz$, we have $wRz$ by transitivity; from this and $zRy$, we get $wRy$ by transitivity, hence $yRw$ by symmetry — therefore $w\in [y]$.

Similarly, $[y]\subseteq [x]$, using $yRx$.

It follows that $[x]=[y]$.