Metamath Proof Explorer

Theorem coass

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) Remove dependency on ax-11 . (Revised by BJ, 25-Oct-2026)

Ref Expression
Assertion coass ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) = ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) )

Proof

Step Hyp Ref Expression
1 relco ⊢ Rel ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 )
2 relco ⊢ Rel ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) )
3 vex ⊢ 𝑥 ∈ V
4 vex ⊢ 𝑦 ∈ V
5 3 4 brco ⊢ ( 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 ↔ ∃ 𝑧 ( 𝑥 𝐶 𝑧 ∧ 𝑧 ( 𝐴 ∘ 𝐵 ) 𝑦 ) )
6 vex ⊢ 𝑧 ∈ V
7 6 4 brco ⊢ ( 𝑧 ( 𝐴 ∘ 𝐵 ) 𝑦 ↔ ∃ 𝑤 ( 𝑧 𝐵 𝑤 ∧ 𝑤 𝐴 𝑦 ) )
8 vex ⊢ 𝑤 ∈ V
9 3 6 8 brcoi ⊢ ( ( 𝑥 𝐶 𝑧 ∧ 𝑧 𝐵 𝑤 ) → 𝑥 ( 𝐵 ∘ 𝐶 ) 𝑤 )
10 3 8 4 brcoi ⊢ ( ( 𝑥 ( 𝐵 ∘ 𝐶 ) 𝑤 ∧ 𝑤 𝐴 𝑦 ) → 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 )
11 9 10 sylan ⊢ ( ( ( 𝑥 𝐶 𝑧 ∧ 𝑧 𝐵 𝑤 ) ∧ 𝑤 𝐴 𝑦 ) → 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 )
12 11 anasss ⊢ ( ( 𝑥 𝐶 𝑧 ∧ ( 𝑧 𝐵 𝑤 ∧ 𝑤 𝐴 𝑦 ) ) → 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 )
13 12 ex ⊢ ( 𝑥 𝐶 𝑧 → ( ( 𝑧 𝐵 𝑤 ∧ 𝑤 𝐴 𝑦 ) → 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 ) )
14 13 exlimdv ⊢ ( 𝑥 𝐶 𝑧 → ( ∃ 𝑤 ( 𝑧 𝐵 𝑤 ∧ 𝑤 𝐴 𝑦 ) → 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 ) )
15 7 14 biimtrid ⊢ ( 𝑥 𝐶 𝑧 → ( 𝑧 ( 𝐴 ∘ 𝐵 ) 𝑦 → 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 ) )
16 15 imp ⊢ ( ( 𝑥 𝐶 𝑧 ∧ 𝑧 ( 𝐴 ∘ 𝐵 ) 𝑦 ) → 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 )
17 16 exlimiv ⊢ ( ∃ 𝑧 ( 𝑥 𝐶 𝑧 ∧ 𝑧 ( 𝐴 ∘ 𝐵 ) 𝑦 ) → 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 )
18 5 17 sylbi ⊢ ( 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 → 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 )
19 3 4 brco ⊢ ( 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 ↔ ∃ 𝑤 ( 𝑥 ( 𝐵 ∘ 𝐶 ) 𝑤 ∧ 𝑤 𝐴 𝑦 ) )
20 3 8 brco ⊢ ( 𝑥 ( 𝐵 ∘ 𝐶 ) 𝑤 ↔ ∃ 𝑧 ( 𝑥 𝐶 𝑧 ∧ 𝑧 𝐵 𝑤 ) )
21 6 8 4 brcoi ⊢ ( ( 𝑧 𝐵 𝑤 ∧ 𝑤 𝐴 𝑦 ) → 𝑧 ( 𝐴 ∘ 𝐵 ) 𝑦 )
22 3 6 4 brcoi ⊢ ( ( 𝑥 𝐶 𝑧 ∧ 𝑧 ( 𝐴 ∘ 𝐵 ) 𝑦 ) → 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 )
23 21 22 sylan2 ⊢ ( ( 𝑥 𝐶 𝑧 ∧ ( 𝑧 𝐵 𝑤 ∧ 𝑤 𝐴 𝑦 ) ) → 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 )
24 23 anassrs ⊢ ( ( ( 𝑥 𝐶 𝑧 ∧ 𝑧 𝐵 𝑤 ) ∧ 𝑤 𝐴 𝑦 ) → 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 )
25 24 ex ⊢ ( ( 𝑥 𝐶 𝑧 ∧ 𝑧 𝐵 𝑤 ) → ( 𝑤 𝐴 𝑦 → 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 ) )
26 25 exlimiv ⊢ ( ∃ 𝑧 ( 𝑥 𝐶 𝑧 ∧ 𝑧 𝐵 𝑤 ) → ( 𝑤 𝐴 𝑦 → 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 ) )
27 20 26 sylbi ⊢ ( 𝑥 ( 𝐵 ∘ 𝐶 ) 𝑤 → ( 𝑤 𝐴 𝑦 → 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 ) )
28 27 imp ⊢ ( ( 𝑥 ( 𝐵 ∘ 𝐶 ) 𝑤 ∧ 𝑤 𝐴 𝑦 ) → 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 )
29 28 exlimiv ⊢ ( ∃ 𝑤 ( 𝑥 ( 𝐵 ∘ 𝐶 ) 𝑤 ∧ 𝑤 𝐴 𝑦 ) → 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 )
30 19 29 sylbi ⊢ ( 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 → 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 )
31 18 30 impbii ⊢ ( 𝑥 ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) 𝑦 ↔ 𝑥 ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) ) 𝑦 )
32 1 2 31 eqbrriv ⊢ ( ( 𝐴 ∘ 𝐵 ) ∘ 𝐶 ) = ( 𝐴 ∘ ( 𝐵 ∘ 𝐶 ) )