Showing the composition of two into functions is a function.

240 Views Asked by At

Below is my solution to the problem...

'Show for any functions $F:B \to C$ and $G:A \to B$, $F \circ G$ is a function.'

$\;$

Solution:

Definition 1: Let $X \subseteq Y \times Z$ be a function. If $Dom(X)=Y$ and $Ran(X) \subseteq Z$, we say '$X$ maps $Y$ into $Z$'; denoted $X:Y \to Z$.

Definition 2: Let $X \subseteq Y \times Z$ be a relation. If for every $y \in Dom(X)$ there is a unique $z \in Ran(X)$ such that $yXz$, then $X$ is a function.


Suppose by way of contradiction that the relation $F \circ G \subseteq A \times C$ is not a function. Note, by Def. 1, $G:A \to B$ implies $G(a)=b$ for all $a \in Dom(G)=A$. Similarly, note $F:B \to C$ implies $F(b)=c$ for all $b \in Dom(F)=B$. It follows that $(a,c) \in F \circ G$; hence $F \circ G \neq \emptyset$.

Since $F \circ G$ is nonempty and not a function, by Def. 2 there must exist an element $a_{0} \in Dom(F \circ G)$ such that $$(a_{0},c_{1}) \in F \circ G \; \text{ and } \; (a_{0},c_{2}) \in F \circ G,$$ where $c_{1},c_{2} \in Ran(F \circ G)$ and $c_{1} \neq c_{2}$.

By the definition of relation composition, $(a_{0},c_{1}) \in F \circ G$ implies there exists a $b_{1} \in B$ such that $$G(a_{0})=b_{1} \; \text{ and } \; F(b_{1})=c_{1}.$$ Similarly, $(a_{0},c_{2}) \in F \circ G$ implies there exists a $b_{2} \in B$ such that $$G(a_{0})=b_{2} \; \text{ and } \; F(b_{2})=c_{2}.$$

Note, as $G:A \to B$ is a function, it must be that \begin{align} G(a_{0})&=b_{1} \\ &=b_{2}. \end{align}It follows that \begin{align} F(b_{1}) &= F(b_{2}) \\ &=c_{1} \\ &=c_{2}, \end{align} contradicting our assumption that $c_{1} \neq c_{2}$. Therefore for any two functions $G:A \to B$ and $F:A \to C$, $F \circ G$ is a function.

$\;$

It seems pretty standard and I feel good about this proof. What gave me any semblance of doubt is that I had to use the contrapositive of the definition of a function in order to proceed with a proof by contradiction. Is this valid? I've used this technique on propositions, statements, and theorems before to manipulate their properties, but I don't think I've ever done so with definitions. Was there a better/ quicker way to do this problem? Anyways, any input would be appreciated. Thank you!