Metamath Proof Explorer

Theorem frrlem4

Description: Lemma for well-founded recursion. Properties of the restriction of an acceptable function to the domain of another acceptable function. (Contributed by Paul Chapman, 21-Apr-2012)

Ref Expression
Hypothesis frrlem4.1 
|- B = { f | E. x ( f Fn x /\ ( x C_ A /\ A. y e. x Pred ( R , A , y ) C_ x ) /\ A. y e. x ( f ` y ) = ( y G ( f |` Pred ( R , A , y ) ) ) ) }
Assertion frrlem4 
|- ( ( g e. B /\ h e. B ) -> ( ( g |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) /\ A. a e. ( dom g i^i dom h ) ( ( g |` ( dom g i^i dom h ) ) ` a ) = ( a G ( ( g |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) ) )

Proof

Step Hyp Ref Expression
1 frrlem4.1 
 |-  B = { f | E. x ( f Fn x /\ ( x C_ A /\ A. y e. x Pred ( R , A , y ) C_ x ) /\ A. y e. x ( f ` y ) = ( y G ( f |` Pred ( R , A , y ) ) ) ) }
2 1 frrlem2 
 |-  ( g e. B -> Fun g )
3 2 funfnd 
 |-  ( g e. B -> g Fn dom g )
4 fnresin1 
 |-  ( g Fn dom g -> ( g |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) )
5 3 4 syl 
 |-  ( g e. B -> ( g |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) )
6 5 adantr 
 |-  ( ( g e. B /\ h e. B ) -> ( g |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) )
7 1 frrlem1 
 |-  B = { g | E. b ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) }
8 7 eqabri 
 |-  ( g e. B <-> E. b ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) )
9 fndm 
 |-  ( g Fn b -> dom g = b )
10 9 adantr 
 |-  ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) ) -> dom g = b )
11 10 raleqdv 
 |-  ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) ) -> ( A. a e. dom g ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) <-> A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) )
12 11 biimp3ar 
 |-  ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) -> A. a e. dom g ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) )
13 rsp 
 |-  ( A. a e. dom g ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) -> ( a e. dom g -> ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) )
14 12 13 syl 
 |-  ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) -> ( a e. dom g -> ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) )
15 14 exlimiv 
 |-  ( E. b ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) -> ( a e. dom g -> ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) )
16 8 15 sylbi 
 |-  ( g e. B -> ( a e. dom g -> ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) )
17 elinel1 
 |-  ( a e. ( dom g i^i dom h ) -> a e. dom g )
18 16 17 impel 
 |-  ( ( g e. B /\ a e. ( dom g i^i dom h ) ) -> ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) )
19 18 adantlr 
 |-  ( ( ( g e. B /\ h e. B ) /\ a e. ( dom g i^i dom h ) ) -> ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) )
20 simpr 
 |-  ( ( ( g e. B /\ h e. B ) /\ a e. ( dom g i^i dom h ) ) -> a e. ( dom g i^i dom h ) )
21 20 fvresd 
 |-  ( ( ( g e. B /\ h e. B ) /\ a e. ( dom g i^i dom h ) ) -> ( ( g |` ( dom g i^i dom h ) ) ` a ) = ( g ` a ) )
22 resres 
 |-  ( ( g |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) = ( g |` ( ( dom g i^i dom h ) i^i Pred ( R , ( dom g i^i dom h ) , a ) ) )
23 predss 
 |-  Pred ( R , ( dom g i^i dom h ) , a ) C_ ( dom g i^i dom h )
24 sseqin2 
 |-  ( Pred ( R , ( dom g i^i dom h ) , a ) C_ ( dom g i^i dom h ) <-> ( ( dom g i^i dom h ) i^i Pred ( R , ( dom g i^i dom h ) , a ) ) = Pred ( R , ( dom g i^i dom h ) , a ) )
25 23 24 mpbi 
 |-  ( ( dom g i^i dom h ) i^i Pred ( R , ( dom g i^i dom h ) , a ) ) = Pred ( R , ( dom g i^i dom h ) , a )
26 1 frrlem1 
 |-  B = { h | E. c ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) }
27 26 eqabri 
 |-  ( h e. B <-> E. c ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) )
28 exdistrv 
 |-  ( E. b E. c ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) <-> ( E. b ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ E. c ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) )
29 inss1 
 |-  ( b i^i c ) C_ b
30 simpl2l 
 |-  ( ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) -> b C_ A )
31 29 30 sstrid 
 |-  ( ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) -> ( b i^i c ) C_ A )
32 simp2r 
 |-  ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) -> A. a e. b Pred ( R , A , a ) C_ b )
