Day 42 — Composition & inverse

Day 42 — Composition & inverse

Stage IV · concept day
Goal: Master function composition \((g\circ f)\); prove associativity; show inverses are unique; use left and right inverses; connect to pipelines and modular software architecture.

Why this matters

Programs are pipelines of functions: parse ∘ validate ∘ handle. Associativity lets you regroup stages; invertibility means undo/rollback; left/right inverses capture “section/retraction” patterns (encode/decode pairs that only work one way). Category-flavored thinking starts here without category theory.

Theory

Composition

For \(f: A\to B\) and \(g: B\to C\), the composition \(g\circ f: A\to C\) is
\[(g\circ f)(a) = g\bigl(f(a)\bigr).\]
Apply \(f\) first, then \(g\). (Read \(\circ\) as “after.”)

Domain/codomain must match: codomain of \(f\) = domain of \(g\) (or \(\subseteq\) with care).

Identity

\(\mathrm{id}_A: A\to A\), \(\mathrm{id}_A(a)=a\).
\(f\circ \mathrm{id}_A = f = \mathrm{id}_B \circ f\) for \(f:A\to B\).

Associativity

\[h\circ (g\circ f) = (h\circ g)\circ f\]
whenever typed. Proof: both send \(a\) to \(h(g(f(a)))\). \(\square\)
So \(h\circ g\circ f\) is unambiguous.

Not commutative

\(g\circ f \neq f\circ g\) in general (often not even both defined).

Inverse (two-sided)

\(f: A\to B\) is invertible if there exists \(f^{-1}: B\to A\) with
\[f^{-1}\circ f = \mathrm{id}_A, \qquad f\circ f^{-1} = \mathrm{id}_B.\]
Then \(f\) is bijective and \(f^{-1}\) is unique (below).

Uniqueness of inverse

If \(g\) and \(h\) both inverses of \(f\), then
\[g = g\circ\mathrm{id}_B = g\circ(f\circ h) = (g\circ f)\circ h = \mathrm{id}_A\circ h = h.\]

Left and right inverses

• Left inverse of \(f: A\to B\): \(\ell: B\to A\) with \(\ell\circ f = \mathrm{id}_A\).
  Exists (for nonempty issues aside) iff \(f\) injective; then \(f\) is a split mono.
  
• Right inverse of \(f\): \(r: B\to A\) with \(f\circ r = \mathrm{id}_B\).
  Exists iff \(f\) surjective (using choice in general); split epi.

If both left and right inverses exist, they coincide and are the two-sided inverse.

Cancellation

If \(f\) injective and \(f\circ g = f\circ h\) then \(g=h\) (left cancel).
If \(f\) surjective and \(g\circ f = h\circ f\) then \(g=h\) (right cancel).

Composition preserves properties

If	Then
\(f,g\) injective	\(g\circ f\) injective
\(f,g\) surjective	\(g\circ f\) surjective
\(f,g\) bijective	\(g\circ f\) bijective, \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\)

Monoid of self-maps

\(\mathrm{Map}(A,A)\) under \(\circ\) is a monoid with unit \(\mathrm{id}_A\). Invertible elements = bijections = symmetric group if finite.

Worked examples

Example 1 — Compute

\(f(x)=x+1\), \(g(x)=2x\) on \(\mathbb{R}\): \((g\circ f)(x)=2(x+1)\), \((f\circ g)(x)=2x+1\).

Example 2 — Associativity numeric

\(f(x)=x+1\), \(g(x)=x^2\), \(h(x)=3x\): both associations give \(3(x+1)^2\).

Example 3 — Inverse linear

\(f(x)=2x+3\), \(f^{-1}(y)=(y-3)/2\). Check both compositions identity.

Example 4 — Inverse order

\((g\circ f)^{-1} = f^{-1}\circ g^{-1}\): undo last first (stack discipline).

Example 5 — Left inverse of injection

\(f:\{1,2\}\to\{a,b,c\}\), \(f(1)=a,f(2)=b\). Left inverse \(\ell(a)=1,\ell(b)=2,\ell(c)=\) anything (say \(1\)).
\(\ell\circ f=\mathrm{id}\) but \(f\circ\ell\neq\mathrm{id}\) (\(c\) issue).

Example 6 — Right inverse of surjection

\(f:\{1,2,3\}\to\{a,b\}\), \(f(1)=f(2)=a\), \(f(3)=b\). Right inverse \(r(a)=1\), \(r(b)=3\).

Example 7 — No left inverse

