Equivalence Relations Proof

**nataliemarie** · November 10th 2009, 09:00 AM

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.

**Drexel28** · November 10th 2009, 12:17 PM

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 $E$ be a set and $\sim$ an equivalence relation on $E$ . If $\ell\in E$ let $\bar{\ell}=\left\{\ell'\in E:\ell\sim\ell'\right\}$ . Prove that either $\bar{\ell}\cap\bar{\ell'}$ is empty or $\bar{\ell}=\bar{\ell'}$

Proof: Let $\bar{\ell}\cap\bar{\ell'}\ne\varnothing$ . Then there exists some $k\in E$ such that $k\in\bar{\ell},\bar{\ell'}$ . By definition though this means that $\ell\sim k$ and $\ell'\sim k$ . Since $\sim$ is an equivalence relation we see that $\ell'\sim k\implies k\sim \ell'$ . Furthermore, we know that $\sim$ is transitive and that $\ell\sim k,k\sim \ell'$ . Therefore $\ell\sim \ell'$ . Now let $x\in\bar{\ell}$ , then $\ell \sim x$ . Once again though, we see that $\ell \sim x$ and $\ell\sim\ell'\implies \ell'\sim\ell$ implies $\ell'\sim x$ . Therefore $x\in\bar{\ell'}$ and $\bar{\ell}\subset\bar{\ell'}$ . The same logic reveals that $x\in\bar{\ell'}\implies x\in\bar{\ell}$ , so that $\bar{\ell'}\subset\bar{\ell}$ . Consequently, $\bar{\ell}=\bar{\ell'}$ . The conclusion follows.

**nataliemarie** · November 10th 2009, 02:40 PM

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

**Drexel28** · November 10th 2009, 02:50 PM

Originally Posted by nataliemarie

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

Why would you?

**nataliemarie** · November 10th 2009, 03:25 PM

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?

**Drexel28** · November 10th 2009, 03:33 PM

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.

Thread: Equivalence Relations Proof

LinkBack

Thread Tools

Display

Equivalence Relations Proof

Similar Math Help Forum Discussions

Mathematical logic--> Binary relations, orders, and equivalence relations/classes

Question on equivalence relations and equivalence classes

equivalence relations

Equivalence Relations

Equivalence Relations

Search Tags