Metamath Proof Explorer

Theorem frrlem14

Description: Lemma for well-founded recursion. Finally, we tie all these threads together and show that dom F = A when given the right S . Specifically, we prove that there can be no R -minimal element of ( A \ dom F ) . (Contributed by Scott Fenton, 7-Dec-2022)

Ref Expression
Hypotheses frrlem11.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 ) ) ) ) }
frrlem11.2 
|- F = frecs ( R , A , G )
frrlem11.3 
|- ( ( ph /\ ( g e. B /\ h e. B ) ) -> ( ( x g u /\ x h v ) -> u = v ) )
frrlem11.4 
|- C = ( ( F |` S ) u. { <. z , ( z G ( F |` Pred ( R , A , z ) ) ) >. } )
frrlem12.5 
|- ( ph -> R Fr A )
frrlem12.6 
|- ( ( ph /\ z e. A ) -> Pred ( R , A , z ) C_ S )
frrlem12.7 
|- ( ( ph /\ z e. A ) -> A. w e. S Pred ( R , A , w ) C_ S )
frrlem13.8 
|- ( ( ph /\ z e. A ) -> S e. _V )
frrlem13.9 
|- ( ( ph /\ z e. A ) -> S C_ A )
frrlem14.10 
|- ( ( ph /\ ( A \ dom F ) =/= (/) ) -> E. z e. ( A \ dom F ) Pred ( R , ( A \ dom F ) , z ) = (/) )
Assertion frrlem14 
|- ( ph -> dom F = A )

Proof

Step Hyp Ref Expression
1 frrlem11.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 frrlem11.2 
 |-  F = frecs ( R , A , G )
3 frrlem11.3 
 |-  ( ( ph /\ ( g e. B /\ h e. B ) ) -> ( ( x g u /\ x h v ) -> u = v ) )
4 frrlem11.4 
 |-  C = ( ( F |` S ) u. { <. z , ( z G ( F |` Pred ( R , A , z ) ) ) >. } )
5 frrlem12.5 
 |-  ( ph -> R Fr A )
6 frrlem12.6 
 |-  ( ( ph /\ z e. A ) -> Pred ( R , A , z ) C_ S )
7 frrlem12.7 
 |-  ( ( ph /\ z e. A ) -> A. w e. S Pred ( R , A , w ) C_ S )
8 frrlem13.8 
 |-  ( ( ph /\ z e. A ) -> S e. _V )
9 frrlem13.9 
 |-  ( ( ph /\ z e. A ) -> S C_ A )
10 frrlem14.10 
 |-  ( ( ph /\ ( A \ dom F ) =/= (/) ) -> E. z e. ( A \ dom F ) Pred ( R , ( A \ dom F ) , z ) = (/) )
11 1 2 frrlem7 
 |-  dom F C_ A
12 11 a1i 
 |-  ( ph -> dom F C_ A )
13 eldifn 
 |-  ( z e. ( A \ dom F ) -> -. z e. dom F )
14 13 adantl 
 |-  ( ( ph /\ z e. ( A \ dom F ) ) -> -. z e. dom F )
15 1 2 3 4 5 6 7 8 9 frrlem13 
 |-  ( ( ph /\ ( z e. ( A \ dom F ) /\ Pred ( R , ( A \ dom F ) , z ) = (/) ) ) -> C e. B )
16 elssuni 
 |-  ( C e. B -> C C_ U. B )
17 15 16 syl 
 |-  ( ( ph /\ ( z e. ( A \ dom F ) /\ Pred ( R , ( A \ dom F ) , z ) = (/) ) ) -> C C_ U. B )
18 1 2 frrlem5 
 |-  F = U. B
19 17 18 sseqtrrdi 
 |-  ( ( ph /\ ( z e. ( A \ dom F ) /\ Pred ( R , ( A \ dom F ) , z ) = (/) ) ) -> C C_ F )
20 dmss 
 |-  ( C C_ F -> dom C C_ dom F )
21 19 20 syl 
 |-  ( ( ph /\ ( z e. ( A \ dom F ) /\ Pred ( R , ( A \ dom F ) , z ) = (/) ) ) -> dom C C_ dom F )
22 ssun2 
 |-  { z } C_ ( dom ( F |` S ) u. { z } )
23 vsnid 
 |-  z e. { z }
24 22 23 sselii 
 |-  z e. ( dom ( F |` S ) u. { z } )
25 4 dmeqi 
 |-  dom C = dom ( ( F |` S ) u. { <. z , ( z G ( F |` Pred ( R , A , z ) ) ) >. } )
26 dmun 
 |-  dom ( ( F |` S ) u. { <. z , ( z G ( F |` Pred ( R , A , z ) ) ) >. } ) = ( dom ( F |` S ) u. dom { <. z , ( z G ( F |` Pred ( R , A , z ) ) ) >. } )
27 ovex 
 |-  ( z G ( F |` Pred ( R , A , z ) ) ) e. _V
28 27 dmsnop 
 |-  dom { <. z , ( z G ( F |` Pred ( R , A , z ) ) ) >. } = { z }
29 28 uneq2i 
 |-  ( dom ( F |` S ) u. dom { <. z , ( z G ( F |` Pred ( R , A , z ) ) ) >. } ) = ( dom ( F |` S ) u. { z } )
30 25 26 29 3eqtri 
 |-  dom C = ( dom ( F |` S ) u. { z } )
31 24 30 eleqtrri 
 |-  z e. dom C
32 31 a1i 
 |-  ( ( ph /\ ( z e. ( A \ dom F ) /\ Pred ( R , ( A \ dom F ) , z ) = (/) ) ) -> z e. dom C )
33 21 32 sseldd 
 |-  ( ( ph /\ ( z e. ( A \ dom F ) /\ Pred ( R , ( A \ dom F ) , z ) = (/) ) ) -> z e. dom F )
34 33 expr 
 |-  ( ( ph /\ z e. ( A \ dom F ) ) -> ( Pred ( R , ( A \ dom F ) , z ) = (/) -> z e. dom F ) )
35 14 34 mtod 
 |-  ( ( ph /\ z e. ( A \ dom F ) ) -> -. Pred ( R , ( A \ dom F ) , z ) = (/) )
36 35 nrexdv 
 |-  ( ph -> -. E. z e. ( A \ dom F ) Pred ( R , ( A \ dom F ) , z ) = (/) )
37 df-ne 
 |-  ( ( A \ dom F ) =/= (/) <-> -. ( A \ dom F ) = (/) )
38 37 10 sylan2br 
 |-  ( ( ph /\ -. ( A \ dom F ) = (/) ) -> E. z e. ( A \ dom F ) Pred ( R , ( A \ dom F ) , z ) = (/) )
39 38 ex 
 |-  ( ph -> ( -. ( A \ dom F ) = (/) -> E. z e. ( A \ dom F ) Pred ( R , ( A \ dom F ) , z ) = (/) ) )
40 36 39 mt3d 
 |-  ( ph -> ( A \ dom F ) = (/) )
41 ssdif0 
 |-  ( A C_ dom F <-> ( A \ dom F ) = (/) )
42 40 41 sylibr 
 |-  ( ph -> A C_ dom F )
43 12 42 eqssd 
 |-  ( ph -> dom F = A )