[a]=[b] <--> a~b

• Aug 16th 2012, 02:20 PM
lamp23
[a]=[b] <--> a~b
Thm: [a]=[b] <--> a~b

I have proved:
[a]=[b] --> a~b

but cannot figure out how to prove:
[a]=[b] <-- a~b

I don't know if I can just write the steps backwards since I don't see how I would know: (4) --> (5)
http://i900.photobucket.com/albums/a...mp23/equiv.jpg

This fact was stated without proof in a youtube playlist on equivalence relations: Equivalence relations 3 - YouTube
• Aug 16th 2012, 02:48 PM
Plato
Re: [a]=[b] <--> a~b
Quote:

Originally Posted by lamp23
Thm: [a]=[b] <--> a~b
I have proved:
[a]=[b] --> a~b
but cannot figure out how to prove:
[a]=[b] <-- a~b

Suppose that $\displaystyle a \sim b$ then if $\displaystyle x\in[a]$ we know that $\displaystyle x \sim a$.
Because $\displaystyle a \sim b~\&~x \sim a$ we know that $\displaystyle x \sim b$ or $\displaystyle x \in [b]$

Can you finish?
• Aug 16th 2012, 02:51 PM
ModusPonens
Re: [a]=[b] <--> a~b
I think (3) and (4) need an existencial quantifier for the variable x. Otherwise, seems fine.
• Aug 16th 2012, 03:00 PM
Plato
Re: [a]=[b] <--> a~b
Quote:

Originally Posted by ModusPonens
I think (3) and (4) need an existencial quantifier for the variable x. Otherwise, seems fine.

Actually no that is not necessary.
If we start with $\displaystyle [a]=[b]$ then because $\displaystyle a\in [a]$ we know that $\displaystyle a\in [b]$ or $\displaystyle a\sim b$.
• Aug 16th 2012, 03:53 PM
lamp23
Re: [a]=[b] <--> a~b
Quote:

Originally Posted by Plato
Suppose that $\displaystyle a \sim b$ then if $\displaystyle x\in[a]$ we know that $\displaystyle x \sim a$.
Because $\displaystyle a \sim b~\&~x \sim a$ we know that $\displaystyle x \sim b$ or $\displaystyle x \in [b]$

Can you finish?

Yes, thanks a lot. I was missing using the given of "Suppose $\displaystyle x\in[a]$"
• Aug 16th 2012, 06:01 PM
ModusPonens
Re: [a]=[b] <--> a~b
Yes. But isn't that a different proof? I mean if we want to make the proof in the OP correct, isn't there a need of a quantifier in order for a (an element, ultimately, a set) to be in relation with another element (which x is not, because it's a free variable)? I'm unsure.
• Aug 16th 2012, 07:11 PM
Deveno
Re: [a]=[b] <--> a~b
yes, something along the lines of: let x be in [a] = [b]. we know such an x exists because both [a] and [b] are non-empty (because ~ is an equivalence, so ~ is reflexive. so at the very least, a is in [a], and b is in [b] (a and b may actually be the same, but perhaps not)).

but it's not necessary to introduce x at all. as Plato points out, we have:

a in [a] = [b], so a in [b], so b~a, and by symmetry, a~b. doing so eliminates the need to use transitivity to show [a] = [b] → a~b (we we *do* need transitivity to show the reverse implication, however).