Non-injective maps cannot have left inverse: \(\ell(f(a_1))=\ell(f(a_2))\) would force \(a_1=a_2\).

Example 8 — Pipeline

\(\mathrm{handle}\circ\mathrm{validate}\circ\mathrm{parse}\): associativity allows \(\mathrm{handle}\circ(\mathrm{validate}\circ\mathrm{parse})\) packaging.

Example 9 — Uniqueness

Two candidate inverses for \(n\mapsto n+1\) on \(\mathbb{Z}\): only \(n\mapsto n-1\).

Example 10 — Permutation composition

Cycles: compose right-to-left as functions.

Example 11 — Identity

Only one identity map on \(A\).

Example 12 — Encode/decode

Base64: decode \(\circ\) encode = id on bytes; encode \(\circ\) decode = id on valid strings—not on all strings (partial inverse).

Example 13 — Cancellation failure

\(f\) constant: \(f\circ g = f\circ h\) always if same codomain patterns—cannot cancel.

Example 14 — Bijective composition inverse formula

Verify \((g\circ f)\circ(f^{-1}\circ g^{-1})=\mathrm{id}\).

Exercises

1. Compute \(g\circ f\) and \(f\circ g\) for \(f(x)=x^2\), \(g(x)=x+2\) on \(\mathbb{R}\).
   
2. Prove associativity in full generality.
   
3. Find inverse of \(f:\mathbb{R}\to\mathbb{R}\), \(f(x)=5-3x\).
   
4. Prove uniqueness of two-sided inverse.
   
5. Prove \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\) when both invertible.
   
6. Prove: \(f\) has a left inverse ⇒ \(f\) injective.
   
7. Prove: \(f\) has a right inverse ⇒ \(f\) surjective.
   
8. Give left inverse for \(n\mapsto 2n\) as \(\mathbb{Z}\to\mathbb{Z}\)? Impossible— not onto wait, it is injective: left inverse from \(\mathbb{Z}\) to \(\mathbb{Z}\)? Left inverse \(\ell:\mathbb{Z}\to\mathbb{Z}\) with \(\ell(2n)=n\)—must define \(\ell\) on odds arbitrarily, e.g. \(\ell(2n)=n\), \(\ell(2n+1)=0\). Check \(\ell(f(n))=\ell(2n)=n\). Yes!
   
9. Show \(n\mapsto 2n\) has no right inverse \(\mathbb{Z}\to\mathbb{Z}\).
   
10. Prove if \(f,g\) bijective then \(g\circ f\) bijective.
    
11. Pipeline: three functions on finite sets—count \(|\mathrm{im}(h\circ g\circ f)|\) bounds.
    
12. Is composition commutative on \(\mathrm{Map}(\{1,2\},\{1,2\})\)? Counterexample.
    
13. Prove left cancellation for injective \(f\).
    
14. Show that if \(f\) invertible, left and right inverses equal \(f^{-1}\).
    
15. CS: middleware stack as composition—what is identity middleware?
    
16. For \(f:A\to B\) bijective, prove \(f^{-1}\) bijective.
    
17. Give \(f\) with two different left inverses (non-surjective injection into larger set).
    
18. Monoid: list all elements of \(\mathrm{Map}(\{1\},\{1\})\).
    
19. Prove \(\mathrm{id}_A\) is the only map that is identity for composition on left and right for all \(f\).
    
20. If \(g\circ f = \mathrm{id}_A\), what can you say about inj/surj of \(f\) and \(g\)?
    
21. Same for \(g\circ f=\mathrm{id}\) and \(f\circ g=\mathrm{id}\).
    
22. Functions \(f_i: A_i \to A_{i+1}\)—write \(n\)-fold composition.
    
23. Invert \(f(x)=e^x\) as \(\mathbb{R}\to(0,\infty)\)—codomain matters.
    
24. Explain stack undo: inverse composition order.
    
25. Prove: if \(g\circ f\) is bijective and \(f\) surjective? Actually if \(g\circ f\) bijective then \(f\) injective and \(g\) surjective—prove.

CS connection

• Unix pipes and method chaining ≈ composition.
  
• Undo stacks apply inverses in reverse order.
  
• Serde: serialize/parse as approximate inverses on valid data.
  
• Database migrations up/down as intended inverses (not always).
  
• Middleware wrap = log ∘ auth ∘ route.
  
• Functional programming compose / >>> operators.

Common pitfalls

