MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  fr3nr Structured version   Visualization version   Unicode version
Theorem fr3nr 6979
Description: A well-founded relation has no 3-cycle loops. Special case of Proposition 6.23 of [TakeutiZaring] p. 30. (Contributed by NM, 10-Apr-1994.) (Revised by Mario Carneiro, 22-Jun-2015.)
Assertion
Ref Expression
fr3nr |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> -. ( B R C /\ C R D /\ D R B ) )
Proof of Theorem fr3nr
Dummy variables x y are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 tpex 6957 . . . . . . 7 |- { B , C , D } e. _V
21a1i 11 . . . . . 6 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> { B , C , D } e. _V )
3 simpl 473 . . . . . 6 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> R Fr A )
4 df-tp 4182 . . . . . . 7 |- { B , C , D } = ( { B , C } u. { D } )
5 simpr1 1067 . . . . . . . . 9 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> B e. A )
6 simpr2 1068 . . . . . . . . 9 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> C e. A )
7 prssi 4353 . . . . . . . . 9 |- ( ( B e. A /\ C e. A ) -> { B , C } C_ A )
85, 6, 7syl2anc 693 . . . . . . . 8 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> { B , C } C_ A )
9 simpr3 1069 . . . . . . . . 9 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> D e. A )
109snssd 4340 . . . . . . . 8 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> { D } C_ A )
118, 10unssd 3789 . . . . . . 7 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> ( { B , C } u. { D } ) C_ A )
124, 11syl5eqss 3649 . . . . . 6 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> { B , C , D } C_ A )
135tpnzd 4314 . . . . . 6 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> { B , C , D } =/= (/) )
14 fri 5076 . . . . . 6 |- ( ( ( { B , C , D } e. _V /\ R Fr A ) /\ ( { B , C , D } C_ A /\ { B , C , D } =/= (/) ) ) -> E. x e. { B , C , D } A. y e. { B , C , D } -. y R x )
152, 3, 12, 13, 14syl22anc 1327 . . . . 5 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> E. x e. { B , C , D } A. y e. { B , C , D } -. y R x )
16 breq2 4657 . . . . . . . . 9 |- ( x = B -> ( y R x <-> y R B ) )
1716notbid 308 . . . . . . . 8 |- ( x = B -> ( -. y R x <-> -. y R B ) )
1817ralbidv 2986 . . . . . . 7 |- ( x = B -> ( A. y e. { B , C , D } -. y R x <-> A. y e. { B , C , D } -. y R B ) )
19 breq2 4657 . . . . . . . . 9 |- ( x = C -> ( y R x <-> y R C ) )
2019notbid 308 . . . . . . . 8 |- ( x = C -> ( -. y R x <-> -. y R C ) )
2120ralbidv 2986 . . . . . . 7 |- ( x = C -> ( A. y e. { B , C , D } -. y R x <-> A. y e. { B , C , D } -. y R C ) )
22 breq2 4657 . . . . . . . . 9 |- ( x = D -> ( y R x <-> y R D ) )
2322notbid 308 . . . . . . . 8 |- ( x = D -> ( -. y R x <-> -. y R D ) )
2423ralbidv 2986 . . . . . . 7 |- ( x = D -> ( A. y e. { B , C , D } -. y R x <-> A. y e. { B , C , D } -. y R D ) )
2518, 21, 24rextpg 4237 . . . . . 6 |- ( ( B e. A /\ C e. A /\ D e. A ) -> ( E. x e. { B , C , D } A. y e. { B , C , D } -. y R x <-> ( A. y e. { B , C , D } -. y R B \/ A. y e. { B , C , D } -. y R C \/ A. y e. { B , C , D } -. y R D ) ) )
2625adantl 482 . . . . 5 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> ( E. x e. { B , C , D } A. y e. { B , C , D } -. y R x <-> ( A. y e. { B , C , D } -. y R B \/ A. y e. { B , C , D } -. y R C \/ A. y e. { B , C , D } -. y R D ) ) )
2715, 26mpbid 222 . . . 4 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> ( A. y e. { B , C , D } -. y R B \/ A. y e. { B , C , D } -. y R C \/ A. y e. { B , C , D } -. y R D ) )
28 snsstp3 4349 . . . . . . 7 |- { D } C_ { B , C , D }
29 snssg 4327 . . . . . . . 8 |- ( D e. A -> ( D e. { B , C , D } <-> { D } C_ { B , C , D } ) )
309, 29syl 17 . . . . . . 7 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> ( D e. { B , C , D } <-> { D } C_ { B , C , D } ) )
3128, 30mpbiri 248 . . . . . 6 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> D e. { B , C , D } )
32 breq1 4656 . . . . . . . 8 |- ( y = D -> ( y R B <-> D R B ) )
3332notbid 308 . . . . . . 7 |- ( y = D -> ( -. y R B <-> -. D R B ) )
3433rspcv 3305 . . . . . 6 |- ( D e. { B , C , D } -> ( A. y e. { B , C , D } -. y R B -> -. D R B ) )
3531, 34syl 17 . . . . 5 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> ( A. y e. { B , C , D } -. y R B -> -. D R B ) )
36 snsstp1 4347 . . . . . . 7 |- { B } C_ { B , C , D }
37 snssg 4327 . . . . . . . 8 |- ( B e. A -> ( B e. { B , C , D } <-> { B } C_ { B , C , D } ) )
385, 37syl 17 . . . . . . 7 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> ( B e. { B , C , D } <-> { B } C_ { B , C , D } ) )
3936, 38mpbiri 248 . . . . . 6 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> B e. { B , C , D } )
40 breq1 4656 . . . . . . . 8 |- ( y = B -> ( y R C <-> B R C ) )
4140notbid 308 . . . . . . 7 |- ( y = B -> ( -. y R C <-> -. B R C ) )
4241rspcv 3305 . . . . . 6 |- ( B e. { B , C , D } -> ( A. y e. { B , C , D } -. y R C -> -. B R C ) )
4339, 42syl 17 . . . . 5 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> ( A. y e. { B , C , D } -. y R C -> -. B R C ) )
44 snsstp2 4348 . . . . . . 7 |- { C } C_ { B , C , D }
45 snssg 4327 . . . . . . . 8 |- ( C e. A -> ( C e. { B , C , D } <-> { C } C_ { B , C , D } ) )
466, 45syl 17 . . . . . . 7 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> ( C e. { B , C , D } <-> { C } C_ { B , C , D } ) )
4744, 46mpbiri 248 . . . . . 6 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> C e. { B , C , D } )
48 breq1 4656 . . . . . . . 8 |- ( y = C -> ( y R D <-> C R D ) )
4948notbid 308 . . . . . . 7 |- ( y = C -> ( -. y R D <-> -. C R D ) )
5049rspcv 3305 . . . . . 6 |- ( C e. { B , C , D } -> ( A. y e. { B , C , D } -. y R D -> -. C R D ) )
5147, 50syl 17 . . . . 5 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> ( A. y e. { B , C , D } -. y R D -> -. C R D ) )
5235, 43, 513orim123d 1407 . . . 4 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> ( ( A. y e. { B , C , D } -. y R B \/ A. y e. { B , C , D } -. y R C \/ A. y e. { B , C , D } -. y R D ) -> ( -. D R B \/ -. B R C \/ -. C R D ) ) )
5327, 52mpd 15 . . 3 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> ( -. D R B \/ -. B R C \/ -. C R D ) )
54 3ianor 1055 . . 3 |- ( -. ( D R B /\ B R C /\ C R D ) <-> ( -. D R B \/ -. B R C \/ -. C R D ) )
5553, 54sylibr 224 . 2 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> -. ( D R B /\ B R C /\ C R D ) )
56 3anrot 1043 . 2 |- ( ( D R B /\ B R C /\ C R D ) <-> ( B R C /\ C R D /\ D R B ) )
5755, 56sylnib 318 1 |- ( ( R Fr A /\ ( B e. A /\ C e. A /\ D e. A ) ) -> -. ( B R C /\ C R D /\ D R B ) )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3   -> wi 4   <-> wb 196   /\ wa 384   \/ w3o 1036   /\ w3a 1037   = wceq 1483   e. wcel 1990   =/= wne 2794   A.wral 2912   E.wrex 2913   _Vcvv 3200   u. cun 3572   C_ wss 3574   (/)c0 3915   {csn 4177   {cpr 4179   {ctp 4181   class class class wbr 4653   Fr wfr 5070
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1722  ax-4 1737  ax-5 1839  ax-6 1888  ax-7 1935  ax-8 1992  ax-9 1999  ax-10 2019  ax-11 2034  ax-12 2047  ax-13 2246  ax-ext 2602  ax-sep 4781  ax-nul 4789  ax-pr 4906  ax-un 6949
This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3or 1038  df-3an 1039  df-tru 1486  df-ex 1705  df-nf 1710  df-sb 1881  df-clab 2609  df-cleq 2615  df-clel 2618  df-nfc 2753  df-ne 2795  df-ral 2917  df-rex 2918  df-rab 2921  df-v 3202  df-sbc 3436  df-dif 3577  df-un 3579  df-in 3581  df-ss 3588  df-nul 3916  df-if 4087  df-sn 4178  df-pr 4180  df-tp 4182  df-op 4184  df-uni 4437  df-br 4654  df-fr 5073
This theorem is referenced by:  epne3  6980  dfwe2  6981
  Copyright terms: Public domain W3C validator