Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Douglas S. Stones Nov 14 '12 at 1:13
add comment

3 Answers

up vote 6 down vote accepted

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$.

share|improve this answer
    
+1. sorry Amy. There's just a small edit. –  B. S. Aug 13 '13 at 10:40
add comment

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]$.

share|improve this answer
add comment

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]$).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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