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

Theorem trer 30532
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 3659 . . . 4  |-  (  .<_  i^i  `'  .<_  )  C_  `'  .<_
2 relcnv 5316 . . . 4  |-  Rel  `'  .<_
3 relss 5032 . . . 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 2403 . 2  |-  ( A. a A. b A. c
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  ->  dom  (  .<_  i^i  `'  .<_  )  =  dom  (  .<_  i^i  `'  .<_  ) )
7 brin 4443 . . . . . . . 8  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  ( r  .<_  s  /\  r `'  .<_  s ) )
8 vex 3061 . . . . . . . . . 10  |-  r  e. 
_V
9 vex 3061 . . . . . . . . . 10  |-  s  e. 
_V
108, 9brcnv 5127 . . . . . . . . 9  |-  ( r `'  .<_  s  <->  s  .<_  r )
1110anbi2i 692 . . . . . . . 8  |-  ( ( r  .<_  s  /\  r `'  .<_  s )  <-> 
( r  .<_  s  /\  s  .<_  r ) )
127, 11bitri 249 . . . . . . 7  |-  ( r (  .<_  i^i  `'  .<_  ) s  <->  ( r  .<_  s  /\  s  .<_  r ) )
13 brin 4443 . . . . . . . 8  |-  ( s (  .<_  i^i  `'  .<_  ) t  <->  ( s  .<_  t  /\  s `'  .<_  t ) )
14 vex 3061 . . . . . . . . . 10  |-  t  e. 
_V
159, 14brcnv 5127 . . . . . . . . 9  |-  ( s `'  .<_  t  <->  t  .<_  s )
1615anbi2i 692 . . . . . . . 8  |-  ( ( s  .<_  t  /\  s `'  .<_  t )  <-> 
( s  .<_  t  /\  t  .<_  s ) )
1713, 16bitri 249 . . . . . . 7  |-  ( s (  .<_  i^i  `'  .<_  ) t  <->  ( s  .<_  t  /\  t  .<_  s ) )
1812, 17anbi12i 695 . . . . . 6  |-  ( ( r (  .<_  i^i  `'  .<_  ) s  /\  s
(  .<_  i^i  `'  .<_  ) t )  <->  ( (
r  .<_  s  /\  s  .<_  r )  /\  (
s  .<_  t  /\  t  .<_  s ) ) )
19 breq1 4397 . . . . . . . . . . . . 13  |-  ( a  =  r  ->  (
a  .<_  b  <->  r  .<_  b ) )
2019anbi1d 703 . . . . . . . . . . . 12  |-  ( a  =  r  ->  (
( a  .<_  b  /\  b  .<_  c )  <->  ( r  .<_  b  /\  b  .<_  c ) ) )
21 breq1 4397 . . . . . . . . . . . 12  |-  ( a  =  r  ->  (
a  .<_  c  <->  r  .<_  c ) )
2220, 21imbi12d 318 . . . . . . . . . . 11  |-  ( a  =  r  ->  (
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  <-> 
( ( r  .<_  b  /\  b  .<_  c )  ->  r  .<_  c ) ) )
23222albidv 1736 . . . . . . . . . 10  |-  ( a  =  r  ->  ( A. b A. c ( ( a  .<_  b  /\  b  .<_  c )  -> 
a  .<_  c )  <->  A. b A. c ( ( r 
.<_  b  /\  b  .<_  c )  ->  r  .<_  c ) ) )
2423spv 2038 . . . . . . . . 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 4398 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
r  .<_  b  <->  r  .<_  s ) )
26 breq1 4397 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
b  .<_  c  <->  s  .<_  c ) )
2725, 26anbi12d 709 . . . . . . . . . . . 12  |-  ( b  =  s  ->  (
( r  .<_  b  /\  b  .<_  c )  <->  ( r  .<_  s  /\  s  .<_  c ) ) )
2827imbi1d 315 . . . . . . . . . . 11  |-  ( b  =  s  ->  (
( ( r  .<_  b  /\  b  .<_  c )  ->  r  .<_  c )  <-> 
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c ) ) )
2928albidv 1734 . . . . . . . . . 10  |-  ( b  =  s  ->  ( A. c ( ( r 
.<_  b  /\  b  .<_  c )  ->  r  .<_  c )  <->  A. c
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c ) ) )
3029spv 2038 . . . . . . . . 9  |-  ( A. b A. c ( ( r  .<_  b  /\  b  .<_  c )  -> 
r  .<_  c )  ->  A. c ( ( r 
.<_  s  /\  s  .<_  c )  ->  r  .<_  c ) )
31 breq2 4398 . . . . . . . . . . . 12  |-  ( c  =  t  ->  (
s  .<_  c  <->  s  .<_  t ) )
3231anbi2d 702 . . . . . . . . . . 11  |-  ( c  =  t  ->  (
( r  .<_  s  /\  s  .<_  c )  <->  ( r  .<_  s  /\  s  .<_  t ) ) )
33 breq2 4398 . . . . . . . . . . 11  |-  ( c  =  t  ->  (
r  .<_  c  <->  r  .<_  t ) )
3432, 33imbi12d 318 . . . . . . . . . 10  |-  ( c  =  t  ->  (
( ( r  .<_  s  /\  s  .<_  c )  ->  r  .<_  c )  <-> 
( ( r  .<_  s  /\  s  .<_  t )  ->  r  .<_  t ) ) )
3534spv 2038 . . . . . . . . 9  |-  ( A. c ( ( r 
.<_  s  /\  s  .<_  c )  ->  r  .<_  c )  ->  (
( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t ) )
36 pm3.3 442 . . . . . . . . . . . . . 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 466 . . . . . . . . . . . 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 466 . . . . . . . . . 10  |-  ( ( ( r  .<_  s  /\  s  .<_  t )  -> 
r  .<_  t )  -> 
( ( r  .<_  s  /\  s  .<_  r )  ->  ( ( s 
.<_  t  /\  t  .<_  s )  ->  r  .<_  t ) ) )
4140impd 429 . . . . . . . . 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 4397 . . . . . . . . . . . . 13  |-  ( a  =  t  ->  (
a  .<_  b  <->  t  .<_  b ) )
4443anbi1d 703 . . . . . . . . . . . 12  |-  ( a  =  t  ->  (
( a  .<_  b  /\  b  .<_  c )  <->  ( t  .<_  b  /\  b  .<_  c ) ) )
45 breq1 4397 . . . . . . . . . . . 12  |-  ( a  =  t  ->  (
a  .<_  c  <->  t  .<_  c ) )
4644, 45imbi12d 318 . . . . . . . . . . 11  |-  ( a  =  t  ->  (
( ( a  .<_  b  /\  b  .<_  c )  ->  a  .<_  c )  <-> 
( ( t  .<_  b  /\  b  .<_  c )  ->  t  .<_  c ) ) )
47462albidv 1736 . . . . . . . . . 10  |-  ( a  =  t  ->  ( A. b A. c ( ( a  .<_  b  /\  b  .<_  c )  -> 
a  .<_  c )  <->  A. b A. c ( ( t 
.<_  b  /\  b  .<_  c )  ->  t  .<_  c ) ) )
4847spv 2038 . . . . . . . . 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 4398 . . . . . . . . . . . . 13  |-  ( b  =  s  ->  (
t  .<_  b  <->  t  .<_  s ) )
5049, 26anbi12d 709 . . . . . . . . . . . 12  |-  ( b  =  s  ->  (
( t  .<_  b  /\  b  .<_  c )  <->  ( t  .<_  s  /\  s  .<_  c ) ) )
5150imbi1d 315 . . . . . . . . . . 11  |-  ( b  =  s  ->  (
( ( t  .<_  b  /\  b  .<_  c )  ->  t  .<_  c )  <-> 
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c ) ) )
5251albidv 1734 . . . . . . . . . 10  |-  ( b  =  s  ->  ( A. c ( ( t 
.<_  b  /\  b  .<_  c )  ->  t  .<_  c )  <->  A. c
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c ) ) )
5352spv 2038 . . . . . . . . 9  |-  ( A. b A. c ( ( t  .<_  b  /\  b  .<_  c )  -> 
t  .<_  c )  ->  A. c ( ( t 
.<_  s  /\  s  .<_  c )  ->  t  .<_  c ) )
54 breq2 4398 . . . . . . . . . . . 12  |-  ( c  =  r  ->  (
s  .<_  c  <->  s  .<_  r ) )
5554anbi2d 702 . . . . . . . . . . 11  |-  ( c  =  r  ->  (
( t  .<_  s  /\  s  .<_  c )  <->  ( t  .<_  s  /\  s  .<_  r ) ) )
56 breq2 4398 . . . . . . . . . . 11  |-  ( c  =  r  ->  (
t  .<_  c  <->  t  .<_  r ) )
5755, 56imbi12d 318 . . . . . . . . . 10  |-  ( c  =  r  ->  (
( ( t  .<_  s  /\  s  .<_  c )  ->  t  .<_  c )  <-> 
( ( t  .<_  s  /\  s  .<_  r )  ->  t  .<_  r ) ) )
5857spv 2038 . . . . . . . . 9  |-  ( A. c ( ( t 
.<_  s  /\  s  .<_  c )  ->  t  .<_  c )  ->  (
( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r ) )
59 pm3.3 442 . . . . . . . . . . . . 13  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( t  .<_  s  -> 
( s  .<_  r  -> 
t  .<_  r ) ) )
6059adantld 465 . . . . . . . . . . . 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 465 . . . . . . . . . 10  |-  ( ( ( t  .<_  s  /\  s  .<_  r )  -> 
t  .<_  r )  -> 
( ( r  .<_  s  /\  s  .<_  r )  ->  ( ( s 
.<_  t  /\  t  .<_  s )  ->  t  .<_  r ) ) )
6362impd 429 . . . . . . . . 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 531 . . . . . . 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 4443 . . . . . . . 8  |-  ( r (  .<_  i^i  `'  .<_  ) t  <->  ( r  .<_  t  /\  r `'  .<_  t ) )
678, 14brcnv 5127 . . . . . . . . 9  |-  ( r `'  .<_  t  <->  t  .<_  r )
6867anbi2i 692 . . . . . . . 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 5127 . . . . . . . . 9  |-  ( s `'  .<_  r  <->  r  .<_  s )
7372bicomi 202 . . . . . . . 8  |-  ( r 
.<_  s  <->  s `'  .<_  r )
7473, 10anbi12ci 696 . . . . . . 7  |-  ( ( r  .<_  s  /\  r `'  .<_  s )  <-> 
( s  .<_  r  /\  s `'  .<_  r ) )
75 brin 4443 . . . . . . 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 535 . . . 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 1740 . . 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 1741 . 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 7269 . 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 1181 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 367   A.wal 1403    = wceq 1405    i^i cin 3412    C_ wss 3413   class class class wbr 4394   `'ccnv 4941   dom cdm 4942   Rel wrel 4947    Er wer 7265
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1639  ax-4 1652  ax-5 1725  ax-6 1771  ax-7 1814  ax-9 1846  ax-10 1861  ax-11 1866  ax-12 1878  ax-13 2026  ax-ext 2380  ax-sep 4516  ax-nul 4524  ax-pr 4629
This theorem depends on definitions:  df-bi 185  df-or 368  df-an 369  df-3an 976  df-tru 1408  df-ex 1634  df-nf 1638  df-sb 1764  df-eu 2242  df-mo 2243  df-clab 2388  df-cleq 2394  df-clel 2397  df-nfc 2552  df-ne 2600  df-ral 2758  df-rex 2759  df-rab 2762  df-v 3060  df-dif 3416  df-un 3418  df-in 3420  df-ss 3427  df-nul 3738  df-if 3885  df-sn 3972  df-pr 3974  df-op 3978  df-br 4395  df-opab 4453  df-xp 4948  df-rel 4949  df-cnv 4950  df-co 4951  df-er 7268
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator