fin1a2lem6 - Metamath Proof Explorer

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

Theorem fin1a2lem6 10423

Description: Lemma for fin1a2 10433. Establish that ω can be broken into two equipollent pieces. (Contributed by Stefan O'Rear, 7-Nov-2014.)

**Hypotheses**
Ref	Expression
fin1a2lem.b	⊢ 𝐸 = (𝑥 ∈ ω ↦ (2_o ·_o 𝑥))
fin1a2lem.aa	⊢ 𝑆 = (𝑥 ∈ On ↦ suc 𝑥)

**Assertion**
Ref	Expression
fin1a2lem6	⊢ (𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(ω ∖ ran 𝐸)

Proof of Theorem fin1a2lem6 Dummy variables 𝑎 𝑏 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		fin1a2lem.aa	. . . 4 ⊢ 𝑆 = (𝑥 ∈ On ↦ suc 𝑥)
2	1	fin1a2lem2 10419	. . 3 ⊢ 𝑆:On–1-1→On
3		fin1a2lem.b	. . . . 5 ⊢ 𝐸 = (𝑥 ∈ ω ↦ (2_o ·_o 𝑥))
4	3	fin1a2lem4 10421	. . . 4 ⊢ 𝐸:ω–1-1→ω
5		f1f 6788	. . . 4 ⊢ (𝐸:ω–1-1→ω → 𝐸:ω⟶ω)
6		frn 6724	. . . . 5 ⊢ (𝐸:ω⟶ω → ran 𝐸 ⊆ ω)
7		omsson 7869	. . . . 5 ⊢ ω ⊆ On
8	6, 7	sstrdi 3991	. . . 4 ⊢ (𝐸:ω⟶ω → ran 𝐸 ⊆ On)
9	4, 5, 8	mp2b 10	. . 3 ⊢ ran 𝐸 ⊆ On
10		f1ores 6848	. . 3 ⊢ ((𝑆:On–1-1→On ∧ ran 𝐸 ⊆ On) → (𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(𝑆 “ ran 𝐸))
11	2, 9, 10	mp2an 691	. 2 ⊢ (𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(𝑆 “ ran 𝐸)
12	9	sseli 3975	. . . . . . . . 9 ⊢ (𝑏 ∈ ran 𝐸 → 𝑏 ∈ On)
13	1	fin1a2lem1 10418	. . . . . . . . 9 ⊢ (𝑏 ∈ On → (𝑆‘𝑏) = suc 𝑏)
14	12, 13	syl 17	. . . . . . . 8 ⊢ (𝑏 ∈ ran 𝐸 → (𝑆‘𝑏) = suc 𝑏)
15	14	eqeq1d 2730	. . . . . . 7 ⊢ (𝑏 ∈ ran 𝐸 → ((𝑆‘𝑏) = 𝑎 ↔ suc 𝑏 = 𝑎))
16	15	rexbiia 3088	. . . . . 6 ⊢ (∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎 ↔ ∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎)
17	4, 5, 6	mp2b 10	. . . . . . . . . . . 12 ⊢ ran 𝐸 ⊆ ω
18	17	sseli 3975	. . . . . . . . . . 11 ⊢ (𝑏 ∈ ran 𝐸 → 𝑏 ∈ ω)
19		peano2 7891	. . . . . . . . . . 11 ⊢ (𝑏 ∈ ω → suc 𝑏 ∈ ω)
20	18, 19	syl 17	. . . . . . . . . 10 ⊢ (𝑏 ∈ ran 𝐸 → suc 𝑏 ∈ ω)
21	3	fin1a2lem5 10422	. . . . . . . . . . . 12 ⊢ (𝑏 ∈ ω → (𝑏 ∈ ran 𝐸 ↔ ¬ suc 𝑏 ∈ ran 𝐸))
22	21	biimpd 228	. . . . . . . . . . 11 ⊢ (𝑏 ∈ ω → (𝑏 ∈ ran 𝐸 → ¬ suc 𝑏 ∈ ran 𝐸))
23	18, 22	mpcom 38	. . . . . . . . . 10 ⊢ (𝑏 ∈ ran 𝐸 → ¬ suc 𝑏 ∈ ran 𝐸)
24	20, 23	jca 511	. . . . . . . . 9 ⊢ (𝑏 ∈ ran 𝐸 → (suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸))
25		eleq1 2817	. . . . . . . . . 10 ⊢ (suc 𝑏 = 𝑎 → (suc 𝑏 ∈ ω ↔ 𝑎 ∈ ω))
26		eleq1 2817	. . . . . . . . . . 11 ⊢ (suc 𝑏 = 𝑎 → (suc 𝑏 ∈ ran 𝐸 ↔ 𝑎 ∈ ran 𝐸))
27	26	notbid 318	. . . . . . . . . 10 ⊢ (suc 𝑏 = 𝑎 → (¬ suc 𝑏 ∈ ran 𝐸 ↔ ¬ 𝑎 ∈ ran 𝐸))
28	25, 27	anbi12d 631	. . . . . . . . 9 ⊢ (suc 𝑏 = 𝑎 → ((suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸) ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸)))
29	24, 28	syl5ibcom 244	. . . . . . . 8 ⊢ (𝑏 ∈ ran 𝐸 → (suc 𝑏 = 𝑎 → (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸)))
30	29	rexlimiv 3144	. . . . . . 7 ⊢ (∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎 → (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
31		peano1 7889	. . . . . . . . . . . . . 14 ⊢ ∅ ∈ ω
32	3	fin1a2lem3 10420	. . . . . . . . . . . . . 14 ⊢ (∅ ∈ ω → (𝐸‘∅) = (2_o ·_o ∅))
33	31, 32	ax-mp 5	. . . . . . . . . . . . 13 ⊢ (𝐸‘∅) = (2_o ·_o ∅)
34		2on 8495	. . . . . . . . . . . . . 14 ⊢ 2_o ∈ On
35		om0 8532	. . . . . . . . . . . . . 14 ⊢ (2_o ∈ On → (2_o ·_o ∅) = ∅)
36	34, 35	ax-mp 5	. . . . . . . . . . . . 13 ⊢ (2_o ·_o ∅) = ∅
37	33, 36	eqtri 2756	. . . . . . . . . . . 12 ⊢ (𝐸‘∅) = ∅
38		f1fun 6790	. . . . . . . . . . . . . 14 ⊢ (𝐸:ω–1-1→ω → Fun 𝐸)
39	4, 38	ax-mp 5	. . . . . . . . . . . . 13 ⊢ Fun 𝐸
40		f1dm 6792	. . . . . . . . . . . . . . 15 ⊢ (𝐸:ω–1-1→ω → dom 𝐸 = ω)
41	4, 40	ax-mp 5	. . . . . . . . . . . . . 14 ⊢ dom 𝐸 = ω
42	31, 41	eleqtrri 2828	. . . . . . . . . . . . 13 ⊢ ∅ ∈ dom 𝐸
43		fvelrn 7081	. . . . . . . . . . . . 13 ⊢ ((Fun 𝐸 ∧ ∅ ∈ dom 𝐸) → (𝐸‘∅) ∈ ran 𝐸)
44	39, 42, 43	mp2an 691	. . . . . . . . . . . 12 ⊢ (𝐸‘∅) ∈ ran 𝐸
45	37, 44	eqeltrri 2826	. . . . . . . . . . 11 ⊢ ∅ ∈ ran 𝐸
46		eleq1 2817	. . . . . . . . . . 11 ⊢ (𝑎 = ∅ → (𝑎 ∈ ran 𝐸 ↔ ∅ ∈ ran 𝐸))
47	45, 46	mpbiri 258	. . . . . . . . . 10 ⊢ (𝑎 = ∅ → 𝑎 ∈ ran 𝐸)
48	47	necon3bi 2963	. . . . . . . . 9 ⊢ (¬ 𝑎 ∈ ran 𝐸 → 𝑎 ≠ ∅)
49		nnsuc 7883	. . . . . . . . 9 ⊢ ((𝑎 ∈ ω ∧ 𝑎 ≠ ∅) → ∃𝑏 ∈ ω 𝑎 = suc 𝑏)
50	48, 49	sylan2 592	. . . . . . . 8 ⊢ ((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) → ∃𝑏 ∈ ω 𝑎 = suc 𝑏)
51		eleq1 2817	. . . . . . . . . . . . 13 ⊢ (𝑎 = suc 𝑏 → (𝑎 ∈ ω ↔ suc 𝑏 ∈ ω))
52		eleq1 2817	. . . . . . . . . . . . . 14 ⊢ (𝑎 = suc 𝑏 → (𝑎 ∈ ran 𝐸 ↔ suc 𝑏 ∈ ran 𝐸))
53	52	notbid 318	. . . . . . . . . . . . 13 ⊢ (𝑎 = suc 𝑏 → (¬ 𝑎 ∈ ran 𝐸 ↔ ¬ suc 𝑏 ∈ ran 𝐸))
54	51, 53	anbi12d 631	. . . . . . . . . . . 12 ⊢ (𝑎 = suc 𝑏 → ((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ↔ (suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸)))
55	54	anbi1d 630	. . . . . . . . . . 11 ⊢ (𝑎 = suc 𝑏 → (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ 𝑏 ∈ ω) ↔ ((suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸) ∧ 𝑏 ∈ ω)))
56		simplr 768	. . . . . . . . . . . 12 ⊢ (((suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸) ∧ 𝑏 ∈ ω) → ¬ suc 𝑏 ∈ ran 𝐸)
57	21	adantl 481	. . . . . . . . . . . 12 ⊢ (((suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸) ∧ 𝑏 ∈ ω) → (𝑏 ∈ ran 𝐸 ↔ ¬ suc 𝑏 ∈ ran 𝐸))
58	56, 57	mpbird 257	. . . . . . . . . . 11 ⊢ (((suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸) ∧ 𝑏 ∈ ω) → 𝑏 ∈ ran 𝐸)
59	55, 58	biimtrdi 252	. . . . . . . . . 10 ⊢ (𝑎 = suc 𝑏 → (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ 𝑏 ∈ ω) → 𝑏 ∈ ran 𝐸))
60	59	com12 32	. . . . . . . . 9 ⊢ (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ 𝑏 ∈ ω) → (𝑎 = suc 𝑏 → 𝑏 ∈ ran 𝐸))
61	60	impr 454	. . . . . . . 8 ⊢ (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ (𝑏 ∈ ω ∧ 𝑎 = suc 𝑏)) → 𝑏 ∈ ran 𝐸)
62		simprr 772	. . . . . . . . 9 ⊢ (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ (𝑏 ∈ ω ∧ 𝑎 = suc 𝑏)) → 𝑎 = suc 𝑏)
63	62	eqcomd 2734	. . . . . . . 8 ⊢ (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ (𝑏 ∈ ω ∧ 𝑎 = suc 𝑏)) → suc 𝑏 = 𝑎)
64	50, 61, 63	reximssdv 3168	. . . . . . 7 ⊢ ((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) → ∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎)
65	30, 64	impbii 208	. . . . . 6 ⊢ (∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎 ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
66	16, 65	bitri 275	. . . . 5 ⊢ (∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎 ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
67		f1fn 6789	. . . . . . 7 ⊢ (𝑆:On–1-1→On → 𝑆 Fn On)
68	2, 67	ax-mp 5	. . . . . 6 ⊢ 𝑆 Fn On
69		fvelimab 6966	. . . . . 6 ⊢ ((𝑆 Fn On ∧ ran 𝐸 ⊆ On) → (𝑎 ∈ (𝑆 “ ran 𝐸) ↔ ∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎))
70	68, 9, 69	mp2an 691	. . . . 5 ⊢ (𝑎 ∈ (𝑆 “ ran 𝐸) ↔ ∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎)
71		eldif 3955	. . . . 5 ⊢ (𝑎 ∈ (ω ∖ ran 𝐸) ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
72	66, 70, 71	3bitr4i 303	. . . 4 ⊢ (𝑎 ∈ (𝑆 “ ran 𝐸) ↔ 𝑎 ∈ (ω ∖ ran 𝐸))
73	72	eqriv 2725	. . 3 ⊢ (𝑆 “ ran 𝐸) = (ω ∖ ran 𝐸)
74		f1oeq3 6824	. . 3 ⊢ ((𝑆 “ ran 𝐸) = (ω ∖ ran 𝐸) → ((𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(𝑆 “ ran 𝐸) ↔ (𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(ω ∖ ran 𝐸)))
75	73, 74	ax-mp 5	. 2 ⊢ ((𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(𝑆 “ ran 𝐸) ↔ (𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(ω ∖ ran 𝐸))
76	11, 75	mpbi 229	1 ⊢ (𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(ω ∖ ran 𝐸)

Colors of variables: wff setvar class

Syntax hints: ¬ wn 3 ↔ wb 205 ∧ wa 395 = wceq 1534 ∈ wcel 2099 ≠ wne 2936 ∃wrex 3066 ∖ cdif 3942 ⊆ wss 3945 ∅c0 4319 ↦ cmpt 5226 dom cdm 5673 ran crn 5674 ↾ cres 5675 “ cima 5676 Oncon0 6364 suc csuc 6366 Fun wfun 6537 Fn wfn 6538 ⟶wf 6539 –1-1→wf1 6540 –1-1-onto→wf1o 6542 ‘cfv 6543 (class class class)co 7415 ωcom 7865 2_oc2o 8475 ·_o comu 8479

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1790 ax-4 1804 ax-5 1906 ax-6 1964 ax-7 2004 ax-8 2101 ax-9 2109 ax-10 2130 ax-11 2147 ax-12 2167 ax-ext 2699 ax-rep 5280 ax-sep 5294 ax-nul 5301 ax-pr 5424 ax-un 7735

This theorem depends on definitions: df-bi 206 df-an 396 df-or 847 df-3or 1086 df-3an 1087 df-tru 1537 df-fal 1547 df-ex 1775 df-nf 1779 df-sb 2061 df-mo 2530 df-eu 2559 df-clab 2706 df-cleq 2720 df-clel 2806 df-nfc 2881 df-ne 2937 df-ral 3058 df-rex 3067 df-reu 3373 df-rab 3429 df-v 3472 df-sbc 3776 df-csb 3891 df-dif 3948 df-un 3950 df-in 3952 df-ss 3962 df-pss 3964 df-nul 4320 df-if 4526 df-pw 4601 df-sn 4626 df-pr 4628 df-op 4632 df-uni 4905 df-iun 4994 df-br 5144 df-opab 5206 df-mpt 5227 df-tr 5261 df-id 5571 df-eprel 5577 df-po 5585 df-so 5586 df-fr 5628 df-we 5630 df-xp 5679 df-rel 5680 df-cnv 5681 df-co 5682 df-dm 5683 df-rn 5684 df-res 5685 df-ima 5686 df-pred 6300 df-ord 6367 df-on 6368 df-lim 6369 df-suc 6370 df-iota 6495 df-fun 6545 df-fn 6546 df-f 6547 df-f1 6548 df-fo 6549 df-f1o 6550 df-fv 6551 df-ov 7418 df-oprab 7419 df-mpo 7420 df-om 7866 df-2nd 7989 df-frecs 8281 df-wrecs 8312 df-recs 8386 df-rdg 8425 df-1o 8481 df-2o 8482 df-oadd 8485 df-omul 8486

This theorem is referenced by: fin1a2lem7 10424

W3C validator

	
		OSZAR »