Metamath Proof Explorer

Theorem fprlem1

Description: Lemma for well-founded recursion with a partial order. Two acceptable functions are compatible. (Contributed by Scott Fenton, 11-Sep-2023)

Ref Expression
Hypotheses fprlem.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 ) ) ) ) }
fprlem.2 
|- F = frecs ( R , A , G )
Assertion fprlem1 
|- ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> ( ( x g u /\ x h v ) -> u = v ) )

Proof

Step Hyp Ref Expression
1 fprlem.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 fprlem.2 
 |-  F = frecs ( R , A , G )
3 vex 
 |-  x e. _V
4 vex 
 |-  u e. _V
5 3 4 breldm 
 |-  ( x g u -> x e. dom g )
6 vex 
 |-  v e. _V
7 3 6 breldm 
 |-  ( x h v -> x e. dom h )
8 elin 
 |-  ( x e. ( dom g i^i dom h ) <-> ( x e. dom g /\ x e. dom h ) )
9 8 biimpri 
 |-  ( ( x e. dom g /\ x e. dom h ) -> x e. ( dom g i^i dom h ) )
10 5 7 9 syl2an 
 |-  ( ( x g u /\ x h v ) -> x e. ( dom g i^i dom h ) )
11 id 
 |-  ( ( x g u /\ x h v ) -> ( x g u /\ x h v ) )
12 4 brresi 
 |-  ( x ( g |` ( dom g i^i dom h ) ) u <-> ( x e. ( dom g i^i dom h ) /\ x g u ) )
13 6 brresi 
 |-  ( x ( h |` ( dom g i^i dom h ) ) v <-> ( x e. ( dom g i^i dom h ) /\ x h v ) )
14 12 13 anbi12i 
 |-  ( ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( h |` ( dom g i^i dom h ) ) v ) <-> ( ( x e. ( dom g i^i dom h ) /\ x g u ) /\ ( x e. ( dom g i^i dom h ) /\ x h v ) ) )
15 an4 
 |-  ( ( ( x e. ( dom g i^i dom h ) /\ x g u ) /\ ( x e. ( dom g i^i dom h ) /\ x h v ) ) <-> ( ( x e. ( dom g i^i dom h ) /\ x e. ( dom g i^i dom h ) ) /\ ( x g u /\ x h v ) ) )
16 14 15 bitri 
 |-  ( ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( h |` ( dom g i^i dom h ) ) v ) <-> ( ( x e. ( dom g i^i dom h ) /\ x e. ( dom g i^i dom h ) ) /\ ( x g u /\ x h v ) ) )
17 10 10 11 16 syl21anbrc 
 |-  ( ( x g u /\ x h v ) -> ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( h |` ( dom g i^i dom h ) ) v ) )
18 inss2 
 |-  ( dom g i^i dom h ) C_ dom h
19 1 frrlem3 
 |-  ( h e. B -> dom h C_ A )
20 18 19 sstrid 
 |-  ( h e. B -> ( dom g i^i dom h ) C_ A )
21 20 adantl 
 |-  ( ( g e. B /\ h e. B ) -> ( dom g i^i dom h ) C_ A )
22 21 adantl 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> ( dom g i^i dom h ) C_ A )
23 simpl1 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> R Fr A )
24 frss 
 |-  ( ( dom g i^i dom h ) C_ A -> ( R Fr A -> R Fr ( dom g i^i dom h ) ) )
25 22 23 24 sylc 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> R Fr ( dom g i^i dom h ) )
26 simpl2 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> R Po A )
27 poss 
 |-  ( ( dom g i^i dom h ) C_ A -> ( R Po A -> R Po ( dom g i^i dom h ) ) )
28 22 26 27 sylc 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> R Po ( dom g i^i dom h ) )
29 simpl3 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> R Se A )
30 sess2 
 |-  ( ( dom g i^i dom h ) C_ A -> ( R Se A -> R Se ( dom g i^i dom h ) ) )
31 22 29 30 sylc 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> R Se ( dom g i^i dom h ) )
32 1 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 ) ) ) ) )
33 32 adantl 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( 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 ) ) ) ) )
34 1 frrlem4 
 |-  ( ( h e. B /\ g e. B ) -> ( ( h |` ( dom h i^i dom g ) ) Fn ( dom h i^i dom g ) /\ A. a e. ( dom h i^i dom g ) ( ( h |` ( dom h i^i dom g ) ) ` a ) = ( a G ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) ) ) ) )
35 incom 
 |-  ( dom g i^i dom h ) = ( dom h i^i dom g )
36 35 reseq2i 
 |-  ( h |` ( dom g i^i dom h ) ) = ( h |` ( dom h i^i dom g ) )
