| Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
||
| Mirrors > Home > MPE Home > Th. List > coass | Structured version Visualization version GIF version | ||
| 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 2200. (Revised by BJ, 25-Oct-2026.) |
| Ref | Expression |
|---|---|
| coass | ⊢ ((𝐴 ∘ 𝐵) ∘ 𝐶) = (𝐴 ∘ (𝐵 ∘ 𝐶)) |
| Step | Hyp | Ref | Expression |
|---|---|---|---|
| 1 | relco 6121 | . 2 ⊢ Rel ((𝐴 ∘ 𝐵) ∘ 𝐶) | |
| 2 | relco 6121 | . 2 ⊢ Rel (𝐴 ∘ (𝐵 ∘ 𝐶)) | |
| 3 | vex 3457 | . . . . 5 ⊢ 𝑥 ∈ V | |
| 4 | vex 3457 | . . . . 5 ⊢ 𝑦 ∈ V | |
| 5 | 3, 4 | brco 5859 | . . . 4 ⊢ (𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦 ↔ ∃𝑧(𝑥𝐶𝑧 ∧ 𝑧(𝐴 ∘ 𝐵)𝑦)) |
| 6 | vex 3457 | . . . . . . . 8 ⊢ 𝑧 ∈ V | |
| 7 | 6, 4 | brco 5859 | . . . . . . 7 ⊢ (𝑧(𝐴 ∘ 𝐵)𝑦 ↔ ∃𝑤(𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦)) |
| 8 | vex 3457 | . . . . . . . . . . . 12 ⊢ 𝑤 ∈ V | |
| 9 | 3, 6, 8 | brcoi 5857 | . . . . . . . . . . 11 ⊢ ((𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤) → 𝑥(𝐵 ∘ 𝐶)𝑤) |
| 10 | 3, 8, 4 | brcoi 5857 | . . . . . . . . . . 11 ⊢ ((𝑥(𝐵 ∘ 𝐶)𝑤 ∧ 𝑤𝐴𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦) |
| 11 | 9, 10 | sylan 592 | . . . . . . . . . 10 ⊢ (((𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤) ∧ 𝑤𝐴𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦) |
| 12 | 11 | anasss 472 | . . . . . . . . 9 ⊢ ((𝑥𝐶𝑧 ∧ (𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦)) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦) |
| 13 | 12 | ex 418 | . . . . . . . 8 ⊢ (𝑥𝐶𝑧 → ((𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦)) |
| 14 | 13 | exlimdv 1970 | . . . . . . 7 ⊢ (𝑥𝐶𝑧 → (∃𝑤(𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦)) |
| 15 | 7, 14 | biimtrid 245 | . . . . . 6 ⊢ (𝑥𝐶𝑧 → (𝑧(𝐴 ∘ 𝐵)𝑦 → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦)) |
| 16 | 15 | imp 412 | . . . . 5 ⊢ ((𝑥𝐶𝑧 ∧ 𝑧(𝐴 ∘ 𝐵)𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦) |
| 17 | 16 | exlimiv 1967 | . . . 4 ⊢ (∃𝑧(𝑥𝐶𝑧 ∧ 𝑧(𝐴 ∘ 𝐵)𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦) |
| 18 | 5, 17 | sylbi 220 | . . 3 ⊢ (𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦 → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦) |
| 19 | 3, 4 | brco 5859 | . . . 4 ⊢ (𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦 ↔ ∃𝑤(𝑥(𝐵 ∘ 𝐶)𝑤 ∧ 𝑤𝐴𝑦)) |
| 20 | 3, 8 | brco 5859 | . . . . . . 7 ⊢ (𝑥(𝐵 ∘ 𝐶)𝑤 ↔ ∃𝑧(𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤)) |
| 21 | 6, 8, 4 | brcoi 5857 | . . . . . . . . . . 11 ⊢ ((𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦) → 𝑧(𝐴 ∘ 𝐵)𝑦) |
| 22 | 3, 6, 4 | brcoi 5857 | . . . . . . . . . . 11 ⊢ ((𝑥𝐶𝑧 ∧ 𝑧(𝐴 ∘ 𝐵)𝑦) → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦) |
| 23 | 21, 22 | sylan2 605 | . . . . . . . . . 10 ⊢ ((𝑥𝐶𝑧 ∧ (𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦)) → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦) |
| 24 | 23 | anassrs 473 | . . . . . . . . 9 ⊢ (((𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤) ∧ 𝑤𝐴𝑦) → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦) |
| 25 | 24 | ex 418 | . . . . . . . 8 ⊢ ((𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤) → (𝑤𝐴𝑦 → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦)) |
| 26 | 25 | exlimiv 1967 | . . . . . . 7 ⊢ (∃𝑧(𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤) → (𝑤𝐴𝑦 → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦)) |
| 27 | 20, 26 | sylbi 220 | . . . . . 6 ⊢ (𝑥(𝐵 ∘ 𝐶)𝑤 → (𝑤𝐴𝑦 → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦)) |
| 28 | 27 | imp 412 | . . . . 5 ⊢ ((𝑥(𝐵 ∘ 𝐶)𝑤 ∧ 𝑤𝐴𝑦) → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦) |
| 29 | 28 | exlimiv 1967 | . . . 4 ⊢ (∃𝑤(𝑥(𝐵 ∘ 𝐶)𝑤 ∧ 𝑤𝐴𝑦) → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦) |
| 30 | 19, 29 | sylbi 220 | . . 3 ⊢ (𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦 → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦) |
| 31 | 18, 30 | impbii 212 | . 2 ⊢ (𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦 ↔ 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦) |
| 32 | 1, 2, 31 | eqbrriv 5775 | 1 ⊢ ((𝐴 ∘ 𝐵) ∘ 𝐶) = (𝐴 ∘ (𝐵 ∘ 𝐶)) |
| Colors of variables: wff setvar class |
| This proof depends on syntax axioms: → wi 4 ∧ wa 401 = wceq 1572 ∃wex 1814 class class class wbr 5107 ∘ ccom 5661 |
| This proof depends on axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1830 ax-4 1844 ax-5 1947 ax-6 2004 ax-7 2045 ax-8 2152 ax-9 2160 ax-ext 2738 ax-sep 5254 ax-pr 5397 |
| This proof depends on definitions: df-bi 210 df-an 402 df-or 862 df-3an 1106 df-tru 1575 df-fal 1585 df-ex 1815 df-sb 2104 df-clab 2745 df-cleq 2758 df-clel 2842 df-rab 3416 df-v 3455 df-ss 3900 df-dif 4049 df-in 4093 df-un 4153 df-nul 4281 df-if 4485 df-sn 4588 df-pr 4590 df-op 4840 df-br 5108 df-opab 5173 df-xp 5663 df-rel 5664 df-co 5666 |
| This theorem is used by: funcoeqres 6886 fcof1oinvd 7331 tposco 8311 mapen 9197 mapfien 9436 hashfacen 14639 relexpsucnnl 15225 relexpaddnn 15246 cofuass 18116 setccatid 18311 estrccatid 18358 frmdup3lem 19114 symggrplem 19132 f1omvdco2 19715 symggen 19737 psgnunilem1 19760 gsumval3 20174 gsumzf1o 20179 gsumzmhm 20204 prds1 20605 psrass1lem 22298 pf1mpf 22727 pf1ind 22730 qtophmeo 24193 uniioombllem2 25961 cncombf 26036 motgrp 29065 pjsdi2i 32818 pjadj2coi 32865 pj3lem1 32867 pj3i 32869 fcoinver 33298 fmptco1f1o 33327 fcobij 33410 fcobijfs 33411 cocnvf1o 33419 symgfcoeu 33743 pmtrcnel2 33751 cycpmconjv 33803 cycpmconjslem1 33815 cycpmconjs 33817 cyc3conja 33818 1arithidomlem2 34173 selvascl 34261 mplvrpmga 34289 mplvrpmrhm 34291 reprpmtf1o 35367 derangenlem 36145 subfacp1lem5 36158 erdsze2lem2 36178 pprodcnveq 36861 coss1b 38218 coindir 38219 coss2b 38220 coindi 38221 cossidres1 38222 coidmid 38227 cocnv 38929 ltrncoidN 41453 trlcoabs2N 42047 trlcoat 42048 trlcone 42053 cdlemg46 42060 cdlemg47 42061 ltrnco4 42064 tgrpgrplem 42074 tendoplass 42108 cdlemi2 42144 cdlemk2 42157 cdlemk4 42159 cdlemk8 42163 cdlemk45 42272 cdlemk54 42283 cdlemk55a 42284 erngdvlem3 42315 erngdvlem3-rN 42323 tendocnv 42346 dvhvaddass 42422 dvhlveclem 42433 cdlemn8 42529 dihopelvalcpre 42573 dih1dimatlem0 42653 aks6d1c6lem5 43495 diophrw 44035 eldioph2 44038 mendring 44450 cortrcltrcl 45061 corclrtrcl 45062 cortrclrcl 45064 cotrclrtrcl 45065 cortrclrtrcl 45066 frege131d 45085 brcofffn 45352 brco3f1o 45354 neicvgnvo 45436 volicoff 47338 voliooicof 47339 ovolval4lem2 47993 3f1oss1 48478 gricushgr 49348 rngccatidALTV 49702 ringccatidALTV 49736 fuco11idx 50878 |
| Copyright terms: Public domain | W3C validator |