And yes, the existential quantifiers make it much easier to solve.

[Syrus]

Homework Statement

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.

Homework Equations

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?

 

[micromass]

Homework Statement

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.

Homework Equations

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?

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.

 

[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.

 

[micromass]

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.

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?