33 simp2r 
 |-  ( ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) -> A. a e. c Pred ( R , A , a ) C_ c )
34 nfra1 
 |-  F/ a A. a e. b Pred ( R , A , a ) C_ b
35 nfra1 
 |-  F/ a A. a e. c Pred ( R , A , a ) C_ c
36 34 35 nfan 
 |-  F/ a ( A. a e. b Pred ( R , A , a ) C_ b /\ A. a e. c Pred ( R , A , a ) C_ c )
37 elinel1 
 |-  ( a e. ( b i^i c ) -> a e. b )
38 rsp 
 |-  ( A. a e. b Pred ( R , A , a ) C_ b -> ( a e. b -> Pred ( R , A , a ) C_ b ) )
39 37 38 syl5com 
 |-  ( a e. ( b i^i c ) -> ( A. a e. b Pred ( R , A , a ) C_ b -> Pred ( R , A , a ) C_ b ) )
40 elinel2 
 |-  ( a e. ( b i^i c ) -> a e. c )
41 rsp 
 |-  ( A. a e. c Pred ( R , A , a ) C_ c -> ( a e. c -> Pred ( R , A , a ) C_ c ) )
42 40 41 syl5com 
 |-  ( a e. ( b i^i c ) -> ( A. a e. c Pred ( R , A , a ) C_ c -> Pred ( R , A , a ) C_ c ) )
43 39 42 anim12d 
 |-  ( a e. ( b i^i c ) -> ( ( A. a e. b Pred ( R , A , a ) C_ b /\ A. a e. c Pred ( R , A , a ) C_ c ) -> ( Pred ( R , A , a ) C_ b /\ Pred ( R , A , a ) C_ c ) ) )
44 ssin 
 |-  ( ( Pred ( R , A , a ) C_ b /\ Pred ( R , A , a ) C_ c ) <-> Pred ( R , A , a ) C_ ( b i^i c ) )
45 44 biimpi 
 |-  ( ( Pred ( R , A , a ) C_ b /\ Pred ( R , A , a ) C_ c ) -> Pred ( R , A , a ) C_ ( b i^i c ) )
46 43 45 syl6com 
 |-  ( ( A. a e. b Pred ( R , A , a ) C_ b /\ A. a e. c Pred ( R , A , a ) C_ c ) -> ( a e. ( b i^i c ) -> Pred ( R , A , a ) C_ ( b i^i c ) ) )
47 36 46 ralrimi 
 |-  ( ( A. a e. b Pred ( R , A , a ) C_ b /\ A. a e. c Pred ( R , A , a ) C_ c ) -> A. a e. ( b i^i c ) Pred ( R , A , a ) C_ ( b i^i c ) )
48 32 33 47 syl2an 
 |-  ( ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) -> A. a e. ( b i^i c ) Pred ( R , A , a ) C_ ( b i^i c ) )
49 simpl1 
 |-  ( ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) -> g Fn b )
50 49 fndmd 
 |-  ( ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) -> dom g = b )
51 simpr1 
 |-  ( ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) -> h Fn c )
52 51 fndmd 
 |-  ( ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) -> dom h = c )
53 ineq12 
 |-  ( ( dom g = b /\ dom h = c ) -> ( dom g i^i dom h ) = ( b i^i c ) )
54 53 sseq1d 
 |-  ( ( dom g = b /\ dom h = c ) -> ( ( dom g i^i dom h ) C_ A <-> ( b i^i c ) C_ A ) )
55 53 sseq2d 
 |-  ( ( dom g = b /\ dom h = c ) -> ( Pred ( R , A , a ) C_ ( dom g i^i dom h ) <-> Pred ( R , A , a ) C_ ( b i^i c ) ) )
56 53 55 raleqbidv 
 |-  ( ( dom g = b /\ dom h = c ) -> ( A. a e. ( dom g i^i dom h ) Pred ( R , A , a ) C_ ( dom g i^i dom h ) <-> A. a e. ( b i^i c ) Pred ( R , A , a ) C_ ( b i^i c ) ) )
57 54 56 anbi12d 
 |-  ( ( dom g = b /\ dom h = c ) -> ( ( ( dom g i^i dom h ) C_ A /\ A. a e. ( dom g i^i dom h ) Pred ( R , A , a ) C_ ( dom g i^i dom h ) ) <-> ( ( b i^i c ) C_ A /\ A. a e. ( b i^i c ) Pred ( R , A , a ) C_ ( b i^i c ) ) ) )
