# Equivalence Principle: A hint on how to start

1. Sep 11, 2012

### dpa

Equivalence Principle: A hint on how to start!!

Hi, I have no idea where to start.

1. Statement Problem
Let X be a non empty set with a equivalence relation ~ on it. Prove that for all x,y$\in$X,
[x]=[y] if and only if x~y.

2. Relevant equations
For the Equivalence Relation to exist, it must be transitive, reflexive and symmetric.

3. The attempt at a solution
I have no idea where to start. May be,
~ exists means that, x=y. But is self evident.
How do I prove the "only If" part as well?

Thank You.

2. Sep 11, 2012

### voko

Re: Equivalence Principle: A hint on how to start!!

What do the square brackets mean in [x] = [y]?

3. Sep 11, 2012

### dpa

Re: Equivalence Principle: A hint on how to start!!

Hi voko,

I did not understand that either. That is the exact statement in the Homework question. I assumed it simply meant x=y.
Can you help me if it is x=y?

Thank You.

4. Sep 11, 2012

### voko

Re: Equivalence Principle: A hint on how to start!!

This cannot be proven for simple equality, because I can easily give you a counter-example.

Can the square brackets mean the "equivalence class" of x?

5. Sep 11, 2012

### dpa

Re: Equivalence Principle: A hint on how to start!!

Yes, that is it. Still, I have no idea how to prove equivalent classes as equal.

6. Sep 11, 2012

### dpa

Re: Equivalence Principle: A hint on how to start!!

I will try it now.
Thank You.
dpa

7. Sep 11, 2012

### voko

Re: Equivalence Principle: A hint on how to start!!

Start by proving the "if" part. Use the definition of the equivalence class and the properties of equivalence.

8. Sep 11, 2012

### dpa

Re: Equivalence Principle: A hint on how to start!!

Here is my solution,

From the definition of equivalence class, we suppose any z such that,
[x]={z$\in$Xlx~z} holds. - - - - - - - - - - - - - - - - -(i)

for every such z,
since,
x~y and x~z=z~x [property of symmetry]
we write from law of transitivity,
z~y exists.
Thus,
we can now define,
[y]={z$\in$Xly~z}, which is true.
can also be written as
[y]={z$\in$Xlx~z} - - - - - - - - - - - - - - - - - - - - - - - - -(ii)
Thus from i and ii, we can write that
[x]=[y]

Now we show that it holds true only when x~y by method of contradiction (how???).
Suppose there exists w such that x~w, but x~y is false,
but what next?

Do I say since x~y does not exist,
we cannot write,
[y]={z$\in$Xly~z} exists for every
[x]={z$\in$Xlx~z}
??
Any more hints?

9. Sep 11, 2012

### dpa

Re: Equivalence Principle: A hint on how to start!!

I got it. I have to prove if a=>b and then if b=>a.
Is first part correct then?

10. Sep 11, 2012

### voko

Re: Equivalence Principle: A hint on how to start!!

The first part seems OK. The second part, prove by contradiction. Suppose there are x and y such that [x] = [y], but x not ~y.

11. Sep 12, 2012

### dpa

Re: Equivalence Principle: A hint on how to start!!

is it better now?

To Prove [x]=[y] iff x~y
Here, First we take x~y and prove [x]=[y]. Then we take x is not ~y but [x]=[y] and arrive at x~y.

Firstly,
For any element zEX and zE[x] we know there exists a relation z~x
Sincem z~x and x~y, we can write from law of transitivity,
z~y which implies zE[y].

Thus we can write from zE[x] and zE[y] that [x]=[y].

Next, we assume x is not ~y but [x]=[y] exists.
Here, [x]=[y] implies there exists an element z where zE[x] and z~x.
There also exists zE[y] for which z~y exists.
Thus from law of transitivity, and from z~y and z~x, we can write,
x~y.

Thus Prooved.

12. Sep 12, 2012

### voko

Re: Equivalence Principle: A hint on how to start!!

In the second part of the proof, instead of saying "there also exists zE[y]" you should say "because [x] = [y], zE[y]".

Otherwise the proof is good.

13. Sep 12, 2012

### dpa

Re: Equivalence Principle: A hint on how to start!!

Someone said zE[x] and zE[y] cannot imply [x]=[y]. It is indeed true if equivalent relation does not exist.
What happens when the equivalence relation x~y does exist as in above example. So, is the first part of proof correct in the light of this comment?
I am totally new and just had one/two class on this topic.
Thank You.

14. Sep 12, 2012

### voko

Re: Equivalence Principle: A hint on how to start!!

The first part of the proof is correct. You take ANY element from [x] and show that it also exists in [y]. You could equally take ANY element for [y] and likewise show it is in [x]. So each contains all the elements of the other.