1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Equivalence relation proof

  1. Sep 8, 2011 #1
    1. The problem statement, all variables and given/known data

    Suppose R and S are relations on a set A, and S is an equivalence relation. We will say that R is compatible with S if for all w,x,y,z ∈ A, if (w,y) ∈ S and (x,z) ∈ S, then (w,x) ∈ R iff (y,z) ∈ R.

    Prove that if R is compatible with S, then there is a unique relation T on A/S such that for all x,y ∈ A, ([x]s, [y]s) ∈ T iff (x,y) ∈ R.


    2. Relevant equations



    3. The attempt at a solution

    Let T = {([x]s,[y]s) ∈ A/S x A/S | (x,y) ∈ R}. Now let Q be any other relation on A/S such that for all x,y ∈ A, ([x]s,[y]s) ∈ T iff (x,y) ∈ R. To show that T = Q, let ([j]s,[k]s) ∈ T. Then (j,k) ∈ R. But then, ([j]s,[k]s) ∈ Q. This time, let ([j]s,[k]s) ∈ Q. Then (j,k) ∈ R, so ([j]s,[k]s) ∈ T.



    This is my attempt at a proof, but I have a couple of concerns. First, my proof doesn't seem to use the premise that R is compatible with S. Also, a given hint has a slightly different unique relation defined than mine, namely: "Let T = {([x]s,[y]s) ∈ A/S x A/S | ∃x∈[x]s ∃y∈[y]s (x,y) ∈ R}"


    Is my alternative correct? Otherwise, could anyone please indicate where my reasoning is flawed?
     
  2. jcsd
  3. Sep 8, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Hi Syrus!

    Like you expect, there is a flaw in your reasoning. But it's a very subtle flaw. Take a [itex]([x]_S,[y]_S)[/itex] in T with (x,y) in R. But since [itex][\cdot]_S[/itex] is an equivalence class, we could have [itex]([x]_S,[y]_S)=([x^\prime]_S,[y^\prime]_S)[/itex] but [itex](x^\prime,y^\prime)\notin R[/itex]!!

    So you see that we don't necessarily have that
    [tex]([x]_S,[y]_S)\in T~\Rightarrow~(x,y)\in R[/tex]

    Or at least, you still have to prove this.
     
  4. Sep 8, 2011 #3
    Wow, yes. That is somewhat subtle indeed. Does realizing something like this on one's own simpy arise from experience? This problem obviously set off some red flags for me, but I'm worried this may happen unknowingly.

    By the way, the existential quantifiers for T make the problem easy to solve, and the premise of compatibility is used.
     
  5. Sep 8, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, that is experience. You always need to be careful with such a thing when dealing with quotient relations! Always ask yourself: what if [itex]([x]_S,[y]_S)=([x^\prime]_S,[y^\prime]_S)[/itex], does it still hold?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Equivalence relation proof
Loading...