Theorem canthp1 10268

Description: A slightly stronger form of Cantor's theorem: For 1 < 𝑛, 𝑛 + 1 < 2↑𝑛. Corollary 1.6 of [KanamoriPincus] p. 417. (Contributed by Mario Carneiro, 18-May-2015.)

Assertion

Ref	Expression
canthp1	⊢ (1o ≺ 𝐴 → (𝐴 ⊔ 1o) ≺ 𝒫 𝐴)

Proof of Theorem canthp1

Dummy variables 𝑓 𝑎 𝑔 𝑟 𝑠 𝑤 𝑥 𝑦 𝑧 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		1sdom2 8877	. . . . 5 ⊢ 1o ≺ 2o
2		sdomdom 8656	. . . . 5 ⊢ (1o ≺ 2o → 1o ≼ 2o)
3	1, 2	ax-mp 5	. . . 4 ⊢ 1o ≼ 2o
4		relsdom 8633	. . . . 5 ⊢ Rel ≺
5	4	brrelex2i 5606	. . . 4 ⊢ (1o ≺ 𝐴 → 𝐴 ∈ V)
6		djudom2 9797	. . . 4 ⊢ ((1o ≼ 2o ∧ 𝐴 ∈ V) → (𝐴 ⊔ 1o) ≼ (𝐴 ⊔ 2o))
7	3, 5, 6	sylancr 590	. . 3 ⊢ (1o ≺ 𝐴 → (𝐴 ⊔ 1o) ≼ (𝐴 ⊔ 2o))
8		canthp1lem1 10266	. . 3 ⊢ (1o ≺ 𝐴 → (𝐴 ⊔ 2o) ≼ 𝒫 𝐴)
9		domtr 8681	. . 3 ⊢ (((𝐴 ⊔ 1o) ≼ (𝐴 ⊔ 2o) ∧ (𝐴 ⊔ 2o) ≼ 𝒫 𝐴) → (𝐴 ⊔ 1o) ≼ 𝒫 𝐴)
10	7, 8, 9	syl2anc 587	. 2 ⊢ (1o ≺ 𝐴 → (𝐴 ⊔ 1o) ≼ 𝒫 𝐴)
11		fal 1557	. . 3 ⊢ ¬ ⊥
12		ensym 8677	. . . . 5 ⊢ ((𝐴 ⊔ 1o) ≈ 𝒫 𝐴 → 𝒫 𝐴 ≈ (𝐴 ⊔ 1o))
13		bren 8636	. . . . 5 ⊢ (𝒫 𝐴 ≈ (𝐴 ⊔ 1o) ↔ ∃𝑓 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o))
14	12, 13	sylib 221	. . . 4 ⊢ ((𝐴 ⊔ 1o) ≈ 𝒫 𝐴 → ∃𝑓 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o))
15		f1of 6661	. . . . . . . . . 10 ⊢ (𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o) → 𝑓:𝒫 𝐴⟶(𝐴 ⊔ 1o))
16		pwidg 4535	. . . . . . . . . . 11 ⊢ (𝐴 ∈ V → 𝐴 ∈ 𝒫 𝐴)
17	5, 16	syl 17	. . . . . . . . . 10 ⊢ (1o ≺ 𝐴 → 𝐴 ∈ 𝒫 𝐴)
18		ffvelrn 6902	. . . . . . . . . 10 ⊢ ((𝑓:𝒫 𝐴⟶(𝐴 ⊔ 1o) ∧ 𝐴 ∈ 𝒫 𝐴) → (𝑓‘𝐴) ∈ (𝐴 ⊔ 1o))
19	15, 17, 18	syl2anr 600	. . . . . . . . 9 ⊢ ((1o ≺ 𝐴 ∧ 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o)) → (𝑓‘𝐴) ∈ (𝐴 ⊔ 1o))
20		dju1dif 9786	. . . . . . . . 9 ⊢ ((𝐴 ∈ V ∧ (𝑓‘𝐴) ∈ (𝐴 ⊔ 1o)) → ((𝐴 ⊔ 1o) ∖ {(𝑓‘𝐴)}) ≈ 𝐴)
21	5, 19, 20	syl2an2r 685	. . . . . . . 8 ⊢ ((1o ≺ 𝐴 ∧ 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o)) → ((𝐴 ⊔ 1o) ∖ {(𝑓‘𝐴)}) ≈ 𝐴)
22		bren 8636	. . . . . . . 8 ⊢ (((𝐴 ⊔ 1o) ∖ {(𝑓‘𝐴)}) ≈ 𝐴 ↔ ∃𝑔 𝑔:((𝐴 ⊔ 1o) ∖ {(𝑓‘𝐴)})–1-1-onto→𝐴)
23	21, 22	sylib 221	. . . . . . 7 ⊢ ((1o ≺ 𝐴 ∧ 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o)) → ∃𝑔 𝑔:((𝐴 ⊔ 1o) ∖ {(𝑓‘𝐴)})–1-1-onto→𝐴)
24		simpll 767	. . . . . . . . 9 ⊢ (((1o ≺ 𝐴 ∧ 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o)) ∧ 𝑔:((𝐴 ⊔ 1o) ∖ {(𝑓‘𝐴)})–1-1-onto→𝐴) → 1o ≺ 𝐴)
25		simplr 769	. . . . . . . . 9 ⊢ (((1o ≺ 𝐴 ∧ 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o)) ∧ 𝑔:((𝐴 ⊔ 1o) ∖ {(𝑓‘𝐴)})–1-1-onto→𝐴) → 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o))
26		simpr 488	. . . . . . . . 9 ⊢ (((1o ≺ 𝐴 ∧ 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o)) ∧ 𝑔:((𝐴 ⊔ 1o) ∖ {(𝑓‘𝐴)})–1-1-onto→𝐴) → 𝑔:((𝐴 ⊔ 1o) ∖ {(𝑓‘𝐴)})–1-1-onto→𝐴)
27		eqeq1 2741	. . . . . . . . . . . 12 ⊢ (𝑤 = 𝑥 → (𝑤 = 𝐴 ↔ 𝑥 = 𝐴))
28		id 22	. . . . . . . . . . . 12 ⊢ (𝑤 = 𝑥 → 𝑤 = 𝑥)
29	27, 28	ifbieq2d 4465	. . . . . . . . . . 11 ⊢ (𝑤 = 𝑥 → if(𝑤 = 𝐴, ∅, 𝑤) = if(𝑥 = 𝐴, ∅, 𝑥))
30	29	cbvmptv 5158	. . . . . . . . . 10 ⊢ (𝑤 ∈ 𝒫 𝐴 ↦ if(𝑤 = 𝐴, ∅, 𝑤)) = (𝑥 ∈ 𝒫 𝐴 ↦ if(𝑥 = 𝐴, ∅, 𝑥))
31	30	coeq2i 5729	. . . . . . . . 9 ⊢ ((𝑔 ∘ 𝑓) ∘ (𝑤 ∈ 𝒫 𝐴 ↦ if(𝑤 = 𝐴, ∅, 𝑤))) = ((𝑔 ∘ 𝑓) ∘ (𝑥 ∈ 𝒫 𝐴 ↦ if(𝑥 = 𝐴, ∅, 𝑥)))
32		eqid 2737	. . . . . . . . . 10 ⊢ {⟨𝑎, 𝑠⟩ ∣ ((𝑎 ⊆ 𝐴 ∧ 𝑠 ⊆ (𝑎 × 𝑎)) ∧ (𝑠 We 𝑎 ∧ ∀𝑧 ∈ 𝑎 (((𝑔 ∘ 𝑓) ∘ (𝑤 ∈ 𝒫 𝐴 ↦ if(𝑤 = 𝐴, ∅, 𝑤)))‘(◡𝑠 “ {𝑧})) = 𝑧))} = {⟨𝑎, 𝑠⟩ ∣ ((𝑎 ⊆ 𝐴 ∧ 𝑠 ⊆ (𝑎 × 𝑎)) ∧ (𝑠 We 𝑎 ∧ ∀𝑧 ∈ 𝑎 (((𝑔 ∘ 𝑓) ∘ (𝑤 ∈ 𝒫 𝐴 ↦ if(𝑤 = 𝐴, ∅, 𝑤)))‘(◡𝑠 “ {𝑧})) = 𝑧))}
33	32	fpwwecbv 10258	. . . . . . . . 9 ⊢ {⟨𝑎, 𝑠⟩ ∣ ((𝑎 ⊆ 𝐴 ∧ 𝑠 ⊆ (𝑎 × 𝑎)) ∧ (𝑠 We 𝑎 ∧ ∀𝑧 ∈ 𝑎 (((𝑔 ∘ 𝑓) ∘ (𝑤 ∈ 𝒫 𝐴 ↦ if(𝑤 = 𝐴, ∅, 𝑤)))‘(◡𝑠 “ {𝑧})) = 𝑧))} = {⟨𝑥, 𝑟⟩ ∣ ((𝑥 ⊆ 𝐴 ∧ 𝑟 ⊆ (𝑥 × 𝑥)) ∧ (𝑟 We 𝑥 ∧ ∀𝑦 ∈ 𝑥 (((𝑔 ∘ 𝑓) ∘ (𝑤 ∈ 𝒫 𝐴 ↦ if(𝑤 = 𝐴, ∅, 𝑤)))‘(◡𝑟 “ {𝑦})) = 𝑦))}
34		eqid 2737	. . . . . . . . 9 ⊢ ∪ dom {⟨𝑎, 𝑠⟩ ∣ ((𝑎 ⊆ 𝐴 ∧ 𝑠 ⊆ (𝑎 × 𝑎)) ∧ (𝑠 We 𝑎 ∧ ∀𝑧 ∈ 𝑎 (((𝑔 ∘ 𝑓) ∘ (𝑤 ∈ 𝒫 𝐴 ↦ if(𝑤 = 𝐴, ∅, 𝑤)))‘(◡𝑠 “ {𝑧})) = 𝑧))} = ∪ dom {⟨𝑎, 𝑠⟩ ∣ ((𝑎 ⊆ 𝐴 ∧ 𝑠 ⊆ (𝑎 × 𝑎)) ∧ (𝑠 We 𝑎 ∧ ∀𝑧 ∈ 𝑎 (((𝑔 ∘ 𝑓) ∘ (𝑤 ∈ 𝒫 𝐴 ↦ if(𝑤 = 𝐴, ∅, 𝑤)))‘(◡𝑠 “ {𝑧})) = 𝑧))}
35	24, 25, 26, 31, 33, 34	canthp1lem2 10267	. . . . . . . 8 ⊢ ¬ ((1o ≺ 𝐴 ∧ 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o)) ∧ 𝑔:((𝐴 ⊔ 1o) ∖ {(𝑓‘𝐴)})–1-1-onto→𝐴)
36	35	pm2.21i 119	. . . . . . 7 ⊢ (((1o ≺ 𝐴 ∧ 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o)) ∧ 𝑔:((𝐴 ⊔ 1o) ∖ {(𝑓‘𝐴)})–1-1-onto→𝐴) → ⊥)
37	23, 36	exlimddv 1943	. . . . . 6 ⊢ ((1o ≺ 𝐴 ∧ 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o)) → ⊥)
38	37	ex 416	. . . . 5 ⊢ (1o ≺ 𝐴 → (𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o) → ⊥))
39	38	exlimdv 1941	. . . 4 ⊢ (1o ≺ 𝐴 → (∃𝑓 𝑓:𝒫 𝐴–1-1-onto→(𝐴 ⊔ 1o) → ⊥))
40	14, 39	syl5 34	. . 3 ⊢ (1o ≺ 𝐴 → ((𝐴 ⊔ 1o) ≈ 𝒫 𝐴 → ⊥))
41	11, 40	mtoi 202	. 2 ⊢ (1o ≺ 𝐴 → ¬ (𝐴 ⊔ 1o) ≈ 𝒫 𝐴)
42		brsdom 8651	. 2 ⊢ ((𝐴 ⊔ 1o) ≺ 𝒫 𝐴 ↔ ((𝐴 ⊔ 1o) ≼ 𝒫 𝐴 ∧ ¬ (𝐴 ⊔ 1o) ≈ 𝒫 𝐴))
43	10, 41, 42	sylanbrc 586	1 ⊢ (1o ≺ 𝐴 → (𝐴 ⊔ 1o) ≺ 𝒫 𝐴)

Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 399   = wceq 1543  ⊥wfal 1555  ∃wex 1787   ∈ wcel 2110  ∀wral 3061  Vcvv 3408   ∖ cdif 3863   ⊆ wss 3866  ∅c0 4237  ifcif 4439  𝒫 cpw 4513  {csn 4541  ∪ cuni 4819   class class class wbr 5053  {copab 5115   ↦ cmpt 5135   We wwe 5508   × cxp 5549  ^◡ccnv 5550  dom cdm 5551   “ cima 5554   ∘ ccom 5555  ⟶wf 6376  –1-1-onto→wf1o 6379  ‘cfv 6380  1_oc1o 8195  2_oc2o 8196   ≈ cen 8623   ≼ cdom 8624   ≺ csdm 8625   ⊔ cdju 9514

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1803  ax-4 1817  ax-5 1918  ax-6 1976  ax-7 2016  ax-8 2112  ax-9 2120  ax-10 2141  ax-11 2158  ax-12 2175  ax-ext 2708  ax-rep 5179  ax-sep 5192  ax-nul 5199  ax-pow 5258  ax-pr 5322  ax-un 7523  ax-inf2 9256

This theorem depends on definitions:  df-bi 210  df-an 400  df-or 848  df-3or 1090  df-3an 1091  df-tru 1546  df-fal 1556  df-ex 1788  df-nf 1792  df-sb 2071  df-mo 2539  df-eu 2568  df-clab 2715  df-cleq 2729  df-clel 2816  df-nfc 2886  df-ne 2941  df-ral 3066  df-rex 3067  df-reu 3068  df-rmo 3069  df-rab 3070  df-v 3410  df-sbc 3695  df-csb 3812  df-dif 3869  df-un 3871  df-in 3873  df-ss 3883  df-pss 3885  df-nul 4238  df-if 4440  df-pw 4515  df-sn 4542  df-pr 4544  df-tp 4546  df-op 4548  df-uni 4820  df-int 4860  df-iun 4906  df-br 5054  df-opab 5116  df-mpt 5136  df-tr 5162  df-id 5455  df-eprel 5460  df-po 5468  df-so 5469  df-fr 5509  df-se 5510  df-we 5511  df-xp 5557  df-rel 5558  df-cnv 5559  df-co 5560  df-dm 5561  df-rn 5562  df-res 5563  df-ima 5564  df-pred 6160  df-ord 6216  df-on 6217  df-lim 6218  df-suc 6219  df-iota 6338  df-fun 6382  df-fn 6383  df-f 6384  df-f1 6385  df-fo 6386  df-f1o 6387  df-fv 6388  df-isom 6389  df-riota 7170  df-ov 7216  df-oprab 7217  df-mpo 7218  df-om 7645  df-1st 7761  df-2nd 7762  df-wrecs 8047  df-recs 8108  df-rdg 8146  df-1o 8202  df-2o 8203  df-er 8391  df-map 8510  df-en 8627  df-dom 8628  df-sdom 8629  df-fin 8630  df-oi 9126  df-dju 9517  df-card 9555

This theorem is referenced by:  finngch  10269  gchdju1  10270