# Math Help - Equivalence relation

1. ## Equivalence relation

If I have a subset, how do I define an equivalence relation.
I understand it has to satisfy three properties:transitive, symmetric and reflexive, but I'm not sure how to give an explicit definition of the equivalence relation, for example on I where
$I=\{(x,y) : 0 \le x\le 1 \ \& \ 0 \le y \le 1\}$

2. Originally Posted by bigdoggy
If I have a subset, how do I define an equivalence relation.
I understand it has to satisfy three properties:transitive, symmetric and reflexive, but I'm not sure how to give an explicit definition of the equivalence relation, for example on I where
$I=\{(x,y) : 0 \le x\le 1 \ \& \ 0 \le y \le 1\}$
How about the old fashioned partition way. Partition $[0,1]\times[0,1]$ Into $\left[0,\frac{1}{2}\right]\times\left[0,1\right]=X_1$ and $\left(\frac{1}{2},1\right]\times\left(0,1\right]$. Define an equivalence relation $\sim$ on $I$ by $(x,y)\sim (x_1,y_1)\text{ iff they belong to the same block}$

3. Originally Posted by Drexel28
How about the old fashioned partition way. Partition $[0,1]\times[0,1]$ Into $\left[0,\frac{1}{2}\right]\times\left[0,1\right]=X_1$ and $\left(\frac{1}{2},1\right]\times\left(0,1\right]$. Define an equivalence relation $\sim$ on $I$ by $(x,y)\sim (x_1,y_1)\text{ iff they belong to the same block}$
Hi
I've never seen that before...please could you elaborate?

4. Originally Posted by bigdoggy
Hi
I've never seen that before...please could you elaborate?
What exactly is troubling you? What the relation means...or why it is an equivalence relation?

5. Originally Posted by Drexel28
What exactly is troubling you? What the relation means...or why it is an equivalence relation?
To be honest I'm new to this area..I've been looking at the problem for a while!
I know how to verify if a relation is an equivalence relation...but I've not seen a problem which asks to 'give the explicit definition of the equivalence relation'...

6. Originally Posted by bigdoggy
To be honest I'm new to this area..I've been looking at the problem for a while!
I know how to verify if a relation is an equivalence relation...but I've not seen a problem which asks to 'give the explicit definition of the equivalence relation'...
Now I'm lost. I thought we were talking about the partition relation I gave you. Is there something else your asking now?

7. Originally Posted by Drexel28
What exactly is troubling you? What the relation means...or why it is an equivalence relation?
I think that it needs to be pointed out that there are uncountably many equivalent relations on that set.

8. Originally Posted by Drexel28
Now I'm lost. I thought we were talking about the partition relation I gave you. Is there something else your asking now?
Sorry...I was referring back to the stated problem.
I guess I'm not sure what 'type' of solution or what it should look like....I understand I'm being extremely vague, but I'm lost on where to start

9. Originally Posted by Plato
I think that it needs to be pointed out that there are uncountably many equivalent relations on that set.
Yes. Plato is right. And not just uncountably man differnt partition relations but relations of every kind and flavor.

10. Originally Posted by Drexel28
Yes. Plato is right. And not just uncountably man differnt partition relations but relations of every kind and flavor.
that adds some clarity...I was, for some reason, expecting there to be one single unique equivalence relation....

11. For an even simpler one (still partition) what about paritioning this set into points whose coordinates are rational and those that are not?

12. Originally Posted by Drexel28
Yes. Plato is right. And not just uncountably man differnt partition relations but relations of every kind and flavor.
My point of course is I do not think that the questioner understands that point.
Nor do I think that he/she has any idea of the one-to-one correspondence between equivalence relations and partitions.

13. If the OP can wait I'll post up the concept of partitions/ERs corresponence.

14. As promised. First we need a little background, namely 'what is a partition?'

Definition: Let $\pi=\left\{E_{\alpha}:\text{ }\alpha\in\mathcal{I}\right\}$ be a collection of sets, with $\mathcal{I}$ being some indexing set. Then $\pi$ is a partition of a set $E$ if

