Metamath Proof Explorer

Theorem lrrecfr

Description: Now we show that R is founded over No . (Contributed by Scott Fenton, 19-Aug-2024)

Ref Expression
Hypothesis lrrec.1 
|- R = { <. x , y >. | x e. ( ( _Left ` y ) u. ( _Right ` y ) ) }
Assertion lrrecfr 
|- R Fr No

Proof

Step Hyp Ref Expression
1 lrrec.1 
 |-  R = { <. x , y >. | x e. ( ( _Left ` y ) u. ( _Right ` y ) ) }
2 df-fr 
 |-  ( R Fr No <-> A. a ( ( a C_ No /\ a =/= (/) ) -> E. p e. a A. q e. a -. q R p ) )
3 bdayfun 
 |-  Fun bday
4 imassrn 
 |-  ( bday " a ) C_ ran bday
5 bdayrn 
 |-  ran bday = On
6 4 5 sseqtri 
 |-  ( bday " a ) C_ On
7 fvex 
 |-  ( bday ` q ) e. _V
8 7 jctr 
 |-  ( q e. a -> ( q e. a /\ ( bday ` q ) e. _V ) )
9 8 eximi 
 |-  ( E. q q e. a -> E. q ( q e. a /\ ( bday ` q ) e. _V ) )
10 n0 
 |-  ( a =/= (/) <-> E. q q e. a )
11 df-rex 
 |-  ( E. q e. a ( bday ` q ) e. _V <-> E. q ( q e. a /\ ( bday ` q ) e. _V ) )
12 9 10 11 3imtr4i 
 |-  ( a =/= (/) -> E. q e. a ( bday ` q ) e. _V )
13 isset 
 |-  ( ( bday ` q ) e. _V <-> E. p p = ( bday ` q ) )
14 eqcom 
 |-  ( p = ( bday ` q ) <-> ( bday ` q ) = p )
15 14 exbii 
 |-  ( E. p p = ( bday ` q ) <-> E. p ( bday ` q ) = p )
16 13 15 bitri 
 |-  ( ( bday ` q ) e. _V <-> E. p ( bday ` q ) = p )
17 16 rexbii 
 |-  ( E. q e. a ( bday ` q ) e. _V <-> E. q e. a E. p ( bday ` q ) = p )
18 rexcom4 
 |-  ( E. q e. a E. p ( bday ` q ) = p <-> E. p E. q e. a ( bday ` q ) = p )
19 17 18 bitri 
 |-  ( E. q e. a ( bday ` q ) e. _V <-> E. p E. q e. a ( bday ` q ) = p )
20 12 19 sylib 
 |-  ( a =/= (/) -> E. p E. q e. a ( bday ` q ) = p )
21 20 adantl 
 |-  ( ( a C_ No /\ a =/= (/) ) -> E. p E. q e. a ( bday ` q ) = p )
22 bdayfn 
 |-  bday Fn No
23 fvelimab 
 |-  ( ( bday Fn No /\ a C_ No ) -> ( p e. ( bday " a ) <-> E. q e. a ( bday ` q ) = p ) )
24 22 23 mpan 
 |-  ( a C_ No -> ( p e. ( bday " a ) <-> E. q e. a ( bday ` q ) = p ) )
25 24 adantr 
 |-  ( ( a C_ No /\ a =/= (/) ) -> ( p e. ( bday " a ) <-> E. q e. a ( bday ` q ) = p ) )
26 25 exbidv 
 |-  ( ( a C_ No /\ a =/= (/) ) -> ( E. p p e. ( bday " a ) <-> E. p E. q e. a ( bday ` q ) = p ) )
27 21 26 mpbird 
 |-  ( ( a C_ No /\ a =/= (/) ) -> E. p p e. ( bday " a ) )
28 n0 
 |-  ( ( bday " a ) =/= (/) <-> E. p p e. ( bday " a ) )
29 27 28 sylibr 
 |-  ( ( a C_ No /\ a =/= (/) ) -> ( bday " a ) =/= (/) )
30 onint 
 |-  ( ( ( bday " a ) C_ On /\ ( bday " a ) =/= (/) ) -> |^| ( bday " a ) e. ( bday " a ) )
31 6 29 30 sylancr 
 |-  ( ( a C_ No /\ a =/= (/) ) -> |^| ( bday " a ) e. ( bday " a ) )
32 fvelima 
 |-  ( ( Fun bday /\ |^| ( bday " a ) e. ( bday " a ) ) -> E. p e. a ( bday ` p ) = |^| ( bday " a ) )
33 3 31 32 sylancr 
 |-  ( ( a C_ No /\ a =/= (/) ) -> E. p e. a ( bday ` p ) = |^| ( bday " a ) )
34 fnfvima 
 |-  ( ( bday Fn No /\ a C_ No /\ q e. a ) -> ( bday ` q ) e. ( bday " a ) )
35 22 34 mp3an1 
 |-  ( ( a C_ No /\ q e. a ) -> ( bday ` q ) e. ( bday " a ) )
36 35 adantlr 
 |-  ( ( ( a C_ No /\ a =/= (/) ) /\ q e. a ) -> ( bday ` q ) e. ( bday " a ) )
37 onnmin 
 |-  ( ( ( bday " a ) C_ On /\ ( bday ` q ) e. ( bday " a ) ) -> -. ( bday ` q ) e. |^| ( bday " a ) )
38 6 36 37 sylancr 
 |-  ( ( ( a C_ No /\ a =/= (/) ) /\ q e. a ) -> -. ( bday ` q ) e. |^| ( bday " a ) )
39 38 ralrimiva 
 |-  ( ( a C_ No /\ a =/= (/) ) -> A. q e. a -. ( bday ` q ) e. |^| ( bday " a ) )
40 eleq2 
 |-  ( ( bday ` p ) = |^| ( bday " a ) -> ( ( bday ` q ) e. ( bday ` p ) <-> ( bday ` q ) e. |^| ( bday " a ) ) )
41 40 notbid 
 |-  ( ( bday ` p ) = |^| ( bday " a ) -> ( -. ( bday ` q ) e. ( bday ` p ) <-> -. ( bday ` q ) e. |^| ( bday " a ) ) )
42 41 ralbidv 
 |-  ( ( bday ` p ) = |^| ( bday " a ) -> ( A. q e. a -. ( bday ` q ) e. ( bday ` p ) <-> A. q e. a -. ( bday ` q ) e. |^| ( bday " a ) ) )
43 39 42 syl5ibrcom 
 |-  ( ( a C_ No /\ a =/= (/) ) -> ( ( bday ` p ) = |^| ( bday " a ) -> A. q e. a -. ( bday ` q ) e. ( bday ` p ) ) )
44 43 reximdv 
 |-  ( ( a C_ No /\ a =/= (/) ) -> ( E. p e. a ( bday ` p ) = |^| ( bday " a ) -> E. p e. a A. q e. a -. ( bday ` q ) e. ( bday ` p ) ) )
45 33 44 mpd 
 |-  ( ( a C_ No /\ a =/= (/) ) -> E. p e. a A. q e. a -. ( bday ` q ) e. ( bday ` p ) )
46 simpll 
 |-  ( ( ( a C_ No /\ a =/= (/) ) /\ ( p e. a /\ q e. a ) ) -> a C_ No )
47 simprr 
 |-  ( ( ( a C_ No /\ a =/= (/) ) /\ ( p e. a /\ q e. a ) ) -> q e. a )
48 46 47 sseldd 
 |-  ( ( ( a C_ No /\ a =/= (/) ) /\ ( p e. a /\ q e. a ) ) -> q e. No )
49 simprl 
 |-  ( ( ( a C_ No /\ a =/= (/) ) /\ ( p e. a /\ q e. a ) ) -> p e. a )
50 46 49 sseldd 
 |-  ( ( ( a C_ No /\ a =/= (/) ) /\ ( p e. a /\ q e. a ) ) -> p e. No )
51 1 lrrecval2 
 |-  ( ( q e. No /\ p e. No ) -> ( q R p <-> ( bday ` q ) e. ( bday ` p ) ) )
52 48 50 51 syl2anc 
 |-  ( ( ( a C_ No /\ a =/= (/) ) /\ ( p e. a /\ q e. a ) ) -> ( q R p <-> ( bday ` q ) e. ( bday ` p ) ) )
53 52 notbid 
 |-  ( ( ( a C_ No /\ a =/= (/) ) /\ ( p e. a /\ q e. a ) ) -> ( -. q R p <-> -. ( bday ` q ) e. ( bday ` p ) ) )
54 53 anassrs 
 |-  ( ( ( ( a C_ No /\ a =/= (/) ) /\ p e. a ) /\ q e. a ) -> ( -. q R p <-> -. ( bday ` q ) e. ( bday ` p ) ) )
55 54 ralbidva 
 |-  ( ( ( a C_ No /\ a =/= (/) ) /\ p e. a ) -> ( A. q e. a -. q R p <-> A. q e. a -. ( bday ` q ) e. ( bday ` p ) ) )
56 55 rexbidva 
 |-  ( ( a C_ No /\ a =/= (/) ) -> ( E. p e. a A. q e. a -. q R p <-> E. p e. a A. q e. a -. ( bday ` q ) e. ( bday ` p ) ) )
57 45 56 mpbird 
 |-  ( ( a C_ No /\ a =/= (/) ) -> E. p e. a A. q e. a -. q R p )
58 2 57 mpgbir 
 |-  R Fr No