Pitfall	What to do instead
Applying \(g\) before \(f\) in \(g\circ f\)	\(f\) first
Writing \(f^{-1}\) for preimage relation when not bijective	Use \(f^{-1}(S)\) for sets carefully
Assuming commutative pipelines	Order matters
Left inverse unique	Not always
Forgetting codomain in invertibility	\(e^x: \mathbb{R}\to\mathbb{R}\) not onto

Checkpoint

• Define and compute \(g\circ f\)
  
• Prove associativity
  
• Unique two-sided inverse
  
• Left ⇒ injective; right ⇒ surjective
  
• \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\)
  
• Pipeline example in own words
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — category-lite vocabulary (optional)

• Monomorphism ≈ injective function (in \(\mathbf{Set}\)).
  
• Epimorphism ≈ surjective function.
  
• Isomorphism ≈ bijective function.
  
• Composition is the morphism operation; \(\mathrm{id}\) are identity morphisms.

You do not need category theory; the words sometimes appear in PL theory papers.

Partial functions and inverses

A partial function may have a partial inverse on its image. Serialization often:
\(\mathrm{decode}\circ\mathrm{encode}=\mathrm{id}\) on messages (left inverse of encode / right inverse of decode on valid codes).

Function graphs as relations

\(f:A\to B\) corresponds to \(R_f=\{(a,f(a))\}\subseteq A\times B\) with unique \(b\) for each \(a\).
Composition of functions matches composition of these relations.

More worked examples

Example 15 — Triple pipeline
\(h\circ g\circ f\) with \(f(x)=x+1\), \(g(x)=2x\), \(h(x)=x^2\): expand.

Example 16 — Inverse of product map
If \(f,g\) invertible, \((f\times g)^{-1}=f^{-1}\times g^{-1}\) on product sets.

Example 17 — No inverse
Projection \(\pi_1\) has right inverses (sections) if \(B\neq\emptyset\): pick default \(b_0\), \(r(a)=(a,b_0)\).

Example 18 — Cancellation
\(2x\) injective on \(\mathbb{R}\) so \(2g=2h\Rightarrow g=h\).

Additional exercises

26. Prove right cancellation for surjective \(f\).
    
27. Show a function can have many right inverses.
    
28. If \(g\circ f=\mathrm{id}_A\) and \(f\circ g=\mathrm{id}_B\), prove \(f\) bijective.
    
29. Middleware: write three stages and two legitimate association parenthesizations.
    
30. Prove \(\mathrm{Map}(A,A)\) is not a group under \(\circ\) if \(|A|\ge 2\) (non-bijective maps).

Extended practice workshop

Pipeline calculations

1. \(f(x)=x-3\), \(g(x)=x^2\), \(h(x)=2x\): expand \(h\circ g\circ f\) and \(f\circ g\circ h\).
   
2. Invert \(f(x)=(ax+b)/(cx+d)\) when defined (matrix intuition optional).
   
3. Show \(\mathrm{id}\) is the only function that is a left and right identity for all composable maps on a fixed set family.

Left/right inverse constructions

4. Injection \(f:\{1,2,3\}\to\{a,b,c,d\}\)—write two different left inverses.
   
5. Surjection \(g:\{1,2,3,4\}\to\{x,y\}\)—write two different right inverses.
   
6. Prove no left inverse if not injective—generic argument.
   
7. Prove no right inverse if not surjective—generic argument.

Algebra of invertible maps

8. If \(f,g:A\to A\) invertible, simplify \((f\circ g)^{-1}\circ f\).
   
9. Solve for \(X\) in \(f\circ X = g\) when \(f\) invertible.
   
10. Solve for \(X\) in \(X\circ f = g\) when \(f\) invertible.

CS scenario write-ups (no code)

11. Logging middleware as \(L\circ H\) vs \(H\circ L\)—semantic difference.
    
12. Encode/decode round-trip equations.
    
13. Database migration up/down as intended inverse pair—failure mode when down not inverse.
    
14. Undo stack: sequence of ops \(f_1,\ldots,f_n\); undo applies \(f_n^{-1},\ldots,f_1^{-1}\).

Self-score

Mark each 1–14: cold / notes / failed. Retake failed within 48h.

Associativity diagram (mental)

\[ A \xrightarrow{f} B \xrightarrow{g} C \xrightarrow{h} D \]

Either path \(A\to D\) is \(h\circ g\circ f\). Parentheses only change evaluation association, not the function.

Quick reference identities

