PDA

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



tegra97
04-03-2007, 06:47 PM
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

stapel
04-03-2007, 06:51 PM
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.

pka
04-03-2007, 07:27 PM
Simply use the definitions:
\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?

tegra97
04-03-2007, 08:04 PM
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.

pka
04-03-2007, 09:41 PM
Any pair (a,b) in SoR means that a is in the dom(R).

tegra97
04-03-2007, 09:47 PM
So would my proof be correct?
thanks