37 fneq12 
 |-  ( ( ( h |` ( dom g i^i dom h ) ) = ( h |` ( dom h i^i dom g ) ) /\ ( dom g i^i dom h ) = ( dom h i^i dom g ) ) -> ( ( h |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) <-> ( h |` ( dom h i^i dom g ) ) Fn ( dom h i^i dom g ) ) )
38 36 35 37 mp2an 
 |-  ( ( h |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) <-> ( h |` ( dom h i^i dom g ) ) Fn ( dom h i^i dom g ) )
39 36 fveq1i 
 |-  ( ( h |` ( dom g i^i dom h ) ) ` a ) = ( ( h |` ( dom h i^i dom g ) ) ` a )
40 predeq2 
 |-  ( ( dom g i^i dom h ) = ( dom h i^i dom g ) -> Pred ( R , ( dom g i^i dom h ) , a ) = Pred ( R , ( dom h i^i dom g ) , a ) )
41 35 40 ax-mp 
 |-  Pred ( R , ( dom g i^i dom h ) , a ) = Pred ( R , ( dom h i^i dom g ) , a )
42 36 41 reseq12i 
 |-  ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) = ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) )
43 42 oveq2i 
 |-  ( a G ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) = ( a G ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) ) )
44 39 43 eqeq12i 
 |-  ( ( ( h |` ( dom g i^i dom h ) ) ` a ) = ( a G ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) <-> ( ( h |` ( dom h i^i dom g ) ) ` a ) = ( a G ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) ) ) )
45 35 44 raleqbii 
 |-  ( A. a e. ( dom g i^i dom h ) ( ( h |` ( dom g i^i dom h ) ) ` a ) = ( a G ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) <-> A. a e. ( dom h i^i dom g ) ( ( h |` ( dom h i^i dom g ) ) ` a ) = ( a G ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) ) ) )
46 38 45 anbi12i 
 |-  ( ( ( h |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) /\ A. a e. ( dom g i^i dom h ) ( ( h |` ( dom g i^i dom h ) ) ` a ) = ( a G ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) ) <-> ( ( h |` ( dom h i^i dom g ) ) Fn ( dom h i^i dom g ) /\ A. a e. ( dom h i^i dom g ) ( ( h |` ( dom h i^i dom g ) ) ` a ) = ( a G ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) ) ) ) )
47 34 46 sylibr 
 |-  ( ( h e. B /\ g e. B ) -> ( ( h |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) /\ A. a e. ( dom g i^i dom h ) ( ( h |` ( dom g i^i dom h ) ) ` a ) = ( a G ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) ) )
48 47 ancoms 
 |-  ( ( g e. B /\ h e. B ) -> ( ( h |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) /\ A. a e. ( dom g i^i dom h ) ( ( h |` ( dom g i^i dom h ) ) ` a ) = ( a G ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) ) )
49 48 adantl 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> ( ( h |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) /\ A. a e. ( dom g i^i dom h ) ( ( h |` ( dom g i^i dom h ) ) ` a ) = ( a G ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) ) )
50 fpr3g 
 |-  ( ( ( R Fr ( dom g i^i dom h ) /\ R Po ( dom g i^i dom h ) /\ R Se ( dom g i^i dom h ) ) /\ ( ( 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 ) ) ) ) /\ ( ( h |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) /\ A. a e. ( dom g i^i dom h ) ( ( h |` ( dom g i^i dom h ) ) ` a ) = ( a G ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) ) ) -> ( g |` ( dom g i^i dom h ) ) = ( h |` ( dom g i^i dom h ) ) )
51 25 28 31 33 49 50 syl311anc 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> ( g |` ( dom g i^i dom h ) ) = ( h |` ( dom g i^i dom h ) ) )
52 51 breqd 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> ( x ( g |` ( dom g i^i dom h ) ) v <-> x ( h |` ( dom g i^i dom h ) ) v ) )
53 52 biimprd 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> ( x ( h |` ( dom g i^i dom h ) ) v -> x ( g |` ( dom g i^i dom h ) ) v ) )
54 1 frrlem2 
 |-  ( g e. B -> Fun g )
55 54 ad2antrl 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> Fun g )
56 funres 
 |-  ( Fun g -> Fun ( g |` ( dom g i^i dom h ) ) )
57 dffun2 
 |-  ( Fun ( g |` ( dom g i^i dom h ) ) <-> ( Rel ( g |` ( dom g i^i dom h ) ) /\ A. x A. u A. v ( ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( g |` ( dom g i^i dom h ) ) v ) -> u = v ) ) )
58 2sp 
 |-  ( A. u A. v ( ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( g |` ( dom g i^i dom h ) ) v ) -> u = v ) -> ( ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( g |` ( dom g i^i dom h ) ) v ) -> u = v ) )
59 58 sps 
 |-  ( A. x A. u A. v ( ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( g |` ( dom g i^i dom h ) ) v ) -> u = v ) -> ( ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( g |` ( dom g i^i dom h ) ) v ) -> u = v ) )
60 57 59 simplbiim 
 |-  ( Fun ( g |` ( dom g i^i dom h ) ) -> ( ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( g |` ( dom g i^i dom h ) ) v ) -> u = v ) )
61 55 56 60 3syl 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> ( ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( g |` ( dom g i^i dom h ) ) v ) -> u = v ) )
62 53 61 sylan2d 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> ( ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( h |` ( dom g i^i dom h ) ) v ) -> u = v ) )
63 17 62 syl5 
 |-  ( ( ( R Fr A /\ R Po A /\ R Se A ) /\ ( g e. B /\ h e. B ) ) -> ( ( x g u /\ x h v ) -> u = v ) )