4
$\begingroup$

THEOREM: If $ \text{ran } F \subseteq \text{dom } G $ then $\text{dom }(G \circ F)= \text{dom }F$

PROOF: if $ F\subseteq A \times B$ and $ G\subseteq B\times C$

then by definition

$\text{dom }F=A \\\text{ ran }F=B$ $\text{dom }G=B\\\text{ran }G=C$

Now $(G \circ F)\subseteq A \times C$ by definition

so $\text{dom}(G \circ F)= A =\text{dom}F$

$ QED $

  • 0
    I’m afraid not; I’ll write up an explanation.2012-09-10

1 Answers 1

2

The fact that a function is a subset of $A\times B$ is no guarantee that the range of the function is $A$, so you can’t infer from $G\circ F\subseteq A\times C$ that $\operatorname{dom}(G\circ F)=A$. You also assumed more than you were given when you made $\operatorname{dom}G=\operatorname{ran}F$: all that you’re allowed to assume is that $\operatorname{dom}G\subseteq\operatorname{ran}F$.

It isn’t really necessary, or even all that helpful in this case, to introduce new names for the domains and ranges of $F$ and $G$; using the $\text{dom}$ and $\text{ran}$ notations explicitly makes it easier to keep in mind just what set we’re talking about at any given moment, so that’s what I’ll do.

By definition $G\circ F=\Big\{\langle a,c\rangle\in\operatorname{dom}F\times\operatorname{ran}G:\langle a,b\rangle\in F\text{ and }\langle b,c\rangle\in G\text{ for some }b\Big\}\;.$

From this definition it’s immediately clear that $\operatorname{dom}(G\circ F)\subseteq\operatorname{dom}F$, so we need only show that $\operatorname{dom}F\subseteq\operatorname{dom}(G\circ F)$. This is an easy bit of ‘element-chasing’: start with an arbitrary $a\in\operatorname{dom}F$, and show that it belongs to $\operatorname{dom}(G\circ F)$.

So let $a\in\operatorname{dom}F$ be arbitrary. Then there is a $b\in\operatorname{ran}F$ such that $\langle a,b\rangle\in F$. But $\operatorname{ran}F\subseteq\operatorname{dom}G$ by hypothesis, so $b\in\operatorname{dom}G$, and therefore there is a $c\in\operatorname{ran}G$ such that $\langle b,c\rangle\in G$. Thus, there is a $b$ such that $\langle a,b\rangle\in F$ and $\langle b,c\rangle\in G$, so $\langle a,c\rangle\in G\circ F$, and hence $a\in\operatorname{dom}(G\circ F)$ by definition. This shows that $\operatorname{dom}F\subseteq\operatorname{dom}(G\circ F)$, and since we already knew that $\operatorname{dom}(G\circ F)\subseteq\operatorname{dom}F$, we’ve shown that $\operatorname{dom}(G\circ F)=\operatorname{dom}F$.