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\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\)