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

Theorem canth2 8648
 Description: Cantor's Theorem. No set is equinumerous to its power set. Specifically, any set has a cardinality (size) strictly less than the cardinality of its power set. For example, the cardinality of real numbers is the same as the cardinality of the power set of integers, so real numbers cannot be put into a one-to-one correspondence with integers. Theorem 23 of [Suppes] p. 97. For the function version, see canth 7088. This is Metamath 100 proof #63. (Contributed by NM, 7-Aug-1994.)
Hypothesis
Ref Expression
canth2.1 𝐴 ∈ V
Assertion
Ref Expression
canth2 𝐴 ≺ 𝒫 𝐴

Proof of Theorem canth2
Dummy variables 𝑥 𝑦 𝑓 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 canth2.1 . . 3 𝐴 ∈ V
21pwex 5257 . . 3 𝒫 𝐴 ∈ V
3 snelpwi 5313 . . . 4 (𝑥𝐴 → {𝑥} ∈ 𝒫 𝐴)
4 vex 3476 . . . . . . 7 𝑥 ∈ V
54sneqr 4747 . . . . . 6 ({𝑥} = {𝑦} → 𝑥 = 𝑦)
6 sneq 4553 . . . . . 6 (𝑥 = 𝑦 → {𝑥} = {𝑦})
75, 6impbii 211 . . . . 5 ({𝑥} = {𝑦} ↔ 𝑥 = 𝑦)
87a1i 11 . . . 4 ((𝑥𝐴𝑦𝐴) → ({𝑥} = {𝑦} ↔ 𝑥 = 𝑦))
93, 8dom3 8531 . . 3 ((𝐴 ∈ V ∧ 𝒫 𝐴 ∈ V) → 𝐴 ≼ 𝒫 𝐴)
101, 2, 9mp2an 690 . 2 𝐴 ≼ 𝒫 𝐴
111canth 7088 . . . . 5 ¬ 𝑓:𝐴onto→𝒫 𝐴
12 f1ofo 6598 . . . . 5 (𝑓:𝐴1-1-onto→𝒫 𝐴𝑓:𝐴onto→𝒫 𝐴)
1311, 12mto 199 . . . 4 ¬ 𝑓:𝐴1-1-onto→𝒫 𝐴
1413nex 1801 . . 3 ¬ ∃𝑓 𝑓:𝐴1-1-onto→𝒫 𝐴
15 bren 8496 . . 3 (𝐴 ≈ 𝒫 𝐴 ↔ ∃𝑓 𝑓:𝐴1-1-onto→𝒫 𝐴)
1614, 15mtbir 325 . 2 ¬ 𝐴 ≈ 𝒫 𝐴
17 brsdom 8510 . 2 (𝐴 ≺ 𝒫 𝐴 ↔ (𝐴 ≼ 𝒫 𝐴 ∧ ¬ 𝐴 ≈ 𝒫 𝐴))
1810, 16, 17mpbir2an 709 1 𝐴 ≺ 𝒫 𝐴
 Colors of variables: wff setvar class Syntax hints:  ¬ wn 3   ↔ wb 208   ∧ wa 398   = wceq 1537  ∃wex 1780   ∈ wcel 2114  Vcvv 3473  𝒫 cpw 4515  {csn 4543   class class class wbr 5042  –onto→wfo 6329  –1-1-onto→wf1o 6330   ≈ cen 8484   ≼ cdom 8485   ≺ csdm 8486 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1911  ax-6 1970  ax-7 2015  ax-8 2116  ax-9 2124  ax-10 2145  ax-11 2161  ax-12 2177  ax-ext 2792  ax-sep 5179  ax-nul 5186  ax-pow 5242  ax-pr 5306  ax-un 7439 This theorem depends on definitions:  df-bi 209  df-an 399  df-or 844  df-3an 1085  df-tru 1540  df-ex 1781  df-nf 1785  df-sb 2070  df-mo 2622  df-eu 2653  df-clab 2799  df-cleq 2813  df-clel 2891  df-nfc 2959  df-ne 3007  df-ral 3130  df-rex 3131  df-rab 3134  df-v 3475  df-sbc 3753  df-csb 3861  df-dif 3916  df-un 3918  df-in 3920  df-ss 3930  df-nul 4270  df-if 4444  df-pw 4517  df-sn 4544  df-pr 4546  df-op 4550  df-uni 4815  df-br 5043  df-opab 5105  df-mpt 5123  df-id 5436  df-xp 5537  df-rel 5538  df-cnv 5539  df-co 5540  df-dm 5541  df-rn 5542  df-res 5543  df-ima 5544  df-iota 6290  df-fun 6333  df-fn 6334  df-f 6335  df-f1 6336  df-fo 6337  df-f1o 6338  df-fv 6339  df-en 8488  df-dom 8489  df-sdom 8490 This theorem is referenced by:  canth2g  8649  r1sdom  9181  alephsucpw2  9515  dfac13  9546  pwsdompw  9604  numthcor  9894  alephexp1  9979  pwcfsdom  9983  cfpwsdom  9984  gchac  10081  inawinalem  10089  tskcard  10181  gruina  10218  grothac  10230  rpnnen  15560  rexpen  15561  rucALT  15563  rectbntr0  23416
 Copyright terms: Public domain W3C validator