The Lumenary · Darasa la 9–12

Composition

Jina: ______________________

Tarehe: ______________________

Utajifunza

Compute composites $g \circ f$ and state their domain and codomain
Show by example that composition is not commutative
Prove that composition is associative and that identity functions are neutral
Prove that composites of injections (surjections, bijections) are injections (surjections, bijections)
Describe sets and functions as a first example of a category

1.
Let $f(x) = x + 3$ and $g(x) = x^2$ . Compute $(g \circ f)(2)$ .
2.
If $f : A \to B$ and $g : B \to C$ , what are the domain and codomain of $g \circ f$ ?
- A. $g \circ f : A \to C$
- B. $g \circ f : B \to B$
- C. $g \circ f : C \to A$
3.
Let $f(x) = 3x$ and $g(x) = x - 2$ . Compute $(g \circ f)(4) - (f \circ g)(4)$ .
4.
Suppose $g \circ f$ is injective. Which of these must be true? (Choose all that apply.)
- A. $f$ is injective
- B. $g$ is injective
- C. $g \circ f$ is surjective
5.
In Lean, comp_assoc is proved by rfl. What does that tell us?
- A.Both sides unfold, by definition, to the same function fun x => h (g (f x)).
- B.Lean checked associativity on many examples.
- C.Associativity is an axiom in Lean.
6.
Finite functions can be stored as dictionaries. Write compose(g, f) returning a dictionary for $g \circ f$ (apply f first!). You may assume every value of f is a key of g.
Kikokotozi — Mazoezi

Majibu — Composition

1.
$f(2) = 5$ , then $g(5) = 25$ . So $(g \circ f)(2) = 25$ , while $(f \circ g)(2) = 7$ — another example that order matters.
2.
$g \circ f : A \to C$ . An input $x \in A$ goes to $f(x) \in B$ and then to $g(f(x)) \in C$ .
3.
$(g \circ f)(4) = g(12) = 10$ and $(f \circ g)(4) = f(2) = 6$ , so the difference is $4$ . In general $(g \circ f)(x) = 3x - 2$ and $(f \circ g)(x) = 3x - 6$ always differ by 4.
4.
$f$ must be injective: if $f(x) = f(y)$ then $(g \circ f)(x) = (g \circ f)(y)$ , so $x = y$ . But $g$ need not be: with $f : \{1\} \to \{1, 2\}$ , $f(1) = 1$ , and $g : \{1, 2\} \to \{1\}$ , the composite is injective but $g$ is not.
5.
g ∘ f is defined as fun x => g (f x), so both h ∘ (g ∘ f) and (h ∘ g) ∘ f unfold to fun x => h (g (f x)). They are equal by definition, which is exactly what rfl certifies.
6.
```
def compose(g, f):
    return {x: g[f[x]] for x in f}
```
The tests check the identity law and one instance of associativity. Passing them is evidence; the proof in the lesson shows associativity holds for all functions.