MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  coass Structured version   Visualization version   GIF version

Theorem coass 6289
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.)
Assertion
Ref Expression
coass ((𝐴 ∘ 𝐵) ∘ 𝐶) = (𝐴 ∘ (𝐵 ∘ 𝐶))

Proof of Theorem coass
Dummy variables 𝑥 𝑦 𝑧 𝑤 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 relco 6121 . 2 Rel ((𝐴 ∘ 𝐵) ∘ 𝐶)
2 relco 6121 . 2 Rel (𝐴 ∘ (𝐵 ∘ 𝐶))
3 vex 3457 . . . . 5 𝑥 ∈ V
4 vex 3457 . . . . 5 𝑦 ∈ V
53, 4brco 5859 . . . 4 (𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦 ↔ ∃𝑧(𝑥𝐶𝑧 ∧ 𝑧(𝐴 ∘ 𝐵)𝑦))
6 vex 3457 . . . . . . . 8 𝑧 ∈ V
76, 4brco 5859 . . . . . . 7 (𝑧(𝐴 ∘ 𝐵)𝑦 ↔ ∃𝑤(𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦))
8 vex 3457 . . . . . . . . . . . 12 𝑤 ∈ V
93, 6, 8brcoi 5857 . . . . . . . . . . 11 ((𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤) → 𝑥(𝐵 ∘ 𝐶)𝑤)
103, 8, 4brcoi 5857 . . . . . . . . . . 11 ((𝑥(𝐵 ∘ 𝐶)𝑤 ∧ 𝑤𝐴𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦)
119, 10sylan 592 . . . . . . . . . 10 (((𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤) ∧ 𝑤𝐴𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦)
1211anasss 472 . . . . . . . . 9 ((𝑥𝐶𝑧 ∧ (𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦)) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦)
1312ex 418 . . . . . . . 8 (𝑥𝐶𝑧 → ((𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦))
1413exlimdv 1970 . . . . . . 7 (𝑥𝐶𝑧 → (∃𝑤(𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦))
157, 14biimtrid 245 . . . . . 6 (𝑥𝐶𝑧 → (𝑧(𝐴 ∘ 𝐵)𝑦 → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦))
1615imp 412 . . . . 5 ((𝑥𝐶𝑧 ∧ 𝑧(𝐴 ∘ 𝐵)𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦)
1716exlimiv 1967 . . . 4 (∃𝑧(𝑥𝐶𝑧 ∧ 𝑧(𝐴 ∘ 𝐵)𝑦) → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦)
185, 17sylbi 220 . . 3 (𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦 → 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦)
193, 4brco 5859 . . . 4 (𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦 ↔ ∃𝑤(𝑥(𝐵 ∘ 𝐶)𝑤 ∧ 𝑤𝐴𝑦))
203, 8brco 5859 . . . . . . 7 (𝑥(𝐵 ∘ 𝐶)𝑤 ↔ ∃𝑧(𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤))
216, 8, 4brcoi 5857 . . . . . . . . . . 11 ((𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦) → 𝑧(𝐴 ∘ 𝐵)𝑦)
223, 6, 4brcoi 5857 . . . . . . . . . . 11 ((𝑥𝐶𝑧 ∧ 𝑧(𝐴 ∘ 𝐵)𝑦) → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦)
2321, 22sylan2 605 . . . . . . . . . 10 ((𝑥𝐶𝑧 ∧ (𝑧𝐵𝑤 ∧ 𝑤𝐴𝑦)) → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦)
2423anassrs 473 . . . . . . . . 9 (((𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤) ∧ 𝑤𝐴𝑦) → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦)
2524ex 418 . . . . . . . 8 ((𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤) → (𝑤𝐴𝑦 → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦))
2625exlimiv 1967 . . . . . . 7 (∃𝑧(𝑥𝐶𝑧 ∧ 𝑧𝐵𝑤) → (𝑤𝐴𝑦 → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦))
2720, 26sylbi 220 . . . . . 6 (𝑥(𝐵 ∘ 𝐶)𝑤 → (𝑤𝐴𝑦 → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦))
2827imp 412 . . . . 5 ((𝑥(𝐵 ∘ 𝐶)𝑤 ∧ 𝑤𝐴𝑦) → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦)
2928exlimiv 1967 . . . 4 (∃𝑤(𝑥(𝐵 ∘ 𝐶)𝑤 ∧ 𝑤𝐴𝑦) → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦)
3019, 29sylbi 220 . . 3 (𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦 → 𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦)
3118, 30impbii 212 . 2 (𝑥((𝐴 ∘ 𝐵) ∘ 𝐶)𝑦 ↔ 𝑥(𝐴 ∘ (𝐵 ∘ 𝐶))𝑦)
321, 2, 31eqbrriv 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