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

Theorem fpwwe 8415
Description: Given any function  F from the powerset of  A to  A, canth2 7157 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 7804. 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 5984 . . . . . 6  |-  ( Y ( F  o.  1st ) R )  =  ( ( F  o.  1st ) `  <. Y ,  R >. )
2 fo1st 6266 . . . . . . . 8  |-  1st : _V -onto-> _V
3 fofn 5559 . . . . . . . 8  |-  ( 1st
: _V -onto-> _V  ->  1st 
Fn  _V )
42, 3ax-mp 8 . . . . . . 7  |-  1st  Fn  _V
5 opex 4340 . . . . . . 7  |-  <. Y ,  R >.  e.  _V
6 fvco2 5701 . . . . . . 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 2386 . . . . 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 4914 . . . . . . . 8  |-  Rel  W
11 brrelex12 4829 . . . . . . . 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 6259 . . . . . . 7  |-  ( ( Y  e.  _V  /\  R  e.  _V )  ->  ( 1st `  <. Y ,  R >. )  =  Y )
1412, 13syl 15 . . . . . 6  |-  ( Y W R  ->  ( 1st `  <. Y ,  R >. )  =  Y )
1514fveq2d 5636 . . . . 5  |-  ( Y W R  ->  ( F `  ( 1st ` 
<. Y ,  R >. ) )  =  ( F `
 Y ) )
168, 15syl5eq 2410 . . . 4  |-  ( Y W R  ->  ( Y ( F  o.  1st ) R )  =  ( F `  Y
) )
1716eleq1d 2432 . . 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 2876 . . . . . . . . . 10  |-  r  e. 
_V
20 cnvexg 5311 . . . . . . . . . 10  |-  ( r  e.  _V  ->  `' r  e.  _V )
21 imaexg 5129 . . . . . . . . . 10  |-  ( `' r  e.  _V  ->  ( `' r " {
y } )  e. 
_V )
2219, 20, 21mp2b 9 . . . . . . . . 9  |-  ( `' r " { y } )  e.  _V
23 vex 2876 . . . . . . . . . . . 12  |-  u  e. 
_V
2419inex1 4257 . . . . . . . . . . . 12  |-  ( r  i^i  ( u  X.  u ) )  e. 
_V
2523, 24algrflem 6352 . . . . . . . . . . 11  |-  ( u ( F  o.  1st ) ( r  i^i  ( u  X.  u
) ) )  =  ( F `  u
)
26 fveq2 5632 . . . . . . . . . . 11  |-  ( u  =  ( `' r
" { y } )  ->  ( F `  u )  =  ( F `  ( `' r " { y } ) ) )
2725, 26syl5eq 2410 . . . . . . . . . 10  |-  ( u  =  ( `' r
" { y } )  ->  ( u
( F  o.  1st ) ( r  i^i  ( u  X.  u
) ) )  =  ( F `  ( `' r " {
y } ) ) )
2827eqeq1d 2374 . . . . . . . . 9  |-  ( u  =  ( `' r
" { y } )  ->  ( (
u ( F  o.  1st ) ( r  i^i  ( u  X.  u
) ) )  =  y  <->  ( F `  ( `' r " {
y } ) )  =  y ) )
2922, 28sbcie 3111 . . . . . . . 8  |-  ( [. ( `' r " {
y } )  /  u ]. ( u ( F  o.  1st )
( r  i^i  (
u  X.  u ) ) )  =  y  <-> 
( F `  ( `' r " {
y } ) )  =  y )
3029ralbii 2652 . . . . . . 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 4185 . . . 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 2389 . . 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 2876 . . . . 5  |-  x  e. 
_V
3736, 19algrflem 6352 . . . 4  |-  ( x ( F  o.  1st ) r )  =  ( F `  x
)
38 simp1 956 . . . . . . 7  |-  ( ( x  C_  A  /\  r  C_  ( x  X.  x )  /\  r  We  x )  ->  x  C_  A )
3936elpw 3720 . . . . . . 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 1752 . . . . . . . 8  |-  ( r  We  x  ->  E. r 
r  We  x )
42413ad2ant3 979 . . . . . . 7  |-  ( ( x  C_  A  /\  r  C_  ( x  X.  x )  /\  r  We  x )  ->  E. r 
r  We  x )
43 ween 7809 . . . . . . 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 3446 . . . . . 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 2450 . . 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 8412 . 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 935   E.wex 1546    = wceq 1647    e. wcel 1715   A.wral 2628   _Vcvv 2873   [.wsbc 3077    i^i cin 3237    C_ wss 3238   ~Pcpw 3714   {csn 3729   <.cop 3732   U.cuni 3929   class class class wbr 4125   {copab 4178    We wwe 4454    X. cxp 4790   `'ccnv 4791   dom cdm 4792   "cima 4795    o. ccom 4796   Rel wrel 4797    Fn wfn 5353   -onto->wfo 5356   ` cfv 5358  (class class class)co 5981   1stc1st 6247   cardccrd 7715
This theorem is referenced by:  canth4  8416  canthnumlem  8417  canthp1lem2  8422
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1551  ax-5 1562  ax-17 1621  ax-9 1659  ax-8 1680  ax-13 1717  ax-14 1719  ax-6 1734  ax-7 1739  ax-11 1751  ax-12 1937  ax-ext 2347  ax-rep 4233  ax-sep 4243  ax-nul 4251  ax-pow 4290  ax-pr 4316  ax-un 4615
This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3or 936  df-3an 937  df-tru 1324  df-ex 1547  df-nf 1550  df-sb 1654  df-eu 2221  df-mo 2222  df-clab 2353  df-cleq 2359  df-clel 2362  df-nfc 2491  df-ne 2531  df-ral 2633  df-rex 2634  df-reu 2635  df-rmo 2636  df-rab 2637  df-v 2875  df-sbc 3078  df-csb 3168  df-dif 3241  df-un 3243  df-in 3245  df-ss 3252  df-pss 3254  df-nul 3544  df-if 3655  df-pw 3716  df-sn 3735  df-pr 3736  df-tp 3737  df-op 3738  df-uni 3930  df-int 3965  df-iun 4009  df-br 4126  df-opab 4180  df-mpt 4181  df-tr 4216  df-eprel 4408  df-id 4412  df-po 4417  df-so 4418  df-fr 4455  df-se 4456  df-we 4457  df-ord 4498  df-on 4499  df-lim 4500  df-suc 4501  df-xp 4798  df-rel 4799  df-cnv 4800  df-co 4801  df-dm 4802  df-rn 4803  df-res 4804  df-ima 4805  df-iota 5322  df-fun 5360  df-fn 5361  df-f 5362  df-f1 5363  df-fo 5364  df-f1o 5365  df-fv 5366  df-isom 5367  df-ov 5984  df-1st 6249  df-riota 6446  df-recs 6530  df-en 7007  df-oi 7372  df-card 7719
  Copyright terms: Public domain W3C validator