4
$\begingroup$

For $x \in X$, let $[x]$ be the set $[x] = \{a \in X | \ x \sim a\}$.

Show that given two elements $x,y \in X$, either

a) $[x]=[y]$ or

b) $[x] \cap [y] = \varnothing$.

How I started it is, if $[x] \cap [y]$ is not empty, then $[x]=[y]$, but then I am kind of lost.

  • 1
    I made some edits to this question, mostly for presentation; please continue to edit (or revert back) if I have (inadvertently) changed the meaning.2012-11-14

3 Answers 3

9

The problem with your "start" is that you are assuming exactly what you want to prove.

You need to apply what you know about the properties of an equivalence relation, in this case, denoted by $\;\sim\;$ You'll need to use the definitions of $[x], [y]$: $[x] = \{a \in X | \ x \sim a\} \text{ and}\;\;[y] = \{a \in X | y \sim a\}.\tag{1}$

Note that $[x]$ and $[y]$ are defined to be sets, which happen also to be equivalence classes. To prove that two sets are equal, show that each is the subset of the other.


$\text{Now, suppose that}\;\; [x] \cap [y] \neq \varnothing.\tag{2}$

Then there must be at least one element $a\in X$ that is in both equivalence classes. So we have $a \in [x]$ and $a\in [y]$. Here's where the definitions given by $(1)$ come in to play; together with the definition of an equivalence relation (the fact that $\sim$ is reflexive, symmetric, transitive), you can show that:

  • $a \in [x]$ and $a \in [y] \rightarrow x \sim y$ and $y\sim x\;\;\forall x\in [x],~\text{and}~ \forall y \in [y]$.

And so we have, trivially $[x]\subset [y] \;\;\text{and}\;\; [y]\subset [x]\iff [x]=[y].$ Therefore, having assumed $(2)$, it follows that $[x] = [y]$.

The only other option is that $(2)$ is false, in which case we have $[x] \cap [y] = \varnothing$.

$\therefore$ either $[x] = [y]$ OR $[x] \cap [y] = \varnothing$.

1

Once you proved that $[x] \cap [y] \neq \varnothing$ implies $[x] = [y]$ then you are done. To do so, just notice that if the intersection is not empty (say it contains $a$), then any element in $[x]$ is equivalent to $a$, and so is any element in $[y]$, so you get your result by transitivity ($[x] \subset [y]$ and $[y] \subset [x]$).

1

Lemma If $u \in [v]$ then $[u] = [v]$ proof: If $u \in [v]$ then by definition of equivalence class we have $v\sim u$, by transitivity of equivalence relations we have $\forall a \in X$, $\ v \sim a$ iff $\ u \sim a$. Hence we conclude $[v] = \{a \in X | \ v \sim a\} = \{a \in X | \ u \sim a\} = [u]$.

Corollary Suppose $u \in [x] \cap [y]$ then $[u] = [x]$ and $[u] = [y]$ so $[x] = [y]$.