MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  fpwwe Unicode version

Theorem fpwwe 8485
Description: Given any function  F from the powerset of  A to  A, canth2 7227 gives that the function is not injective, but we can say rather more than that. There is a unique well-ordered subset  <. X , 
( W `  X
) >. which "agrees" with  F in the sense that each initial segment maps to its upper bound, and such that the entire set maps to an element of the set (so that it cannot be extended without losing the well-ordering). This theorem can be used to prove dfac8a 7875. Theorem 1.1 of [KanamoriPincus] p. 415. (Contributed by Mario Carneiro, 18-May-2015.)
Hypotheses
Ref Expression
fpwwe.1  |-  W  =  { <. x ,  r
>.  |  ( (
x  C_  A  /\  r  C_  ( x  X.  x ) )  /\  ( r  We  x  /\  A. y  e.  x  ( F `  ( `' r " { y } ) )  =  y ) ) }
fpwwe.2  |-  ( ph  ->  A  e.  _V )
fpwwe.3  |-  ( (
ph  /\  x  e.  ( ~P A  i^i  dom  card ) )  ->  ( F `  x )  e.  A )
fpwwe.4  |-  X  = 
U. dom  W
Assertion
Ref Expression
fpwwe  |-  ( ph  ->  ( ( Y W R  /\  ( F `
 Y )  e.  Y )  <->  ( Y  =  X  /\  R  =  ( W `  X
) ) ) )
Distinct variable groups:    x, r, A    y, r, F, x    ph, r, x, y    R, r, x, y    X, r, x, y    Y, r, x, y    W, r, x, y
Allowed substitution hint:    A( y)

