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

Theorem fpwwe 8270
Description: Given any function  F from the powerset of  A to  A, canth2 7016 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 7659. 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 5863 . . . . . 6  |-  ( Y ( F  o.  1st ) R )  =  ( ( F  o.  1st ) `  <. Y ,  R >. )
2 fo1st 6141 . . . . . . . 8  |-  1st : _V -onto-> _V
3 fofn 5455 . . . . . . . 8  |-  ( 1st
: _V -onto-> _V  ->  1st 
Fn  _V )
42, 3ax-mp 8 . . . . . . 7  |-  1st  Fn  _V
5 opex 4239 . . . . . . 7  |-  <. Y ,  R >.  e.  _V
6 fvco2 5596 . . . . . . 7  |-  ( ( 1st  Fn  _V  /\  <. Y ,  R >.  e. 
_V )  ->  (
( F  o.  1st ) `  <. Y ,  R >. )  =  ( F `  ( 1st `  <. Y ,  R >. ) ) )
74, 5, 6mp2an 653 . . . . . 6  |-  ( ( F  o.  1st ) `  <. Y ,  R >. )  =  ( F `
 ( 1st `  <. Y ,  R >. )
)
81, 7eqtri 2305 . . . . 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 4813 . . . . . . . 8  |-  Rel  W
11 brrelex12 4728 . . . . . . . 8  |-  ( ( Rel  W  /\  Y W R )  ->  ( Y  e.  _V  /\  R  e.  _V ) )
1210, 11mpan 651 . . . . . . 7  |-  ( Y W R  ->  ( Y  e.  _V  /\  R  e.  _V ) )
13 op1stg 6134 . . . . . . 7  |-  ( ( Y  e.  _V  /\  R  e.  _V )  ->  ( 1st `  <. Y ,  R >. )  =  Y )
1412, 13syl 15 . . . . . 6  |-  ( Y W R  ->  ( 1st `  <. Y ,  R >. )  =  Y )
1514fveq2d 5531 . . . . 5  |-  ( Y W R  ->  ( F `  ( 1st ` 
<. Y ,  R >. ) )  =  ( F `
 Y ) )
168, 15syl5eq 2329 . . . 4  |-  ( Y W R  ->  ( Y ( F  o.  1st ) R )  =  ( F `  Y
) )
1716eleq1d 2351 . . 3  |-  ( Y W R  ->  (
( Y ( F  o.  1st ) R )  e.  Y  <->  ( F `  Y )  e.  Y
) )
1817pm5.32i 618 . 2  |-  ( ( Y W R  /\  ( Y ( F  o.  1st ) R )  e.  Y )  <->  ( Y W R  /\  ( F `  Y )  e.  Y ) )
19 vex 2793 . . . . . . . . . 10  |-  r  e. 
_V
20 cnvexg 5210 . . . . . . . . . 10  |-  ( r  e.  _V  ->  `' r  e.  _V )
21 imaexg 5028 . . . . . . . . . 10  |-  ( `' r  e.  _V  ->  ( `' r " {
y } )  e. 
_V )
2219, 20, 21mp2b 9 . . . . . . . . 9  |-  ( `' r " { y } )  e.  _V
23 vex 2793 . . . . . . . . . . . 12  |-  u  e. 
_V
2419inex1 4157 . . . . . . . . . . . 12  |-  ( r  i^i  ( u  X.  u ) )  e. 
_V
2523, 24algrflem 6226 . . . . . . . . . . 11  |-  ( u ( F  o.  1st ) ( r  i^i  ( u  X.  u
) ) )  =  ( F `  u
)
26 fveq2 5527 . . . . . . . . . . 11  |-  ( u  =  ( `' r
" { y } )  ->  ( F `  u )  =  ( F `  ( `' r " { y } ) ) )
2725, 26syl5eq 2329 . . . . . . . . . 10  |-  ( u  =  ( `' r
" { y } )  ->  ( u
( F  o.  1st ) ( r  i^i  ( u  X.  u
) ) )  =  ( F `  ( `' r " {
y } ) ) )
2827eqeq1d 2293 . . . . . . . . 9  |-  ( u  =  ( `' r
" { y } )  ->  ( (
u ( F  o.  1st ) ( r  i^i  ( u  X.  u
) ) )  =  y  <->  ( F `  ( `' r " {
y } ) )  =  y ) )
2922, 28sbcie 3027 . . . . . . . 8  |-  ( [. ( `' r " {
y } )  /  u ]. ( u ( F  o.  1st )
( r  i^i  (
u  X.  u ) ) )  =  y  <-> 
( F `  ( `' r " {
y } ) )  =  y )
3029ralbii 2569 . . . . . . 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 675 . . . . . 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 675 . . . . 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 4085 . . . 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 2308 . . 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 2793 . . . . 5  |-  x  e. 
_V
3736, 19algrflem 6226 . . . 4  |-  ( x ( F  o.  1st ) r )  =  ( F `  x
)
38 simp1 955 . . . . . . 7  |-  ( ( x  C_  A  /\  r  C_  ( x  X.  x )  /\  r  We  x )  ->  x  C_  A )
3936elpw 3633 . . . . . . 7  |-  ( x  e.  ~P A  <->  x  C_  A
)
4038, 39sylibr 203 . . . . . 6  |-  ( ( x  C_  A  /\  r  C_  ( x  X.  x )  /\  r  We  x )  ->  x  e.  ~P A )
41 19.8a 1720 . . . . . . . 8  |-  ( r  We  x  ->  E. r 
r  We  x )
42413ad2ant3 978 . . . . . . 7  |-  ( ( x  C_  A  /\  r  C_  ( x  X.  x )  /\  r  We  x )  ->  E. r 
r  We  x )
43 ween 7664 . . . . . . 7  |-  ( x  e.  dom  card  <->  E. r 
r  We  x )
4442, 43sylibr 203 . . . . . 6  |-  ( ( x  C_  A  /\  r  C_  ( x  X.  x )  /\  r  We  x )  ->  x  e.  dom  card )
45 elin 3360 . . . . . 6  |-  ( x  e.  ( ~P A  i^i  dom  card )  <->  ( x  e.  ~P A  /\  x  e.  dom  card ) )
4640, 44, 45sylanbrc 645 . . . . 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 460 . . . 4  |-  ( (
ph  /\  ( x  C_  A  /\  r  C_  ( x  X.  x
)  /\  r  We  x ) )  -> 
( F `  x
)  e.  A )
4937, 48syl5eqel 2369 . . 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 8267 . 2  |-  ( ph  ->  ( ( Y W R  /\  ( Y ( F  o.  1st ) R )  e.  Y
)  <->  ( Y  =  X  /\  R  =  ( W `  X
) ) ) )
5218, 51syl5bbr 250 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 176    /\ wa 358    /\ w3a 934   E.wex 1530    = wceq 1625    e. wcel 1686   A.wral 2545   _Vcvv 2790   [.wsbc 2993    i^i cin 3153    C_ wss 3154   ~Pcpw 3627   {csn 3642   <.cop 3645   U.cuni 3829   class class class wbr 4025   {copab 4078    We wwe 4353    X. cxp 4689   `'ccnv 4690   dom cdm 4691   "cima 4694    o. ccom 4695   Rel wrel 4696    Fn wfn 5252   -onto->wfo 5255   ` cfv 5257  (class class class)co 5860   1stc1st 6122   cardccrd 7570
This theorem is referenced by:  canth4  8271  canthnumlem  8272  canthp1lem2  8277
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1535  ax-5 1546  ax-17 1605  ax-9 1637  ax-8 1645  ax-13 1688  ax-14 1690  ax-6 1705  ax-7 1710  ax-11 1717  ax-12 1868  ax-ext 2266  ax-rep 4133  ax-sep 4143  ax-nul 4151  ax-pow 4190  ax-pr 4216  ax-un 4514
This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3or 935  df-3an 936  df-tru 1310  df-ex 1531  df-nf 1534  df-sb 1632  df-eu 2149  df-mo 2150  df-clab 2272  df-cleq 2278  df-clel 2281  df-nfc 2410  df-ne 2450  df-ral 2550  df-rex 2551  df-reu 2552  df-rmo 2553  df-rab 2554  df-v 2792  df-sbc 2994  df-csb 3084  df-dif 3157  df-un 3159  df-in 3161  df-ss 3168  df-pss 3170  df-nul 3458  df-if 3568  df-pw 3629  df-sn 3648  df-pr 3649  df-tp 3650  df-op 3651  df-uni 3830  df-int 3865  df-iun 3909  df-br 4026  df-opab 4080  df-mpt 4081  df-tr 4116  df-eprel 4307  df-id 4311  df-po 4316  df-so 4317  df-fr 4354  df-se 4355  df-we 4356  df-ord 4397  df-on 4398  df-lim 4399  df-suc 4400  df-xp 4697  df-rel 4698  df-cnv 4699  df-co 4700  df-dm 4701  df-rn 4702  df-res 4703  df-ima 4704  df-iota 5221  df-fun 5259  df-fn 5260  df-f 5261  df-f1 5262  df-fo 5263  df-f1o 5264  df-fv 5265  df-isom 5266  df-ov 5863  df-1st 6124  df-riota 6306  df-recs 6390  df-en 6866  df-oi 7227  df-card 7574
  Copyright terms: Public domain W3C validator