\[ \begin{align*} (h\circ g)\circ f &= h\circ(g\circ f),\\ f\circ\mathrm{id} &= \mathrm{id}\circ f = f,\\ (g\circ f)^{-1} &= f^{-1}\circ g^{-1} \quad\text{(when invertible)},\\ \ell\circ f=\mathrm{id} &\Rightarrow f\text{ injective},\\ f\circ r=\mathrm{id} &\Rightarrow f\text{ surjective}. \end{align*} \]

Checkpoint recap (composition day)

• Compute two non-commuting compositions
  
• Prove associativity in one line of pointwise reasoning
  
• Produce a left inverse for a concrete injection
  
• State uniqueness of two-sided inverse
  
• Explain undo-stack reverse order

Synthesis

Composition is the algebra of pipelines: \((g\circ f)(x)=g(f(x))\), apply \(f\) first. Associativity is free (pointwise); commutativity is rare. Two-sided inverses undo perfectly; left/right inverses capture one-sided encode/decode. Undo stacks reverse order because \((g\circ f)^{-1}=f^{-1}\circ g^{-1}\).

Algebra card

\[ \begin{align*} (h\circ g)\circ f &= h\circ(g\circ f),\\ f\circ\mathrm{id} &= \mathrm{id}\circ f = f,\\ (g\circ f)^{-1} &= f^{-1}\circ g^{-1} \quad\text{(both bijective)},\\ \exists \ell:\; \ell\circ f=\mathrm{id} &\Rightarrow f\text{ injective},\\ \exists r:\; f\circ r=\mathrm{id} &\Rightarrow f\text{ surjective}. \end{align*} \]

More worked examples

Example — Non-commute.
\(f(x)=x+1\), \(g(x)=2x\): \((g\circ f)(x)=2x+2\), \((f\circ g)(x)=2x+1\).

Example — Left inverse of injection.
\(f:\mathbb{N}\to\mathbb{Z}\), \(f(n)=n\). Left inverse \(r:\mathbb{Z}\to\mathbb{N}\) can send negatives to \(0\) and nonnegatives to themselves: \(r\circ f=\mathrm{id}_{\mathbb{N}}\), but \(f\circ r\neq\mathrm{id}_{\mathbb{Z}}\).

Example — Right inverse of surjection.
\(f:\mathbb{Z}\to\mathbb{N}_0\), \(f(n)=|n|\). Choose \(r(k)=k\); then \(f\circ r=\mathrm{id}\) on \(\mathbb{N}_0\). Not injective, so no two-sided inverse.

Example — Unique two-sided inverse.
If \(g\circ f=\mathrm{id}_A\) and \(f\circ g=\mathrm{id}_B\) and also \(h\) is another two-sided inverse, then \(g=g\circ\mathrm{id}_B=g\circ(f\circ h)=(g\circ f)\circ h=h\).

Example — Pipeline invertibility.
Parse then validate: even if each stage has a right inverse “locally,” the composite needs matching domains; failure of validate is not undone by unparse alone.

Extra exercises (synthesis)

31. Compute \(g\circ f\) and \(f\circ g\) for \(f(x)=x^2\), \(g(x)=x+1\) on \(\mathbb{R}\).
    
32. Prove associativity pointwise in three lines.
    
33. Show \(f(n)=2n\) on \(\mathbb{Z}\) has a left inverse \(\mathbb{Z}\to\mathbb{Z}\) (define one) but no right inverse.
    
34. Prove: if \(f\) has a two-sided inverse, then \(f\) is bijective.
    
35. Prove: if \(f\) is bijective, the inverse is unique.
    
36. CS: serialization \(S\) and deserialization \(D\) with \(D\circ S=\mathrm{id}\) (left inverse of \(S\))—what does that guarantee about \(S\)? About \(D\)?

Inverse existence summary

Situation	Inverse type
\(f\) injective, \(A\neq\emptyset\) issues aside	left inverse exists (AC for general sets; constructive for finite/nice \(f\))
\(f\) surjective	right inverse (same caveat)
\(f\) bijective	unique two-sided inverse
Finite \(|A|=|B|\)	inj ⇒ bij ⇒ inverse

Next: infinite sizes—when do bijections with \(\mathbb{N}\) exist, and when does diagonalization forbid them?

Tomorrow

Day 43 — Countability. Countable unions; \(\mathbb{Z},\mathbb{Q}\) countable sketches; Cantor diagonal \((0,1)\) uncountable; continuum awareness; \(|\mathcal{P}(\mathbb{N})| > |\mathbb{N}|\).