# Equivalence Relations Proof

• Nov 10th 2009, 09:00 AM
nataliemarie
Equivalence Relations Proof
For homework I am supposed to prove a proposition that says: Assume we are given an equivalence relation on set A.
For a1 and a2 in A either [a1] = [a2] or [a1] intersect [a2] = the empty set.
where [a1] means the equivalence class of a1 in A and the or is inclusive.
i tried breaking it up into cases one case where [a1] = [a2] and the other where if [a1] did not = [a2] the [a1] intersect [a2] must = the empty set. But apparently that wasn't correct.

Can anyone help??? I'd really appreciate it.
• Nov 10th 2009, 12:17 PM
Drexel28
Quote:

Originally Posted by nataliemarie
For homework I am supposed to prove a proposition that says: Assume we are given an equivalence relation on set A.
For a1 and a2 in A either [a1] = [a2] or [a1] intersect [a2] = the empty set.
where [a1] means the equivalence class of a1 in A and the or is inclusive.
i tried breaking it up into cases one case where [a1] = [a2] and the other where if [a1] did not = [a2] the [a1] intersect [a2] must = the empty set. But apparently that wasn't correct.

Can anyone help??? I'd really appreciate it.

Problem: Let $\displaystyle E$ be a set and $\displaystyle \sim$ an equivalence relation on $\displaystyle E$. If $\displaystyle \ell\in E$ let $\displaystyle \bar{\ell}=\left\{\ell'\in E:\ell\sim\ell'\right\}$. Prove that either $\displaystyle \bar{\ell}\cap\bar{\ell'}$ is empty or $\displaystyle \bar{\ell}=\bar{\ell'}$

Proof: Let $\displaystyle \bar{\ell}\cap\bar{\ell'}\ne\varnothing$. Then there exists some $\displaystyle k\in E$ such that $\displaystyle k\in\bar{\ell},\bar{\ell'}$. By definition though this means that $\displaystyle \ell\sim k$ and $\displaystyle \ell'\sim k$. Since $\displaystyle \sim$ is an equivalence relation we see that $\displaystyle \ell'\sim k\implies k\sim \ell'$. Furthermore, we know that $\displaystyle \sim$ is transitive and that $\displaystyle \ell\sim k,k\sim \ell'$. Therefore $\displaystyle \ell\sim \ell'$. Now let $\displaystyle x\in\bar{\ell}$, then $\displaystyle \ell \sim x$. Once again though, we see that $\displaystyle \ell \sim x$ and $\displaystyle \ell\sim\ell'\implies \ell'\sim\ell$ implies $\displaystyle \ell'\sim x$. Therefore $\displaystyle x\in\bar{\ell'}$ and $\displaystyle \bar{\ell}\subset\bar{\ell'}$. The same logic reveals that $\displaystyle x\in\bar{\ell'}\implies x\in\bar{\ell}$, so that $\displaystyle \bar{\ell'}\subset\bar{\ell}$. Consequently, $\displaystyle \bar{\ell}=\bar{\ell'}$. The conclusion follows.
• Nov 10th 2009, 02:40 PM
nataliemarie
I understand that, but shouldn't I also prove that the intersection is the empty set?
• Nov 10th 2009, 02:50 PM
Drexel28
Quote:

Originally Posted by nataliemarie
I understand that, but shouldn't I also prove that the intersection is the empty set?

Why would you?
• Nov 10th 2009, 03:25 PM
nataliemarie
Because for an or statement the basic proof is too show that if the first half is true, and if the first half isnt true then the second half must be true for the proposition to hold.

so if a1 doesnt equal a2 then their intersection is the empty set. why do i not have to prove that part?
• Nov 10th 2009, 03:33 PM
Drexel28
Quote:

Originally Posted by nataliemarie
Because for an or statement the basic proof is too show that if the first half is true, and if the first half isnt true then the second half must be true for the proposition to hold.

so if a1 doesnt equal a2 then their intersection is the empty set. why do i not have to prove that part?

I think it follows from the original part. But if you feel that it is neccessary, practice never hurt! Try it yourself and report back if you have any issues.