Users' Mathboxes Mathbox for Scott Fenton < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  frrlem1 Unicode version

Theorem frrlem1 24352
Description: Lemma for founded recursion. The final item we are interested in is the union of acceptable functions  B. This lemma just changes bound variables for later use. (Contributed by Paul Chapman, 21-Apr-2012.)
Hypothesis
Ref Expression
frrlem1.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
Ref Expression
frrlem1  |-  B  =  { g  |  E. z ( g  Fn  z  /\  ( z 
C_  A  /\  A. w  e.  z  Pred ( R ,  A ,  w )  C_  z  /\  A. w  e.  z  ( g `  w
)  =  ( w G ( g  |`  Pred ( R ,  A ,  w ) ) ) ) ) }
Distinct variable groups:    A, f,
g, w, x, y, z    f, G, g, w, x, y, z    R, f, g, w, x, y, z
Allowed substitution hints:    B( x, y, z, w, f, g)

Proof of Theorem frrlem1
StepHypRef Expression
1 frrlem1.1 . 2  |-  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 fneq1 5349 . . . . . 6  |-  ( f  =  g  ->  (
f  Fn  x  <->  g  Fn  x ) )
3 fveq1 5540 . . . . . . . . 9  |-  ( f  =  g  ->  (
f `  y )  =  ( g `  y ) )
4 reseq1 4965 . . . . . . . . . 10  |-  ( f  =  g  ->  (
f  |`  Pred ( R ,  A ,  y )
)  =  ( g  |`  Pred ( R ,  A ,  y )
) )
54oveq2d 5890 . . . . . . . . 9  |-  ( f  =  g  ->  (
y G ( f  |`  Pred ( R ,  A ,  y )
) )  =  ( y G ( g  |`  Pred ( R ,  A ,  y )
) ) )
63, 5eqeq12d 2310 . . . . . . . 8  |-  ( f  =  g  ->  (
( f `  y
)  =  ( y G ( f  |`  Pred ( R ,  A ,  y ) ) )  <->  ( g `  y )  =  ( y G ( g  |`  Pred ( R ,  A ,  y )
) ) ) )
76ralbidv 2576 . . . . . . 7  |-  ( f  =  g  ->  ( A. y  e.  x  ( f `  y
)  =  ( y G ( f  |`  Pred ( R ,  A ,  y ) ) )  <->  A. y  e.  x  ( g `  y
)  =  ( y G ( g  |`  Pred ( R ,  A ,  y ) ) ) ) )
873anbi3d 1258 . . . . . 6  |-  ( f  =  g  ->  (
( 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 )
) ) )  <->  ( x  C_  A  /\  A. y  e.  x  Pred ( R ,  A ,  y )  C_  x  /\  A. y  e.  x  ( g `  y )  =  ( y G ( g  |`  Pred ( R ,  A , 
y ) ) ) ) ) )
92, 8anbi12d 691 . . . . 5  |-  ( f  =  g  ->  (
( 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 )
) ) ) )  <-> 
( g  Fn  x  /\  ( x  C_  A  /\  A. y  e.  x  Pred ( R ,  A ,  y )  C_  x  /\  A. y  e.  x  ( g `  y )  =  ( y G ( g  |`  Pred ( R ,  A ,  y )
) ) ) ) ) )
109exbidv 1616 . . . 4  |-  ( f  =  g  ->  ( 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 ) ) ) ) )  <->  E. x
( g  Fn  x  /\  ( x  C_  A  /\  A. y  e.  x  Pred ( R ,  A ,  y )  C_  x  /\  A. y  e.  x  ( g `  y )  =  ( y G ( g  |`  Pred ( R ,  A ,  y )
) ) ) ) ) )
11 fneq2 5350 . . . . . 6  |-  ( x  =  z  ->  (
g  Fn  x  <->  g  Fn  z ) )
12 sseq1 3212 . . . . . . 7  |-  ( x  =  z  ->  (
x  C_  A  <->  z  C_  A ) )
13 sseq2 3213 . . . . . . . . 9  |-  ( x  =  z  ->  ( Pred ( R ,  A ,  y )  C_  x 
<-> 
Pred ( R ,  A ,  y )  C_  z ) )
1413raleqbi1dv 2757 . . . . . . . 8  |-  ( x  =  z  ->  ( A. y  e.  x  Pred ( R ,  A ,  y )  C_  x 
<-> 
A. y  e.  z 
Pred ( R ,  A ,  y )  C_  z ) )
15 predeq3 24242 . . . . . . . . . 10  |-  ( y  =  w  ->  Pred ( R ,  A , 
y )  =  Pred ( R ,  A ,  w ) )
1615sseq1d 3218 . . . . . . . . 9  |-  ( y  =  w  ->  ( Pred ( R ,  A ,  y )  C_  z 
<-> 
Pred ( R ,  A ,  w )  C_  z ) )
1716cbvralv 2777 . . . . . . . 8  |-  ( A. y  e.  z  Pred ( R ,  A , 
y )  C_  z  <->  A. w  e.  z  Pred ( R ,  A ,  w )  C_  z
)
1814, 17syl6bb 252 . . . . . . 7  |-  ( x  =  z  ->  ( A. y  e.  x  Pred ( R ,  A ,  y )  C_  x 
<-> 
A. w  e.  z 
Pred ( R ,  A ,  w )  C_  z ) )
19 raleq 2749 . . . . . . . 8  |-  ( x  =  z  ->  ( A. y  e.  x  ( g `  y
)  =  ( y G ( g  |`  Pred ( R ,  A ,  y ) ) )  <->  A. y  e.  z  ( g `  y
)  =  ( y G ( g  |`  Pred ( R ,  A ,  y ) ) ) ) )
20 fveq2 5541 . . . . . . . . . 10  |-  ( y  =  w  ->  (
g `  y )  =  ( g `  w ) )
21 id 19 . . . . . . . . . . 11  |-  ( y  =  w  ->  y  =  w )
2215reseq2d 4971 . . . . . . . . . . 11  |-  ( y  =  w  ->  (
g  |`  Pred ( R ,  A ,  y )
)  =  ( g  |`  Pred ( R ,  A ,  w )
) )
2321, 22oveq12d 5892 . . . . . . . . . 10  |-  ( y  =  w  ->  (
y G ( g  |`  Pred ( R ,  A ,  y )
) )  =  ( w G ( g  |`  Pred ( R ,  A ,  w )
) ) )
2420, 23eqeq12d 2310 . . . . . . . . 9  |-  ( y  =  w  ->  (
( g `  y
)  =  ( y G ( g  |`  Pred ( R ,  A ,  y ) ) )  <->  ( g `  w )  =  ( w G ( g  |`  Pred ( R ,  A ,  w )
) ) ) )
2524cbvralv 2777 . . . . . . . 8  |-  ( A. y  e.  z  (
g `  y )  =  ( y G ( g  |`  Pred ( R ,  A , 
y ) ) )  <->  A. w  e.  z 
( g `  w
)  =  ( w G ( g  |`  Pred ( R ,  A ,  w ) ) ) )
2619, 25syl6bb 252 . . . . . . 7  |-  ( x  =  z  ->  ( A. y  e.  x  ( g `  y
)  =  ( y G ( g  |`  Pred ( R ,  A ,  y ) ) )  <->  A. w  e.  z  ( g `  w
)  =  ( w G ( g  |`  Pred ( R ,  A ,  w ) ) ) ) )
2712, 18, 263anbi123d 1252 . . . . . 6  |-  ( x  =  z  ->  (
( x  C_  A  /\  A. y  e.  x  Pred ( R ,  A ,  y )  C_  x  /\  A. y  e.  x  ( g `  y )  =  ( y G ( g  |`  Pred ( R ,  A ,  y )
) ) )  <->  ( z  C_  A  /\  A. w  e.  z  Pred ( R ,  A ,  w
)  C_  z  /\  A. w  e.  z  ( g `  w )  =  ( w G ( g  |`  Pred ( R ,  A ,  w ) ) ) ) ) )
2811, 27anbi12d 691 . . . . 5  |-  ( x  =  z  ->  (
( g  Fn  x  /\  ( x  C_  A  /\  A. y  e.  x  Pred ( R ,  A ,  y )  C_  x  /\  A. y  e.  x  ( g `  y )  =  ( y G ( g  |`  Pred ( R ,  A ,  y )
) ) ) )  <-> 
( g  Fn  z  /\  ( z  C_  A  /\  A. w  e.  z 
Pred ( R ,  A ,  w )  C_  z  /\  A. w  e.  z  ( g `  w )  =  ( w G ( g  |`  Pred ( R ,  A ,  w )
) ) ) ) ) )
2928cbvexv 1956 . . . 4  |-  ( E. x ( g  Fn  x  /\  ( x 
C_  A  /\  A. y  e.  x  Pred ( R ,  A , 
y )  C_  x  /\  A. y  e.  x  ( g `  y
)  =  ( y G ( g  |`  Pred ( R ,  A ,  y ) ) ) ) )  <->  E. z
( g  Fn  z  /\  ( z  C_  A  /\  A. w  e.  z 
Pred ( R ,  A ,  w )  C_  z  /\  A. w  e.  z  ( g `  w )  =  ( w G ( g  |`  Pred ( R ,  A ,  w )
) ) ) ) )
3010, 29syl6bb 252 . . 3  |-  ( f  =  g  ->  ( 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 ) ) ) ) )  <->  E. z
( g  Fn  z  /\  ( z  C_  A  /\  A. w  e.  z 
Pred ( R ,  A ,  w )  C_  z  /\  A. w  e.  z  ( g `  w )  =  ( w G ( g  |`  Pred ( R ,  A ,  w )
) ) ) ) ) )
3130cbvabv 2415 . 2  |-  { 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 ) ) ) ) ) }  =  { g  |  E. z ( g  Fn  z  /\  (
z  C_  A  /\  A. w  e.  z  Pred ( R ,  A ,  w )  C_  z  /\  A. w  e.  z  ( g `  w
)  =  ( w G ( g  |`  Pred ( R ,  A ,  w ) ) ) ) ) }
321, 31eqtri 2316 1  |-  B  =  { g  |  E. z ( g  Fn  z  /\  ( z 
C_  A  /\  A. w  e.  z  Pred ( R ,  A ,  w )  C_  z  /\  A. w  e.  z  ( g `  w
)  =  ( w G ( g  |`  Pred ( R ,  A ,  w ) ) ) ) ) }
Colors of variables: wff set class
Syntax hints:    /\ wa 358    /\ w3a 934   E.wex 1531    = wceq 1632   {cab 2282   A.wral 2556    C_ wss 3165    |` cres 4707    Fn wfn 5266   ` cfv 5271  (class class class)co 5874   Predcpred 24238
This theorem is referenced by:  frrlem2  24353  frrlem3  24354  frrlem4  24355  frrlem5e  24360
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1536  ax-5 1547  ax-17 1606  ax-9 1644  ax-8 1661  ax-6 1715  ax-7 1720  ax-11 1727  ax-12 1878  ax-ext 2277
This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3an 936  df-tru 1310  df-ex 1532  df-nf 1535  df-sb 1639  df-clab 2283  df-cleq 2289  df-clel 2292  df-nfc 2421  df-ral 2561  df-rex 2562  df-rab 2565  df-v 2803  df-dif 3168  df-un 3170  df-in 3172  df-ss 3179  df-nul 3469  df-if 3579  df-sn 3659  df-pr 3660  df-op 3662  df-uni 3844  df-br 4040  df-opab 4094  df-xp 4711  df-rel 4712  df-cnv 4713  df-co 4714  df-dm 4715  df-rn 4716  df-res 4717  df-ima 4718  df-iota 5235  df-fun 5273  df-fn 5274  df-fv 5279  df-ov 5877  df-pred 24239
  Copyright terms: Public domain W3C validator