Proof of Theorem fpwwe
Dummy variable  u is distinct from all other variables.
StepHypRef Expression
1 df-ov 6051 . . . . . 6  |-  ( Y ( F  o.  1st ) R )  =  ( ( F  o.  1st ) `  <. Y ,  R >. )
2 fo1st 6333 . . . . . . . 8  |-  1st : _V -onto-> _V
3 fofn 5622 . . . . . . . 8  |-  ( 1st
: _V -onto-> _V  ->  1st 
Fn  _V )
42, 3ax-mp 8 . . . . . . 7  |-  1st  Fn  _V
5 opex 4395 . . . . . . 7  |-  <. Y ,  R >.  e.  _V
6 fvco2 5765 . . . . . . 7  |-  ( ( 1st  Fn  _V  /\  <. Y ,  R >.  e. 
_V )  ->  (
( F  o.  1st ) `  <. Y ,  R >. )  =  ( F `  ( 1st `  <. Y ,  R >. ) ) )
74, 5, 6mp2an 654 . . . . . 6  |-  ( ( F  o.  1st ) `  <. Y ,  R >. )  =  ( F `
 ( 1st `  <. Y ,  R >. )
)
81, 7eqtri 2432 . . . . 5  |-  ( Y ( F  o.  1st ) R )  =  ( F `  ( 1st `  <. Y ,  R >. ) )
9 fpwwe.1 . . . . . . . . 9  |-  W  =  { <. x ,  r
>.  |  ( (
x  C_  A  /\  r  C_  ( x  X.  x ) )  /\  ( r  We  x  /\  A. y  e.  x  ( F `  ( `' r " { y } ) )  =  y ) ) }
109relopabi 4967 . . . . . . . 8  |-  Rel  W
11 brrelex12 4882 . . . . . . . 8  |-  ( ( Rel  W  /\  Y W R )  ->  ( Y  e.  _V  /\  R  e.  _V ) )
1210, 11mpan 652 . . . . . . 7  |-  ( Y W R  ->  ( Y  e.  _V  /\  R  e.  _V ) )
13 op1stg 6326 . . . . . . 7  |-  ( ( Y  e.  _V  /\  R  e.  _V )  ->  ( 1st `  <. Y ,  R >. )  =  Y )
1412, 13syl 16 . . . . . 6  |-  ( Y W R  ->  ( 1st `  <. Y ,  R >. )  =  Y )
1514fveq2d 5699 . . . . 5  |-  ( Y W R  ->  ( F `  ( 1st ` 
<. Y ,  R >. ) )  =  ( F `
 Y ) )
168, 15syl5eq 2456 . . . 4  |-  ( Y W R  ->  ( Y ( F  o.  1st ) R )  =  ( F `  Y
) )
1716eleq1d 2478 . . 3  |-  ( Y W R  ->  (
( Y ( F  o.  1st ) R )  e.  Y  <->  ( F `  Y )  e.  Y
) )
1817pm5.32i 619 . 2  |-  ( ( Y W R  /\  ( Y ( F  o.  1st ) R )  e.  Y )  <->  ( Y W R  /\  ( F `  Y )  e.  Y ) )
19 vex 2927 . . . . . . . . . 10  |-  r  e. 
_V
20 cnvexg 5372 . . . . . . . . . 10  |-  ( r  e.  _V  ->  `' r  e.  _V )
21 imaexg 5184 . . . . . . . . . 10  |-  ( `' r  e.  _V  ->  ( `' r " {
y } )  e. 
_V )
2219, 20, 21mp2b 10 . . . . . . . . 9  |-  ( `' r " { y } )  e.  _V
23 vex 2927 . . . . . . . . . . . 12  |-  u  e. 
_V
2419inex1 4312 . . . . . . . . . . . 12  |-  ( r  i^i  ( u  X.  u ) )  e. 
_V
2523, 24algrflem 6422 . . . . . . . . . . 11  |-  ( u ( F  o.  1st ) ( r  i^i  ( u  X.  u
) ) )  =  ( F `  u
)
26 fveq2 5695 . . . . . . . . . . 11  |-  ( u  =  ( `' r
" { y } )  ->  ( F `  u )  =  ( F `  ( `' r " { y } ) ) )
2725, 26syl5eq 2456 . . . . . . . . . 10  |-  ( u  =  ( `' r
" { y } )  ->  ( u
( F  o.  1st ) ( r  i^i  ( u  X.  u
) ) )  =  ( F `  ( `' r " {
y } ) ) )
2827eqeq1d 2420 . . . . . . . . 9  |-  ( u  =  ( `' r
" { y } )  ->  ( (
u ( F  o.  1st ) ( r  i^i  ( u  X.  u
) ) )  =  y  <->  ( F `  ( `' r " {
y } ) )  =  y ) )
2922, 28sbcie 3163 . . . . . . . 8  |-  ( [. ( `' r " {
y } )  /  u ]. ( u ( F  o.  1st )
( r  i^i  (
u  X.  u ) ) )  =  y  <-> 
( F `  ( `' r " {
y } ) )  =  y )
3029ralbii 2698 . . . . . . 7  |-  ( A. y  e.  x  [. ( `' r " {
y } )  /  u ]. ( u ( F  o.  1st )
( r  i^i  (
u  X.  u ) ) )  =  y  <->  A. y  e.  x  ( F `  ( `' r " { y } ) )  =  y )
3130anbi2i 676 . . . . . 6  |-  ( ( r  We  x  /\  A. y  e.  x  [. ( `' r " {
y } )  /  u ]. ( u ( F  o.  1st )
( r  i^i  (
u  X.  u ) ) )  =  y )  <->  ( r  We  x  /\  A. y  e.  x  ( F `  ( `' r " { y } ) )  =  y ) )
3231anbi2i 676 . . . . 5  |-  ( ( ( x  C_  A  /\  r  C_  ( x  X.  x ) )  /\  ( r  We  x  /\  A. y  e.  x  [. ( `' r " { y } )  /  u ]. ( u ( F  o.  1st ) ( r  i^i  ( u  X.  u ) ) )  =  y ) )  <->  ( ( x 
C_  A  /\  r  C_  ( x  X.  x
) )  /\  (
r  We  x  /\  A. y  e.  x  ( F `  ( `' r " { y } ) )  =  y ) ) )
3332opabbii 4240 . . . 4  |-  { <. x ,  r >.  |  ( ( x  C_  A  /\  r  C_  ( x  X.  x ) )  /\  ( r  We  x  /\  A. y  e.  x  [. ( `' r " { y } )  /  u ]. ( u ( F  o.  1st ) ( r  i^i  ( u  X.  u ) ) )  =  y ) ) }  =  { <. x ,  r >.  |  ( ( x 
C_  A  /\  r  C_  ( x  X.  x
) )  /\  (
r  We  x  /\  A. y  e.  x  ( F `  ( `' r " { y } ) )  =  y ) ) }
349, 33eqtr4i 2435 . . 3  |-  W  =  { <. x ,  r
>.  |  ( (
x  C_  A  /\  r  C_  ( x  X.  x ) )  /\  ( r  We  x  /\  A. y  e.  x  [. ( `' r " { y } )  /  u ]. (
u ( F  o.  1st ) ( r  i^i  ( u  X.  u
) ) )  =  y ) ) }
35 fpwwe.2 . . 3  |-  ( ph  ->  A  e.  _V )
36 vex 2927 . . . . 5  |-  x  e. 
_V
3736, 19algrflem 6422 . . . 4  |-  ( x ( F  o.  1st ) r )  =  ( F `  x
)
38 simp1 957 . . . . . . 7  |-  ( ( x  C_  A  /\  r  C_  ( x  X.  x )  /\  r  We  x )  ->  x  C_  A )
3936elpw 3773 . . . . . . 7  |-  ( x  e.  ~P A  <->  x  C_  A
)
4038, 39sylibr 204 . . . . . 6  |-  ( ( x  C_  A  /\  r  C_  ( x  X.  x )  /\  r  We  x )  ->  x  e.  ~P A )
41 19.8a 1758 . . . . . . . 8  |-  ( r  We  x  ->  E. r 
r  We  x )
42413ad2ant3 980 . . . . . . 7  |-  ( ( x  C_  A  /\  r  C_  ( x  X.  x )  /\  r  We  x )  ->  E. r 
r  We  x )
43 ween 7880 . . . . . . 7  |-  ( x  e.  dom  card  <->  E. r 
r  We  x )
4442, 43sylibr 204 . . . . . 6  |-  ( ( x  C_  A  /\  r  C_  ( x  X.  x )  /\  r  We  x )  ->  x  e.  dom  card )
45 elin 3498 . . . . . 6  |-  ( x  e.  ( ~P A  i^i  dom  card )  <->  ( x  e.  ~P A  /\  x  e.  dom  card ) )
4640, 44, 45sylanbrc 646 . . . . 5  |-  ( ( x  C_  A  /\  r  C_  ( x  X.  x )  /\  r  We  x )  ->  x  e.  ( ~P A  i^i  dom 
card ) )
47 fpwwe.3 . . . . 5  |-  ( (
ph  /\  x  e.  ( ~P A  i^i  dom  card ) )  ->  ( F `  x )  e.  A )
4846, 47sylan2 461 . . . 4  |-  ( (
ph  /\  ( x  C_  A  /\  r  C_  ( x  X.  x
)  /\  r  We  x ) )  -> 
( F `  x
)  e.  A )
4937, 48syl5eqel 2496 . . 3  |-  ( (
ph  /\  ( x  C_  A  /\  r  C_  ( x  X.  x
)  /\  r  We  x ) )  -> 
( x ( F  o.  1st ) r )  e.  A )
50 fpwwe.4 . . 3  |-  X  = 
U. dom  W
5134, 35, 49, 50fpwwe2 8482 . 2  |-  ( ph  ->  ( ( Y W R  /\  ( Y ( F  o.  1st ) R )  e.  Y
)  <->  ( Y  =  X  /\  R  =  ( W `  X
) ) ) )
5218, 51syl5bbr 251 1  |-  ( ph  ->  ( ( Y W R  /\  ( F `
 Y )  e.  Y )  <->  ( Y  =  X  /\  R  =  ( W `  X
) ) ) )
Colors of variables: wff set class
Syntax hints:    -> wi 4    <-> wb 177    /\ wa 359    /\ w3a 936   E.wex 1547    = wceq 1649    e. wcel 1721   A.wral 2674   _Vcvv 2924   [.wsbc 3129    i^i cin 3287    C_ wss 3288   ~Pcpw 3767   {csn 3782   <.cop 3785   U.cuni 3983   class class class wbr 4180   {copab 4233    We wwe 4508    X. cxp 4843   `'ccnv 4844   dom cdm 4845   "cima 4848    o. ccom 4849   Rel wrel 4850    Fn wfn 5416   -onto->wfo 5419   ` cfv 5421  (class class class)co 6048   1stc1st 6314   cardccrd 7786
This theorem is referenced by:  canth4  8486  canthnumlem  8487  canthp1lem2  8492
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1662  ax-8 1683  ax-13 1723  ax-14 1725  ax-6 1740  ax-7 1745  ax-11 1757  ax-12 1946  ax-ext 2393  ax-rep 4288  ax-sep 4298  ax-nul 4306  ax-pow 4345  ax-pr 4371  ax-un 4668
This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2266  df-mo 2267  df-clab 2399  df-cleq 2405  df-clel 2408  df-nfc 2537  df-ne 2577  df-ral 2679  df-rex 2680  df-reu 2681  df-rmo 2682  df-rab 2683  df-v 2926  df-sbc 3130  df-csb 3220  df-dif 3291  df-un 3293  df-in 3295  df-ss 3302  df-pss 3304  df-nul 3597  df-if 3708  df-pw 3769  df-sn 3788  df-pr 3789  df-tp 3790  df-op 3791  df-uni 3984  df-int 4019  df-iun 4063  df-br 4181  df-opab 4235  df-mpt 4236  df-tr 4271  df-eprel 4462  df-id 4466  df-po 4471  df-so 4472  df-fr 4509  df-se 4510  df-we 4511  df-ord 4552  df-on 4553  df-lim 4554  df-suc 4555  df-xp 4851  df-rel 4852  df-cnv 4853  df-co 4854  df-dm 4855  df-rn 4856  df-res 4857  df-ima 4858  df-iota 5385  df-fun 5423  df-fn 5424  df-f 5425  df-f1 5426  df-fo 5427  df-f1o 5428  df-fv 5429  df-isom 5430  df-ov 6051  df-1st 6316  df-riota 6516  df-recs 6600  df-en 7077  df-oi 7443  df-card 7790
  Copyright terms: Public domain W3C validator