Theorem canth2 4473

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

Hypothesis

Ref	Expression
canth2.1	⊢ A ∈ V

Assertion

Ref	Expression
canth2	⊢ A ≺ ℘A

Proof of Theorem canth2

Step	Hyp	Ref	Expression
1		brsdom 4372	. 2 ⊢ (A ≺ ℘A ↔ (A ≼ ℘A ⋀ ¬ A ≈ ℘A))
2		canth2.1	. . 3 ⊢ A ∈ V
3		visset 1810	. . . . . 6 ⊢ x ∈ V
4	3	snelpw 2748	. . . . 5 ⊢ (x ∈ A ↔ {x} ∈ ℘A)
5	4	biimp 151	. . . 4 ⊢ (x ∈ A → {x} ∈ ℘A)
6	3	sneqr 2474	. . . . . 6 ⊢ ({x} = {y} → x = y)
7		sneq 2414	. . . . . 6 ⊢ (x = y → {x} = {y})
8	6, 7	impbi 157	. . . . 5 ⊢ ({x} = {y} ↔ x = y)
9	8	a1i 8	. . . 4 ⊢ ((x ∈ A ⋀ y ∈ A) → ({x} = {y} ↔ x = y))
10	5, 9	dom2 4395	. . 3 ⊢ (A ∈ V → A ≼ ℘A)
11	2, 10	ax-mp 7	. 2 ⊢ A ≼ ℘A
12	2	canth 3902	. . . . 5 ⊢ ¬ f:A–onto→℘A
13		f1ofo 3690	. . . . 5 ⊢ (f:A–1-1-onto→℘A → f:A–onto→℘A)
14	12, 13	mto 106	. . . 4 ⊢ ¬ f:A–1-1-onto→℘A
15	14	nex 1100	. . 3 ⊢ ¬ ∃f f:A–1-1-onto→℘A
16	2	pwex 2741	. . . 4 ⊢ ℘A ∈ V
17	16	bren 4368	. . 3 ⊢ (A ≈ ℘A ↔ ∃f f:A–1-1-onto→℘A)
18	15, 17	mtbir 192	. 2 ⊢ ¬ A ≈ ℘A
19	1, 11, 18	mpbir2an 729	1 ⊢ A ≺ ℘A

Syntax hints:  ¬ wn 2   ↔ wb 146   ⋀ wa 223   = wceq 955   ∈ wcel 957  ∃wex 979  Vcvv 1808  ℘cpw 2398  {csn 2406   class class class wbr 2615  –onto→wfo 3176  –1-1-onto→wf1o 3177   ≈ cen 4357   ≼ cdom 4358   ≺ csdm 4359

This theorem is referenced by:  canth2g 4474  1sdom2 4514  numthcor 4769  alephsucpw 4853  pnfnemnf 5519  infmap1 7533

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 961  ax-gen 962  ax-8 963  ax-9 964  ax-10 965  ax-11 966  ax-12 967  ax-13 968  ax-14 969  ax-17 970  ax-4 972  ax-5o 974  ax-6o 977  ax-9o 1122  ax-10o 1139  ax-16 1209  ax-11o 1217  ax-ext 1458  ax-rep 2689  ax-sep 2699  ax-pow 2738  ax-pr 2775  ax-un 2862

This theorem depends on definitions:  df-bi 147  df-or 224  df-an 225  df-ex 980  df-sb 1171  df-eu 1381  df-mo 1382  df-clab 1463  df-cleq 1468  df-clel 1471  df-ne 1585  df-ral 1647  df-rex 1648  df-rab 1650  df-v 1809  df-dif 2046  df-un 2047  df-in 2048  df-ss 2050  df-nul 2278  df-pw 2399  df-sn 2409  df-pr 2410  df-op 2413  df-uni 2500  df-br 2616  df-opab 2663  df-id 2831  df-xp 3180  df-rel 3181  df-cnv 3182  df-co 3183  df-dm 3184  df-rn 3185  df-res 3186  df-ima 3187  df-fun 3188  df-fn 3189  df-f 3190  df-f1 3191  df-fo 3192  df-f1o 3193  df-fv 3194  df-en 4360  df-dom 4361  df-sdom 4362

Copyright terms: Public domain