Homework Help: Equivalence relation proof

1. Sep 8, 2011

Syrus

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. Sep 8, 2011

micromass

Hi Syrus!

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

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

Or at least, you still have to prove this.

3. Sep 8, 2011

Syrus

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.

4. Sep 8, 2011

micromass

Yes, that is experience. You always need to be careful with such a thing when dealing with quotient relations! Always ask yourself: what if $([x]_S,[y]_S)=([x^\prime]_S,[y^\prime]_S)$, does it still hold?

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook