Lemma·L08
Associativity of addition
Grouping does not matter when adding.
for all
.
In words
Adding m to k and then adding n gives the same result as adding the sum of m and n to k, for all natural numbers k, m, n.
Never needed: F03 · F04 · F05 · F06 · F08 · F10 · F11 · F12 · F13 · A02 · A03 · A04 · A05 · A07 · A08 (computed from the citation graph, not asserted).
Proof
- 1Fix and ; we induct on using T05 applied to (Separation).
- 2Base: , both steps by the first equation of D027.
- 3Step: assume . Then by the second equation of D027 (thrice) and the induction hypothesis with substitutivity.
- 4T05 gives ; since were arbitrary, the identity holds for all (universal generalization).
∎
Remarks
The first of the classical laws of arithmetic, and structurally the simplest: the recursion of addition lives entirely in the right argument, and associativity only reshuffles right arguments. Commutativity is subtler because it must move the recursion across to the left argument.