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

Theorem trer 31480
 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 3796 . . . 4 ( ) ⊆
2 relcnv 5422 . . . 4 Rel
3 relss 5129 . . . 4 (( ) ⊆ → (Rel → Rel ( )))
41, 2, 3mp2 9 . . 3 Rel ( )
54a1i 11 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → Rel ( ))
6 eqidd 2611 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → dom ( ) = dom ( ))
7 brin 4634 . . . . . . . 8 (𝑟( )𝑠 ↔ (𝑟 𝑠𝑟 𝑠))
8 vex 3176 . . . . . . . . . 10 𝑟 ∈ V
9 vex 3176 . . . . . . . . . 10 𝑠 ∈ V
108, 9brcnv 5227 . . . . . . . . 9 (𝑟 𝑠𝑠 𝑟)
1110anbi2i 726 . . . . . . . 8 ((𝑟 𝑠𝑟 𝑠) ↔ (𝑟 𝑠𝑠 𝑟))
127, 11bitri 263 . . . . . . 7 (𝑟( )𝑠 ↔ (𝑟 𝑠𝑠 𝑟))
13 brin 4634 . . . . . . . 8 (𝑠( )𝑡 ↔ (𝑠 𝑡𝑠 𝑡))
14 vex 3176 . . . . . . . . . 10 𝑡 ∈ V
159, 14brcnv 5227 . . . . . . . . 9 (𝑠 𝑡𝑡 𝑠)
1615anbi2i 726 . . . . . . . 8 ((𝑠 𝑡𝑠 𝑡) ↔ (𝑠 𝑡𝑡 𝑠))
1713, 16bitri 263 . . . . . . 7 (𝑠( )𝑡 ↔ (𝑠 𝑡𝑡 𝑠))
1812, 17anbi12i 729 . . . . . 6 ((𝑟( )𝑠𝑠( )𝑡) ↔ ((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)))
19 breq1 4586 . . . . . . . . . . . . 13 (𝑎 = 𝑟 → (𝑎 𝑏𝑟 𝑏))
2019anbi1d 737 . . . . . . . . . . . 12 (𝑎 = 𝑟 → ((𝑎 𝑏𝑏 𝑐) ↔ (𝑟 𝑏𝑏 𝑐)))
21 breq1 4586 . . . . . . . . . . . 12 (𝑎 = 𝑟 → (𝑎 𝑐𝑟 𝑐))
2220, 21imbi12d 333 . . . . . . . . . . 11 (𝑎 = 𝑟 → (((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐)))
23222albidv 1838 . . . . . . . . . 10 (𝑎 = 𝑟 → (∀𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐)))
2423spv 2248 . . . . . . . . 9 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐))
25 breq2 4587 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑟 𝑏𝑟 𝑠))
26 breq1 4586 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑏 𝑐𝑠 𝑐))
2725, 26anbi12d 743 . . . . . . . . . . . 12 (𝑏 = 𝑠 → ((𝑟 𝑏𝑏 𝑐) ↔ (𝑟 𝑠𝑠 𝑐)))
2827imbi1d 330 . . . . . . . . . . 11 (𝑏 = 𝑠 → (((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) ↔ ((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐)))
2928albidv 1836 . . . . . . . . . 10 (𝑏 = 𝑠 → (∀𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) ↔ ∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐)))
3029spv 2248 . . . . . . . . 9 (∀𝑏𝑐((𝑟 𝑏𝑏 𝑐) → 𝑟 𝑐) → ∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐))
31 breq2 4587 . . . . . . . . . . . 12 (𝑐 = 𝑡 → (𝑠 𝑐𝑠 𝑡))
3231anbi2d 736 . . . . . . . . . . 11 (𝑐 = 𝑡 → ((𝑟 𝑠𝑠 𝑐) ↔ (𝑟 𝑠𝑠 𝑡)))
33 breq2 4587 . . . . . . . . . . 11 (𝑐 = 𝑡 → (𝑟 𝑐𝑟 𝑡))
3432, 33imbi12d 333 . . . . . . . . . 10 (𝑐 = 𝑡 → (((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐) ↔ ((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡)))
3534spv 2248 . . . . . . . . 9 (∀𝑐((𝑟 𝑠𝑠 𝑐) → 𝑟 𝑐) → ((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡))
36 pm3.3 459 . . . . . . . . . . . . . 14 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑟 𝑠 → (𝑠 𝑡𝑟 𝑡)))
3736com23 84 . . . . . . . . . . . . 13 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑠 𝑡 → (𝑟 𝑠𝑟 𝑡)))
3837adantrd 483 . . . . . . . . . . . 12 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → ((𝑠 𝑡𝑡 𝑠) → (𝑟 𝑠𝑟 𝑡)))
3938com23 84 . . . . . . . . . . 11 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (𝑟 𝑠 → ((𝑠 𝑡𝑡 𝑠) → 𝑟 𝑡)))
4039adantrd 483 . . . . . . . . . 10 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → ((𝑟 𝑠𝑠 𝑟) → ((𝑠 𝑡𝑡 𝑠) → 𝑟 𝑡)))
4140impd 446 . . . . . . . . 9 (((𝑟 𝑠𝑠 𝑡) → 𝑟 𝑡) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟 𝑡))
4224, 30, 35, 414syl 19 . . . . . . . 8 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟 𝑡))
43 breq1 4586 . . . . . . . . . . . . 13 (𝑎 = 𝑡 → (𝑎 𝑏𝑡 𝑏))
4443anbi1d 737 . . . . . . . . . . . 12 (𝑎 = 𝑡 → ((𝑎 𝑏𝑏 𝑐) ↔ (𝑡 𝑏𝑏 𝑐)))
45 breq1 4586 . . . . . . . . . . . 12 (𝑎 = 𝑡 → (𝑎 𝑐𝑡 𝑐))
4644, 45imbi12d 333 . . . . . . . . . . 11 (𝑎 = 𝑡 → (((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐)))
47462albidv 1838 . . . . . . . . . 10 (𝑎 = 𝑡 → (∀𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) ↔ ∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐)))
4847spv 2248 . . . . . . . . 9 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐))
49 breq2 4587 . . . . . . . . . . . . 13 (𝑏 = 𝑠 → (𝑡 𝑏𝑡 𝑠))
5049, 26anbi12d 743 . . . . . . . . . . . 12 (𝑏 = 𝑠 → ((𝑡 𝑏𝑏 𝑐) ↔ (𝑡 𝑠𝑠 𝑐)))
5150imbi1d 330 . . . . . . . . . . 11 (𝑏 = 𝑠 → (((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) ↔ ((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐)))
5251albidv 1836 . . . . . . . . . 10 (𝑏 = 𝑠 → (∀𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) ↔ ∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐)))
5352spv 2248 . . . . . . . . 9 (∀𝑏𝑐((𝑡 𝑏𝑏 𝑐) → 𝑡 𝑐) → ∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐))
54 breq2 4587 . . . . . . . . . . . 12 (𝑐 = 𝑟 → (𝑠 𝑐𝑠 𝑟))
5554anbi2d 736 . . . . . . . . . . 11 (𝑐 = 𝑟 → ((𝑡 𝑠𝑠 𝑐) ↔ (𝑡 𝑠𝑠 𝑟)))
56 breq2 4587 . . . . . . . . . . 11 (𝑐 = 𝑟 → (𝑡 𝑐𝑡 𝑟))
5755, 56imbi12d 333 . . . . . . . . . 10 (𝑐 = 𝑟 → (((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐) ↔ ((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟)))
5857spv 2248 . . . . . . . . 9 (∀𝑐((𝑡 𝑠𝑠 𝑐) → 𝑡 𝑐) → ((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟))
59 pm3.3 459 . . . . . . . . . . . . 13 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (𝑡 𝑠 → (𝑠 𝑟𝑡 𝑟)))
6059adantld 482 . . . . . . . . . . . 12 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → ((𝑠 𝑡𝑡 𝑠) → (𝑠 𝑟𝑡 𝑟)))
6160com23 84 . . . . . . . . . . 11 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (𝑠 𝑟 → ((𝑠 𝑡𝑡 𝑠) → 𝑡 𝑟)))
6261adantld 482 . . . . . . . . . 10 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → ((𝑟 𝑠𝑠 𝑟) → ((𝑠 𝑡𝑡 𝑠) → 𝑡 𝑟)))
6362impd 446 . . . . . . . . 9 (((𝑡 𝑠𝑠 𝑟) → 𝑡 𝑟) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑡 𝑟))
6448, 53, 58, 634syl 19 . . . . . . . 8 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑡 𝑟))
6542, 64jcad 554 . . . . . . 7 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → (𝑟 𝑡𝑡 𝑟)))
66 brin 4634 . . . . . . . 8 (𝑟( )𝑡 ↔ (𝑟 𝑡𝑟 𝑡))
678, 14brcnv 5227 . . . . . . . . 9 (𝑟 𝑡𝑡 𝑟)
6867anbi2i 726 . . . . . . . 8 ((𝑟 𝑡𝑟 𝑡) ↔ (𝑟 𝑡𝑡 𝑟))
6966, 68bitr2i 264 . . . . . . 7 ((𝑟 𝑡𝑡 𝑟) ↔ 𝑟( )𝑡)
7065, 69syl6ib 240 . . . . . 6 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → (((𝑟 𝑠𝑠 𝑟) ∧ (𝑠 𝑡𝑡 𝑠)) → 𝑟( )𝑡))
7118, 70syl5bi 231 . . . . 5 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡))
729, 8brcnv 5227 . . . . . . . . 9 (𝑠 𝑟𝑟 𝑠)
7372bicomi 213 . . . . . . . 8 (𝑟 𝑠𝑠 𝑟)
7473, 10anbi12ci 730 . . . . . . 7 ((𝑟 𝑠𝑟 𝑠) ↔ (𝑠 𝑟𝑠 𝑟))
75 brin 4634 . . . . . . 7 (𝑠( )𝑟 ↔ (𝑠 𝑟𝑠 𝑟))
7674, 7, 753bitr4i 291 . . . . . 6 (𝑟( )𝑠𝑠( )𝑟)
7776biimpi 205 . . . . 5 (𝑟( )𝑠𝑠( )𝑟)
7871, 77jctil 558 . . . 4 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
7978alrimiv 1842 . . 3 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
8079alrimivv 1843 . 2 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ∀𝑟𝑠𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡)))
81 dfer2 7630 . 2 (( ) Er dom ( ) ↔ (Rel ( ) ∧ dom ( ) = dom ( ) ∧ ∀𝑟𝑠𝑡((𝑟( )𝑠𝑠( )𝑟) ∧ ((𝑟( )𝑠𝑠( )𝑡) → 𝑟( )𝑡))))
825, 6, 80, 81syl3anbrc 1239 1 (∀𝑎𝑏𝑐((𝑎 𝑏𝑏 𝑐) → 𝑎 𝑐) → ( ) Er dom ( ))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ∧ wa 383  ∀wal 1473   = wceq 1475   ∩ cin 3539   ⊆ wss 3540   class class class wbr 4583  ◡ccnv 5037  dom cdm 5038  Rel wrel 5043   Er wer 7626 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1713  ax-4 1728  ax-5 1827  ax-6 1875  ax-7 1922  ax-9 1986  ax-10 2006  ax-11 2021  ax-12 2034  ax-13 2234  ax-ext 2590  ax-sep 4709  ax-nul 4717  ax-pr 4833 This theorem depends on definitions:  df-bi 196  df-or 384  df-an 385  df-3an 1033  df-tru 1478  df-ex 1696  df-nf 1701  df-sb 1868  df-eu 2462  df-mo 2463  df-clab 2597  df-cleq 2603  df-clel 2606  df-nfc 2740  df-rab 2905  df-v 3175  df-dif 3543  df-un 3545  df-in 3547  df-ss 3554  df-nul 3875  df-if 4037  df-sn 4126  df-pr 4128  df-op 4132  df-br 4584  df-opab 4644  df-xp 5044  df-rel 5045  df-cnv 5046  df-co 5047  df-er 7629 This theorem is referenced by: (None)
 Copyright terms: Public domain W3C validator