Metamath Proof Explorer

Theorem wfrlem5

Description: Lemma for well-founded recursion. The values of two acceptable functions agree within their domains. (Contributed by Scott Fenton, 21-Apr-2011) (Revised by Mario Carneiro, 26-Jun-2015)

Ref Expression
Hypotheses wfrlem5.1 
|- R We A
wfrlem5.2 
|- R Se A
wfrlem5.3 
|- 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 ) = ( F ` ( f |` Pred ( R , A , y ) ) ) ) }
Assertion wfrlem5 
|- ( ( g e. B /\ h e. B ) -> ( ( x g u /\ x h v ) -> u = v ) )

Proof

Step Hyp Ref Expression
1 wfrlem5.1 
 |-  R We A
2 wfrlem5.2 
 |-  R Se A
3 wfrlem5.3 
 |-  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 ) = ( F ` ( f |` Pred ( R , A , y ) ) ) ) }
4 vex 
 |-  x e. _V
5 vex 
 |-  u e. _V
6 4 5 breldm 
 |-  ( x g u -> x e. dom g )
7 vex 
 |-  v e. _V
8 4 7 breldm 
 |-  ( x h v -> x e. dom h )
9 6 8 anim12i 
 |-  ( ( x g u /\ x h v ) -> ( x e. dom g /\ x e. dom h ) )
10 elin 
 |-  ( x e. ( dom g i^i dom h ) <-> ( x e. dom g /\ x e. dom h ) )
11 9 10 sylibr 
 |-  ( ( x g u /\ x h v ) -> x e. ( dom g i^i dom h ) )
12 anandi 
 |-  ( ( x e. ( dom g i^i dom h ) /\ ( x g u /\ x h v ) ) <-> ( ( x e. ( dom g i^i dom h ) /\ x g u ) /\ ( x e. ( dom g i^i dom h ) /\ x h v ) ) )
13 5 brresi 
 |-  ( x ( g |` ( dom g i^i dom h ) ) u <-> ( x e. ( dom g i^i dom h ) /\ x g u ) )
14 7 brresi 
 |-  ( x ( h |` ( dom g i^i dom h ) ) v <-> ( x e. ( dom g i^i dom h ) /\ x h v ) )
15 13 14 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 ) ) )
16 12 15 sylbb2 
 |-  ( ( x e. ( dom g i^i dom h ) /\ ( x g u /\ x h v ) ) -> ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( h |` ( dom g i^i dom h ) ) v ) )
17 11 16 mpancom 
 |-  ( ( 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 3 wfrlem3 
 |-  ( g e. B -> dom g C_ A )
19 ssinss1 
 |-  ( dom g C_ A -> ( dom g i^i dom h ) C_ A )
20 wess 
 |-  ( ( dom g i^i dom h ) C_ A -> ( R We A -> R We ( dom g i^i dom h ) ) )
21 1 20 mpi 
 |-  ( ( dom g i^i dom h ) C_ A -> R We ( dom g i^i dom h ) )
22 sess2 
 |-  ( ( dom g i^i dom h ) C_ A -> ( R Se A -> R Se ( dom g i^i dom h ) ) )
23 2 22 mpi 
 |-  ( ( dom g i^i dom h ) C_ A -> R Se ( dom g i^i dom h ) )
24 21 23 jca 
 |-  ( ( dom g i^i dom h ) C_ A -> ( R We ( dom g i^i dom h ) /\ R Se ( dom g i^i dom h ) ) )
25 18 19 24 3syl 
 |-  ( g e. B -> ( R We ( dom g i^i dom h ) /\ R Se ( dom g i^i dom h ) ) )
26 25 adantr 
 |-  ( ( g e. B /\ h e. B ) -> ( R We ( dom g i^i dom h ) /\ R Se ( dom g i^i dom h ) ) )
27 3 wfrlem4 
 |-  ( ( 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 ) = ( F ` ( ( g |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) ) )
28 3 wfrlem4 
 |-  ( ( 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 ) = ( F ` ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) ) ) ) )
29 28 ancoms 
 |-  ( ( g e. B /\ h 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 ) = ( F ` ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) ) ) ) )
