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 33549
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 4209 . . . 4 ( ) ⊆
2 relcnv 5964 . . . 4 Rel
3 relss 5654 . . . 4 (( ) ⊆ → (Rel → Rel ( )))
41, 2, 3mp2 9 . . 3 Rel ( )
54a1i 11 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → Rel ( ))
6 eqidd 2825 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → dom ( ) = dom ( ))
7 brin 5114 . . . . . . . 8 (𝑟( )𝑠 ↔ (𝑟 𝑠𝑟 𝑠))
8 vex 3502 . . . . . . . . . 10 𝑟 ∈ V
9 vex 3502 . . . . . . . . . 10 𝑠 ∈ V
108, 9brcnv 5751 . . . . . . . . 9 (𝑟 𝑠𝑠 𝑟)
1110anbi2i 622 . . . . . . . 8 ((𝑟 𝑠𝑟 𝑠) ↔ (𝑟 𝑠𝑠 𝑟))
127, 11bitri 276 . . . . . . 7 (𝑟( )𝑠 ↔ (𝑟 𝑠𝑠 𝑟))
13 brin 5114 . . . . . . . 8 (𝑠( )𝑡 ↔ (𝑠 𝑡𝑠 𝑡))
14 vex 3502 . . . . . . . . . 10 𝑡 ∈ V
159, 14brcnv 5751 . . . . . . . . 9 (𝑠 𝑡𝑡 𝑠)
1615anbi2i 622 . . . . . . . 8 ((𝑠 𝑡𝑠 𝑡) ↔ (𝑠 𝑡𝑡 𝑠))
1713, 16bitri 276 . . . . . . 7 (𝑠( )𝑡 ↔ (𝑠 𝑡𝑡 𝑠))
1812, 17anbi12i 626 . . . . . 6 ((𝑟( )𝑠𝑠( )𝑡) ↔ ((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)))
19 breq1 5065 . . . . . . . . . . . . 13 (𝑎 = 𝑟 → (𝑎 𝑏𝑟 𝑏))
2019anbi1d 629 . . . . . . . . . . . 12 (𝑎 = 𝑟 → ((𝑎 𝑏𝑏 𝑐) ↔ (𝑟 𝑏𝑏 𝑐)))
21 breq1 5065 . . . . . . . . . . . 12 (𝑎 = 𝑟 → (𝑎 𝑐𝑟 𝑐))
2220, 21imbi12d 346 . . . . . . . . . . 11 (𝑎 = 𝑟 → (((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐)))
23222albidv 1917 . . . . . . . . . 10 (𝑎 = 𝑟 → (∀𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐)))
2423spv 2407 . . . . . . . . 9 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐))
25 breq2 5066 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑟 𝑏𝑟 𝑠))
26 breq1 5065 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑏 𝑐𝑠 𝑐))
2725, 26anbi12d 630 . . . . . . . . . . . 12 (𝑏 = 𝑠 → ((𝑟 𝑏𝑏 𝑐) ↔ (𝑟 𝑠𝑠 𝑐)))
2827imbi1d 343 . . . . . . . . . . 11 (𝑏 = 𝑠 → (((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) ↔ ((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐)))
2928albidv 1914 . . . . . . . . . 10 (𝑏 = 𝑠 → (∀𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) ↔ ∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐)))
3029spv 2407 . . . . . . . . 9 (∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) → ∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐))
31 breq2 5066 . . . . . . . . . . . 12 (𝑐 = 𝑡 → (𝑠 𝑐𝑠 𝑡))
3231anbi2d 628 . . . . . . . . . . 11 (𝑐 = 𝑡 → ((𝑟 𝑠𝑠 𝑐) ↔ (𝑟 𝑠𝑠 𝑡)))
33 breq2 5066 . . . . . . . . . . 11 (𝑐 = 𝑡 → (𝑟 𝑐𝑟 𝑡))
3432, 33imbi12d 346 . . . . . . . . . 10 (𝑐 = 𝑡 → (((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐) ↔ ((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡)))
3534spv 2407 . . . . . . . . 9 (∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐) → ((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡))
36 pm3.3 449 . . . . . . . . . . . . . 14 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑟 𝑠 → (𝑠 𝑡𝑟 𝑡)))
3736com23 86 . . . . . . . . . . . . 13 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑠 𝑡 → (𝑟 𝑠𝑟 𝑡)))
3837adantrd 492 . . . . . . . . . . . 12 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → ((𝑠 𝑡𝑡 𝑠) → (𝑟 𝑠𝑟 𝑡)))
3938com23 86 . . . . . . . . . . 11 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑟 𝑠 → ((𝑠 𝑡𝑡 𝑠) → 𝑟 𝑡)))
4039adantrd 492 . . . . . . . . . 10 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → ((𝑟 𝑠𝑠 𝑟) → ((𝑠 𝑡𝑡 𝑠) → 𝑟 𝑡)))
4140impd 411 . . . . . . . . 9 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟 𝑡))
4224, 30, 35, 414syl 19 . . . . . . . 8 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟 𝑡))
43 breq1 5065 . . . . . . . . . . . . 13 (𝑎 = 𝑡 → (𝑎 𝑏𝑡 𝑏))
4443anbi1d 629 . . . . . . . . . . . 12 (𝑎 = 𝑡 → ((𝑎 𝑏𝑏 𝑐) ↔ (𝑡 𝑏𝑏 𝑐)))
45 breq1 5065 . . . . . . . . . . . 12 (𝑎 = 𝑡 → (𝑎 𝑐𝑡 𝑐))
4644, 45imbi12d 346 . . . . . . . . . . 11 (𝑎 = 𝑡 → (((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐)))
47462albidv 1917 . . . . . . . . . 10 (𝑎 = 𝑡 → (∀𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐)))
4847spv 2407 . . . . . . . . 9 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐))
49 breq2 5066 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑡 𝑏𝑡 𝑠))
5049, 26anbi12d 630 . . . . . . . . . . . 12 (𝑏 = 𝑠 → ((𝑡 𝑏𝑏 𝑐) ↔ (𝑡 𝑠𝑠 𝑐)))
5150imbi1d 343 . . . . . . . . . . 11 (𝑏 = 𝑠 → (((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) ↔ ((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐)))
5251albidv 1914 . . . . . . . . . 10 (𝑏 = 𝑠 → (∀𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) ↔ ∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐)))
5352spv 2407 . . . . . . . . 9 (∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) → ∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐))
54 breq2 5066 . . . . . . . . . . . 12 (𝑐 = 𝑟 → (𝑠 𝑐𝑠 𝑟))
5554anbi2d 628 . . . . . . . . . . 11 (𝑐 = 𝑟 → ((𝑡 𝑠𝑠 𝑐) ↔ (𝑡 𝑠𝑠 𝑟)))
56 breq2 5066 . . . . . . . . . . 11 (𝑐 = 𝑟 → (𝑡 𝑐𝑡 𝑟))
5755, 56imbi12d 346 . . . . . . . . . 10 (𝑐 = 𝑟 → (((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐) ↔ ((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟)))
5857spv 2407 . . . . . . . . 9 (∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐) → ((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟))
59 pm3.3 449 . . . . . . . . . . . . 13 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (𝑡 𝑠 → (𝑠 𝑟𝑡 𝑟)))
6059adantld 491 . . . . . . . . . . . 12 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → ((𝑠 𝑡𝑡 𝑠) → (𝑠 𝑟𝑡 𝑟)))
6160com23 86 . . . . . . . . . . 11 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (𝑠 𝑟 → ((𝑠 𝑡𝑡 𝑠) → 𝑡 𝑟)))
6261adantld 491 . . . . . . . . . 10 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → ((𝑟 𝑠𝑠 𝑟) → ((𝑠 𝑡𝑡 𝑠) → 𝑡 𝑟)))
6362impd 411 . . . . . . . . 9 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑡 𝑟))
6448, 53, 58, 634syl 19 . . . . . . . 8 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑡 𝑟))
6542, 64jcad 513 . . . . . . 7 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → (𝑟 𝑡𝑡 𝑟)))
66 brin 5114 . . . . . . . 8 (𝑟( )𝑡 ↔ (𝑟 𝑡𝑟 𝑡))
678, 14brcnv 5751 . . . . . . . . 9 (𝑟 𝑡𝑡 𝑟)
6867anbi2i 622 . . . . . . . 8 ((𝑟 𝑡𝑟 𝑡) ↔ (𝑟 𝑡𝑡 𝑟))
6966, 68bitr2i 277 . . . . . . 7 ((𝑟 𝑡𝑡 𝑟) ↔ 𝑟( )𝑡)
7065, 69syl6ib 252 . . . . . 6 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟( )𝑡))
7118, 70syl5bi 243 . . . . 5 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡))
729, 8brcnv 5751 . . . . . . . . 9 (𝑠 𝑟𝑟 𝑠)
7372bicomi 225 . . . . . . . 8 (𝑟 𝑠𝑠 𝑟)
7473, 10anbi12ci 627 . . . . . . 7 ((𝑟 𝑠𝑟 𝑠) ↔ (𝑠 𝑟𝑠 𝑟))
75 brin 5114 . . . . . . 7 (𝑠( )𝑟 ↔ (𝑠 𝑟𝑠 𝑟))
7674, 7, 753bitr4i 304 . . . . . 6 (𝑟( )𝑠𝑠( )𝑟)
7776biimpi 217 . . . . 5 (𝑟( )𝑠𝑠( )𝑟)
7871, 77jctil 520 . . . 4 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
7978alrimiv 1921 . . 3 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
8079alrimivv 1922 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑟𝑠𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
81 dfer2 8283 . 2 (( ) Er dom ( ) ↔ (Rel ( ) ∧ dom ( ) = dom ( ) ∧ ∀𝑟𝑠𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡))))
825, 6, 80, 81syl3anbrc 1337 1 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ( ) Er dom ( ))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 396  wal 1528   = wceq 1530  cin 3938  wss 3939   class class class wbr 5062  ccnv 5552  dom cdm 5553  Rel wrel 5558   Er wer 8279
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1789  ax-4 1803  ax-5 1904  ax-6 1963  ax-7 2008  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2152  ax-12 2167  ax-13 2385  ax-ext 2796  ax-sep 5199  ax-nul 5206  ax-pr 5325
This theorem depends on definitions:  df-bi 208  df-an 397  df-or 844  df-3an 1083  df-tru 1533  df-ex 1774  df-nf 1778  df-sb 2063  df-mo 2615  df-eu 2649  df-clab 2803  df-cleq 2817  df-clel 2897  df-nfc 2967  df-rab 3151  df-v 3501  df-dif 3942  df-un 3944  df-in 3946  df-ss 3955  df-nul 4295  df-if 4470  df-sn 4564  df-pr 4566  df-op 4570  df-br 5063  df-opab 5125  df-xp 5559  df-rel 5560  df-cnv 5561  df-co 5562  df-er 8282
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator