Composite, Relations, and Domain: Let R:A->B and....

tegra97

New member
Joined
Sep 2, 2006
Messages
38
Let R be a relation from A to B and S be a relation from B to C. Prove that Dom(S o R) is a subset of Dom(R). (the notation "o" represents the composite of R and S is S o R)

So can we say S o R is a relation from A to C since S o R is a subset of A x B. So its true that Dom (S o R) is a subset of Dom (R). Am I missing something? thanks
 
Why are you trying to work with the cross of A and B, when you are given that R is a function from A to B? The cross is not involved in any of the givens, is it?

Instead, you might want to try the (fairly standard) practice of "element chasing". To show that the domain of S(R(A)) is a subset of the domain of R (that is, of A), pick an element of the domain of S(R(A)), and see where it goes. Try to show that it is indeed an element of A.

Eliz.
 
Simply use the definitions:
\(\displaystyle \left( {x,y} \right) \in S \circ R\quad \Leftrightarrow \quad \left( {\exists z \in B} \right)\left[ {\left( {x,z} \right) \in R \wedge \left( {z,y} \right) \in S} \right]\).
How does domain relate to that definition?
 
pka said:
How does domain relate to that definition?
That the domain belongs to S o R and belongs to R.
So if (x,z) belongs to R and (z,y) belongs S, then x belongs to S o R then x belongs to R. So Dom(S o R) is a subset of Dom (R)?
When I do an example problem with numbers I can see that Dom(S o R) will be in Dom (R). I just have trouble writing it.
 
Any pair (a,b) in SoR means that a is in the dom(R).
 
Top