30 incom 
 |-  ( dom g i^i dom h ) = ( dom h i^i dom g )
31 30 reseq2i 
 |-  ( h |` ( dom g i^i dom h ) ) = ( h |` ( dom h i^i dom g ) )
32 31 fneq1i 
 |-  ( ( h |` ( dom g i^i dom h ) ) Fn ( dom g i^i dom h ) <-> ( h |` ( dom h i^i dom g ) ) Fn ( dom g i^i dom h ) )
33 30 fneq2i 
 |-  ( ( h |` ( dom h i^i dom g ) ) Fn ( dom g i^i dom h ) <-> ( h |` ( dom h i^i dom g ) ) Fn ( dom h i^i dom g ) )
34 32 33 bitri 
 |-  ( ( 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 ) )
35 31 fveq1i 
 |-  ( ( h |` ( dom g i^i dom h ) ) ` a ) = ( ( h |` ( dom h i^i dom g ) ) ` a )
36 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 ) )
37 30 36 ax-mp 
 |-  Pred ( R , ( dom g i^i dom h ) , a ) = Pred ( R , ( dom h i^i dom g ) , a )
38 31 37 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 ) )
39 38 fveq2i 
 |-  ( F ` ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) = ( F ` ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) ) )
40 35 39 eqeq12i 
 |-  ( ( ( h |` ( dom g i^i dom h ) ) ` a ) = ( F ` ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) <-> ( ( h |` ( dom h i^i dom g ) ) ` a ) = ( F ` ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) ) ) )
41 30 40 raleqbii 
 |-  ( A. a e. ( dom g i^i dom h ) ( ( h |` ( dom g i^i dom h ) ) ` a ) = ( F ` ( ( 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 ) = ( F ` ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) ) ) )
42 34 41 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 ) = ( F ` ( ( 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 ) = ( F ` ( ( h |` ( dom h i^i dom g ) ) |` Pred ( R , ( dom h i^i dom g ) , a ) ) ) ) )
43 29 42 sylibr 
 |-  ( ( 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 ) = ( F ` ( ( h |` ( dom g i^i dom h ) ) |` Pred ( R , ( dom g i^i dom h ) , a ) ) ) ) )
44 wfr3g 
 |-  ( ( ( R We ( 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 ) = ( F ` ( ( 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 ) = ( F ` ( ( 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 ) ) )
45 26 27 43 44 syl3anc 
 |-  ( ( g e. B /\ h e. B ) -> ( g |` ( dom g i^i dom h ) ) = ( h |` ( dom g i^i dom h ) ) )
46 45 breqd 
 |-  ( ( g e. B /\ h e. B ) -> ( x ( g |` ( dom g i^i dom h ) ) v <-> x ( h |` ( dom g i^i dom h ) ) v ) )
47 46 biimprd 
 |-  ( ( g e. B /\ h e. B ) -> ( x ( h |` ( dom g i^i dom h ) ) v -> x ( g |` ( dom g i^i dom h ) ) v ) )
48 3 wfrlem2 
 |-  ( g e. B -> Fun g )
49 funres 
 |-  ( Fun g -> Fun ( g |` ( dom g i^i dom h ) ) )
50 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 ) ) )
51 50 simprbi 
 |-  ( Fun ( 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 ) )
52 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 ) )
53 52 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 ) )
54 48 49 51 53 4syl 
 |-  ( g e. B -> ( ( x ( g |` ( dom g i^i dom h ) ) u /\ x ( g |` ( dom g i^i dom h ) ) v ) -> u = v ) )
55 54 adantr 
 |-  ( ( 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 ) )
56 47 55 sylan2d 
 |-  ( ( 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 ) )
57 17 56 syl5 
 |-  ( ( g e. B /\ h e. B ) -> ( ( x g u /\ x h v ) -> u = v ) )