Thread: 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!

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.

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)