Users' Mathboxes Mathbox for Jeff Hankins < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  trer Structured version   Visualization version   GIF version

Theorem trer 31944
Description: A relation intersected with its converse is an equivalence relation if the relation is transitive. (Contributed by Jeff Hankins, 6-Oct-2009.) (Revised by Mario Carneiro, 12-Aug-2015.)
Assertion
Ref Expression
trer (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ( ) Er dom ( ))
Distinct variable group:   𝑎,𝑏,𝑐,

Proof of Theorem trer
Dummy variables 𝑟 𝑠 𝑡 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 inss2 3817 . . . 4 ( ) ⊆
2 relcnv 5466 . . . 4 Rel
3 relss 5172 . . . 4 (( ) ⊆ → (Rel → Rel ( )))
41, 2, 3mp2 9 . . 3 Rel ( )
54a1i 11 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → Rel ( ))
6 eqidd 2627 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → dom ( ) = dom ( ))
7 brin 4669 . . . . . . . 8 (𝑟( )𝑠 ↔ (𝑟 𝑠𝑟 𝑠))
8 vex 3194 . . . . . . . . . 10 𝑟 ∈ V
9 vex 3194 . . . . . . . . . 10 𝑠 ∈ V
108, 9brcnv 5270 . . . . . . . . 9 (𝑟 𝑠𝑠 𝑟)
1110anbi2i 729 . . . . . . . 8 ((𝑟 𝑠𝑟 𝑠) ↔ (𝑟 𝑠𝑠 𝑟))
127, 11bitri 264 . . . . . . 7 (𝑟( )𝑠 ↔ (𝑟 𝑠𝑠 𝑟))
13 brin 4669 . . . . . . . 8 (𝑠( )𝑡 ↔ (𝑠 𝑡𝑠 𝑡))
14 vex 3194 . . . . . . . . . 10 𝑡 ∈ V
159, 14brcnv 5270 . . . . . . . . 9 (𝑠 𝑡𝑡 𝑠)
1615anbi2i 729 . . . . . . . 8 ((𝑠 𝑡𝑠 𝑡) ↔ (𝑠 𝑡𝑡 𝑠))
1713, 16bitri 264 . . . . . . 7 (𝑠( )𝑡 ↔ (𝑠 𝑡𝑡 𝑠))
1812, 17anbi12i 732 . . . . . 6 ((𝑟( )𝑠𝑠( )𝑡) ↔ ((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)))
19 breq1 4621 . . . . . . . . . . . . 13 (𝑎 = 𝑟 → (𝑎 𝑏𝑟 𝑏))
2019anbi1d 740 . . . . . . . . . . . 12 (𝑎 = 𝑟 → ((𝑎 𝑏𝑏 𝑐) ↔ (𝑟 𝑏𝑏 𝑐)))
21 breq1 4621 . . . . . . . . . . . 12 (𝑎 = 𝑟 → (𝑎 𝑐𝑟 𝑐))
2220, 21imbi12d 334 . . . . . . . . . . 11 (𝑎 = 𝑟 → (((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐)))
23222albidv 1853 . . . . . . . . . 10 (𝑎 = 𝑟 → (∀𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐)))
2423spv 2264 . . . . . . . . 9 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐))
25 breq2 4622 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑟 𝑏𝑟 𝑠))
26 breq1 4621 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑏 𝑐𝑠 𝑐))
2725, 26anbi12d 746 . . . . . . . . . . . 12 (𝑏 = 𝑠 → ((𝑟 𝑏𝑏 𝑐) ↔ (𝑟 𝑠𝑠 𝑐)))
2827imbi1d 331 . . . . . . . . . . 11 (𝑏 = 𝑠 → (((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) ↔ ((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐)))
2928albidv 1851 . . . . . . . . . 10 (𝑏 = 𝑠 → (∀𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) ↔ ∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐)))
3029spv 2264 . . . . . . . . 9 (∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) → ∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐))
31 breq2 4622 . . . . . . . . . . . 12 (𝑐 = 𝑡 → (𝑠 𝑐𝑠 𝑡))
3231anbi2d 739 . . . . . . . . . . 11 (𝑐 = 𝑡 → ((𝑟 𝑠𝑠 𝑐) ↔ (𝑟 𝑠𝑠 𝑡)))
33 breq2 4622 . . . . . . . . . . 11 (𝑐 = 𝑡 → (𝑟 𝑐𝑟 𝑡))
3432, 33imbi12d 334 . . . . . . . . . 10 (𝑐 = 𝑡 → (((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐) ↔ ((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡)))
3534spv 2264 . . . . . . . . 9 (∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐) → ((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡))
36 pm3.3 460 . . . . . . . . . . . . . 14 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑟 𝑠 → (𝑠 𝑡𝑟 𝑡)))
3736com23 86 . . . . . . . . . . . . 13 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑠 𝑡 → (𝑟 𝑠𝑟 𝑡)))
3837adantrd 484 . . . . . . . . . . . 12 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → ((𝑠 𝑡𝑡 𝑠) → (𝑟 𝑠𝑟 𝑡)))
3938com23 86 . . . . . . . . . . 11 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑟 𝑠 → ((𝑠 𝑡𝑡 𝑠) → 𝑟 𝑡)))
4039adantrd 484 . . . . . . . . . 10 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → ((𝑟 𝑠𝑠 𝑟) → ((𝑠 𝑡𝑡 𝑠) → 𝑟 𝑡)))
4140impd 447 . . . . . . . . 9 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟 𝑡))
4224, 30, 35, 414syl 19 . . . . . . . 8 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟 𝑡))
43 breq1 4621 . . . . . . . . . . . . 13 (𝑎 = 𝑡 → (𝑎 𝑏𝑡 𝑏))
4443anbi1d 740 . . . . . . . . . . . 12 (𝑎 = 𝑡 → ((𝑎 𝑏𝑏 𝑐) ↔ (𝑡 𝑏𝑏 𝑐)))
45 breq1 4621 . . . . . . . . . . . 12 (𝑎 = 𝑡 → (𝑎 𝑐𝑡 𝑐))
4644, 45imbi12d 334 . . . . . . . . . . 11 (𝑎 = 𝑡 → (((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐)))
47462albidv 1853 . . . . . . . . . 10 (𝑎 = 𝑡 → (∀𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐)))
4847spv 2264 . . . . . . . . 9 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐))
49 breq2 4622 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑡 𝑏𝑡 𝑠))
5049, 26anbi12d 746 . . . . . . . . . . . 12 (𝑏 = 𝑠 → ((𝑡 𝑏𝑏 𝑐) ↔ (𝑡 𝑠𝑠 𝑐)))
5150imbi1d 331 . . . . . . . . . . 11 (𝑏 = 𝑠 → (((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) ↔ ((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐)))
5251albidv 1851 . . . . . . . . . 10 (𝑏 = 𝑠 → (∀𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) ↔ ∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐)))
5352spv 2264 . . . . . . . . 9 (∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) → ∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐))
54 breq2 4622 . . . . . . . . . . . 12 (𝑐 = 𝑟 → (𝑠 𝑐𝑠 𝑟))
5554anbi2d 739 . . . . . . . . . . 11 (𝑐 = 𝑟 → ((𝑡 𝑠𝑠 𝑐) ↔ (𝑡 𝑠𝑠 𝑟)))
56 breq2 4622 . . . . . . . . . . 11 (𝑐 = 𝑟 → (𝑡 𝑐𝑡 𝑟))
5755, 56imbi12d 334 . . . . . . . . . 10 (𝑐 = 𝑟 → (((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐) ↔ ((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟)))
5857spv 2264 . . . . . . . . 9 (∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐) → ((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟))
59 pm3.3 460 . . . . . . . . . . . . 13 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (𝑡 𝑠 → (𝑠 𝑟𝑡 𝑟)))
6059adantld 483 . . . . . . . . . . . 12 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → ((𝑠 𝑡𝑡 𝑠) → (𝑠 𝑟𝑡 𝑟)))
6160com23 86 . . . . . . . . . . 11 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (𝑠 𝑟 → ((𝑠 𝑡𝑡 𝑠) → 𝑡 𝑟)))
6261adantld 483 . . . . . . . . . 10 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → ((𝑟 𝑠𝑠 𝑟) → ((𝑠 𝑡𝑡 𝑠) → 𝑡 𝑟)))
6362impd 447 . . . . . . . . 9 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑡 𝑟))
6448, 53, 58, 634syl 19 . . . . . . . 8 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑡 𝑟))
6542, 64jcad 555 . . . . . . 7 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → (𝑟 𝑡𝑡 𝑟)))
66 brin 4669 . . . . . . . 8 (𝑟( )𝑡 ↔ (𝑟 𝑡𝑟 𝑡))
678, 14brcnv 5270 . . . . . . . . 9 (𝑟 𝑡𝑡 𝑟)
6867anbi2i 729 . . . . . . . 8 ((𝑟 𝑡𝑟 𝑡) ↔ (𝑟 𝑡𝑡 𝑟))
6966, 68bitr2i 265 . . . . . . 7 ((𝑟 𝑡𝑡 𝑟) ↔ 𝑟( )𝑡)
7065, 69syl6ib 241 . . . . . 6 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟( )𝑡))
7118, 70syl5bi 232 . . . . 5 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡))
729, 8brcnv 5270 . . . . . . . . 9 (𝑠 𝑟𝑟 𝑠)
7372bicomi 214 . . . . . . . 8 (𝑟 𝑠𝑠 𝑟)
7473, 10anbi12ci 733 . . . . . . 7 ((𝑟 𝑠𝑟 𝑠) ↔ (𝑠 𝑟𝑠 𝑟))
75 brin 4669 . . . . . . 7 (𝑠( )𝑟 ↔ (𝑠 𝑟𝑠 𝑟))
7674, 7, 753bitr4i 292 . . . . . 6 (𝑟( )𝑠𝑠( )𝑟)
7776biimpi 206 . . . . 5 (𝑟( )𝑠𝑠( )𝑟)
7871, 77jctil 559 . . . 4 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
7978alrimiv 1857 . . 3 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
8079alrimivv 1858 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑟𝑠𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
81 dfer2 7689 . 2 (( ) Er dom ( ) ↔ (Rel ( ) ∧ dom ( ) = dom ( ) ∧ ∀𝑟𝑠𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡))))
825, 6, 80, 81syl3anbrc 1244 1 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ( ) Er dom ( ))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 384  wal 1478   = wceq 1480  cin 3559  wss 3560   class class class wbr 4618  ccnv 5078  dom cdm 5079  Rel wrel 5084   Er wer 7685
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1719  ax-4 1734  ax-5 1841  ax-6 1890  ax-7 1937  ax-9 2001  ax-10 2021  ax-11 2036  ax-12 2049  ax-13 2250  ax-ext 2606  ax-sep 4746  ax-nul 4754  ax-pr 4872
This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3an 1038  df-tru 1483  df-ex 1702  df-nf 1707  df-sb 1883  df-eu 2478  df-mo 2479  df-clab 2613  df-cleq 2619  df-clel 2622  df-nfc 2756  df-rab 2921  df-v 3193  df-dif 3563  df-un 3565  df-in 3567  df-ss 3574  df-nul 3897  df-if 4064  df-sn 4154  df-pr 4156  df-op 4160  df-br 4619  df-opab 4679  df-xp 5085  df-rel 5086  df-cnv 5087  df-co 5088  df-er 7688
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator