PROOF 120

Prove.

Composition is associative but not commutative

On sets and correspondences.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

Definition D1

For g: X → Y and f: Y → Z, the composition f∘g: X → Z is defined by (f∘g)(x) = f(g(x)).

Proof.

g(x) ∈ Y and f is defined on Y, so f(g(x)) is determined.convention

∎

Theorem T1

For h: W → X, g: X → Y, f: Y → Z, (f∘g)∘h = f∘(g∘h)

Proof.

(1)Both compositions are correspondences from W to Z.assumption, D1

(2)Take an arbitrary w ∈ W.assumption

(3)((f∘g)∘h)(w) = (f∘g)(h(w))D1

(4)(f∘g)(h(w)) = f(g(h(w)))D1

(5)(f∘(g∘h))(w) = f((g∘h)(w))D1

(6)(g∘h)(w) = g(h(w)), so f((g∘h)(w)) = f(g(h(w)))D1, E1

(7)((f∘g)∘h)(w) = (f∘(g∘h))(w)(3), (4), (5), (6)

(8)w was arbitrary, so the two compositions have equal values at every point.(2), (7)

(9)Hence (f∘g)∘h = f∘(g∘h)(8), A1

∎

Theorem T2

The proposition that f∘g = g∘f for all f, g is false.

Proof.

(1)Let f(x) = x + 1, g(x) = 2x. Both are functions from ℝ to ℝ.assumption

(2)g(1) = 2 × 1 = 2(1), A2

(3)(f∘g)(1) = f(g(1)) = f(2) = 2 + 1 = 3(1), (2), D1, E1, A3

(4)f(1) = 1 + 1 = 2(1), A3

(5)(g∘f)(1) = g(f(1)) = g(2) = 2 × 2 = 4(1), (4), D1, E1, A3

(6)Since 3 ≠ 4, (f∘g)(1) ≠ (g∘f)(1)(3), (5), A4

(7)If f∘g = g∘f, the values at 1 would have to agree, so f∘g ≠ g∘f(6), E2

(8)There is one counterexample, so the universal proposition is false.(7), A5

∎

Corollary C

In composition, parentheses may be omitted but the order cannot be exchanged. This property is not restricted to functions.

Proof.

(1)The placement of parentheses does not change the result, so one may write f∘g∘h.T1

(2)f∘g cannot be rewritten as g∘f.T2

(3)The matrix product is the composition of linear transformations, and that product is likewise associative and not commutative.A6

∎

Remark

Can A1 be removed from this proof?

Separate the lines that assert sameness from the lines that assert difference. The two demand different amounts.