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

Theorem trer 28511
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 3571 . . . 4  |-  (  .<_  i^i  `'  .<_  )  C_  `'  .<_
2 relcnv 5206 . . . 4  |-  Rel  `'  .<_
3 relss 4927 . . . 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 2444 . 2  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  dom  (  .<_  i^i  `'  .<_  )  =  dom  (  .<_  i^i  `'  .<_  ) )
7 brin 4341 . . . . . . . 8  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  ( r  .<_  s  /\  r `'  .<_  s ) )
8 vex 2975 . . . . . . . . . 10  |-  r  e. 
_V
9 vex 2975 . . . . . . . . . 10  |-  s  e. 
_V
108, 9brcnv 5022 . . . . . . . . 9  |-  ( r `'  .<_  s  <->  s  .<_  r )
1110anbi2i 694 . . . . . . . 8  |-  ( ( r  .<_  s  /\  r `'  .<_  s )  <-> 
( r  .<_  s  /\  s  .<_  r ) )
127, 11bitri 249 . . . . . . 7  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  ( r  .<_  s  /\  s  .<_  r ) )
13 brin 4341 . . . . . . . 8  |-  ( s (  .<_  i^i  `'  .<_  ) t  <->  ( s  .<_  t  /\  s `'  .<_  t ) )
14 vex 2975 . . . . . . . . . 10  |-  t  e. 
_V
159, 14brcnv 5022 . . . . . . . . 9  |-  ( s `'  .<_  t  <->  t  .<_  s )
1615anbi2i 694 . . . . . . . 8  |-  ( ( s  .<_  t  /\  s `'  .<_  t )  <-> 
( s  .<_  t  /\  t  .<_  s ) )
1713, 16bitri 249 . . . . . . 7  |-  ( s (  .<_  i^i  `'  .<_  ) t  <->  ( s  .<_  t  /\  t  .<_  s ) )
1812, 17anbi12i 697 . . . . . 6  |-  ( ( r (  .<_  i^i  `'  .<_  ) s  /\  s
(  .<_  i^i  `'  .<_  ) t )  <->  ( (
r  .<_  s  /\  s  .<_  r )  /\  (
s  .<_  t  /\  t  .<_  s ) ) )
19 breq1 4295 . . . . . . . . . . . . 13  |-  ( a  =  r  ->  (
a  .<_  b  <->  r  .<_  b ) )
2019anbi1d 704 . . . . . . . . . . . 12  |-  ( a  =  r  ->  (
( a  .<_  b  /\  b  .<_  c )  <->  ( r  .<_  b  /\  b  .<_  c ) ) )
21 breq1 4295 . . . . . . . . . . . 12  |-  ( a  =  r  ->  (
a  .<_  c  <->  r  .<_  c ) )
2220, 21imbi12d 320 . . . . . . . . . . 11  |-  ( a  =  r  ->  (
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  <-> 
( ( r  .<_  b  /\  b  .<_  c )  ->  r  .<_  c ) ) )
23222albidv 1681 . . . . . . . . . 10  |-  ( a  =  r  ->  ( A. b A. c ( ( a  .<_  b  /\  b  .<_  c )  -> 
a  .<_  c )  <->  A. b A. c ( ( r 
.<_  b  /\  b  .<_  c )  ->  r  .<_  c ) ) )
2423spv 1955 . . . . . . . . 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 4296 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
r  .<_  b  <->  r  .<_  s ) )
26 breq1 4295 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
b  .<_  c  <->  s  .<_  c ) )
2725, 26anbi12d 710 . . . . . . . . . . . 12  |-  ( b  =  s  ->  (
( r  .<_  b  /\  b  .<_  c )  <->  ( r  .<_  s  /\  s  .<_  c ) ) )
2827imbi1d 317 . . . . . . . . . . 11  |-  ( b  =  s  ->  (
( ( r  .<_  b  /\  b  .<_  c )  ->  r  .<_  c )  <-> 
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c ) ) )
2928albidv 1679 . . . . . . . . . 10  |-  ( b  =  s  ->  ( A. c ( ( r 
.<_  b  /\  b  .<_  c )  ->  r  .<_  c )  <->  A. c
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c ) ) )
3029spv 1955 . . . . . . . . 9  |-  ( A. b A. c ( ( r  .<_  b  /\  b  .<_  c )  -> 
r  .<_  c )  ->  A. c ( ( r 
.<_  s  /\  s  .<_  c )  ->  r  .<_  c ) )
31 breq2 4296 . . . . . . . . . . . 12  |-  ( c  =  t  ->  (
s  .<_  c  <->  s  .<_  t ) )
3231anbi2d 703 . . . . . . . . . . 11  |-  ( c  =  t  ->  (
( r  .<_  s  /\  s  .<_  c )  <->  ( r  .<_  s  /\  s  .<_  t ) ) )
33 breq2 4296 . . . . . . . . . . 11  |-  ( c  =  t  ->  (
r  .<_  c  <->  r  .<_  t ) )
3432, 33imbi12d 320 . . . . . . . . . 10  |-  ( c  =  t  ->  (
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c )  <-> 
( ( r  .<_  s  /\  s  .<_  t )  ->  r  .<_  t ) ) )
3534spv 1955 . . . . . . . . 9  |-  ( A. c ( ( r 
.<_  s  /\  s  .<_  c )  ->  r  .<_  c )  ->  (
( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t ) )
36 pm3.3 444 . . . . . . . . . . . . . 14  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( r  .<_  s  -> 
( s  .<_  t  -> 
r  .<_  t ) ) )
3736com23 78 . . . . . . . . . . . . 13  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( s  .<_  t  -> 
( r  .<_  s  -> 
r  .<_  t ) ) )
3837adantrd 468 . . . . . . . . . . . 12  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  ( r  .<_  s  ->  r  .<_  t ) ) )
3938com23 78 . . . . . . . . . . 11  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( r  .<_  s  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  r  .<_  t ) ) )
4039adantrd 468 . . . . . . . . . 10  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( ( r  .<_  s  /\  s  .<_  r )  ->  ( ( s 
.<_  t  /\  t  .<_  s )  ->  r  .<_  t ) ) )
4140impd 431 . . . . . . . . 9  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( ( ( r 
.<_  s  /\  s  .<_  r )  /\  (
s  .<_  t  /\  t  .<_  s ) )  -> 
r  .<_  t ) )
4224, 30, 35, 414syl 21 . . . . . . . 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 4295 . . . . . . . . . . . . 13  |-  ( a  =  t  ->  (
a  .<_  b  <->  t  .<_  b ) )
4443anbi1d 704 . . . . . . . . . . . 12  |-  ( a  =  t  ->  (
( a  .<_  b  /\  b  .<_  c )  <->  ( t  .<_  b  /\  b  .<_  c ) ) )
45 breq1 4295 . . . . . . . . . . . 12  |-  ( a  =  t  ->  (
a  .<_  c  <->  t  .<_  c ) )
4644, 45imbi12d 320 . . . . . . . . . . 11  |-  ( a  =  t  ->  (
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  <-> 
( ( t  .<_  b  /\  b  .<_  c )  ->  t  .<_  c ) ) )
47462albidv 1681 . . . . . . . . . 10  |-  ( a  =  t  ->  ( A. b A. c ( ( a  .<_  b  /\  b  .<_  c )  -> 
a  .<_  c )  <->  A. b A. c ( ( t 
.<_  b  /\  b  .<_  c )  ->  t  .<_  c ) ) )
4847spv 1955 . . . . . . . . 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 4296 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
t  .<_  b  <->  t  .<_  s ) )
5049, 26anbi12d 710 . . . . . . . . . . . 12  |-  ( b  =  s  ->  (
( t  .<_  b  /\  b  .<_  c )  <->  ( t  .<_  s  /\  s  .<_  c ) ) )
5150imbi1d 317 . . . . . . . . . . 11  |-  ( b  =  s  ->  (
( ( t  .<_  b  /\  b  .<_  c )  ->  t  .<_  c )  <-> 
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c ) ) )
5251albidv 1679 . . . . . . . . . 10  |-  ( b  =  s  ->  ( A. c ( ( t 
.<_  b  /\  b  .<_  c )  ->  t  .<_  c )  <->  A. c
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c ) ) )
5352spv 1955 . . . . . . . . 9  |-  ( A. b A. c ( ( t  .<_  b  /\  b  .<_  c )  -> 
t  .<_  c )  ->  A. c ( ( t 
.<_  s  /\  s  .<_  c )  ->  t  .<_  c ) )
54 breq2 4296 . . . . . . . . . . . 12  |-  ( c  =  r  ->  (
s  .<_  c  <->  s  .<_  r ) )
5554anbi2d 703 . . . . . . . . . . 11  |-  ( c  =  r  ->  (
( t  .<_  s  /\  s  .<_  c )  <->  ( t  .<_  s  /\  s  .<_  r ) ) )
56 breq2 4296 . . . . . . . . . . 11  |-  ( c  =  r  ->  (
t  .<_  c  <->  t  .<_  r ) )
5755, 56imbi12d 320 . . . . . . . . . 10  |-  ( c  =  r  ->  (
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c )  <-> 
( ( t  .<_  s  /\  s  .<_  r )  ->  t  .<_  r ) ) )
5857spv 1955 . . . . . . . . 9  |-  ( A. c ( ( t 
.<_  s  /\  s  .<_  c )  ->  t  .<_  c )  ->  (
( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r ) )
59 pm3.3 444 . . . . . . . . . . . . 13  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( t  .<_  s  -> 
( s  .<_  r  -> 
t  .<_  r ) ) )
6059adantld 467 . . . . . . . . . . . 12  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  ( s  .<_  r  ->  t  .<_  r ) ) )
6160com23 78 . . . . . . . . . . 11  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( s  .<_  r  -> 
( ( s  .<_  t  /\  t  .<_  s )  ->  t  .<_  r ) ) )
6261adantld 467 . . . . . . . . . 10  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( ( r  .<_  s  /\  s  .<_  r )  ->  ( ( s 
.<_  t  /\  t  .<_  s )  ->  t  .<_  r ) ) )
6362impd 431 . . . . . . . . 9  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( ( ( r 
.<_  s  /\  s  .<_  r )  /\  (
s  .<_  t  /\  t  .<_  s ) )  -> 
t  .<_  r ) )
6448, 53, 58, 634syl 21 . . . . . . . 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 533 . . . . . . 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 4341 . . . . . . . 8  |-  ( r (  .<_  i^i  `'  .<_  ) t  <->  ( r  .<_  t  /\  r `'  .<_  t ) )
678, 14brcnv 5022 . . . . . . . . 9  |-  ( r `'  .<_  t  <->  t  .<_  r )
6867anbi2i 694 . . . . . . . 8  |-  ( ( r  .<_  t  /\  r `'  .<_  t )  <-> 
( r  .<_  t  /\  t  .<_  r ) )
6966, 68bitr2i 250 . . . . . . 7  |-  ( ( r  .<_  t  /\  t  .<_  r )  <->  r (  .<_  i^i  `'  .<_  ) t )
7065, 69syl6ib 226 . . . . . 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 217 . . . . 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 5022 . . . . . . . . 9  |-  ( s `'  .<_  r  <->  r  .<_  s )
7372bicomi 202 . . . . . . . 8  |-  ( r 
.<_  s  <->  s `'  .<_  r )
7473, 10anbi12ci 698 . . . . . . 7  |-  ( ( r  .<_  s  /\  r `'  .<_  s )  <-> 
( s  .<_  r  /\  s `'  .<_  r ) )
75 brin 4341 . . . . . . 7  |-  ( s (  .<_  i^i  `'  .<_  ) r  <->  ( s  .<_  r  /\  s `'  .<_  r ) )
7674, 7, 753bitr4i 277 . . . . . 6  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  s (  .<_  i^i  `'  .<_  ) r )
7776biimpi 194 . . . . 5  |-  ( r (  .<_  i^i  `'  .<_  ) s  ->  s (  .<_  i^i  `'  .<_  ) r )
7871, 77jctil 537 . . . 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 1685 . . 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 1686 . 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 7102 . 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 1172 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 369   A.wal 1367    = wceq 1369    i^i cin 3327    C_ wss 3328   class class class wbr 4292   `'ccnv 4839   dom cdm 4840   Rel wrel 4845    Er wer 7098
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1591  ax-4 1602  ax-5 1670  ax-6 1708  ax-7 1728  ax-9 1760  ax-10 1775  ax-11 1780  ax-12 1792  ax-13 1943  ax-ext 2423  ax-sep 4413  ax-nul 4421  ax-pr 4531
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3an 967  df-tru 1372  df-ex 1587  df-nf 1590  df-sb 1701  df-eu 2257  df-mo 2258  df-clab 2430  df-cleq 2436  df-clel 2439  df-nfc 2568  df-ne 2608  df-ral 2720  df-rex 2721  df-rab 2724  df-v 2974  df-dif 3331  df-un 3333  df-in 3335  df-ss 3342  df-nul 3638  df-if 3792  df-sn 3878  df-pr 3880  df-op 3884  df-br 4293  df-opab 4351  df-xp 4846  df-rel 4847  df-cnv 4848  df-co 4849  df-er 7101
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator