# Thread: Proofs: Domain of composite functions

1. ## Proofs: Domain of composite functions

Here is the question I am trying to solve:

Let R be a relation from A to B and S be a relation from B to C

Prove that: Dom($\displaystyle S \circ R$) $\displaystyle \subseteq$ Dom(R)
I imagine that I would begin by trying to prove that:

$\displaystyle \varphi \in$ Dom ($\displaystyle S \circ R$) $\displaystyle \Rightarrow \varphi \in$ Dom(R)

however, I have no idea how to go about doing this. no doubt this stems from my inability to define the domain of a composite function

any help would be much appreciated!

2. Originally Posted by DHC
Let R be a relation from A to B and S be a relation from B to C, Prove that: Dom(SoR ) Dom(R)
Here is the definition of the composition.
$\displaystyle \left( {a,b} \right) \in S \circ R \Rightarrow \left( {\exists c \in B} \right)\left[ {\left( {a,c} \right) \in R \wedge \left( {c,b} \right) \in S} \right]$.
From which the proof follows rather easily.

3. Originally Posted by Plato
Here is the definition of the composition.
$\displaystyle \left( {a,b} \right) \in S \circ R \Rightarrow \left( {\exists c \in B} \right)\left[ {\left( {a,c} \right) \in R \wedge \left( {c,b} \right) \in S} \right]$.
From which the proof follows rather easily.
how does this sound, then?

$\displaystyle S \circ R =${$\displaystyle (a,c): (\exists b \in B) (a,b) \in R \wedge (b,c) \in S$} $\displaystyle \Rightarrow Dom(S \circ R)=${$\displaystyle x \in Dom(R): R(x) \in Dom(S)$}

hence for x to be in $\displaystyle Dom(S \circ R)$, x must be in Dom(R)