Metamath Proof Explorer

Theorem nnaass

Description: Addition of natural numbers is associative. Theorem 4K(1) of Enderton p. 81. (Contributed by NM, 20-Sep-1995) (Revised by Mario Carneiro, 15-Nov-2014)

Ref Expression
Assertion nnaass ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ∧ 𝐶 ∈ ω ) → ( ( 𝐴 +o 𝐵 ) +o 𝐶 ) = ( 𝐴 +o ( 𝐵 +o 𝐶 ) ) )

Proof

Step Hyp Ref Expression
1 oveq2 ⊢ ( 𝑥 = 𝐶 → ( ( 𝐴 +o 𝐵 ) +o 𝑥 ) = ( ( 𝐴 +o 𝐵 ) +o 𝐶 ) )
2 oveq2 ⊢ ( 𝑥 = 𝐶 → ( 𝐵 +o 𝑥 ) = ( 𝐵 +o 𝐶 ) )
3 2 oveq2d ⊢ ( 𝑥 = 𝐶 → ( 𝐴 +o ( 𝐵 +o 𝑥 ) ) = ( 𝐴 +o ( 𝐵 +o 𝐶 ) ) )
4 1 3 eqeq12d ⊢ ( 𝑥 = 𝐶 → ( ( ( 𝐴 +o 𝐵 ) +o 𝑥 ) = ( 𝐴 +o ( 𝐵 +o 𝑥 ) ) ↔ ( ( 𝐴 +o 𝐵 ) +o 𝐶 ) = ( 𝐴 +o ( 𝐵 +o 𝐶 ) ) ) )
5 4 imbi2d ⊢ ( 𝑥 = 𝐶 → ( ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) → ( ( 𝐴 +o 𝐵 ) +o 𝑥 ) = ( 𝐴 +o ( 𝐵 +o 𝑥 ) ) ) ↔ ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) → ( ( 𝐴 +o 𝐵 ) +o 𝐶 ) = ( 𝐴 +o ( 𝐵 +o 𝐶 ) ) ) ) )
6 oveq2 ⊢ ( 𝑥 = ∅ → ( ( 𝐴 +o 𝐵 ) +o 𝑥 ) = ( ( 𝐴 +o 𝐵 ) +o ∅ ) )
7 oveq2 ⊢ ( 𝑥 = ∅ → ( 𝐵 +o 𝑥 ) = ( 𝐵 +o ∅ ) )
8 7 oveq2d ⊢ ( 𝑥 = ∅ → ( 𝐴 +o ( 𝐵 +o 𝑥 ) ) = ( 𝐴 +o ( 𝐵 +o ∅ ) ) )
9 6 8 eqeq12d ⊢ ( 𝑥 = ∅ → ( ( ( 𝐴 +o 𝐵 ) +o 𝑥 ) = ( 𝐴 +o ( 𝐵 +o 𝑥 ) ) ↔ ( ( 𝐴 +o 𝐵 ) +o ∅ ) = ( 𝐴 +o ( 𝐵 +o ∅ ) ) ) )
10 oveq2 ⊢ ( 𝑥 = 𝑦 → ( ( 𝐴 +o 𝐵 ) +o 𝑥 ) = ( ( 𝐴 +o 𝐵 ) +o 𝑦 ) )
11 oveq2 ⊢ ( 𝑥 = 𝑦 → ( 𝐵 +o 𝑥 ) = ( 𝐵 +o 𝑦 ) )
12 11 oveq2d ⊢ ( 𝑥 = 𝑦 → ( 𝐴 +o ( 𝐵 +o 𝑥 ) ) = ( 𝐴 +o ( 𝐵 +o 𝑦 ) ) )
13 10 12 eqeq12d ⊢ ( 𝑥 = 𝑦 → ( ( ( 𝐴 +o 𝐵 ) +o 𝑥 ) = ( 𝐴 +o ( 𝐵 +o 𝑥 ) ) ↔ ( ( 𝐴 +o 𝐵 ) +o 𝑦 ) = ( 𝐴 +o ( 𝐵 +o 𝑦 ) ) ) )
14 oveq2 ⊢ ( 𝑥 = suc 𝑦 → ( ( 𝐴 +o 𝐵 ) +o 𝑥 ) = ( ( 𝐴 +o 𝐵 ) +o suc 𝑦 ) )
15 oveq2 ⊢ ( 𝑥 = suc 𝑦 → ( 𝐵 +o 𝑥 ) = ( 𝐵 +o suc 𝑦 ) )
16 15 oveq2d ⊢ ( 𝑥 = suc 𝑦 → ( 𝐴 +o ( 𝐵 +o 𝑥 ) ) = ( 𝐴 +o ( 𝐵 +o suc 𝑦 ) ) )
17 14 16 eqeq12d ⊢ ( 𝑥 = suc 𝑦 → ( ( ( 𝐴 +o 𝐵 ) +o 𝑥 ) = ( 𝐴 +o ( 𝐵 +o 𝑥 ) ) ↔ ( ( 𝐴 +o 𝐵 ) +o suc 𝑦 ) = ( 𝐴 +o ( 𝐵 +o suc 𝑦 ) ) ) )
18 nnacl ⊢ ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) → ( 𝐴 +o 𝐵 ) ∈ ω )
19 nna0 ⊢ ( ( 𝐴 +o 𝐵 ) ∈ ω → ( ( 𝐴 +o 𝐵 ) +o ∅ ) = ( 𝐴 +o 𝐵 ) )
20 18 19 syl ⊢ ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) → ( ( 𝐴 +o 𝐵 ) +o ∅ ) = ( 𝐴 +o 𝐵 ) )
21 nna0 ⊢ ( 𝐵 ∈ ω → ( 𝐵 +o ∅ ) = 𝐵 )
22 21 oveq2d ⊢ ( 𝐵 ∈ ω → ( 𝐴 +o ( 𝐵 +o ∅ ) ) = ( 𝐴 +o 𝐵 ) )
23 22 adantl ⊢ ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) → ( 𝐴 +o ( 𝐵 +o ∅ ) ) = ( 𝐴 +o 𝐵 ) )
24 20 23 eqtr4d ⊢ ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) → ( ( 𝐴 +o 𝐵 ) +o ∅ ) = ( 𝐴 +o ( 𝐵 +o ∅ ) ) )
25 suceq ⊢ ( ( ( 𝐴 +o 𝐵 ) +o 𝑦 ) = ( 𝐴 +o ( 𝐵 +o 𝑦 ) ) → suc ( ( 𝐴 +o 𝐵 ) +o 𝑦 ) = suc ( 𝐴 +o ( 𝐵 +o 𝑦 ) ) )
26 nnasuc ⊢ ( ( ( 𝐴 +o 𝐵 ) ∈ ω ∧ 𝑦 ∈ ω ) → ( ( 𝐴 +o 𝐵 ) +o suc 𝑦 ) = suc ( ( 𝐴 +o 𝐵 ) +o 𝑦 ) )
27 18 26 sylan ⊢ ( ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) ∧ 𝑦 ∈ ω ) → ( ( 𝐴 +o 𝐵 ) +o suc 𝑦 ) = suc ( ( 𝐴 +o 𝐵 ) +o 𝑦 ) )
28 nnasuc ⊢ ( ( 𝐵 ∈ ω ∧ 𝑦 ∈ ω ) → ( 𝐵 +o suc 𝑦 ) = suc ( 𝐵 +o 𝑦 ) )
29 28 oveq2d ⊢ ( ( 𝐵 ∈ ω ∧ 𝑦 ∈ ω ) → ( 𝐴 +o ( 𝐵 +o suc 𝑦 ) ) = ( 𝐴 +o suc ( 𝐵 +o 𝑦 ) ) )
30 29 adantl ⊢ ( ( 𝐴 ∈ ω ∧ ( 𝐵 ∈ ω ∧ 𝑦 ∈ ω ) ) → ( 𝐴 +o ( 𝐵 +o suc 𝑦 ) ) = ( 𝐴 +o suc ( 𝐵 +o 𝑦 ) ) )
31 nnacl ⊢ ( ( 𝐵 ∈ ω ∧ 𝑦 ∈ ω ) → ( 𝐵 +o 𝑦 ) ∈ ω )
32 nnasuc ⊢ ( ( 𝐴 ∈ ω ∧ ( 𝐵 +o 𝑦 ) ∈ ω ) → ( 𝐴 +o suc ( 𝐵 +o 𝑦 ) ) = suc ( 𝐴 +o ( 𝐵 +o 𝑦 ) ) )
33 31 32 sylan2 ⊢ ( ( 𝐴 ∈ ω ∧ ( 𝐵 ∈ ω ∧ 𝑦 ∈ ω ) ) → ( 𝐴 +o suc ( 𝐵 +o 𝑦 ) ) = suc ( 𝐴 +o ( 𝐵 +o 𝑦 ) ) )
34 30 33 eqtrd ⊢ ( ( 𝐴 ∈ ω ∧ ( 𝐵 ∈ ω ∧ 𝑦 ∈ ω ) ) → ( 𝐴 +o ( 𝐵 +o suc 𝑦 ) ) = suc ( 𝐴 +o ( 𝐵 +o 𝑦 ) ) )
35 34 anassrs ⊢ ( ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) ∧ 𝑦 ∈ ω ) → ( 𝐴 +o ( 𝐵 +o suc 𝑦 ) ) = suc ( 𝐴 +o ( 𝐵 +o 𝑦 ) ) )
36 27 35 eqeq12d ⊢ ( ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) ∧ 𝑦 ∈ ω ) → ( ( ( 𝐴 +o 𝐵 ) +o suc 𝑦 ) = ( 𝐴 +o ( 𝐵 +o suc 𝑦 ) ) ↔ suc ( ( 𝐴 +o 𝐵 ) +o 𝑦 ) = suc ( 𝐴 +o ( 𝐵 +o 𝑦 ) ) ) )
37 25 36 imbitrrid ⊢ ( ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) ∧ 𝑦 ∈ ω ) → ( ( ( 𝐴 +o 𝐵 ) +o 𝑦 ) = ( 𝐴 +o ( 𝐵 +o 𝑦 ) ) → ( ( 𝐴 +o 𝐵 ) +o suc 𝑦 ) = ( 𝐴 +o ( 𝐵 +o suc 𝑦 ) ) ) )
38 37 expcom ⊢ ( 𝑦 ∈ ω → ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) → ( ( ( 𝐴 +o 𝐵 ) +o 𝑦 ) = ( 𝐴 +o ( 𝐵 +o 𝑦 ) ) → ( ( 𝐴 +o 𝐵 ) +o suc 𝑦 ) = ( 𝐴 +o ( 𝐵 +o suc 𝑦 ) ) ) ) )
39 9 13 17 24 38 finds2 ⊢ ( 𝑥 ∈ ω → ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) → ( ( 𝐴 +o 𝐵 ) +o 𝑥 ) = ( 𝐴 +o ( 𝐵 +o 𝑥 ) ) ) )
40 5 39 vtoclga ⊢ ( 𝐶 ∈ ω → ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) → ( ( 𝐴 +o 𝐵 ) +o 𝐶 ) = ( 𝐴 +o ( 𝐵 +o 𝐶 ) ) ) )
41 40 com12 ⊢ ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ) → ( 𝐶 ∈ ω → ( ( 𝐴 +o 𝐵 ) +o 𝐶 ) = ( 𝐴 +o ( 𝐵 +o 𝐶 ) ) ) )
42 41 3impia ⊢ ( ( 𝐴 ∈ ω ∧ 𝐵 ∈ ω ∧ 𝐶 ∈ ω ) → ( ( 𝐴 +o 𝐵 ) +o 𝐶 ) = ( 𝐴 +o ( 𝐵 +o 𝐶 ) ) )