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

Theorem trer 26003
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 3498 . . . 4  |-  (  .<_  i^i  `'  .<_  )  C_  `'  .<_
2 relcnv 5175 . . . 4  |-  Rel  `'  .<_
3 relss 4896 . . . 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 2381 . 2  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  dom  (  .<_  i^i  `'  .<_  )  =  dom  (  .<_  i^i  `'  .<_  ) )
7 brin 4193 . . . . . . . 8  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  ( r  .<_  s  /\  r `'  .<_  s ) )
8 vex 2895 . . . . . . . . . 10  |-  r  e. 
_V
9 vex 2895 . . . . . . . . . 10  |-  s  e. 
_V
108, 9brcnv 4988 . . . . . . . . 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 4193 . . . . . . . 8  |-  ( s (  .<_  i^i  `'  .<_  ) t  <->  ( s  .<_  t  /\  s `'  .<_  t ) )
14 vex 2895 . . . . . . . . . 10  |-  t  e. 
_V
159, 14brcnv 4988 . . . . . . . . 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 4149 . . . . . . . . . . . . 13  |-  ( a  =  r  ->  (
a  .<_  b  <->  r  .<_  b ) )
2019anbi1d 686 . . . . . . . . . . . 12  |-  ( a  =  r  ->  (
( a  .<_  b  /\  b  .<_  c )  <->  ( r  .<_  b  /\  b  .<_  c ) ) )
21 breq1 4149 . . . . . . . . . . . 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 1634 . . . . . . . . . 10  |-  ( a  =  r  ->  ( A. b A. c ( ( a  .<_  b  /\  b  .<_  c )  -> 
a  .<_  c )  <->  A. b A. c ( ( r 
.<_  b  /\  b  .<_  c )  ->  r  .<_  c ) ) )
2423spv 2024 . . . . . . . . 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 4150 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
r  .<_  b  <->  r  .<_  s ) )
26 breq1 4149 . . . . . . . . . . . . 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 1632 . . . . . . . . . 10  |-  ( b  =  s  ->  ( A. c ( ( r 
.<_  b  /\  b  .<_  c )  ->  r  .<_  c )  <->  A. c
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c ) ) )
3029spv 2024 . . . . . . . . 9  |-  ( A. b A. c ( ( r  .<_  b  /\  b  .<_  c )  -> 
r  .<_  c )  ->  A. c ( ( r 
.<_  s  /\  s  .<_  c )  ->  r  .<_  c ) )
31 breq2 4150 . . . . . . . . . . . . 13  |-  ( c  =  t  ->  (
s  .<_  c  <->  s  .<_  t ) )
3231anbi2d 685 . . . . . . . . . . . 12  |-  ( c  =  t  ->  (
( r  .<_  s  /\  s  .<_  c )  <->  ( r  .<_  s  /\  s  .<_  t ) ) )
33 breq2 4150 . . . . . . . . . . . 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 2024 . . . . . . . . . 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 4149 . . . . . . . . . . . . 13  |-  ( a  =  t  ->  (
a  .<_  b  <->  t  .<_  b ) )
4544anbi1d 686 . . . . . . . . . . . 12  |-  ( a  =  t  ->  (
( a  .<_  b  /\  b  .<_  c )  <->  ( t  .<_  b  /\  b  .<_  c ) ) )
46 breq1 4149 . . . . . . . . . . . 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 1634 . . . . . . . . . 10  |-  ( a  =  t  ->  ( A. b A. c ( ( a  .<_  b  /\  b  .<_  c )  -> 
a  .<_  c )  <->  A. b A. c ( ( t 
.<_  b  /\  b  .<_  c )  ->  t  .<_  c ) ) )
4948spv 2024 . . . . . . . . 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 4150 . . . . . . . . . . . . 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 1632 . . . . . . . . . 10  |-  ( b  =  s  ->  ( A. c ( ( t 
.<_  b  /\  b  .<_  c )  ->  t  .<_  c )  <->  A. c
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c ) ) )
5453spv 2024 . . . . . . . . 9  |-  ( A. b A. c ( ( t  .<_  b  /\  b  .<_  c )  -> 
t  .<_  c )  ->  A. c ( ( t 
.<_  s  /\  s  .<_  c )  ->  t  .<_  c ) )
55 breq2 4150 . . . . . . . . . . . . 13  |-  ( c  =  r  ->  (
s  .<_  c  <->  s  .<_  r ) )
5655anbi2d 685 . . . . . . . . . . . 12  |-  ( c  =  r  ->  (
( t  .<_  s  /\  s  .<_  c )  <->  ( t  .<_  s  /\  s  .<_  r ) ) )
57 breq2 4150 . . . . . . . . . . . 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 2024 . . . . . . . . . 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 4193 . . . . . . . 8  |-  ( r (  .<_  i^i  `'  .<_  ) t  <->  ( r  .<_  t  /\  r `'  .<_  t ) )
698, 14brcnv 4988 . . . . . . . . 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 4988 . . . . . . . . 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 4193 . . . . . . 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 1638 . . 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 1639 . 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 6835 . 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 1546    = wceq 1649    i^i cin 3255    C_ wss 3256   class class class wbr 4146   `'ccnv 4810   dom cdm 4811   Rel wrel 4816    Er wer 6831
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1661  ax-8 1682  ax-14 1721  ax-6 1736  ax-7 1741  ax-11 1753  ax-12 1939  ax-ext 2361  ax-sep 4264  ax-nul 4272  ax-pr 4337
This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2235  df-mo 2236  df-clab 2367  df-cleq 2373  df-clel 2376  df-nfc 2505  df-ne 2545  df-ral 2647  df-rex 2648  df-rab 2651  df-v 2894  df-dif 3259  df-un 3261  df-in 3263  df-ss 3270  df-nul 3565  df-if 3676  df-sn 3756  df-pr 3757  df-op 3759  df-br 4147  df-opab 4201  df-xp 4817  df-rel 4818  df-cnv 4819  df-co 4820  df-er 6834
  Copyright terms: Public domain W3C validator