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

Theorem trer 34080
 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 4136 . . . 4 ( ) ⊆
2 relcnv 5943 . . . 4 Rel
3 relss 5629 . . . 4 (( ) ⊆ → (Rel → Rel ( )))
41, 2, 3mp2 9 . . 3 Rel ( )
54a1i 11 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → Rel ( ))
6 eqidd 2759 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → dom ( ) = dom ( ))
7 brin 5087 . . . . . . . 8 (𝑟( )𝑠 ↔ (𝑟 𝑠𝑟 𝑠))
8 vex 3413 . . . . . . . . . 10 𝑟 ∈ V
9 vex 3413 . . . . . . . . . 10 𝑠 ∈ V
108, 9brcnv 5727 . . . . . . . . 9 (𝑟 𝑠𝑠 𝑟)
1110anbi2i 625 . . . . . . . 8 ((𝑟 𝑠𝑟 𝑠) ↔ (𝑟 𝑠𝑠 𝑟))
127, 11bitri 278 . . . . . . 7 (𝑟( )𝑠 ↔ (𝑟 𝑠𝑠 𝑟))
13 brin 5087 . . . . . . . 8 (𝑠( )𝑡 ↔ (𝑠 𝑡𝑠 𝑡))
14 vex 3413 . . . . . . . . . 10 𝑡 ∈ V
159, 14brcnv 5727 . . . . . . . . 9 (𝑠 𝑡𝑡 𝑠)
1615anbi2i 625 . . . . . . . 8 ((𝑠 𝑡𝑠 𝑡) ↔ (𝑠 𝑡𝑡 𝑠))
1713, 16bitri 278 . . . . . . 7 (𝑠( )𝑡 ↔ (𝑠 𝑡𝑡 𝑠))
1812, 17anbi12i 629 . . . . . 6 ((𝑟( )𝑠𝑠( )𝑡) ↔ ((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)))
19 breq1 5038 . . . . . . . . . . . . 13 (𝑎 = 𝑟 → (𝑎 𝑏𝑟 𝑏))
2019anbi1d 632 . . . . . . . . . . . 12 (𝑎 = 𝑟 → ((𝑎 𝑏𝑏 𝑐) ↔ (𝑟 𝑏𝑏 𝑐)))
21 breq1 5038 . . . . . . . . . . . 12 (𝑎 = 𝑟 → (𝑎 𝑐𝑟 𝑐))
2220, 21imbi12d 348 . . . . . . . . . . 11 (𝑎 = 𝑟 → (((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐)))
23222albidv 1924 . . . . . . . . . 10 (𝑎 = 𝑟 → (∀𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐)))
2423spvv 2003 . . . . . . . . 9 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐))
25 breq2 5039 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑟 𝑏𝑟 𝑠))
26 breq1 5038 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑏 𝑐𝑠 𝑐))
2725, 26anbi12d 633 . . . . . . . . . . . 12 (𝑏 = 𝑠 → ((𝑟 𝑏𝑏 𝑐) ↔ (𝑟 𝑠𝑠 𝑐)))
2827imbi1d 345 . . . . . . . . . . 11 (𝑏 = 𝑠 → (((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) ↔ ((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐)))
2928albidv 1921 . . . . . . . . . 10 (𝑏 = 𝑠 → (∀𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) ↔ ∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐)))
3029spvv 2003 . . . . . . . . 9 (∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) → ∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐))
31 breq2 5039 . . . . . . . . . . . 12 (𝑐 = 𝑡 → (𝑠 𝑐𝑠 𝑡))
3231anbi2d 631 . . . . . . . . . . 11 (𝑐 = 𝑡 → ((𝑟 𝑠𝑠 𝑐) ↔ (𝑟 𝑠𝑠 𝑡)))
33 breq2 5039 . . . . . . . . . . 11 (𝑐 = 𝑡 → (𝑟 𝑐𝑟 𝑡))
3432, 33imbi12d 348 . . . . . . . . . 10 (𝑐 = 𝑡 → (((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐) ↔ ((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡)))
3534spvv 2003 . . . . . . . . 9 (∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐) → ((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡))
36 pm3.3 452 . . . . . . . . . . . . . 14 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑟 𝑠 → (𝑠 𝑡𝑟 𝑡)))
3736com23 86 . . . . . . . . . . . . 13 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑠 𝑡 → (𝑟 𝑠𝑟 𝑡)))
3837adantrd 495 . . . . . . . . . . . 12 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → ((𝑠 𝑡𝑡 𝑠) → (𝑟 𝑠𝑟 𝑡)))
3938com23 86 . . . . . . . . . . 11 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑟 𝑠 → ((𝑠 𝑡𝑡 𝑠) → 𝑟 𝑡)))
4039adantrd 495 . . . . . . . . . 10 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → ((𝑟 𝑠𝑠 𝑟) → ((𝑠 𝑡𝑡 𝑠) → 𝑟 𝑡)))
4140impd 414 . . . . . . . . 9 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟 𝑡))
4224, 30, 35, 414syl 19 . . . . . . . 8 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟 𝑡))
43 breq1 5038 . . . . . . . . . . . . 13 (𝑎 = 𝑡 → (𝑎 𝑏𝑡 𝑏))
4443anbi1d 632 . . . . . . . . . . . 12 (𝑎 = 𝑡 → ((𝑎 𝑏𝑏 𝑐) ↔ (𝑡 𝑏𝑏 𝑐)))
45 breq1 5038 . . . . . . . . . . . 12 (𝑎 = 𝑡 → (𝑎 𝑐𝑡 𝑐))
4644, 45imbi12d 348 . . . . . . . . . . 11 (𝑎 = 𝑡 → (((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐)))
47462albidv 1924 . . . . . . . . . 10 (𝑎 = 𝑡 → (∀𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐)))
4847spvv 2003 . . . . . . . . 9 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐))
49 breq2 5039 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑡 𝑏𝑡 𝑠))
5049, 26anbi12d 633 . . . . . . . . . . . 12 (𝑏 = 𝑠 → ((𝑡 𝑏𝑏 𝑐) ↔ (𝑡 𝑠𝑠 𝑐)))
5150imbi1d 345 . . . . . . . . . . 11 (𝑏 = 𝑠 → (((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) ↔ ((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐)))
5251albidv 1921 . . . . . . . . . 10 (𝑏 = 𝑠 → (∀𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) ↔ ∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐)))
5352spvv 2003 . . . . . . . . 9 (∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) → ∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐))
54 breq2 5039 . . . . . . . . . . . 12 (𝑐 = 𝑟 → (𝑠 𝑐𝑠 𝑟))
5554anbi2d 631 . . . . . . . . . . 11 (𝑐 = 𝑟 → ((𝑡 𝑠𝑠 𝑐) ↔ (𝑡 𝑠𝑠 𝑟)))
56 breq2 5039 . . . . . . . . . . 11 (𝑐 = 𝑟 → (𝑡 𝑐𝑡 𝑟))
5755, 56imbi12d 348 . . . . . . . . . 10 (𝑐 = 𝑟 → (((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐) ↔ ((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟)))
5857spvv 2003 . . . . . . . . 9 (∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐) → ((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟))
59 pm3.3 452 . . . . . . . . . . . . 13 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (𝑡 𝑠 → (𝑠 𝑟𝑡 𝑟)))
6059adantld 494 . . . . . . . . . . . 12 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → ((𝑠 𝑡𝑡 𝑠) → (𝑠 𝑟𝑡 𝑟)))
6160com23 86 . . . . . . . . . . 11 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (𝑠 𝑟 → ((𝑠 𝑡𝑡 𝑠) → 𝑡 𝑟)))
6261adantld 494 . . . . . . . . . 10 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → ((𝑟 𝑠𝑠 𝑟) → ((𝑠 𝑡𝑡 𝑠) → 𝑡 𝑟)))
6362impd 414 . . . . . . . . 9 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑡 𝑟))
6448, 53, 58, 634syl 19 . . . . . . . 8 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑡 𝑟))
6542, 64jcad 516 . . . . . . 7 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → (𝑟 𝑡𝑡 𝑟)))
66 brin 5087 . . . . . . . 8 (𝑟( )𝑡 ↔ (𝑟 𝑡𝑟 𝑡))
678, 14brcnv 5727 . . . . . . . . 9 (𝑟 𝑡𝑡 𝑟)
6867anbi2i 625 . . . . . . . 8 ((𝑟 𝑡𝑟 𝑡) ↔ (𝑟 𝑡𝑡 𝑟))
6966, 68bitr2i 279 . . . . . . 7 ((𝑟 𝑡𝑡 𝑟) ↔ 𝑟( )𝑡)
7065, 69syl6ib 254 . . . . . 6 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟( )𝑡))
7118, 70syl5bi 245 . . . . 5 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡))
729, 8brcnv 5727 . . . . . . . . 9 (𝑠 𝑟𝑟 𝑠)
7372bicomi 227 . . . . . . . 8 (𝑟 𝑠𝑠 𝑟)
7473, 10anbi12ci 630 . . . . . . 7 ((𝑟 𝑠𝑟 𝑠) ↔ (𝑠 𝑟𝑠 𝑟))
75 brin 5087 . . . . . . 7 (𝑠( )𝑟 ↔ (𝑠 𝑟𝑠 𝑟))
7674, 7, 753bitr4i 306 . . . . . 6 (𝑟( )𝑠𝑠( )𝑟)
7776biimpi 219 . . . . 5 (𝑟( )𝑠𝑠( )𝑟)
7871, 77jctil 523 . . . 4 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
7978alrimiv 1928 . . 3 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
8079alrimivv 1929 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑟𝑠𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
81 dfer2 8305 . 2 (( ) Er dom ( ) ↔ (Rel ( ) ∧ dom ( ) = dom ( ) ∧ ∀𝑟𝑠𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡))))
825, 6, 80, 81syl3anbrc 1340 1 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ( ) Er dom ( ))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ∧ wa 399  ∀wal 1536   = wceq 1538   ∩ cin 3859   ⊆ wss 3860   class class class wbr 5035  ◡ccnv 5526  dom cdm 5527  Rel wrel 5532   Er wer 8301 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1911  ax-6 1970  ax-7 2015  ax-8 2113  ax-9 2121  ax-11 2158  ax-12 2175  ax-ext 2729  ax-sep 5172  ax-nul 5179  ax-pr 5301 This theorem depends on definitions:  df-bi 210  df-an 400  df-or 845  df-3an 1086  df-tru 1541  df-fal 1551  df-ex 1782  df-sb 2070  df-clab 2736  df-cleq 2750  df-clel 2830  df-rab 3079  df-v 3411  df-dif 3863  df-un 3865  df-in 3867  df-ss 3877  df-nul 4228  df-if 4424  df-sn 4526  df-pr 4528  df-op 4532  df-br 5036  df-opab 5098  df-xp 5533  df-rel 5534  df-cnv 5535  df-co 5536  df-er 8304 This theorem is referenced by: (None)
 Copyright terms: Public domain W3C validator