1) $E_{\alpha_1}\cap E_{\alpha_2}=\varnothing\quad\alpha_1\ne \alpha_2$

2) $\bigcup_{\alpha\in\mathcal{I}}E_{\alpha}=E$

In simpler terms, a collection of sets (specifically subsets) of $E$ is a partition if no two of them overlap and their union is the entire set. Think about it as taking the whole set and cutting it into pieces. We call the indvidual $E_{\alpha}$'s 'blocks' of the partition.

Definition: Equivalence class- Let $E$ be a set, and $\sim$ and equivalence relation on $E$. Then the set $\bar{a}=\left\{x:a\sim x\right\}$ is called the equivalence class of $a$.

Theorem: A parition $\pi$ of $E$ induces an equivalence relation on $E$.

Proof: This relation, which we'll call $\stackrel{\pi}{\sim}$, is defined by $a\stackrel{\pi}{\sim}b\Longleftrightarrow \left(a\in E_{\alpha}\right)\wedge \left(b\in E_{\alpha}\right)$ for the same $E_{\alpha}\in \pi$. We prove that is satisfies the three conditions of an equivalence relation.

1. Relfexive- Since $a$ belongs to precisely one set it is clear that $a\stackrel{\pi}{\sim}a$

2. Symmetric- Keeping in mind that each element belongs to exactly one element of $\pi$ it is clear that if $a\stackrel{\pi}{\sim}b\Longleftrightarrow \left(a\in E_{\alpha}\right)\wedge\left(b\in E_{\alpha}\right)$ that $\left(b\in E_{\alpha}\right)\wedge\left(a\in E_{\alpha}\right)\Longleftrightarrow b\stackrel{\pi}{\sim}a$

3. Transitive- Suppose that $a\stackrel{\pi}{\sim}b\Longleftrightarrow a,b\in E_{\alpha}$ and $b\stackrel{\pi}{\sim}c\Longleftrightarrow b,c\in E_{\alpha}$. And note that since [tex]b[\math] belongs to precisely one $E_{\alpha}$ that $a,c$ must belong the same $E_{\alpha}$ or in other words $a\stackrel{\pi}{\sim}c$

This proves that a partition $\pi$ defines a relation on $E$.

We next move onto our next concept.

Theorem: An equivalence relation $\sim$ on a set $E$ induces a partition on $E$

Proof: Define a parition $\pi$ on $E$ by $\pi=\left\{\bar{a}:a\in E\right\}$. Let us show that this is a parition.

1) Suppose that $\bar{a}\ne \bar{b}$. WLOG Let $x\in\bar{a}$ then $a\sim x$ so that $x\sim a$ which of course means that $x\nsim a$. This means that $x\notin\bar{b}$. Thus no element of $\bar{a}$ is in $\bar{b}$. The exact same method shows that no element of $\bar{b}$ is in $\bar{a}$. Thus $\bar{a}\cap\bar{b}=\varnothing$.

2) Clearly $\forall a\in E$ $a\in\bar{a}$. So clearly every element of $E$ is in some equivalence class (namely it's own equivalence class). So $\bigcup_{a\in E}\bar{a}=\bigcup_{x\in\pi}x=E$.

This shows that $\pi$ is a partition of $E$

This is all that is really needed. But just in case here is one last theorem.

Theorem: If $\bar{a}\cap\bar{b}\ne\varnothing$ then $\bar{a}=\bar{b}$

Proof: If $\bar{a}\cap\bar{b}\ne\varnothing$ hen there exists some $c\in\bar{a},\bar{b}$ but by definition that means that $a\sim c$ and $b\sim c$. But because $\sim$ is an equivalence relation we can see that bu symmetry $b\sim c\implies c\sim b$. So $a\sim c$ and $c\sim b$ which by transitivity means that $a\sim b$. Now clearly then for any $x\in \bar{a}$ we can see that $x\sim a$ and $a\sim b$ therefore $x\sim b$, so $\bar{a}\subset\bar{b}$. The same methodology shows that $\bar{b}\subset\bar{a}$. Thus we conclude that $\bar{a}=\bar{b}$

This just about does it. It's late and I easily could have made a typo but I hope you get the point.