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 10318

Description: Lemma for fin1a2 10328. 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 10314	. . 3 ⊢ 𝑆:On–1-1→On
3		fin1a2lem.b	. . . . 5 ⊢ 𝐸 = (𝑥 ∈ ω ↦ (2_o ·_o 𝑥))
4	3	fin1a2lem4 10316	. . . 4 ⊢ 𝐸:ω–1-1→ω
5		f1f 6730	. . . 4 ⊢ (𝐸:ω–1-1→ω → 𝐸:ω⟶ω)
6		frn 6669	. . . . 5 ⊢ (𝐸:ω⟶ω → ran 𝐸 ⊆ ω)
7		omsson 7814	. . . . 5 ⊢ ω ⊆ On
8	6, 7	sstrdi 3935	. . . 4 ⊢ (𝐸:ω⟶ω → ran 𝐸 ⊆ On)
9	4, 5, 8	mp2b 10	. . 3 ⊢ ran 𝐸 ⊆ On
10		f1ores 6788	. . 3 ⊢ ((𝑆:On–1-1→On ∧ ran 𝐸 ⊆ On) → (𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(𝑆 “ ran 𝐸))
11	2, 9, 10	mp2an 693	. 2 ⊢ (𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(𝑆 “ ran 𝐸)
12	9	sseli 3918	. . . . . . . . 9 ⊢ (𝑏 ∈ ran 𝐸 → 𝑏 ∈ On)
13	1	fin1a2lem1 10313	. . . . . . . . 9 ⊢ (𝑏 ∈ On → (𝑆‘𝑏) = suc 𝑏)
14	12, 13	syl 17	. . . . . . . 8 ⊢ (𝑏 ∈ ran 𝐸 → (𝑆‘𝑏) = suc 𝑏)
15	14	eqeq1d 2739	. . . . . . 7 ⊢ (𝑏 ∈ ran 𝐸 → ((𝑆‘𝑏) = 𝑎 ↔ suc 𝑏 = 𝑎))
16	15	rexbiia 3083	. . . . . 6 ⊢ (∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎 ↔ ∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎)
17	4, 5, 6	mp2b 10	. . . . . . . . . . . 12 ⊢ ran 𝐸 ⊆ ω
18	17	sseli 3918	. . . . . . . . . . 11 ⊢ (𝑏 ∈ ran 𝐸 → 𝑏 ∈ ω)
19		peano2 7834	. . . . . . . . . . 11 ⊢ (𝑏 ∈ ω → suc 𝑏 ∈ ω)
20	18, 19	syl 17	. . . . . . . . . 10 ⊢ (𝑏 ∈ ran 𝐸 → suc 𝑏 ∈ ω)
21	3	fin1a2lem5 10317	. . . . . . . . . . . 12 ⊢ (𝑏 ∈ ω → (𝑏 ∈ ran 𝐸 ↔ ¬ suc 𝑏 ∈ ran 𝐸))
22	21	biimpd 229	. . . . . . . . . . 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 2825	. . . . . . . . . 10 ⊢ (suc 𝑏 = 𝑎 → (suc 𝑏 ∈ ω ↔ 𝑎 ∈ ω))
26		eleq1 2825	. . . . . . . . . . 11 ⊢ (suc 𝑏 = 𝑎 → (suc 𝑏 ∈ ran 𝐸 ↔ 𝑎 ∈ ran 𝐸))
27	26	notbid 318	. . . . . . . . . 10 ⊢ (suc 𝑏 = 𝑎 → (¬ suc 𝑏 ∈ ran 𝐸 ↔ ¬ 𝑎 ∈ ran 𝐸))
28	25, 27	anbi12d 633	. . . . . . . . 9 ⊢ (suc 𝑏 = 𝑎 → ((suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸) ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸)))
29	24, 28	syl5ibcom 245	. . . . . . . 8 ⊢ (𝑏 ∈ ran 𝐸 → (suc 𝑏 = 𝑎 → (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸)))
30	29	rexlimiv 3132	. . . . . . 7 ⊢ (∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎 → (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
31		peano1 7833	. . . . . . . . . . . . . 14 ⊢ ∅ ∈ ω
32	3	fin1a2lem3 10315	. . . . . . . . . . . . . 14 ⊢ (∅ ∈ ω → (𝐸‘∅) = (2_o ·_o ∅))
33	31, 32	ax-mp 5	. . . . . . . . . . . . 13 ⊢ (𝐸‘∅) = (2_o ·_o ∅)
34		2on 8411	. . . . . . . . . . . . . 14 ⊢ 2_o ∈ On
35		om0 8445	. . . . . . . . . . . . . 14 ⊢ (2_o ∈ On → (2_o ·_o ∅) = ∅)
36	34, 35	ax-mp 5	. . . . . . . . . . . . 13 ⊢ (2_o ·_o ∅) = ∅
37	33, 36	eqtri 2760	. . . . . . . . . . . 12 ⊢ (𝐸‘∅) = ∅
38		f1fun 6732	. . . . . . . . . . . . . 14 ⊢ (𝐸:ω–1-1→ω → Fun 𝐸)
39	4, 38	ax-mp 5	. . . . . . . . . . . . 13 ⊢ Fun 𝐸
40		f1dm 6734	. . . . . . . . . . . . . . 15 ⊢ (𝐸:ω–1-1→ω → dom 𝐸 = ω)
41	4, 40	ax-mp 5	. . . . . . . . . . . . . 14 ⊢ dom 𝐸 = ω
42	31, 41	eleqtrri 2836	. . . . . . . . . . . . 13 ⊢ ∅ ∈ dom 𝐸
43		fvelrn 7022	. . . . . . . . . . . . 13 ⊢ ((Fun 𝐸 ∧ ∅ ∈ dom 𝐸) → (𝐸‘∅) ∈ ran 𝐸)
44	39, 42, 43	mp2an 693	. . . . . . . . . . . 12 ⊢ (𝐸‘∅) ∈ ran 𝐸
45	37, 44	eqeltrri 2834	. . . . . . . . . . 11 ⊢ ∅ ∈ ran 𝐸
46		eleq1 2825	. . . . . . . . . . 11 ⊢ (𝑎 = ∅ → (𝑎 ∈ ran 𝐸 ↔ ∅ ∈ ran 𝐸))
47	45, 46	mpbiri 258	. . . . . . . . . 10 ⊢ (𝑎 = ∅ → 𝑎 ∈ ran 𝐸)
48	47	necon3bi 2959	. . . . . . . . 9 ⊢ (¬ 𝑎 ∈ ran 𝐸 → 𝑎 ≠ ∅)
49		nnsuc 7828	. . . . . . . . 9 ⊢ ((𝑎 ∈ ω ∧ 𝑎 ≠ ∅) → ∃𝑏 ∈ ω 𝑎 = suc 𝑏)
50	48, 49	sylan2 594	. . . . . . . 8 ⊢ ((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) → ∃𝑏 ∈ ω 𝑎 = suc 𝑏)
51		eleq1 2825	. . . . . . . . . . . . 13 ⊢ (𝑎 = suc 𝑏 → (𝑎 ∈ ω ↔ suc 𝑏 ∈ ω))
52		eleq1 2825	. . . . . . . . . . . . . 14 ⊢ (𝑎 = suc 𝑏 → (𝑎 ∈ ran 𝐸 ↔ suc 𝑏 ∈ ran 𝐸))
53	52	notbid 318	. . . . . . . . . . . . 13 ⊢ (𝑎 = suc 𝑏 → (¬ 𝑎 ∈ ran 𝐸 ↔ ¬ suc 𝑏 ∈ ran 𝐸))
54	51, 53	anbi12d 633	. . . . . . . . . . . 12 ⊢ (𝑎 = suc 𝑏 → ((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ↔ (suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸)))
55	54	anbi1d 632	. . . . . . . . . . 11 ⊢ (𝑎 = suc 𝑏 → (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ 𝑏 ∈ ω) ↔ ((suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸) ∧ 𝑏 ∈ ω)))
56		simplr 769	. . . . . . . . . . . 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 253	. . . . . . . . . 10 ⊢ (𝑎 = suc 𝑏 → (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ 𝑏 ∈ ω) → 𝑏 ∈ ran 𝐸))
60	59	com12 32	. . . . . . . . 9 ⊢ (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ 𝑏 ∈ ω) → (𝑎 = suc 𝑏 → 𝑏 ∈ ran 𝐸))
61	60	impr 454	. . . . . . . 8 ⊢ (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ (𝑏 ∈ ω ∧ 𝑎 = suc 𝑏)) → 𝑏 ∈ ran 𝐸)
62		simprr 773	. . . . . . . . 9 ⊢ (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ (𝑏 ∈ ω ∧ 𝑎 = suc 𝑏)) → 𝑎 = suc 𝑏)
63	62	eqcomd 2743	. . . . . . . 8 ⊢ (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ (𝑏 ∈ ω ∧ 𝑎 = suc 𝑏)) → suc 𝑏 = 𝑎)
64	50, 61, 63	reximssdv 3156	. . . . . . 7 ⊢ ((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) → ∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎)
65	30, 64	impbii 209	. . . . . 6 ⊢ (∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎 ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
66	16, 65	bitri 275	. . . . 5 ⊢ (∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎 ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
67		f1fn 6731	. . . . . . 7 ⊢ (𝑆:On–1-1→On → 𝑆 Fn On)
68	2, 67	ax-mp 5	. . . . . 6 ⊢ 𝑆 Fn On
69		fvelimab 6906	. . . . . 6 ⊢ ((𝑆 Fn On ∧ ran 𝐸 ⊆ On) → (𝑎 ∈ (𝑆 “ ran 𝐸) ↔ ∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎))
70	68, 9, 69	mp2an 693	. . . . 5 ⊢ (𝑎 ∈ (𝑆 “ ran 𝐸) ↔ ∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎)
71		eldif 3900	. . . . 5 ⊢ (𝑎 ∈ (ω ∖ ran 𝐸) ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
72	66, 70, 71	3bitr4i 303	. . . 4 ⊢ (𝑎 ∈ (𝑆 “ ran 𝐸) ↔ 𝑎 ∈ (ω ∖ ran 𝐸))
73	72	eqriv 2734	. . 3 ⊢ (𝑆 “ ran 𝐸) = (ω ∖ ran 𝐸)
74		f1oeq3 6764	. . 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 230	1 ⊢ (𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(ω ∖ ran 𝐸)

Colors of variables: wff setvar class

Syntax hints: ¬ wn 3 ↔ wb 206 ∧ wa 395 = wceq 1542 ∈ wcel 2114 ≠ wne 2933 ∃wrex 3062 ∖ cdif 3887 ⊆ wss 3890 ∅c0 4274 ↦ cmpt 5167 dom cdm 5624 ran crn 5625 ↾ cres 5626 “ cima 5627 Oncon0 6317 suc csuc 6319 Fun wfun 6486 Fn wfn 6487 ⟶wf 6488 –1-1→wf1 6489 –1-1-onto→wf1o 6491 ‘cfv 6492 (class class class)co 7360 ωcom 7810 2_oc2o 8392 ·_o comu 8396

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1797 ax-4 1811 ax-5 1912 ax-6 1969 ax-7 2010 ax-8 2116 ax-9 2124 ax-10 2147 ax-11 2163 ax-12 2185 ax-ext 2709 ax-rep 5212 ax-sep 5231 ax-nul 5241 ax-pr 5370 ax-un 7682

This theorem depends on definitions: df-bi 207 df-an 396 df-or 849 df-3or 1088 df-3an 1089 df-tru 1545 df-fal 1555 df-ex 1782 df-nf 1786 df-sb 2069 df-mo 2540 df-eu 2570 df-clab 2716 df-cleq 2729 df-clel 2812 df-nfc 2886 df-ne 2934 df-ral 3053 df-rex 3063 df-reu 3344 df-rab 3391 df-v 3432 df-sbc 3730 df-csb 3839 df-dif 3893 df-un 3895 df-in 3897 df-ss 3907 df-pss 3910 df-nul 4275 df-if 4468 df-pw 4544 df-sn 4569 df-pr 4571 df-op 4575 df-uni 4852 df-iun 4936 df-br 5087 df-opab 5149 df-mpt 5168 df-tr 5194 df-id 5519 df-eprel 5524 df-po 5532 df-so 5533 df-fr 5577 df-we 5579 df-xp 5630 df-rel 5631 df-cnv 5632 df-co 5633 df-dm 5634 df-rn 5635 df-res 5636 df-ima 5637 df-pred 6259 df-ord 6320 df-on 6321 df-lim 6322 df-suc 6323 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-ov 7363 df-oprab 7364 df-mpo 7365 df-om 7811 df-2nd 7936 df-frecs 8224 df-wrecs 8255 df-recs 8304 df-rdg 8342 df-1o 8398 df-2o 8399 df-oadd 8402 df-omul 8403

This theorem is referenced by: fin1a2lem7 10319

W3C validator