1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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
    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
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook