Lemma 3.3.12

Lemma 3.3.12 (Composition is associative). Let \(f:Z\to W,~g:Y\to Z\), and \(h:X\to Y\) be functions. Then \(f\circ(g\circ h)=(f\circ g)\circ h\).

\(Proof~by~Tao\). Since \(f\circ g\) is a function from \(X\) to \(Z\), \(f\circ(g\circ h)\) is a function from \(X\) to \(W\). Simliarly \(f\circ g\) is a function from \(Y\) to \(W\), and hence \((f\circ g)\circ h\) is a function from \(X\) to \(W\). Thus \(f\circ(g\circ h)\) and \((f\circ g)\circ h\) have the same domain and range. In order to check that they are equal, we see from Definition 3.3.7 that we have to verify that \((f\circ(g\circ h))(x)=((f\circ g)\circ h)(x)\) for all \(x\in X\). But by Definition 3.3.10 $$ (f\circ (g\circ h))(x)=f((g\circ h)(x)) $$

$$ =f(g(h(x))) $$

$$ =(f\circ g)(h(x)) $$

$$ =((f\circ g)\circ h)(x) $$

as desired. \(\square\)

\(Proof~in~Structured~Derivation~Form\).

• \(+\) Notation: \(\text{Domain}(f:X\to Y)= X\)

• \(+\) Notation: \(\text{Range}(f:X\to Y)=Y\)

• \(\bullet\) Show that \(f\circ(g\circ h)=(f\circ g)\circ h\), when

• – \(f:Z\to W\)

• – \(g:Y\to Z\)

• – \(h:X\to Y\)

• \(\Vdash\) \(f\circ(g\circ h)=(f\circ g)\circ h\)

• \(\equiv\) { Claim 1, Claim2, Claim 3, and Definition 3.3.7, modus ponens}

  • \(\text{True}\)

• \(\square\)

  • \(\bullet\) Claim 1. Show that \(\text{Domain}(f\circ (g\circ h))=\text{Domain}((f\circ g)\circ h)\)

  • \(\Vdash\) { show that domains of both sides are \(X\) }

    • \(\bullet\) Show that \(\text{Domain}(f\circ (g\circ h))=X\)

    • \(\Vdash\) \(\text{Domain}(f\circ (g\circ h))\)

    • \(=\) { let \(p=g\circ h\),
      \(~~~\) Definition 3.3.10, \(p:X\to Z\) }

      • \(\text{Domain}(f\circ p)\)

    • \(=\) { let \(q=f\circ p\),
      \(~~~\) Definition 3.3.10, \(q:X\to W\) }

      • \(X\)

    • \(\square\)

    • \(\bullet\) Show that \(\text{Domain}((f\circ g)\circ h)=X\)

    • \(\Vdash\) \(\text{Domain}((f\circ g)\circ h)\)

    • \(=\) { let \(p=f\circ g\),
      \(~~~\) Definition 3.3.10, \(p:Y\to W\) }

      • \(\text{Domain}(p\circ h)\)

    • \(=\) { let \(q=p\circ h\),
      \(~~~\) Definition 3.3.10, \(q:Z\to W\) }

      • \(X\)

    • \(\square\)

  • \(\square\)

  • \(\bullet\) Claim 2. Show that \(\text{Range}(f\circ (g\circ h))=\text{Range}((f\circ g)\circ h)\)

  • \(\Vdash\) { show that ranges of both sides are \(W\) }

    • \(\bullet\) Show that \(\text{Range}(f\circ (g\circ h))=W\)

    • \(\Vdash\) \(\text{Range}(f\circ (g\circ h))\)

    • \(=\) { let \(p=g\circ h\),
      \(~~~\) Definition 3.3.10, \(p:X\to Z\) }

      • \(\text{Range}(f\circ p)\)

    • \(=\) { let \(q=f\circ p\),
      \(~~~\) Definition 3.3.10, \(q:X\to W\) }

      • \(W\)

    • \(\square\)

    • \(\bullet\) Show that \(\text{Range}((f\circ g)\circ h)=W\)

    • \(\Vdash\) \(\text{Range}((f\circ g)\circ h)\)

    • \(=\) { let \(p=f\circ g\),
      \(~~~\) Definition 3.3.10, \(p:Y\to W\) }

      • \(\text{Range}(p\circ h)\)

    • \(=\) { let \(q=p\circ h\),
      \(~~~\) Definition 3.3.10, \(q:Z\to W\) }

      • \(W\)

    • \(\square\)

  • \(\square\)

  • \(\bullet\) Claim 3. Show that \(\forall x,~(f\circ (g\circ h))(x)=((f\circ g)\circ h)(x)\)

  • \(\Vdash\) \((f\circ (g\circ h))(x)\)

  • \(=\) { Definition 3.3.10 }

    • \(f((g\circ h)(x))\)

  • \(=\) { Definition 3.3.10 }

    • \(f((g(h(x)))\)

  • \(=\) { Definition 3.3.10 }

    • \((f\circ g)(h(x))\)

  • \(=\) { Definition 3.3.10 }

    • \((f\circ g)\circ h)(x)\)

  • \(\square\)