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.

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.

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

Powered by vBulletin® Version 4.2.2 Copyright © 2014 vBulletin Solutions, Inc. All rights reserved.