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

Theorem pwfi 8246
 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 (𝐴 ∈ Fin ↔ 𝒫 𝐴 ∈ Fin)

Proof of Theorem pwfi
Dummy variables 𝑚 𝑘 𝑐 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 isfi 7964 . . 3 (𝐴 ∈ Fin ↔ ∃𝑚 ∈ ω 𝐴𝑚)
2 pweq 4152 . . . . . . 7 (𝑚 = ∅ → 𝒫 𝑚 = 𝒫 ∅)
32eleq1d 2684 . . . . . 6 (𝑚 = ∅ → (𝒫 𝑚 ∈ Fin ↔ 𝒫 ∅ ∈ Fin))
4 pweq 4152 . . . . . . 7 (𝑚 = 𝑘 → 𝒫 𝑚 = 𝒫 𝑘)
54eleq1d 2684 . . . . . 6 (𝑚 = 𝑘 → (𝒫 𝑚 ∈ Fin ↔ 𝒫 𝑘 ∈ Fin))
6 pweq 4152 . . . . . . . 8 (𝑚 = suc 𝑘 → 𝒫 𝑚 = 𝒫 suc 𝑘)
7 df-suc 5717 . . . . . . . . 9 suc 𝑘 = (𝑘 ∪ {𝑘})
87pweqi 4153 . . . . . . . 8 𝒫 suc 𝑘 = 𝒫 (𝑘 ∪ {𝑘})
96, 8syl6eq 2670 . . . . . . 7 (𝑚 = suc 𝑘 → 𝒫 𝑚 = 𝒫 (𝑘 ∪ {𝑘}))
109eleq1d 2684 . . . . . 6 (𝑚 = suc 𝑘 → (𝒫 𝑚 ∈ Fin ↔ 𝒫 (𝑘 ∪ {𝑘}) ∈ Fin))
11 pw0 4334 . . . . . . . 8 𝒫 ∅ = {∅}
12 df1o2 7557 . . . . . . . 8 1𝑜 = {∅}
1311, 12eqtr4i 2645 . . . . . . 7 𝒫 ∅ = 1𝑜
14 1onn 7704 . . . . . . . 8 1𝑜 ∈ ω
15 ssid 3616 . . . . . . . 8 1𝑜 ⊆ 1𝑜
16 ssnnfi 8164 . . . . . . . 8 ((1𝑜 ∈ ω ∧ 1𝑜 ⊆ 1𝑜) → 1𝑜 ∈ Fin)
1714, 15, 16mp2an 707 . . . . . . 7 1𝑜 ∈ Fin
1813, 17eqeltri 2695 . . . . . 6 𝒫 ∅ ∈ Fin
19 eqid 2620 . . . . . . . 8 (𝑐 ∈ 𝒫 𝑘 ↦ (𝑐 ∪ {𝑘})) = (𝑐 ∈ 𝒫 𝑘 ↦ (𝑐 ∪ {𝑘}))
2019pwfilem 8245 . . . . . . 7 (𝒫 𝑘 ∈ Fin → 𝒫 (𝑘 ∪ {𝑘}) ∈ Fin)
2120a1i 11 . . . . . 6 (𝑘 ∈ ω → (𝒫 𝑘 ∈ Fin → 𝒫 (𝑘 ∪ {𝑘}) ∈ Fin))
223, 5, 10, 18, 21finds1 7080 . . . . 5 (𝑚 ∈ ω → 𝒫 𝑚 ∈ Fin)
23 pwen 8118 . . . . 5 (𝐴𝑚 → 𝒫 𝐴 ≈ 𝒫 𝑚)
24 enfii 8162 . . . . 5 ((𝒫 𝑚 ∈ Fin ∧ 𝒫 𝐴 ≈ 𝒫 𝑚) → 𝒫 𝐴 ∈ Fin)
2522, 23, 24syl2an 494 . . . 4 ((𝑚 ∈ ω ∧ 𝐴𝑚) → 𝒫 𝐴 ∈ Fin)
2625rexlimiva 3024 . . 3 (∃𝑚 ∈ ω 𝐴𝑚 → 𝒫 𝐴 ∈ Fin)
271, 26sylbi 207 . 2 (𝐴 ∈ Fin → 𝒫 𝐴 ∈ Fin)
28 pwexr 6959 . . . 4 (𝒫 𝐴 ∈ Fin → 𝐴 ∈ V)
29 canth2g 8099 . . . 4 (𝐴 ∈ V → 𝐴 ≺ 𝒫 𝐴)
30 sdomdom 7968 . . . 4 (𝐴 ≺ 𝒫 𝐴𝐴 ≼ 𝒫 𝐴)
3128, 29, 303syl 18 . . 3 (𝒫 𝐴 ∈ Fin → 𝐴 ≼ 𝒫 𝐴)
32 domfi 8166 . . 3 ((𝒫 𝐴 ∈ Fin ∧ 𝐴 ≼ 𝒫 𝐴) → 𝐴 ∈ Fin)
3331, 32mpdan 701 . 2 (𝒫 𝐴 ∈ Fin → 𝐴 ∈ Fin)
3427, 33impbii 199 1 (𝐴 ∈ Fin ↔ 𝒫 𝐴 ∈ Fin)
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ↔ wb 196   = wceq 1481   ∈ wcel 1988  ∃wrex 2910  Vcvv 3195   ∪ cun 3565   ⊆ wss 3567  ∅c0 3907  𝒫 cpw 4149  {csn 4168   class class class wbr 4644   ↦ cmpt 4720  suc csuc 5713  ωcom 7050  1𝑜c1o 7538   ≈ cen 7937   ≼ cdom 7938   ≺ csdm 7939  Fincfn 7940 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1720  ax-4 1735  ax-5 1837  ax-6 1886  ax-7 1933  ax-8 1990  ax-9 1997  ax-10 2017  ax-11 2032  ax-12 2045  ax-13 2244  ax-ext 2600  ax-sep 4772  ax-nul 4780  ax-pow 4834  ax-pr 4897  ax-un 6934 This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3or 1037  df-3an 1038  df-tru 1484  df-ex 1703  df-nf 1708  df-sb 1879  df-eu 2472  df-mo 2473  df-clab 2607  df-cleq 2613  df-clel 2616  df-nfc 2751  df-ne 2792  df-ral 2914  df-rex 2915  df-reu 2916  df-rab 2918  df-v 3197  df-sbc 3430  df-csb 3527  df-dif 3570  df-un 3572  df-in 3574  df-ss 3581  df-pss 3583  df-nul 3908  df-if 4078  df-pw 4151  df-sn 4169  df-pr 4171  df-tp 4173  df-op 4175  df-uni 4428  df-int 4467  df-iun 4513  df-br 4645  df-opab 4704  df-mpt 4721  df-tr 4744  df-id 5014  df-eprel 5019  df-po 5025  df-so 5026  df-fr 5063  df-we 5065  df-xp 5110  df-rel 5111  df-cnv 5112  df-co 5113  df-dm 5114  df-rn 5115  df-res 5116  df-ima 5117  df-pred 5668  df-ord 5714  df-on 5715  df-lim 5716  df-suc 5717  df-iota 5839  df-fun 5878  df-fn 5879  df-f 5880  df-f1 5881  df-fo 5882  df-f1o 5883  df-fv 5884  df-ov 6638  df-oprab 6639  df-mpt2 6640  df-om 7051  df-1st 7153  df-2nd 7154  df-wrecs 7392  df-recs 7453  df-rdg 7491  df-1o 7545  df-2o 7546  df-oadd 7549  df-er 7727  df-map 7844  df-en 7941  df-dom 7942  df-sdom 7943  df-fin 7944 This theorem is referenced by:  mapfi  8247  r1fin  8621  dfac12k  8954  pwsdompw  9011  ackbij1lem5  9031  ackbij1lem9  9035  ackbij1lem10  9036  ackbij1lem14  9040  ackbij1b  9046  isfin1-2  9192  isfin1-3  9193  domtriomlem  9249  dominf  9252  dominfac  9380  gchhar  9486  omina  9498  gchina  9506  hashpw  13206  hashbclem  13219  qshash  14540  ackbijnn  14541  incexclem  14549  incexc  14550  incexc2  14551  hashbccl  15688  lagsubg2  17636  lagsubg  17637  orbsta2  17728  sylow1lem3  17996  sylow1lem5  17998  sylow2alem2  18014  sylow2a  18015  sylow2blem2  18017  sylow2blem3  18018  sylow3lem3  18025  sylow3lem4  18026  sylow3lem6  18028  pgpfac1lem5  18459  discmp  21182  cmpfi  21192  dis1stc  21283  1stckgenlem  21337  ptcmpfi  21597  fiufl  21701  musum  24898  qerclwwlksnfi  26930  hasheuni  30121  coinfliplem  30514  ballotth  30573  erdszelem2  31148  kelac2lem  37453  pwinfig  37685
 Copyright terms: Public domain W3C validator