58 50 52 57 syl2anc 
 |-  ( ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) -> ( ( ( dom g i^i dom h ) C_ A /\ A. a e. ( dom g i^i dom h ) Pred ( R , A , a ) C_ ( dom g i^i dom h ) ) <-> ( ( b i^i c ) C_ A /\ A. a e. ( b i^i c ) Pred ( R , A , a ) C_ ( b i^i c ) ) ) )
59 31 48 58 mpbir2and 
 |-  ( ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) -> ( ( dom g i^i dom h ) C_ A /\ A. a e. ( dom g i^i dom h ) Pred ( R , A , a ) C_ ( dom g i^i dom h ) ) )
60 59 exlimivv 
 |-  ( E. b E. c ( ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) -> ( ( dom g i^i dom h ) C_ A /\ A. a e. ( dom g i^i dom h ) Pred ( R , A , a ) C_ ( dom g i^i dom h ) ) )
61 28 60 sylbir 
 |-  ( ( E. b ( g Fn b /\ ( b C_ A /\ A. a e. b Pred ( R , A , a ) C_ b ) /\ A. a e. b ( g ` a ) = ( a G ( g |` Pred ( R , A , a ) ) ) ) /\ E. c ( h Fn c /\ ( c C_ A /\ A. a e. c Pred ( R , A , a ) C_ c ) /\ A. a e. c ( h ` a ) = ( a G ( h |` Pred ( R , A , a ) ) ) ) ) -> ( ( dom g i^i dom h ) C_ A /\ A. a e. ( dom g i^i dom h ) Pred ( R , A , a ) C_ ( dom g i^i dom h ) ) )
62 8 27 61 syl2anb 
 |-  ( ( g e. B /\ h e. B ) -> ( ( dom g i^i dom h ) C_ A /\ A. a e. ( dom g i^i dom h ) Pred ( R , A , a ) C_ ( dom g i^i dom h ) ) )
63 62 adantr 
 |-  ( ( ( g e. B /\ h e. B ) /\ a e. ( dom g i^i dom h ) ) -> ( ( dom g i^i dom h ) C_ A /\ A. a e. ( dom g i^i dom h ) Pred ( R , A , a ) C_ ( dom g i^i dom h ) ) )
64 preddowncl 
 |-  ( ( ( dom g i^i dom h ) C_ A /\ A. a e. ( dom g i^i dom h ) Pred ( R , A , a ) C_ ( dom g i^i dom h ) ) -> ( a e. ( dom g i^i dom h ) -> Pred ( R , ( dom g i^i dom h ) , a ) = Pred ( R , A , a ) ) )
65 63 20 64 sylc 
 |-  ( ( ( g e. B /\ h e. B ) /\ a e. ( dom g i^i dom h ) ) -> Pred ( R , ( dom g i^i dom h ) , a ) = Pred ( R , A , a ) )
66 25 65 eqtrid 
 |-  ( ( ( g e. B /\ h e. B ) /\ a e. ( dom g i^i dom h ) ) -> ( ( dom g i^i dom h ) i^i Pred ( R , ( dom g i^i dom h ) , a ) ) = Pred ( R , A , a ) )
67 66 reseq2d 
 |-  ( ( ( g e. B /\ h e. B ) /\ a e. ( dom g i^i dom h ) ) -> ( g |` ( ( dom g i^i dom h ) i^i Pred ( R , ( dom g i^i dom h ) , a ) ) ) = ( g |` Pred ( R , A , a ) ) )
68 22 67 eqtrid 
 |-  ( ( ( g e. B /\ h e. B ) /\ a e. ( dom g i^i dom h ) ) -> ( ( g |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) = ( g |` Pred ( R , A , a ) ) )
69 68 oveq2d 
 |-  ( ( ( g e. B /\ h e. B ) /\ a e. ( dom g i^i dom h ) ) -> ( a G ( ( g |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) = ( a G ( g |` Pred ( R , A , a ) ) ) )
70 19 21 69 3eqtr4d 
 |-  ( ( ( g e. B /\ h e. B ) /\ a e. ( dom g i^i dom h ) ) -> ( ( g |` ( dom g i^i dom h ) ) ` a ) = ( a G ( ( g |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) )
71 70 ralrimiva 
 |-  ( ( g e. B /\ h e. B ) -> A. a e. ( dom g i^i dom h ) ( ( g |` ( dom g i^i dom h ) ) ` a ) = ( a G ( ( g |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) )
72 6 71 jca 
 |-  ( ( g e. B /\ h e. B ) -> ( ( g |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) /\ A. a e. ( dom g i^i dom h ) ( ( g |` ( dom g i^i dom h ) ) ` a ) = ( a G ( ( g |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) ) )