Proving Equivalence Class Intersection and Equality

[wolfmanzak]

Homework Statement

I'm trying to prove that "if R is an equivalence relation on a set A, prove that if s and t are elements of A then either intersect [t] = empty set, or, =[t]"

Homework Equations

The Attempt at a Solution

I know that if you were to start trying to solve this you could try to do a proof by contradiction where you assume that intersect [t] is not= empty set and thus you could pick an x in intersect [t] and that x~s and x~t and thus s~t so then because they are in the same equivalence class that =[t]. But I want to find a more direct way to show that " intersect [t] = empty set" and I'm a bit lost as to how to do so. Any and all help is welcome.

 

[micromass]

I'm a bit confused? Your proof is already a direct proof...
Proving something of the form [tex]P\Rightarrow Q\vee R[/tex] always happens the same way: assume P holds and Q doesnt, prove that R holds. This is exactly what you've done. I really see no more direct proof...

 

[wolfmanzak]

Suppose[tex]{\cal R}[/tex] is an equivalence relation on set [tex]A[/tex]. Prove that if s and t are elements of [tex]A[/tex], then either [tex]E_{s} \cap E_{t}= \varnothing[/tex] or [tex]E_{s} = E_{t}[/tex]

Here is the actual statement of the problem...I'm just trying to find other ways of doing this proof...I'm not sure if the way I did the proof is the best method and want some other ways to do it. I appreciate your help, let me know what you think.

 

[micromass]

The way you proved it is the best possible proof there is. But maybe someone else will provide with a better proof that I don't know about...

 

[wolfmanzak]

Equivalence Class Proofs (Need other ideas)

Homework Statement

Suppose [tex]{\cal R}[/tex] is an equivalence relation on set [tex]A[/tex]. Prove that if [tex]s[/tex] and [tex]t[/tex] are elements of [tex]A[/tex], then either [tex]E_{s} \cap E_{t}= \varnothing[/tex] or [tex]E_{s} = E_{t}[/tex].

Homework Equations

The Attempt at a Solution

My thought process tells me to do a proof by contradiction where you assume that [tex]E_{s} \cap E_{t} \ne \varnothing[/tex]. And thus you can pick an [tex]x \in E_{s} \cap E_{t}[/tex]. This gives you x~s and x~t, and becaues it's an equivalence relation, that s~t, which finally shows that [tex]E_{s} = E_{t}[/tex]. I'm basically showing this to give you my ideas so far, I would greatly appreciate any other suggestions or thought as to how to do this proof. I'm at a loss for other ideas.

 

[radou]

Actually, the concept of the proof is not basically contradiction. You assumed the classes are not disjoint, and arrived at a conclusion that they are equal. So, they are either disjoint, or equal.

You have only shown that s~t, but this doesn't immediately show they're equal. Take any element x in Es, and show it is in Et too, and vice versa. Then you can conclude that they're equal.

 

[wolfmanzak]

How would I do that? I'm basically running on a hunch that [tex]E_{s}=E_{t}[/tex] if s~t. First, how do I prove that? From there I think I can follow with the proof that I first asked about...but I'm just trying to figure out how to show that if two elements of a set are related, then there Equivalence classes are equal?

 

[HallsofIvy]

Consider two cases:
1) t is in [itex]E_s[/itex] and show that if x~t then x~s.

2) t is not in [itex]E_s[/itex] and show that if x~t the x is not equivalent to s (this might require contradiction).

 

[wolfmanzak]

Well, I understand what you mean...I am just looking for another way around it. I do appreciate your help though, thank you.

Can you tell me how you would prove this one though? It follows closely to what I've already inquired about, again I'm just looking for the best way to do this, either by direct proof, contradiction, etc.

Suppose [tex]\sim[/tex] is an equivalence relation on a set [tex]A[/tex]. If a~b for some a,b [tex]\in S[/tex] then [tex]E_{a} = E_{b}[/tex].

 

[wolfmanzak]

I am very close at figuring this out, or so I think...tell me how you would prove this...I think that if I can get a good grasp at the logic and method by which this can be proved, then I think that I can get much closer to an actual proof of the question I asked originally. Thank you in advance for your help! It's most appreciated!


It follows closely to what I've already inquired about, again I'm just looking for the best way to do this, either by direct proof, contradiction, etc.

Suppose [tex]\sim[/tex] is an equivalence relation on a set [tex]A[/tex]. If a~b for some a,b [tex]\in S[/tex] then [tex]E_{a} = E_{b}[/tex].

 

[micromass]

You've got to prove that two sets are equal. For this you need to show

[tex]x\in E_a \ \Leftrightarrow \ x\in E_b[/tex]

So take an x in E_a, we know that [tex]x\sim a[/tex]. What you need to show now is that [tex]x\sim b[/tex].

 

[HallsofIvy]

You have, for some reason, posted the same question twice. I have merged the two threads.

 

[wolfmanzak]

Thanks for the help, from all of you. It is much appreciated. I believe I have a much better understanding of it now.

Thanks again,
WMZ