Discrete-math 12

Associativity of the function composition #theorem

\begin{matrix} Let \\ f : A \to B \\ g : B \to C \\ h : C \to D \\ h \circ (g \circ f) = (h \circ g) \circ f \\ Proof: \\ \underset{―}{For function h \circ (g \circ f)} \\ f : A \to B, g : B \to C \\ By definition of composition: (g \circ f) : A \to C \\ h : C \to D \\ By definition of composition: (h \circ (g \circ f)) : A \to D \\ \underset{―}{For function (h \circ g) \circ f} \\ g : B \to C, h : C \to D \\ By definition of composition: (h \circ g) : B \to D \\ f : A \to B \\ By definition of composition: ((h \circ g) \circ f) : A \to D \\ ⟹ {\begin{matrix} D o m (h \circ (g \circ f)) = D o m ((h \circ g) \circ f) \\ R a n g e (h \circ (g \circ f)) = R a n g e ((h \circ g) \circ f) \end{matrix} (1) \\ Let a \in A \\ (h \circ (g \circ f)) (a) = h ((g \circ f) (a)) = h (g (f (a))) \\ ((h \circ g) \circ f) (a) = (h \circ g) (f (a)) = h (g (f (a))) \\ ⟹ \forall a \in A : (h \circ (g \circ f)) (a) = ((h \circ g) \circ f) (a) (2) \\ (1) and (2) ⟹ h \circ (g \circ f) = (h \circ g) \circ f \end{matrix}

\begin{matrix} Let f : A \to B, g : B \to C \\ 1. & If (g \circ f) is one-to-one, then f is one-to-one \\ 2. & If (g \circ f) is onto, then g is onto \end{matrix}

\begin{matrix} Proof for 1. \\ Let a_{1}, a_{2} \in A : f (a_{1}) = f (a_{2}) \\ g is complete and to one ⟹ g (f (a_{1})) = g (f (a_{2})) \\ ⟹ By definition of composition: (g \circ f) (a_{1}) = (g \circ f) (a_{2}) \\ (g \circ f) is one-to-one ⟹ a_{1} = a_{2} \\ ⟹ \forall a_{1}, a_{2} \in A : f (a_{1}) = f (a_{2}) \to a_{1} = a_{2} \end{matrix}

\begin{matrix} Proof for 2. \\ Let c \in C \\ (g \circ f) is onto ⟹ \forall c \in C : \exists a \in A : (g \circ f) (a) = c ⟺ g (f (a)) = c \\ Let b = f (a), b \in B \\ ⟹ \forall c \in C : \exists b \in B : g (b) = c \end{matrix}

\begin{matrix} Let f_{1} : A \to B, f_{2} : B \to C \\ If f_{1}, f_{2} are one-to-one \\ Then (f_{2} \circ f_{1}) is one-to-one \\ Proof: \\ Let a_{1}, a_{2} \in A : (f_{2} \circ f_{1}) (a_{1}) = (f_{2} \circ f_{1}) (a_{2}) \\ By definition of composition: (f_{2} \circ f_{1}) (a_{1}) = (f_{2} \circ f_{1}) (a_{2}) ⟺ f_{2} (f_{1} (a_{1})) = f_{2} (f_{1} (a_{2})) \\ f_{2} is one-to-one ⟹ f_{1} (a_{1}) = f_{1} (a_{2}) \\ f_{1} is one-to-one ⟹ a_{1} = a_{2} \\ ⟹ \forall a_{1}, a_{2} \in A : (f_{2} \circ f_{1}) (a_{1}) = (f_{2} \circ f_{1}) (a_{2}) \to a_{1} = a_{2} \end{matrix}

\begin{matrix} Let f_{1}, f_{2}, \dots, f_{n} be one-to-one functions, such that \\ the composition (((f_{n} \circ \dots) \circ f_{2}) \circ f_{1}) is defined \\ Then, (((f_{n} \circ \dots) \circ f_{2}) \circ f_{1}) is also one-to-one \end{matrix}

\begin{matrix} Proof: \\ Base case. Let n = 1 \\ (((f_{n} \circ \dots) \circ f_{2}) \circ f_{1}) = (f_{1}) \\ (f_{1}) is one-to-one \\ Induction step. Let (((f_{n} \circ \dots) \circ f_{2}) \circ f_{1}) be one-to-one \\ Composition of functions is associative \\ ⟹ (((f_{n + 1} \circ \dots) \circ f_{2}) \circ f_{1}) = (f_{n + 1} \circ (((f_{n} \circ \dots) \circ f_{2}) \circ f_{1})) \\ Let g = (((f_{n} \circ \dots) \circ f_{2}) \circ f_{1}) \\ Then (((f_{n + 1} \circ \dots) \circ f_{2}) \circ f_{1}) = (f_{n + 1} \circ g) \\ g is one-to-one and f_{n + 1} is one-to-one \\ By the lemma above: (f_{n + 1} \circ g) is one-to-one \\ ⟹ (((f_{n + 1} \circ \dots) \circ f_{2}) \circ f_{1}) is one-to-one \\ Base case + induction step ⟹ Proved by induction \end{matrix}