Discrete-math 13

Invertible function #definition

\begin{matrix} Function f : A \to B is called invertible if there exists a function g : B \to A such that \\ (g \circ f) = I d_{A} \\ (f \circ g) = I d_{B} \\ In this case, g is called the inverse of f and vice versa \end{matrix}

\begin{matrix} f : R \to R, f (x) = x + 1 \\ g : R \to R, g (x) = x - 1 \\ (g \circ f) (x) = f (g (x)) = x \\ (f \circ g) (x) = g (f (x)) = x \end{matrix}

\begin{matrix} If function has in inverse, it is unique \\ Let f : A \to B \\ \exists g : B \to A : (g \circ f) = I d_{A} ⟹ \exists! g : B \to A : (g \circ f) = I d_{A} \\ Proof: \\ Let g_{1}, g_{2} : B \to A : (g_{1} \circ f) = I d_{A} \land (f \circ g_{2}) = I d_{B} \\ Let b \in B \\ g_{2} (b) = (I d_{A} \circ g_{2}) (b) = ((g_{1} \circ f) \circ g_{2}) (b) = (g_{1} \circ (f \circ g_{2})) (b) = \\ = (g_{1} \circ I d_{B}) (b) = g_{1} (b) \\ ⟹ \forall b \in B : g_{1} (b) = g_{2} (b) ⟹ g_{1} = g_{2} \end{matrix}

\begin{matrix} Inverse function is usually denoted as f^{- 1} \end{matrix}

\begin{matrix} Let f : A \to B \\ (f^{- 1})^{- 1} = f \\ Proof: \\ \exists f^{- 1} : B \to A : (f^{- 1} \circ f) = I d_{A}, (f \circ f^{- 1}) = I d_{B} \\ By definition: f^{- 1} is invertible and f is an inverse of f^{- 1} \end{matrix}

\begin{matrix} Let f : A \to B, g : B \to C be invertible functions \\ Then (g \circ f) is invertible, and (g \circ f)^{- 1} = (f^{- 1} \circ g^{- 1}) \\ Proof: \\ ((g \circ f) \circ (f^{- 1} \circ g^{- 1})) = (g \circ (f \circ f^{- 1}) \circ g^{- 1}) = (g \circ (I d_{B} \circ g^{- 1})) = (g \circ g^{- 1}) = I d_{C} \\ ((f^{- 1} \circ g^{- 1}) \circ (g \circ f)) = (f^{- 1} \circ (g^{- 1} \circ g) \circ f) = (f^{- 1} \circ (I d_{B} \circ f)) = (f^{- 1} \circ f) = I d_{A} \end{matrix}

\begin{matrix} Let f : A \to B \\ \exists f^{- 1} ⟺ f is bijective \\ Proof: \\ Let \exists f^{- 1} \\ (f^{- 1} \circ f) = I d_{A}, (f \circ f^{- 1}) = I d_{B} \\ I d_{A} is injective ⟹ (f^{- 1} \circ f) is injective ⟹ f is injective \\ I d_{B} is surjective ⟹ (f \circ f^{- 1}) is surjective ⟹ f is surjective \\ ⟹ f is bijective & [1] \\ Let f be bijective \\ Let f^{- 1} = {(b, a) \in B \times A | f (a) = b} \\ f is surjective ⟹ \forall b \in B \exists a \in A : f (a) = b \\ ⟺ \forall b \in B \exists a \in A : (b, a) \in f^{- 1} \\ ⟹ f^{- 1} is complete & (1) \\ f is injective ⟹ \forall b \in B, \forall a_{1}, a_{2} \in A : [f (a_{1}) = f (a_{2}) = b \to a_{1} = a_{2}] \\ ⟺ \forall b \in B, \forall a_{1}, a_{2} \in A : [(b, a_{1}), (b, a_{2}) \in f^{- 1} \to a_{1} = a_{2}] \\ ⟹ f^{- 1} is to one & (2) \\ (1) \land (2) ⟹ f^{- 1} : B \to A, f^{- 1} (b) = a \\ (f^{- 1} \circ f) (a) = f^{- 1} (f (a)) = f^{- 1} (b) = a ⟹ (f^{- 1} \circ f) = I d_{A} \\ (f \circ f^{- 1}) (b) = f (f^{- 1} (b)) = f (a) = b ⟹ (f \circ f^{- 1}) = I d_{B} \\ ⟹ \exists f^{- 1} & [2] \\ [1] \land [2] ⟹ f^{- 1} ⟺ f is bijective \end{matrix}