Equivalence relation

**bigdoggy** · November 6th 2009, 11:50 AM

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\}$

**Drexel28** · November 6th 2009, 01:52 PM

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

**bigdoggy** · November 6th 2009, 01:55 PM

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?

**Drexel28** · November 6th 2009, 01:57 PM

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?

**bigdoggy** · November 6th 2009, 02:00 PM

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

**Drexel28** · November 6th 2009, 02:01 PM

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?

**Plato** · November 6th 2009, 02:04 PM

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.

**bigdoggy** · November 6th 2009, 02:06 PM

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

**Drexel28** · November 6th 2009, 02:06 PM

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.

**bigdoggy** · November 6th 2009, 02:10 PM

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

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

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

**Plato** · November 6th 2009, 02:10 PM

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.

**Drexel28** · November 6th 2009, 02:32 PM

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

**Drexel28** · November 6th 2009, 08:27 PM

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.

Thread: Equivalence relation

LinkBack

Thread Tools

Display

Equivalence relation

Similar Math Help Forum Discussions

For the following relation, show that R is an equivalence relation and determine the.

equivalence relation and equivalence classes

Equivalence relation and order of each equivalence class

equivalence relation

Equivalence relation and Equivalence classes?

Search Tags