Question

R is a relation from A to B. S and T are relations from B to C. Prove/disprove (S ∩ T) o R = (S ∩ R) o (T ∩ R)?

I'm having a hunch that's is true. I already proved t (S∩T) o R ⊆ (S∩R) o (T∩R). Now I need help proving the other direction

Answer 1

here is what i have so far...

Answer 2

oh wait, typo hold on

Answer 3

(S ∩ T) o R = (S o R) ∩ (T o R)?

Answer 4

again, I proved
(S∩T) o R ⊆ (SoR) ∩ (T o R)

Answer 5

Use \[
(b,c)\in S\land (b,c)\in T \land (a,b) \in R \\
\implies [(b,c)\in S\land (a,b) \in R]\land [(b,c)\in T \land (a,b) \in R]
\]

Answer 6

Basically \(p\implies p\land p\)

Answer 7

Then move them around with commutative property.

Answer 8

I fixed my typo. It was supposed to be
(S ∩ T) o R = (S o R) ∩ (T o R)

not (S ∩ R) o (T ∩ R)

:D

Answer 9

ok, here is what i have:
let (x,y) ∈ (S o R) ∩ (T o R), then
(x,y) ∈(SoR) and (x,y) ∈ (ToR)
∃b∈B [(x,b)∈R and (b,y)∈S] and ∃b'∈B [(x,b')∈R and (b',y)∈T]

Answer 10

the problem is that i can not move the ∃b out in front because that is not equivalent to the statement above

Answer 11

also b and b' may not be the same element

Answer 12

Then find a counter example.

Answer 13

huhm... so I need to come up with (x,y) ∈ (S o R) ∩ (T o R) but, (x,y) ∉ (S ∩ T) o R ?

Answer 14

S = {(1,2)}
T = {(1,3)}
R = {(2,1), (3,1)}

\((S\cap T) \circ R= \emptyset \circ R = \emptyset \)
While
\[
(S\circ R)\cap (T\circ R) = \{(1,1)\}\cap \{(1,1)\} = \{(1,1)\}
\]

Answer 15

wait how is S o R = { (1,1) }

Answer 16

?

Answer 17

Just reverse the order

Answer 18

reverse what order?

Answer 19

S = {(2,1)}
T = {(3,1)}
R = {(1,2), (1,3)}

\((S\cap T) \circ R= \emptyset \circ R = \emptyset \)
While
\[
(S\circ R)\cap (T\circ R) = \{(1,1)\}\cap \{(1,1)\} = \{(1,1)\}
\]

Answer 20

Perfect! thanks a punch! ^^

Answer 21

so the statement is false after all.

Answer 22

thanks a *bunch* XD haha