Question

Need help on proving Dom(S o R) ⊆ Dom(R).

R is a relation from A to B
and S is a relation from B to C.

Answer 1

Dom is domain by the way

Answer 2

I can write out the definition for Dom(R).
Dom(R) = {a∈A | ∃b∈B (a,b) ∈ R}

Answer 3

Dom(R) = {a∈A | ∃b∈B ((a,b) ∈ R)}

Answer 4

Can you do the same for S of R?

Answer 5

Dom(R o S) = {a∈A | ∃c∈C ((a,c) ∈ S o R) }

Answer 6

right?

Answer 7

Yes, but you can write c a different way - what about
\[ D(S o R) = \{a \in A | \exists b \in B \space : (a, b) \in R \space \& \space (a,R(b)) \in S\} \]

Answer 8

Or whatever notation you use for the range of the relation R...

Answer 9

I can't seem to make sense of the set above. Could you explain it further?

Answer 10

Sure. So R relates a to b, and S relates b to c, where a,b, and c are elements of A, B, and C respectively.

For an object to be an element of Dom S o R, that would mean that it would have to relate "a" to "c". That has to be an intermediary - S o R relates some "a" to a "b", and then that "b" to a "c". Therefore, we can say that:

The domain of the relation S o R is all "a" such that there exists a "b" whereby (a,b) is an element of R, and FURTHERMORE that there exists a "c" such that (b,c) is an element of S.

I got a bit sloppy with my notation, and it wasn't strictly correct - what I should have said was
\[ D(SoR) = \{ a \in A | \exists b \in B \space \& \space c \in C : (a,b) \in R \space \& \space (b,c) \in S \} \]

Answer 11

Also, should say "There has to be an intermediary ... "

Answer 12

so basically you just broke down (a,c)∈SoR more.

\[Dom(SoR) = \left\{ a∈A | ∃c∈C [∃b∈B ((a,b)∈ R and (b,c)∈S)] \right\}\]

Answer 13

right?

Answer 14

Yep, that's it. Do you see your way to the end now?

Answer 15

Huhm... But how is it that Dom(S o R) ⊆ Dom(R) though? the way I understand it is because there is one more condition in Dom(S o R). Namely "∃c∈C" condition while the only condition in Dom(R) is only "∃b∈B". Is that why?

Answer 16

Yes, that's why. It's possible that Dom (S o R) is equal to Dom R, but it's also possible that there may be some "a" that is related to some "b"s, but NONE of those "b"s are related to a "c".

Answer 17

To be more precise, you can write
\[ Dom(S o R) = Dom (R) \cap Dom(S o R) \]
which is obviously true, and it immediately follows that
\[ Dom(R) \subseteq Dom(S o R) \]

Answer 18

ah I see. Thank you so much for the explanation :)

Answer 19

No problem, glad it was helpful.