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

Theorem pwfi 7872
Description: The power set of a finite set is finite and vice-versa. Theorem 38 of [Suppes] p. 104 and its converse, Theorem 40 of [Suppes] p. 105. (Contributed by NM, 26-Mar-2007.)
Assertion
Ref Expression
pwfi  |-  ( A  e.  Fin  <->  ~P A  e.  Fin )

Proof of Theorem pwfi
Dummy variables  m  k  c are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 isfi 7597 . . 3  |-  ( A  e.  Fin  <->  E. m  e.  om  A  ~~  m
)
2 pweq 3982 . . . . . . 7  |-  ( m  =  (/)  ->  ~P m  =  ~P (/) )
32eleq1d 2491 . . . . . 6  |-  ( m  =  (/)  ->  ( ~P m  e.  Fin  <->  ~P (/)  e.  Fin ) )
4 pweq 3982 . . . . . . 7  |-  ( m  =  k  ->  ~P m  =  ~P k
)
54eleq1d 2491 . . . . . 6  |-  ( m  =  k  ->  ( ~P m  e.  Fin  <->  ~P k  e.  Fin )
)
6 pweq 3982 . . . . . . . 8  |-  ( m  =  suc  k  ->  ~P m  =  ~P suc  k )
7 df-suc 5445 . . . . . . . . 9  |-  suc  k  =  ( k  u. 
{ k } )
87pweqi 3983 . . . . . . . 8  |-  ~P suc  k  =  ~P (
k  u.  { k } )
96, 8syl6eq 2479 . . . . . . 7  |-  ( m  =  suc  k  ->  ~P m  =  ~P ( k  u.  {
k } ) )
109eleq1d 2491 . . . . . 6  |-  ( m  =  suc  k  -> 
( ~P m  e. 
Fin 
<->  ~P ( k  u. 
{ k } )  e.  Fin ) )
11 pw0 4144 . . . . . . . 8  |-  ~P (/)  =  { (/)
}
12 df1o2 7199 . . . . . . . 8  |-  1o  =  { (/) }
1311, 12eqtr4i 2454 . . . . . . 7  |-  ~P (/)  =  1o
14 1onn 7345 . . . . . . . 8  |-  1o  e.  om
15 ssid 3483 . . . . . . . 8  |-  1o  C_  1o
16 ssnnfi 7794 . . . . . . . 8  |-  ( ( 1o  e.  om  /\  1o  C_  1o )  ->  1o  e.  Fin )
1714, 15, 16mp2an 676 . . . . . . 7  |-  1o  e.  Fin
1813, 17eqeltri 2506 . . . . . 6  |-  ~P (/)  e.  Fin
19 eqid 2422 . . . . . . . 8  |-  ( c  e.  ~P k  |->  ( c  u.  { k } ) )  =  ( c  e.  ~P k  |->  ( c  u. 
{ k } ) )
2019pwfilem 7871 . . . . . . 7  |-  ( ~P k  e.  Fin  ->  ~P ( k  u.  {
k } )  e. 
Fin )
2120a1i 11 . . . . . 6  |-  ( k  e.  om  ->  ( ~P k  e.  Fin  ->  ~P ( k  u. 
{ k } )  e.  Fin ) )
223, 5, 10, 18, 21finds1 6733 . . . . 5  |-  ( m  e.  om  ->  ~P m  e.  Fin )
23 pwen 7748 . . . . 5  |-  ( A 
~~  m  ->  ~P A  ~~  ~P m )
24 enfii 7792 . . . . 5  |-  ( ( ~P m  e.  Fin  /\ 
~P A  ~~  ~P m )  ->  ~P A  e.  Fin )
2522, 23, 24syl2an 479 . . . 4  |-  ( ( m  e.  om  /\  A  ~~  m )  ->  ~P A  e.  Fin )
2625rexlimiva 2913 . . 3  |-  ( E. m  e.  om  A  ~~  m  ->  ~P A  e.  Fin )
271, 26sylbi 198 . 2  |-  ( A  e.  Fin  ->  ~P A  e.  Fin )
28 elex 3090 . . . . 5  |-  ( ~P A  e.  Fin  ->  ~P A  e.  _V )
29 pwexb 6613 . . . . 5  |-  ( A  e.  _V  <->  ~P A  e.  _V )
3028, 29sylibr 215 . . . 4  |-  ( ~P A  e.  Fin  ->  A  e.  _V )
31 canth2g 7729 . . . 4  |-  ( A  e.  _V  ->  A  ~<  ~P A )
32 sdomdom 7601 . . . 4  |-  ( A 
~<  ~P A  ->  A  ~<_  ~P A )
3330, 31, 323syl 18 . . 3  |-  ( ~P A  e.  Fin  ->  A  ~<_  ~P A )
34 domfi 7796 . . 3  |-  ( ( ~P A  e.  Fin  /\  A  ~<_  ~P A )  ->  A  e.  Fin )
3533, 34mpdan 672 . 2  |-  ( ~P A  e.  Fin  ->  A  e.  Fin )
3627, 35impbii 190 1  |-  ( A  e.  Fin  <->  ~P A  e.  Fin )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    <-> wb 187    = wceq 1437    e. wcel 1868   E.wrex 2776   _Vcvv 3081    u. cun 3434    C_ wss 3436   (/)c0 3761   ~Pcpw 3979   {csn 3996   class class class wbr 4420    |-> cmpt 4479   suc csuc 5441   omcom 6703   1oc1o 7180    ~~ cen 7571    ~<_ cdom 7572    ~< csdm 7573   Fincfn 7574
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1665  ax-4 1678  ax-5 1748  ax-6 1794  ax-7 1839  ax-8 1870  ax-9 1872  ax-10 1887  ax-11 1892  ax-12 1905  ax-13 2053  ax-ext 2400  ax-sep 4543  ax-nul 4552  ax-pow 4599  ax-pr 4657  ax-un 6594
This theorem depends on definitions:  df-bi 188  df-or 371  df-an 372  df-3or 983  df-3an 984  df-tru 1440  df-ex 1660  df-nf 1664  df-sb 1787  df-eu 2269  df-mo 2270  df-clab 2408  df-cleq 2414  df-clel 2417  df-nfc 2572  df-ne 2620  df-ral 2780  df-rex 2781  df-reu 2782  df-rab 2784  df-v 3083  df-sbc 3300  df-csb 3396  df-dif 3439  df-un 3441  df-in 3443  df-ss 3450  df-pss 3452  df-nul 3762  df-if 3910  df-pw 3981  df-sn 3997  df-pr 3999  df-tp 4001  df-op 4003  df-uni 4217  df-int 4253  df-iun 4298  df-br 4421  df-opab 4480  df-mpt 4481  df-tr 4516  df-eprel 4761  df-id 4765  df-po 4771  df-so 4772  df-fr 4809  df-we 4811  df-xp 4856  df-rel 4857  df-cnv 4858  df-co 4859  df-dm 4860  df-rn 4861  df-res 4862  df-ima 4863  df-pred 5396  df-ord 5442  df-on 5443  df-lim 5444  df-suc 5445  df-iota 5562  df-fun 5600  df-fn 5601  df-f 5602  df-f1 5603  df-fo 5604  df-f1o 5605  df-fv 5606  df-ov 6305  df-oprab 6306  df-mpt2 6307  df-om 6704  df-1st 6804  df-2nd 6805  df-wrecs 7033  df-recs 7095  df-rdg 7133  df-1o 7187  df-2o 7188  df-oadd 7191  df-er 7368  df-map 7479  df-en 7575  df-dom 7576  df-sdom 7577  df-fin 7578
This theorem is referenced by:  mapfi  7873  r1fin  8246  dfac12k  8578  pwsdompw  8635  ackbij1lem5  8655  ackbij1lem9  8659  ackbij1lem10  8660  ackbij1lem14  8664  ackbij1b  8670  isfin1-2  8816  isfin1-3  8817  domtriomlem  8873  dominf  8876  dominfac  8999  gchhar  9105  omina  9117  gchina  9125  hashpw  12606  hashbclem  12613  qshash  13873  ackbijnn  13874  incexclem  13882  incexc  13883  incexc2  13884  hashbccl  14943  lagsubg2  16866  lagsubg  16867  orbsta2  16956  sylow1lem3  17240  sylow1lem5  17242  sylow2alem2  17258  sylow2a  17259  sylow2blem2  17261  sylow2blem3  17262  sylow3lem3  17269  sylow3lem4  17270  sylow3lem6  17272  pgpfac1lem5  17700  discmp  20400  cmpfi  20410  dis1stc  20501  1stckgenlem  20555  ptcmpfi  20815  fiufl  20918  musum  24107  qerclwwlknfi  25543  hasheuni  28902  coinfliplem  29307  ballotth  29366  ballotthOLD  29404  erdszelem2  29911  kelac2lem  35842  pwinfig  36085
  Copyright terms: Public domain W3C validator