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

Theorem trer 30972
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  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  (  .<_  i^i  `'  .<_  )  Er  dom  (  .<_  i^i  `'  .<_  ) )
Distinct variable group:    a, b, c,  .<_

Proof of Theorem trer
Dummy variables  r 
s  t are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 inss2 3653 . . . 4  |-  (  .<_  i^i  `'  .<_  )  C_  `'  .<_
2 relcnv 5207 . . . 4  |-  Rel  `'  .<_
3 relss 4922 . . . 4  |-  ( ( 
.<_  i^i  `'  .<_  )  C_  `'  .<_  ->  ( Rel  `'  .<_  ->  Rel  (  .<_  i^i  `'  .<_  ) ) )
41, 2, 3mp2 9 . . 3  |-  Rel  (  .<_  i^i  `'  .<_  )
54a1i 11 . 2  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  Rel  (  .<_  i^i  `'  .<_  ) )
6 eqidd 2452 . 2  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  dom  (  .<_  i^i  `'  .<_  )  =  dom  (  .<_  i^i  `'  .<_  ) )
7 brin 4452 . . . . . . . 8  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  ( r  .<_  s  /\  r `'  .<_  s ) )
8 vex 3048 . . . . . . . . . 10  |-  r  e. 
_V
9 vex 3048 . . . . . . . . . 10  |-  s  e. 
_V
108, 9brcnv 5017 . . . . . . . . 9  |-  ( r `'  .<_  s  <->  s  .<_  r )
1110anbi2i 700 . . . . . . . 8  |-  ( ( r  .<_  s  /\  r `'  .<_  s )  <-> 
( r  .<_  s  /\  s  .<_  r ) )
127, 11bitri 253 . . . . . . 7  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  ( r  .<_  s  /\  s  .<_  r ) )
13 brin 4452 . . . . . . . 8  |-  ( s (  .<_  i^i  `'  .<_  ) t  <->  ( s  .<_  t  /\  s `'  .<_  t ) )
14 vex 3048 . . . . . . . . . 10  |-  t  e. 
_V
159, 14brcnv 5017 . . . . . . . . 9  |-  ( s `'  .<_  t  <->  t  .<_  s )
1615anbi2i 700 . . . . . . . 8  |-  ( ( s  .<_  t  /\  s `'  .<_  t )  <-> 
( s  .<_  t  /\  t  .<_  s ) )
1713, 16bitri 253 . . . . . . 7  |-  ( s (  .<_  i^i  `'  .<_  ) t  <->  ( s  .<_  t  /\  t  .<_  s ) )
1812, 17anbi12i 703 . . . . . 6  |-  ( ( r (  .<_  i^i  `'  .<_  ) s  /\  s
(  .<_  i^i  `'  .<_  ) t )  <->  ( (
r  .<_  s  /\  s  .<_  r )  /\  (
s  .<_  t  /\  t  .<_  s ) ) )
19 breq1 4405 . . . . . . . . . . . . 13  |-  ( a  =  r  ->  (
a  .<_  b  <->  r  .<_  b ) )
2019anbi1d 711 . . . . . . . . . . . 12  |-  ( a  =  r  ->  (
( a  .<_  b  /\  b  .<_  c )  <->  ( r  .<_  b  /\  b  .<_  c ) ) )
21 breq1 4405 . . . . . . . . . . . 12  |-  ( a  =  r  ->  (
a  .<_  c  <->  r  .<_  c ) )
2220, 21imbi12d 322 . . . . . . . . . . 11  |-  ( a  =  r  ->  (
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  <-> 
( ( r  .<_  b  /\  b  .<_  c )  ->  r  .<_  c ) ) )
23222albidv 1769 . . . . . . . . . 10  |-  ( a  =  r  ->  ( A. b A. c ( ( a  .<_  b  /\  b  .<_  c )  -> 
a  .<_  c )  <->  A. b A. c ( ( r 
.<_  b  /\  b  .<_  c )  ->  r  .<_  c ) ) )
2423spv 2104 . . . . . . . . 9  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  A. b A. c
( ( r  .<_  b  /\  b  .<_  c )  ->  r  .<_  c ) )
25 breq2 4406 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
r  .<_  b  <->  r  .<_  s ) )
26 breq1 4405 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
b  .<_  c  <->  s  .<_  c ) )
2725, 26anbi12d 717 . . . . . . . . . . . 12  |-  ( b  =  s  ->  (
( r  .<_  b  /\  b  .<_  c )  <->  ( r  .<_  s  /\  s  .<_  c ) ) )
2827imbi1d 319 . . . . . . . . . . 11  |-  ( b  =  s  ->  (
( ( r  .<_  b  /\  b  .<_  c )  ->  r  .<_  c )  <-> 
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c ) ) )
2928albidv 1767 . . . . . . . . . 10  |-  ( b  =  s  ->  ( A. c ( ( r 
.<_  b  /\  b  .<_  c )  ->  r  .<_  c )  <->  A. c
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c ) ) )
3029spv 2104 . . . . . . . . 9  |-  ( A. b A. c ( ( r  .<_  b  /\  b  .<_  c )  -> 
r  .<_  c )  ->  A. c ( ( r 
.<_  s  /\  s  .<_  c )  ->  r  .<_  c ) )
31 breq2 4406 . . . . . . . . . . . 12  |-  ( c  =  t  ->  (
s  .<_  c  <->  s  .<_  t ) )
3231anbi2d 710 . . . . . . . . . . 11  |-  ( c  =  t  ->  (
( r  .<_  s  /\  s  .<_  c )  <->  ( r  .<_  s  /\  s  .<_  t ) ) )
33 breq2 4406 . . . . . . . . . . 11  |-  ( c  =  t  ->  (
r  .<_  c  <->  r  .<_  t ) )
3432, 33imbi12d 322 . . . . . . . . . 10  |-  ( c  =  t  ->  (
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c )  <-> 
( ( r  .<_  s  /\  s  .<_  t )  ->  r  .<_  t ) ) )
3534spv 2104 . . . . . . . . 9  |-  ( A. c ( ( r 
.<_  s  /\  s  .<_  c )  ->  r  .<_  c )  ->  (
( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t ) )
36 pm3.3 446 . . . . . . . . . . . . . 14  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( r  .<_  s  -> 
( s  .<_  t  -> 
r  .<_  t ) ) )
3736com23 81 . . . . . . . . . . . . 13  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( s  .<_  t  -> 
( r  .<_  s  -> 
r  .<_  t ) ) )
3837adantrd 470 . . . . . . . . . . . 12  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  ( r  .<_  s  ->  r  .<_  t ) ) )
3938com23 81 . . . . . . . . . . 11  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( r  .<_  s  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  r  .<_  t ) ) )
4039adantrd 470 . . . . . . . . . 10  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( ( r  .<_  s  /\  s  .<_  r )  ->  ( ( s 
.<_  t  /\  t  .<_  s )  ->  r  .<_  t ) ) )
4140impd 433 . . . . . . . . 9  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( ( ( r 
.<_  s  /\  s  .<_  r )  /\  (
s  .<_  t  /\  t  .<_  s ) )  -> 
r  .<_  t ) )
4224, 30, 35, 414syl 19 . . . . . . . 8  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  ( ( ( r  .<_  s  /\  s  .<_  r )  /\  ( s  .<_  t  /\  t  .<_  s ) )  ->  r  .<_  t ) )
43 breq1 4405 . . . . . . . . . . . . 13  |-  ( a  =  t  ->  (
a  .<_  b  <->  t  .<_  b ) )
4443anbi1d 711 . . . . . . . . . . . 12  |-  ( a  =  t  ->  (
( a  .<_  b  /\  b  .<_  c )  <->  ( t  .<_  b  /\  b  .<_  c ) ) )
45 breq1 4405 . . . . . . . . . . . 12  |-  ( a  =  t  ->  (
a  .<_  c  <->  t  .<_  c ) )
4644, 45imbi12d 322 . . . . . . . . . . 11  |-  ( a  =  t  ->  (
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  <-> 
( ( t  .<_  b  /\  b  .<_  c )  ->  t  .<_  c ) ) )
47462albidv 1769 . . . . . . . . . 10  |-  ( a  =  t  ->  ( A. b A. c ( ( a  .<_  b  /\  b  .<_  c )  -> 
a  .<_  c )  <->  A. b A. c ( ( t 
.<_  b  /\  b  .<_  c )  ->  t  .<_  c ) ) )
4847spv 2104 . . . . . . . . 9  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  A. b A. c
( ( t  .<_  b  /\  b  .<_  c )  ->  t  .<_  c ) )
49 breq2 4406 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
t  .<_  b  <->  t  .<_  s ) )
5049, 26anbi12d 717 . . . . . . . . . . . 12  |-  ( b  =  s  ->  (
( t  .<_  b  /\  b  .<_  c )  <->  ( t  .<_  s  /\  s  .<_  c ) ) )
5150imbi1d 319 . . . . . . . . . . 11  |-  ( b  =  s  ->  (
( ( t  .<_  b  /\  b  .<_  c )  ->  t  .<_  c )  <-> 
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c ) ) )
5251albidv 1767 . . . . . . . . . 10  |-  ( b  =  s  ->  ( A. c ( ( t 
.<_  b  /\  b  .<_  c )  ->  t  .<_  c )  <->  A. c
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c ) ) )
5352spv 2104 . . . . . . . . 9  |-  ( A. b A. c ( ( t  .<_  b  /\  b  .<_  c )  -> 
t  .<_  c )  ->  A. c ( ( t 
.<_  s  /\  s  .<_  c )  ->  t  .<_  c ) )
54 breq2 4406 . . . . . . . . . . . 12  |-  ( c  =  r  ->  (
s  .<_  c  <->  s  .<_  r ) )
5554anbi2d 710 . . . . . . . . . . 11  |-  ( c  =  r  ->  (
( t  .<_  s  /\  s  .<_  c )  <->  ( t  .<_  s  /\  s  .<_  r ) ) )
56 breq2 4406 . . . . . . . . . . 11  |-  ( c  =  r  ->  (
t  .<_  c  <->  t  .<_  r ) )
5755, 56imbi12d 322 . . . . . . . . . 10  |-  ( c  =  r  ->  (
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c )  <-> 
( ( t  .<_  s  /\  s  .<_  r )  ->  t  .<_  r ) ) )
5857spv 2104 . . . . . . . . 9  |-  ( A. c ( ( t 
.<_  s  /\  s  .<_  c )  ->  t  .<_  c )  ->  (
( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r ) )
59 pm3.3 446 . . . . . . . . . . . . 13  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( t  .<_  s  -> 
( s  .<_  r  -> 
t  .<_  r ) ) )
6059adantld 469 . . . . . . . . . . . 12  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  ( s  .<_  r  ->  t  .<_  r ) ) )
6160com23 81 . . . . . . . . . . 11  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( s  .<_  r  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  t  .<_  r ) ) )
6261adantld 469 . . . . . . . . . 10  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( ( r  .<_  s  /\  s  .<_  r )  ->  ( ( s 
.<_  t  /\  t  .<_  s )  ->  t  .<_  r ) ) )
6362impd 433 . . . . . . . . 9  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( ( ( r 
.<_  s  /\  s  .<_  r )  /\  (
s  .<_  t  /\  t  .<_  s ) )  -> 
t  .<_  r ) )
6448, 53, 58, 634syl 19 . . . . . . . 8  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  ( ( ( r  .<_  s  /\  s  .<_  r )  /\  ( s  .<_  t  /\  t  .<_  s ) )  ->  t  .<_  r ) )
6542, 64jcad 536 . . . . . . 7  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  ( ( ( r  .<_  s  /\  s  .<_  r )  /\  ( s  .<_  t  /\  t  .<_  s ) )  ->  ( r  .<_  t  /\  t  .<_  r ) ) )
66 brin 4452 . . . . . . . 8  |-  ( r (  .<_  i^i  `'  .<_  ) t  <->  ( r  .<_  t  /\  r `'  .<_  t ) )
678, 14brcnv 5017 . . . . . . . . 9  |-  ( r `'  .<_  t  <->  t  .<_  r )
6867anbi2i 700 . . . . . . . 8  |-  ( ( r  .<_  t  /\  r `'  .<_  t )  <-> 
( r  .<_  t  /\  t  .<_  r ) )
6966, 68bitr2i 254 . . . . . . 7  |-  ( ( r  .<_  t  /\  t  .<_  r )  <->  r (  .<_  i^i  `'  .<_  ) t )
7065, 69syl6ib 230 . . . . . 6  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  ( ( ( r  .<_  s  /\  s  .<_  r )  /\  ( s  .<_  t  /\  t  .<_  s ) )  ->  r (  .<_  i^i  `'  .<_  ) t ) )
7118, 70syl5bi 221 . . . . 5  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  ( ( r (  .<_  i^i  `'  .<_  ) s  /\  s ( 
.<_  i^i  `'  .<_  ) t )  ->  r (  .<_  i^i  `'  .<_  ) t ) )
729, 8brcnv 5017 . . . . . . . . 9  |-  ( s `'  .<_  r  <->  r  .<_  s )
7372bicomi 206 . . . . . . . 8  |-  ( r 
.<_  s  <->  s `'  .<_  r )
7473, 10anbi12ci 704 . . . . . . 7  |-  ( ( r  .<_  s  /\  r `'  .<_  s )  <-> 
( s  .<_  r  /\  s `'  .<_  r ) )
75 brin 4452 . . . . . . 7  |-  ( s (  .<_  i^i  `'  .<_  ) r  <->  ( s  .<_  r  /\  s `'  .<_  r ) )
7674, 7, 753bitr4i 281 . . . . . 6  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  s (  .<_  i^i  `'  .<_  ) r )
7776biimpi 198 . . . . 5  |-  ( r (  .<_  i^i  `'  .<_  ) s  ->  s (  .<_  i^i  `'  .<_  ) r )
7871, 77jctil 540 . . . 4  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  ( ( r (  .<_  i^i  `'  .<_  ) s  ->  s (  .<_  i^i  `'  .<_  ) r )  /\  ( ( r (  .<_  i^i  `'  .<_  ) s  /\  s
(  .<_  i^i  `'  .<_  ) t )  ->  r
(  .<_  i^i  `'  .<_  ) t ) ) )
7978alrimiv 1773 . . 3  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  A. t ( ( r (  .<_  i^i  `'  .<_  ) s  ->  s
(  .<_  i^i  `'  .<_  ) r )  /\  (
( r (  .<_  i^i  `'  .<_  ) s  /\  s (  .<_  i^i  `'  .<_  ) t )  -> 
r (  .<_  i^i  `'  .<_  ) t ) ) )
8079alrimivv 1774 . 2  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  A. r A. s A. t ( ( r (  .<_  i^i  `'  .<_  ) s  ->  s (  .<_  i^i  `'  .<_  ) r )  /\  ( ( r (  .<_  i^i  `'  .<_  ) s  /\  s
(  .<_  i^i  `'  .<_  ) t )  ->  r
(  .<_  i^i  `'  .<_  ) t ) ) )
81 dfer2 7364 . 2  |-  ( ( 
.<_  i^i  `'  .<_  )  Er 
dom  (  .<_  i^i  `'  .<_  )  <->  ( Rel  (  .<_  i^i  `'  .<_  )  /\  dom  (  .<_  i^i  `'  .<_  )  =  dom  (  .<_  i^i  `'  .<_  )  /\  A. r A. s A. t ( ( r (  .<_  i^i  `'  .<_  ) s  ->  s (  .<_  i^i  `'  .<_  ) r )  /\  ( ( r (  .<_  i^i  `'  .<_  ) s  /\  s
(  .<_  i^i  `'  .<_  ) t )  ->  r
(  .<_  i^i  `'  .<_  ) t ) ) ) )
825, 6, 80, 81syl3anbrc 1192 1  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  (  .<_  i^i  `'  .<_  )  Er  dom  (  .<_  i^i  `'  .<_  ) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    /\ wa 371   A.wal 1442    = wceq 1444    i^i cin 3403    C_ wss 3404   class class class wbr 4402   `'ccnv 4833   dom cdm 4834   Rel wrel 4839    Er wer 7360
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1669  ax-4 1682  ax-5 1758  ax-6 1805  ax-7 1851  ax-9 1896  ax-10 1915  ax-11 1920  ax-12 1933  ax-13 2091  ax-ext 2431  ax-sep 4525  ax-nul 4534  ax-pr 4639
This theorem depends on definitions:  df-bi 189  df-or 372  df-an 373  df-3an 987  df-tru 1447  df-ex 1664  df-nf 1668  df-sb 1798  df-eu 2303  df-mo 2304  df-clab 2438  df-cleq 2444  df-clel 2447  df-nfc 2581  df-ne 2624  df-ral 2742  df-rex 2743  df-rab 2746  df-v 3047  df-dif 3407  df-un 3409  df-in 3411  df-ss 3418  df-nul 3732  df-if 3882  df-sn 3969  df-pr 3971  df-op 3975  df-br 4403  df-opab 4462  df-xp 4840  df-rel 4841  df-cnv 4842  df-co 4843  df-er 7363
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator