In this section we give some cancellation laws for composition. Let \(f:X\to Y,~\tilde{f}:X\to Y,~g:Y\to Z\), and \(\tilde{g}:Y\to Z\) be functions. Show that if \(g\circ f=g\circ\tilde{f}\) and \(g\) is injective, then \(f=\tilde{f}\). Is this same statement true if \(g\) is not injective? Show that if \(g\circ f=\tilde{g}\circ f\) and \(f\) is surjective, then \(g=\tilde{g}\). Is the same statement true if \(f\) is not surjective?
-
\(\bullet\) Show that \(g\circ f=g\circ\tilde{f}\implies f=\tilde{f}\) when
-
– \(g\) is injective: \(g(y)=g(y')\implies y=y'\)
-
\(\Vdash\) \(g\circ f=g\circ\tilde{f}\)
-
\(\equiv\) { Definition 3.3.7 }
- \(\forall x,~(g\circ f)(x)=(g\circ\tilde{f})(x)\)
-
\(\equiv\) { Definition 3.3.10 }
- \(\forall x,~g(f(x))=g(\tilde{f}(x))\)
-
\(\Rightarrow\) { \(g\) is injective }
- \(\forall x,~f(x)=\tilde{f}(x)\)
-
\(\equiv\) { Definition 3.3.7 }
- \(f=\tilde{f}\)
-
\(\square\)
-
\(\bullet\) Show that \(g\circ f=g\circ\tilde{f}\) when
-
– \(g(y)=y^2\)
-
– \(f(x)=x\)
-
– \(\tilde{f}(x)=-x\)
-
\(\Vdash\) \(g(f(x))=g(\tilde{f}(x))\)
-
\(\equiv\) { \(f(x)=x,\tilde{f}(x)=-x\) }
- \(g(x)=g(-x)\)
-
\(\equiv\) { \(g(x)=x^2,~ g(-x)=(-x)^2=x^2\) }
- \(x^2=x^2\)
-
\(\square\)
-
\(\bullet\) Show that \(g\circ f=\tilde{g}\circ f\) when
-
– \(f\) is surjective: \(\forall y\in Y~\exists x\in X,~f(x)=y\)
-
\(\Vdash\) \(g\circ f=\tilde{g}\circ f\)
-
\(\equiv\) { Definition 3.3.7 }
- \(\forall x,~(g\circ f)(x)=(\tilde{g}\circ f)(x)\)
-
\(\equiv\) { Definition 3.3.10 }
- \(\forall x, g(f(x))=\tilde{g}(f(x))\)
-
\(\equiv\) { \(f\) is surjective }
- \(\forall y\in Y,~g(y)=\tilde{g}(y)\)
-
\(\equiv\) { Definition 3.3.7 }
- \(g=\tilde{g}\)
-
\(\square\)
Another one
Exercise 3.3.4 In this section we give some cancellation laws for composition. Let \(f : X \to Y\), \(\tilde{f} : X \to Y\), \(g : Y \to Z\), and \(\tilde{g} : Y \to Z\) be functions. Show that if \(g \cdot f = g \cdot \tilde{f}\) and \(g\) is injective, then \(f = \tilde{f}\). Is the same statement true if \(g\) is not injective? Show that if \(g \cdot f = \tilde{g} \cdot f\) and \(f\) is surjective, then \(g = \tilde{g}\). Is the same statement true if f is not surjective?
Claim 1
- \(\bullet\) If \(g\) is injective, then there exists a \(r\) function, such that \(r \cdot g = \mathbb{1}\). The function \(r\) is called retraction.
Claim 2
- \(\bullet\) If \(f\) is surjective, then there exists a \(s\) function, such that \(f \cdot s = \mathbb{1}\). The function \(s\) is called section.
Proof 1
- \(\bullet\) Show that if \(g \cdot f = g \cdot \tilde{f}\) and \(g\) is injective, then \(f = \tilde{f}\).
- - \(f : X \to Y\), \(\tilde{f} : X \to Y\), \(g : Y \to Z\), and \(\tilde{g} : Y \to Z\)
- - Claim 1: If \(g\) is injective, then \(\exists r,\ r \cdot g = \mathbb{1}\)
- \(\Vdash\) \(g \cdot f = g \cdot \tilde{f}\)
-
\(\vdash\) { Claim 1 }
- \(r \cdot (g \cdot f) = r \cdot (g \cdot \tilde{f})\)
-
\(\vdash\) { Associativity of functions }
- \((r \cdot g) \cdot f = (r \cdot g) \cdot \tilde{f}\)
-
\(\vdash\) { Claim 1 }
- \(\mathbb{1} \cdot f = \mathbb{1} \cdot \tilde{f}\)
-
\(\vdash\) { Definition of the identity function }
- \(f = \tilde{f}\)
- \(\square\)
Proof 2
- \(\bullet\) Show that if \(g \cdot f = \tilde{g} \cdot f\) and \(f\) is surjective, then \(g = \tilde{g}\)
- - \(f : X \to Y\), \(\tilde{f} : X \to Y\), \(g : Y \to Z\), and \(\tilde{g} : Y \to Z\)
- - Claim 2: If \(f\) is surjective, then \(\exists s,\ f \cdot s = \mathbb{1}\)
- \(\Vdash\) \(g \cdot f = \tilde{g} \cdot f\)
-
\(\vdash\) { Claim 2 }
- \((g \cdot f) \cdot s = (\tilde{g} \cdot f) \cdot s\)
-
\(\vdash\) { Associativity of functions }
- \(g \cdot (f \cdot s) = \tilde{g} \cdot (f \cdot s)\)
-
\(\vdash\) { Claim 1 }
- \(g \cdot \mathbb{1} = \tilde{g} \cdot \mathbb{1}\)
-
\(\vdash\) { Definition of the identity function }
- \(g = \tilde{g}\)
- \(\square\)