Let \(f:X\to Y\) and \(g:X\to Y\) be functions. Show that if \(f\) and \(g\) are both injective, then so is \(g\circ f\); similarly, show that if \(f\) and \(g\) are both surjective, then so is \(g\circ f\).
- \(\bullet\) Show that \(g\circ f\) is injective when
- – A1 : \(f\) is injective
- – A2 : \(g\) is injective
- \(\Vdash\) \(x\neq x'\)
-
\(\Rightarrow\) { A1 and Definition 3.3.14 }
- \(f(x)\neq f(x')\)
-
\(\Rightarrow\) { A2 and Definition 3.3.14 }
- \(g(f(x))\neq g(f(x'))\)
-
\(\equiv\) { Definition 3.3.10 }
- \((g\circ f)(x)\neq(g\circ f)(x')\)
-
\(\vdash\) { Definition 3.3.14 }
- \(g\circ f\) is injective
- \(\square\)
- \(\bullet\) Show that \(g\circ f\) is surjective when
- – A1: \(g:Y\to Z\) is surjective
- – A2: \(f:X\to Y\) is surjective
-
\(\Vdash\) { Proof by let binding }
- \(\Vdash\) \(z' \in Z\)
-
\(\vdash\) { A1 }
- \(\forall z\in Z, \exists y\in Y,~g(y)=z\)
-
\(\vdash\) { \(\forall E(z'/z)\) }
- \(\exists y\in Y,~g(y)=z'\)
-
\(\vdash\) { \(\exists E(t/y)\) }
- P1: \(g(t)=z'\)
-
\(\triangle\)
-
\(\Vdash\) { A2 }
- \(\forall y \in Y, \exists x\in X,~f(x)=y\)
-
\(\vdash\) { \(\forall E(t/y)\) }
- \(\exists x\in X,~f(x)=t\)
-
\(\vdash\) { \(\exists E(t'/x)\) }
- P2: \(f(t')=t\)
-
\(\Vdash\) { P1, P2 }
- \(g(f(t'))= z'\)
-
\(\vdash\) { Definition 3.3.14 }
- \((g\circ f)(t')=z'\)
-
\(\vdash\) { \(\exists I(x/t')\) }
- \(\exists x\in X, (g\circ f)(x)=z'\)
-
\(\Vdash\) { A2 }
-
\(\vdash\) { \(\forall I(z/z')\) }
- \(\forall z\in Z, \exists x\in X, (g\circ f)(x)=z\)
-
\(\vdash\) { Definition 3.3.17 }
- \(g\circ f\) is surjective
- \(\square\)