Theorem canth2 9065

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 7317. 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.

Step	Hyp	Ref	Expression
1		canth2.1	. . 3 ⊢ 𝐴 ∈ V
2	1	pwex 5316	. . 3 ⊢ 𝒫 𝐴 ∈ V
3		snelpwi 5390	. . . 4 ⊢ (𝑥 ∈ 𝐴 → {𝑥} ∈ 𝒫 𝐴)
4		vex 3436	. . . . . . 7 ⊢ 𝑥 ∈ V
5	4	sneqr 4778	. . . . . 6 ⊢ ({𝑥} = {𝑦} → 𝑥 = 𝑦)
6		sneq 4572	. . . . . 6 ⊢ (𝑥 = 𝑦 → {𝑥} = {𝑦})
7	5, 6	impbii 210	. . . . 5 ⊢ ({𝑥} = {𝑦} ↔ 𝑥 = 𝑦)
8	7	a1i 11	. . . 4 ⊢ ((𝑥 ∈ 𝐴 ∧ 𝑦 ∈ 𝐴) → ({𝑥} = {𝑦} ↔ 𝑥 = 𝑦))
9	3, 8	dom3 8940	. . 3 ⊢ ((𝐴 ∈ V ∧ 𝒫 𝐴 ∈ V) → 𝐴 ≼ 𝒫 𝐴)
10	1, 2, 9	mp2an 698	. 2 ⊢ 𝐴 ≼ 𝒫 𝐴
11	1	canth 7317	. . . . 5 ⊢ ¬ 𝑓:𝐴–onto→𝒫 𝐴
12		f1ofo 6781	. . . . 5 ⊢ (𝑓:𝐴–1-1-onto→𝒫 𝐴 → 𝑓:𝐴–onto→𝒫 𝐴)
13	11, 12	mto 198	. . . 4 ⊢ ¬ 𝑓:𝐴–1-1-onto→𝒫 𝐴
14	13	nex 1807	. . 3 ⊢ ¬ ∃𝑓 𝑓:𝐴–1-1-onto→𝒫 𝐴
15		bren 8900	. . 3 ⊢ (𝐴 ≈ 𝒫 𝐴 ↔ ∃𝑓 𝑓:𝐴–1-1-onto→𝒫 𝐴)
16	14, 15	mtbir 324	. 2 ⊢ ¬ 𝐴 ≈ 𝒫 𝐴
17		brsdom 8918	. 2 ⊢ (𝐴 ≺ 𝒫 𝐴 ↔ (𝐴 ≼ 𝒫 𝐴 ∧ ¬ 𝐴 ≈ 𝒫 𝐴))
18	10, 16, 17	mpbir2an 717	1 ⊢ 𝐴 ≺ 𝒫 𝐴

Syntax hints:  ¬ wn 3   ↔ wb 207   ∧ wa 396   = wceq 1547  ∃wex 1786   ∈ wcel 2119  Vcvv 3432  𝒫 cpw 4536  {csn 4562   class class class wbr 5079  –onto→wfo 6490  –1-1-onto→wf1o 6491   ≈ cen 8887   ≼ cdom 8888   ≺ csdm 8889

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1802  ax-4 1816  ax-5 1917  ax-6 1974  ax-7 2015  ax-8 2121  ax-9 2129  ax-10 2152  ax-11 2168  ax-12 2189  ax-ext 2712  ax-sep 5225  ax-nul 5235  ax-pow 5301  ax-pr 5369  ax-un 7685

This theorem depends on definitions:  df-bi 208  df-an 397  df-or 854  df-3an 1094  df-tru 1550  df-fal 1560  df-ex 1787  df-nf 1791  df-sb 2074  df-mo 2543  df-eu 2573  df-clab 2719  df-cleq 2732  df-clel 2815  df-nfc 2889  df-ne 2936  df-ral 3055  df-rex 3065  df-rab 3393  df-v 3434  df-sbc 3731  df-csb 3839  df-dif 3893  df-un 3895  df-in 3897  df-ss 3907  df-nul 4269  df-if 4462  df-pw 4538  df-sn 4563  df-pr 4565  df-op 4569  df-uni 4846  df-br 5080  df-opab 5142  df-mpt 5161  df-id 5520  df-xp 5631  df-rel 5632  df-cnv 5633  df-co 5634  df-dm 5635  df-rn 5636  df-res 5637  df-ima 5638  df-iota 6448  df-fun 6494  df-fn 6495  df-f 6496  df-f1 6497  df-fo 6498  df-f1o 6499  df-fv 6500  df-en 8891  df-dom 8892  df-sdom 8893

This theorem is referenced by:  canth2g  9066  r1sdom  9696  alephsucpw2  10031  dfac13  10063  pwsdompw  10123  numthcor  10414  alephexp1  10500  pwcfsdom  10504  cfpwsdom  10505  gchac  10602  inawinalem  10610  tskcard  10702  gruina  10739  grothac  10751  rpnnen  16192  rexpen  16193  rucALT  16195  rectbntr0  24823