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 6724	. . . 4 ⊢ (𝐸:ω–1-1→ω → 𝐸:ω⟶ω)
6		frn 6663	. . . . 5 ⊢ (𝐸:ω⟶ω → ran 𝐸 ⊆ ω)
7		omsson 7810	. . . . 5 ⊢ ω ⊆ On
8	6, 7	sstrdi 3950	. . . 4 ⊢ (𝐸:ω⟶ω → ran 𝐸 ⊆ On)
9	4, 5, 8	mp2b 10	. . 3 ⊢ ran 𝐸 ⊆ On
10		f1ores 6782	. . 3 ⊢ ((𝑆:On–1-1→On ∧ ran 𝐸 ⊆ On) → (𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(𝑆 “ ran 𝐸))
11	2, 9, 10	mp2an 692	. 2 ⊢ (𝑆 ↾ ran 𝐸):ran 𝐸–1-1-onto→(𝑆 “ ran 𝐸)
12	9	sseli 3933	. . . . . . . . 9 ⊢ (𝑏 ∈ ran 𝐸 → 𝑏 ∈ On)
13	1	fin1a2lem1 10313	. . . . . . . . 9 ⊢ (𝑏 ∈ On → (𝑆‘𝑏) = suc 𝑏)
14	12, 13	syl 17	. . . . . . . 8 ⊢ (𝑏 ∈ ran 𝐸 → (𝑆‘𝑏) = suc 𝑏)
15	14	eqeq1d 2731	. . . . . . 7 ⊢ (𝑏 ∈ ran 𝐸 → ((𝑆‘𝑏) = 𝑎 ↔ suc 𝑏 = 𝑎))
16	15	rexbiia 3074	. . . . . 6 ⊢ (∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎 ↔ ∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎)
17	4, 5, 6	mp2b 10	. . . . . . . . . . . 12 ⊢ ran 𝐸 ⊆ ω
18	17	sseli 3933	. . . . . . . . . . 11 ⊢ (𝑏 ∈ ran 𝐸 → 𝑏 ∈ ω)
19		peano2 7830	. . . . . . . . . . 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 2816	. . . . . . . . . 10 ⊢ (suc 𝑏 = 𝑎 → (suc 𝑏 ∈ ω ↔ 𝑎 ∈ ω))
26		eleq1 2816	. . . . . . . . . . 11 ⊢ (suc 𝑏 = 𝑎 → (suc 𝑏 ∈ ran 𝐸 ↔ 𝑎 ∈ ran 𝐸))
27	26	notbid 318	. . . . . . . . . 10 ⊢ (suc 𝑏 = 𝑎 → (¬ suc 𝑏 ∈ ran 𝐸 ↔ ¬ 𝑎 ∈ ran 𝐸))
28	25, 27	anbi12d 632	. . . . . . . . 9 ⊢ (suc 𝑏 = 𝑎 → ((suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸) ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸)))
29	24, 28	syl5ibcom 245	. . . . . . . 8 ⊢ (𝑏 ∈ ran 𝐸 → (suc 𝑏 = 𝑎 → (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸)))
30	29	rexlimiv 3123	. . . . . . 7 ⊢ (∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎 → (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
31		peano1 7829	. . . . . . . . . . . . . 14 ⊢ ∅ ∈ ω
32	3	fin1a2lem3 10315	. . . . . . . . . . . . . 14 ⊢ (∅ ∈ ω → (𝐸‘∅) = (2_o ·_o ∅))
33	31, 32	ax-mp 5	. . . . . . . . . . . . 13 ⊢ (𝐸‘∅) = (2_o ·_o ∅)
34		2on 8408	. . . . . . . . . . . . . 14 ⊢ 2_o ∈ On
35		om0 8442	. . . . . . . . . . . . . 14 ⊢ (2_o ∈ On → (2_o ·_o ∅) = ∅)
36	34, 35	ax-mp 5	. . . . . . . . . . . . 13 ⊢ (2_o ·_o ∅) = ∅
37	33, 36	eqtri 2752	. . . . . . . . . . . 12 ⊢ (𝐸‘∅) = ∅
38		f1fun 6726	. . . . . . . . . . . . . 14 ⊢ (𝐸:ω–1-1→ω → Fun 𝐸)
39	4, 38	ax-mp 5	. . . . . . . . . . . . 13 ⊢ Fun 𝐸
40		f1dm 6728	. . . . . . . . . . . . . . 15 ⊢ (𝐸:ω–1-1→ω → dom 𝐸 = ω)
41	4, 40	ax-mp 5	. . . . . . . . . . . . . 14 ⊢ dom 𝐸 = ω
42	31, 41	eleqtrri 2827	. . . . . . . . . . . . 13 ⊢ ∅ ∈ dom 𝐸
43		fvelrn 7014	. . . . . . . . . . . . 13 ⊢ ((Fun 𝐸 ∧ ∅ ∈ dom 𝐸) → (𝐸‘∅) ∈ ran 𝐸)
44	39, 42, 43	mp2an 692	. . . . . . . . . . . 12 ⊢ (𝐸‘∅) ∈ ran 𝐸
45	37, 44	eqeltrri 2825	. . . . . . . . . . 11 ⊢ ∅ ∈ ran 𝐸
46		eleq1 2816	. . . . . . . . . . 11 ⊢ (𝑎 = ∅ → (𝑎 ∈ ran 𝐸 ↔ ∅ ∈ ran 𝐸))
47	45, 46	mpbiri 258	. . . . . . . . . 10 ⊢ (𝑎 = ∅ → 𝑎 ∈ ran 𝐸)
48	47	necon3bi 2951	. . . . . . . . 9 ⊢ (¬ 𝑎 ∈ ran 𝐸 → 𝑎 ≠ ∅)
49		nnsuc 7824	. . . . . . . . 9 ⊢ ((𝑎 ∈ ω ∧ 𝑎 ≠ ∅) → ∃𝑏 ∈ ω 𝑎 = suc 𝑏)
50	48, 49	sylan2 593	. . . . . . . 8 ⊢ ((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) → ∃𝑏 ∈ ω 𝑎 = suc 𝑏)
51		eleq1 2816	. . . . . . . . . . . . 13 ⊢ (𝑎 = suc 𝑏 → (𝑎 ∈ ω ↔ suc 𝑏 ∈ ω))
52		eleq1 2816	. . . . . . . . . . . . . 14 ⊢ (𝑎 = suc 𝑏 → (𝑎 ∈ ran 𝐸 ↔ suc 𝑏 ∈ ran 𝐸))
53	52	notbid 318	. . . . . . . . . . . . 13 ⊢ (𝑎 = suc 𝑏 → (¬ 𝑎 ∈ ran 𝐸 ↔ ¬ suc 𝑏 ∈ ran 𝐸))
54	51, 53	anbi12d 632	. . . . . . . . . . . 12 ⊢ (𝑎 = suc 𝑏 → ((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ↔ (suc 𝑏 ∈ ω ∧ ¬ suc 𝑏 ∈ ran 𝐸)))
55	54	anbi1d 631	. . . . . . . . . . 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 253	. . . . . . . . . 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 2735	. . . . . . . 8 ⊢ (((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) ∧ (𝑏 ∈ ω ∧ 𝑎 = suc 𝑏)) → suc 𝑏 = 𝑎)
64	50, 61, 63	reximssdv 3147	. . . . . . 7 ⊢ ((𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸) → ∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎)
65	30, 64	impbii 209	. . . . . 6 ⊢ (∃𝑏 ∈ ran 𝐸 suc 𝑏 = 𝑎 ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
66	16, 65	bitri 275	. . . . 5 ⊢ (∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎 ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
67		f1fn 6725	. . . . . . 7 ⊢ (𝑆:On–1-1→On → 𝑆 Fn On)
68	2, 67	ax-mp 5	. . . . . 6 ⊢ 𝑆 Fn On
69		fvelimab 6899	. . . . . 6 ⊢ ((𝑆 Fn On ∧ ran 𝐸 ⊆ On) → (𝑎 ∈ (𝑆 “ ran 𝐸) ↔ ∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎))
70	68, 9, 69	mp2an 692	. . . . 5 ⊢ (𝑎 ∈ (𝑆 “ ran 𝐸) ↔ ∃𝑏 ∈ ran 𝐸(𝑆‘𝑏) = 𝑎)
71		eldif 3915	. . . . 5 ⊢ (𝑎 ∈ (ω ∖ ran 𝐸) ↔ (𝑎 ∈ ω ∧ ¬ 𝑎 ∈ ran 𝐸))
72	66, 70, 71	3bitr4i 303	. . . 4 ⊢ (𝑎 ∈ (𝑆 “ ran 𝐸) ↔ 𝑎 ∈ (ω ∖ ran 𝐸))
73	72	eqriv 2726	. . 3 ⊢ (𝑆 “ ran 𝐸) = (ω ∖ ran 𝐸)
74		f1oeq3 6758	. . 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 1540 ∈ wcel 2109 ≠ wne 2925 ∃wrex 3053 ∖ cdif 3902 ⊆ wss 3905 ∅c0 4286 ↦ cmpt 5176 dom cdm 5623 ran crn 5624 ↾ cres 5625 “ cima 5626 Oncon0 6311 suc csuc 6313 Fun wfun 6480 Fn wfn 6481 ⟶wf 6482 –1-1→wf1 6483 –1-1-onto→wf1o 6485 ‘cfv 6486 (class class class)co 7353 ωcom 7806 2_oc2o 8389 ·_o comu 8393

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1795 ax-4 1809 ax-5 1910 ax-6 1967 ax-7 2008 ax-8 2111 ax-9 2119 ax-10 2142 ax-11 2158 ax-12 2178 ax-ext 2701 ax-rep 5221 ax-sep 5238 ax-nul 5248 ax-pr 5374 ax-un 7675

This theorem depends on definitions: df-bi 207 df-an 396 df-or 848 df-3or 1087 df-3an 1088 df-tru 1543 df-fal 1553 df-ex 1780 df-nf 1784 df-sb 2066 df-mo 2533 df-eu 2562 df-clab 2708 df-cleq 2721 df-clel 2803 df-nfc 2878 df-ne 2926 df-ral 3045 df-rex 3054 df-reu 3346 df-rab 3397 df-v 3440 df-sbc 3745 df-csb 3854 df-dif 3908 df-un 3910 df-in 3912 df-ss 3922 df-pss 3925 df-nul 4287 df-if 4479 df-pw 4555 df-sn 4580 df-pr 4582 df-op 4586 df-uni 4862 df-iun 4946 df-br 5096 df-opab 5158 df-mpt 5177 df-tr 5203 df-id 5518 df-eprel 5523 df-po 5531 df-so 5532 df-fr 5576 df-we 5578 df-xp 5629 df-rel 5630 df-cnv 5631 df-co 5632 df-dm 5633 df-rn 5634 df-res 5635 df-ima 5636 df-pred 6253 df-ord 6314 df-on 6315 df-lim 6316 df-suc 6317 df-iota 6442 df-fun 6488 df-fn 6489 df-f 6490 df-f1 6491 df-fo 6492 df-f1o 6493 df-fv 6494 df-ov 7356 df-oprab 7357 df-mpo 7358 df-om 7807 df-2nd 7932 df-frecs 8221 df-wrecs 8252 df-recs 8301 df-rdg 8339 df-1o 8395 df-2o 8396 df-oadd 8399 df-omul 8400

This theorem is referenced by: fin1a2lem7 10319

W3C validator