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

Theorem trer 26300
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 3554 . . . 4  |-  (  .<_  i^i  `'  .<_  )  C_  `'  .<_
2 relcnv 5234 . . . 4  |-  Rel  `'  .<_
3 relss 4955 . . . 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 2436 . 2  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  dom  (  .<_  i^i  `'  .<_  )  =  dom  (  .<_  i^i  `'  .<_  ) )
7 brin 4251 . . . . . . . 8  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  ( r  .<_  s  /\  r `'  .<_  s ) )
8 vex 2951 . . . . . . . . . 10  |-  r  e. 
_V
9 vex 2951 . . . . . . . . . 10  |-  s  e. 
_V
108, 9brcnv 5047 . . . . . . . . 9  |-  ( r `'  .<_  s  <->  s  .<_  r )
1110anbi2i 676 . . . . . . . 8  |-  ( ( r  .<_  s  /\  r `'  .<_  s )  <-> 
( r  .<_  s  /\  s  .<_  r ) )
127, 11bitri 241 . . . . . . 7  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  ( r  .<_  s  /\  s  .<_  r ) )
13 brin 4251 . . . . . . . 8  |-  ( s (  .<_  i^i  `'  .<_  ) t  <->  ( s  .<_  t  /\  s `'  .<_  t ) )
14 vex 2951 . . . . . . . . . 10  |-  t  e. 
_V
159, 14brcnv 5047 . . . . . . . . 9  |-  ( s `'  .<_  t  <->  t  .<_  s )
1615anbi2i 676 . . . . . . . 8  |-  ( ( s  .<_  t  /\  s `'  .<_  t )  <-> 
( s  .<_  t  /\  t  .<_  s ) )
1713, 16bitri 241 . . . . . . 7  |-  ( s (  .<_  i^i  `'  .<_  ) t  <->  ( s  .<_  t  /\  t  .<_  s ) )
1812, 17anbi12i 679 . . . . . 6  |-  ( ( r (  .<_  i^i  `'  .<_  ) s  /\  s
(  .<_  i^i  `'  .<_  ) t )  <->  ( (
r  .<_  s  /\  s  .<_  r )  /\  (
s  .<_  t  /\  t  .<_  s ) ) )
19 breq1 4207 . . . . . . . . . . . . 13  |-  ( a  =  r  ->  (
a  .<_  b  <->  r  .<_  b ) )
2019anbi1d 686 . . . . . . . . . . . 12  |-  ( a  =  r  ->  (
( a  .<_  b  /\  b  .<_  c )  <->  ( r  .<_  b  /\  b  .<_  c ) ) )
21 breq1 4207 . . . . . . . . . . . 12  |-  ( a  =  r  ->  (
a  .<_  c  <->  r  .<_  c ) )
2220, 21imbi12d 312 . . . . . . . . . . 11  |-  ( a  =  r  ->  (
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  <-> 
( ( r  .<_  b  /\  b  .<_  c )  ->  r  .<_  c ) ) )
23222albidv 1637 . . . . . . . . . 10  |-  ( a  =  r  ->  ( A. b A. c ( ( a  .<_  b  /\  b  .<_  c )  -> 
a  .<_  c )  <->  A. b A. c ( ( r 
.<_  b  /\  b  .<_  c )  ->  r  .<_  c ) ) )
2423spv 1965 . . . . . . . . 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 4208 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
r  .<_  b  <->  r  .<_  s ) )
26 breq1 4207 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
b  .<_  c  <->  s  .<_  c ) )
2725, 26anbi12d 692 . . . . . . . . . . . 12  |-  ( b  =  s  ->  (
( r  .<_  b  /\  b  .<_  c )  <->  ( r  .<_  s  /\  s  .<_  c ) ) )
2827imbi1d 309 . . . . . . . . . . 11  |-  ( b  =  s  ->  (
( ( r  .<_  b  /\  b  .<_  c )  ->  r  .<_  c )  <-> 
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c ) ) )
2928albidv 1635 . . . . . . . . . 10  |-  ( b  =  s  ->  ( A. c ( ( r 
.<_  b  /\  b  .<_  c )  ->  r  .<_  c )  <->  A. c
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c ) ) )
3029spv 1965 . . . . . . . . 9  |-  ( A. b A. c ( ( r  .<_  b  /\  b  .<_  c )  -> 
r  .<_  c )  ->  A. c ( ( r 
.<_  s  /\  s  .<_  c )  ->  r  .<_  c ) )
31 breq2 4208 . . . . . . . . . . . . 13  |-  ( c  =  t  ->  (
s  .<_  c  <->  s  .<_  t ) )
3231anbi2d 685 . . . . . . . . . . . 12  |-  ( c  =  t  ->  (
( r  .<_  s  /\  s  .<_  c )  <->  ( r  .<_  s  /\  s  .<_  t ) ) )
33 breq2 4208 . . . . . . . . . . . 12  |-  ( c  =  t  ->  (
r  .<_  c  <->  r  .<_  t ) )
3432, 33imbi12d 312 . . . . . . . . . . 11  |-  ( c  =  t  ->  (
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c )  <-> 
( ( r  .<_  s  /\  s  .<_  t )  ->  r  .<_  t ) ) )
3534spv 1965 . . . . . . . . . 10  |-  ( A. c ( ( r 
.<_  s  /\  s  .<_  c )  ->  r  .<_  c )  ->  (
( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t ) )
36 pm3.3 432 . . . . . . . . . . . . . . 15  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( r  .<_  s  -> 
( s  .<_  t  -> 
r  .<_  t ) ) )
3736com23 74 . . . . . . . . . . . . . 14  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( s  .<_  t  -> 
( r  .<_  s  -> 
r  .<_  t ) ) )
3837adantrd 455 . . . . . . . . . . . . 13  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  ( r  .<_  s  ->  r  .<_  t ) ) )
3938com23 74 . . . . . . . . . . . 12  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( r  .<_  s  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  r  .<_  t ) ) )
4039adantrd 455 . . . . . . . . . . 11  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( ( r  .<_  s  /\  s  .<_  r )  ->  ( ( s 
.<_  t  /\  t  .<_  s )  ->  r  .<_  t ) ) )
4140imp3a 421 . . . . . . . . . 10  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( ( ( r 
.<_  s  /\  s  .<_  r )  /\  (
s  .<_  t  /\  t  .<_  s ) )  -> 
r  .<_  t ) )
4235, 41syl 16 . . . . . . . . 9  |-  ( A. c ( ( r 
.<_  s  /\  s  .<_  c )  ->  r  .<_  c )  ->  (
( ( r  .<_  s  /\  s  .<_  r )  /\  ( s  .<_  t  /\  t  .<_  s ) )  ->  r  .<_  t ) )
4324, 30, 423syl 19 . . . . . . . 8  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  ( ( ( r  .<_  s  /\  s  .<_  r )  /\  ( s  .<_  t  /\  t  .<_  s ) )  ->  r  .<_  t ) )
44 breq1 4207 . . . . . . . . . . . . 13  |-  ( a  =  t  ->  (
a  .<_  b  <->  t  .<_  b ) )
4544anbi1d 686 . . . . . . . . . . . 12  |-  ( a  =  t  ->  (
( a  .<_  b  /\  b  .<_  c )  <->  ( t  .<_  b  /\  b  .<_  c ) ) )
46 breq1 4207 . . . . . . . . . . . 12  |-  ( a  =  t  ->  (
a  .<_  c  <->  t  .<_  c ) )
4745, 46imbi12d 312 . . . . . . . . . . 11  |-  ( a  =  t  ->  (
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  <-> 
( ( t  .<_  b  /\  b  .<_  c )  ->  t  .<_  c ) ) )
48472albidv 1637 . . . . . . . . . 10  |-  ( a  =  t  ->  ( A. b A. c ( ( a  .<_  b  /\  b  .<_  c )  -> 
a  .<_  c )  <->  A. b A. c ( ( t 
.<_  b  /\  b  .<_  c )  ->  t  .<_  c ) ) )
4948spv 1965 . . . . . . . . 9  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  A. b A. c
( ( t  .<_  b  /\  b  .<_  c )  ->  t  .<_  c ) )
50 breq2 4208 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
t  .<_  b  <->  t  .<_  s ) )
5150, 26anbi12d 692 . . . . . . . . . . . 12  |-  ( b  =  s  ->  (
( t  .<_  b  /\  b  .<_  c )  <->  ( t  .<_  s  /\  s  .<_  c ) ) )
5251imbi1d 309 . . . . . . . . . . 11  |-  ( b  =  s  ->  (
( ( t  .<_  b  /\  b  .<_  c )  ->  t  .<_  c )  <-> 
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c ) ) )
5352albidv 1635 . . . . . . . . . 10  |-  ( b  =  s  ->  ( A. c ( ( t 
.<_  b  /\  b  .<_  c )  ->  t  .<_  c )  <->  A. c
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c ) ) )
5453spv 1965 . . . . . . . . 9  |-  ( A. b A. c ( ( t  .<_  b  /\  b  .<_  c )  -> 
t  .<_  c )  ->  A. c ( ( t 
.<_  s  /\  s  .<_  c )  ->  t  .<_  c ) )
55 breq2 4208 . . . . . . . . . . . . 13  |-  ( c  =  r  ->  (
s  .<_  c  <->  s  .<_  r ) )
5655anbi2d 685 . . . . . . . . . . . 12  |-  ( c  =  r  ->  (
( t  .<_  s  /\  s  .<_  c )  <->  ( t  .<_  s  /\  s  .<_  r ) ) )
57 breq2 4208 . . . . . . . . . . . 12  |-  ( c  =  r  ->  (
t  .<_  c  <->  t  .<_  r ) )
5856, 57imbi12d 312 . . . . . . . . . . 11  |-  ( c  =  r  ->  (
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c )  <-> 
( ( t  .<_  s  /\  s  .<_  r )  ->  t  .<_  r ) ) )
5958spv 1965 . . . . . . . . . 10  |-  ( A. c ( ( t 
.<_  s  /\  s  .<_  c )  ->  t  .<_  c )  ->  (
( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r ) )
60 pm3.3 432 . . . . . . . . . . . . . 14  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( t  .<_  s  -> 
( s  .<_  r  -> 
t  .<_  r ) ) )
6160adantld 454 . . . . . . . . . . . . 13  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  ( s  .<_  r  ->  t  .<_  r ) ) )
6261com23 74 . . . . . . . . . . . 12  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( s  .<_  r  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  t  .<_  r ) ) )
6362adantld 454 . . . . . . . . . . 11  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( ( r  .<_  s  /\  s  .<_  r )  ->  ( ( s 
.<_  t  /\  t  .<_  s )  ->  t  .<_  r ) ) )
6463imp3a 421 . . . . . . . . . 10  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( ( ( r 
.<_  s  /\  s  .<_  r )  /\  (
s  .<_  t  /\  t  .<_  s ) )  -> 
t  .<_  r ) )
6559, 64syl 16 . . . . . . . . 9  |-  ( A. c ( ( t 
.<_  s  /\  s  .<_  c )  ->  t  .<_  c )  ->  (
( ( r  .<_  s  /\  s  .<_  r )  /\  ( s  .<_  t  /\  t  .<_  s ) )  ->  t  .<_  r ) )
6649, 54, 653syl 19 . . . . . . . 8  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  ( ( ( r  .<_  s  /\  s  .<_  r )  /\  ( s  .<_  t  /\  t  .<_  s ) )  ->  t  .<_  r ) )
6743, 66jcad 520 . . . . . . 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 ) ) )
68 brin 4251 . . . . . . . 8  |-  ( r (  .<_  i^i  `'  .<_  ) t  <->  ( r  .<_  t  /\  r `'  .<_  t ) )
698, 14brcnv 5047 . . . . . . . . 9  |-  ( r `'  .<_  t  <->  t  .<_  r )
7069anbi2i 676 . . . . . . . 8  |-  ( ( r  .<_  t  /\  r `'  .<_  t )  <-> 
( r  .<_  t  /\  t  .<_  r ) )
7168, 70bitr2i 242 . . . . . . 7  |-  ( ( r  .<_  t  /\  t  .<_  r )  <->  r (  .<_  i^i  `'  .<_  ) t )
7267, 71syl6ib 218 . . . . . 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 ) )
7318, 72syl5bi 209 . . . . 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 ) )
749, 8brcnv 5047 . . . . . . . . 9  |-  ( s `'  .<_  r  <->  r  .<_  s )
7574bicomi 194 . . . . . . . 8  |-  ( r 
.<_  s  <->  s `'  .<_  r )
7675, 10anbi12ci 680 . . . . . . 7  |-  ( ( r  .<_  s  /\  r `'  .<_  s )  <-> 
( s  .<_  r  /\  s `'  .<_  r ) )
77 brin 4251 . . . . . . 7  |-  ( s (  .<_  i^i  `'  .<_  ) r  <->  ( s  .<_  r  /\  s `'  .<_  r ) )
7876, 7, 773bitr4i 269 . . . . . 6  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  s (  .<_  i^i  `'  .<_  ) r )
7978biimpi 187 . . . . 5  |-  ( r (  .<_  i^i  `'  .<_  ) s  ->  s (  .<_  i^i  `'  .<_  ) r )
8073, 79jctil 524 . . . 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 ) ) )
8180alrimiv 1641 . . 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 ) ) )
8281alrimivv 1642 . 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 ) ) )
83 dfer2 6898 . 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 ) ) ) )
845, 6, 82, 83syl3anbrc 1138 1  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  (  .<_  i^i  `'  .<_  )  Er  dom  (  .<_  i^i  `'  .<_  ) )
Colors of variables: wff set class
Syntax hints:    -> wi 4    /\ wa 359   A.wal 1549    = wceq 1652    i^i cin 3311    C_ wss 3312   class class class wbr 4204   `'ccnv 4869   dom cdm 4870   Rel wrel 4875    Er wer 6894
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1555  ax-5 1566  ax-17 1626  ax-9 1666  ax-8 1687  ax-14 1729  ax-6 1744  ax-7 1749  ax-11 1761  ax-12 1950  ax-ext 2416  ax-sep 4322  ax-nul 4330  ax-pr 4395
This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3an 938  df-tru 1328  df-ex 1551  df-nf 1554  df-sb 1659  df-eu 2284  df-mo 2285  df-clab 2422  df-cleq 2428  df-clel 2431  df-nfc 2560  df-ne 2600  df-ral 2702  df-rex 2703  df-rab 2706  df-v 2950  df-dif 3315  df-un 3317  df-in 3319  df-ss 3326  df-nul 3621  df-if 3732  df-sn 3812  df-pr 3813  df-op 3815  df-br 4205  df-opab 4259  df-xp 4876  df-rel 4877  df-cnv 4878  df-co 4879  df-er 6897
  Copyright terms: Public domain W3C validator