Theorem coass 4762

Description: Associative law for class composition. Theorem 27 of [Suppes] p. 64. Also Exercise 21 of [Enderton] p. 53. Interestingly, this law holds for any classes whatsoever, not just functions or even relations. (Contributed by NM, 27-Jan-1997.)

Assertion

Ref	Expression
coass	⊢ ((A ∘ B) ∘ 𝐶) = (A ∘ (B ∘ 𝐶))

Proof of Theorem coass

Dummy variables x y z w are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		relco 4742	. 2 ⊢ Rel ((A ∘ B) ∘ 𝐶)
2		relco 4742	. 2 ⊢ Rel (A ∘ (B ∘ 𝐶))
3		excom 1532	. . . 4 ⊢ (∃z∃w(x𝐶z ∧ (zBw ∧ wAy)) ↔ ∃w∃z(x𝐶z ∧ (zBw ∧ wAy)))
4		anass 383	. . . . 5 ⊢ (((x𝐶z ∧ zBw) ∧ wAy) ↔ (x𝐶z ∧ (zBw ∧ wAy)))
5	4	2exbii 1475	. . . 4 ⊢ (∃w∃z((x𝐶z ∧ zBw) ∧ wAy) ↔ ∃w∃z(x𝐶z ∧ (zBw ∧ wAy)))
6	3, 5	bitr4i 176	. . 3 ⊢ (∃z∃w(x𝐶z ∧ (zBw ∧ wAy)) ↔ ∃w∃z((x𝐶z ∧ zBw) ∧ wAy))
7		vex 2534	. . . . . . 7 ⊢ z ∈ V
8		vex 2534	. . . . . . 7 ⊢ y ∈ V
9	7, 8	brco 4429	. . . . . 6 ⊢ (z(A ∘ B)y ↔ ∃w(zBw ∧ wAy))
10	9	anbi2i 433	. . . . 5 ⊢ ((x𝐶z ∧ z(A ∘ B)y) ↔ (x𝐶z ∧ ∃w(zBw ∧ wAy)))
11	10	exbii 1474	. . . 4 ⊢ (∃z(x𝐶z ∧ z(A ∘ B)y) ↔ ∃z(x𝐶z ∧ ∃w(zBw ∧ wAy)))
12		vex 2534	. . . . 5 ⊢ x ∈ V
13	12, 8	opelco 4430	. . . 4 ⊢ (⟨x, y⟩ ∈ ((A ∘ B) ∘ 𝐶) ↔ ∃z(x𝐶z ∧ z(A ∘ B)y))
14		exdistr 1765	. . . 4 ⊢ (∃z∃w(x𝐶z ∧ (zBw ∧ wAy)) ↔ ∃z(x𝐶z ∧ ∃w(zBw ∧ wAy)))
15	11, 13, 14	3bitr4i 201	. . 3 ⊢ (⟨x, y⟩ ∈ ((A ∘ B) ∘ 𝐶) ↔ ∃z∃w(x𝐶z ∧ (zBw ∧ wAy)))
16		vex 2534	. . . . . . 7 ⊢ w ∈ V
17	12, 16	brco 4429	. . . . . 6 ⊢ (x(B ∘ 𝐶)w ↔ ∃z(x𝐶z ∧ zBw))
18	17	anbi1i 434	. . . . 5 ⊢ ((x(B ∘ 𝐶)w ∧ wAy) ↔ (∃z(x𝐶z ∧ zBw) ∧ wAy))
19	18	exbii 1474	. . . 4 ⊢ (∃w(x(B ∘ 𝐶)w ∧ wAy) ↔ ∃w(∃z(x𝐶z ∧ zBw) ∧ wAy))
20	12, 8	opelco 4430	. . . 4 ⊢ (⟨x, y⟩ ∈ (A ∘ (B ∘ 𝐶)) ↔ ∃w(x(B ∘ 𝐶)w ∧ wAy))
21		19.41v 1760	. . . . 5 ⊢ (∃z((x𝐶z ∧ zBw) ∧ wAy) ↔ (∃z(x𝐶z ∧ zBw) ∧ wAy))
22	21	exbii 1474	. . . 4 ⊢ (∃w∃z((x𝐶z ∧ zBw) ∧ wAy) ↔ ∃w(∃z(x𝐶z ∧ zBw) ∧ wAy))
23	19, 20, 22	3bitr4i 201	. . 3 ⊢ (⟨x, y⟩ ∈ (A ∘ (B ∘ 𝐶)) ↔ ∃w∃z((x𝐶z ∧ zBw) ∧ wAy))
24	6, 15, 23	3bitr4i 201	. 2 ⊢ (⟨x, y⟩ ∈ ((A ∘ B) ∘ 𝐶) ↔ ⟨x, y⟩ ∈ (A ∘ (B ∘ 𝐶)))
25	1, 2, 24	eqrelriiv 4357	1 ⊢ ((A ∘ B) ∘ 𝐶) = (A ∘ (B ∘ 𝐶))

Syntax hints:   ∧ wa 97   = wceq 1226  ∃wex 1358   ∈ wcel 1370  ⟨cop 3349   class class class wbr 3734   ∘ ccom 4272

This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 99  ax-ia2 100  ax-ia3 101  ax-io 617  ax-5 1312  ax-7 1313  ax-gen 1314  ax-ie1 1359  ax-ie2 1360  ax-8 1372  ax-10 1373  ax-11 1374  ax-i12 1375  ax-bnd 1376  ax-4 1377  ax-14 1382  ax-17 1396  ax-i9 1400  ax-ial 1405  ax-i5r 1406  ax-ext 2000  ax-sep 3845  ax-pow 3897  ax-pr 3914

This theorem depends on definitions:  df-bi 110  df-3an 873  df-tru 1229  df-nf 1326  df-sb 1624  df-eu 1881  df-mo 1882  df-clab 2005  df-cleq 2011  df-clel 2014  df-nfc 2145  df-ral 2285  df-rex 2286  df-v 2533  df-un 2895  df-in 2897  df-ss 2904  df-pw 3332  df-sn 3352  df-pr 3353  df-op 3355  df-br 3735  df-opab 3789  df-xp 4274  df-rel 4275  df-co 4277

This theorem is referenced by:  funcoeqres  5078  fcof1o  5350  tposco  5808