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

Theorem 1arith 15412
Description: Fundamental theorem of arithmetic, where a prime factorization is represented as a sequence of prime exponents, for which only finitely many primes have nonzero exponent. The function 𝑀 maps the set of positive integers one-to-one onto the set of prime factorizations 𝑅. (Contributed by Paul Chapman, 17-Nov-2012.) (Proof shortened by Mario Carneiro, 30-May-2014.)
Hypotheses
Ref Expression
1arith.1 𝑀 = (𝑛 ∈ ℕ ↦ (𝑝 ∈ ℙ ↦ (𝑝 pCnt 𝑛)))
1arith.2 𝑅 = {𝑒 ∈ (ℕ0𝑚 ℙ) ∣ (𝑒 “ ℕ) ∈ Fin}
Assertion
Ref Expression
1arith 𝑀:ℕ–1-1-onto𝑅
Distinct variable groups:   𝑒,𝑛,𝑝   𝑒,𝑀   𝑅,𝑛
Allowed substitution hints:   𝑅(𝑒,𝑝)   𝑀(𝑛,𝑝)

Proof of Theorem 1arith
Dummy variables 𝑓 𝑔 𝑘 𝑞 𝑥 𝑦 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 zex 11216 . . . . . . 7 ℤ ∈ V
2 prmz 15170 . . . . . . . 8 (𝑞 ∈ ℙ → 𝑞 ∈ ℤ)
32ssriv 3568 . . . . . . 7 ℙ ⊆ ℤ
41, 3ssexi 4723 . . . . . 6 ℙ ∈ V
54mptex 6365 . . . . 5 (𝑝 ∈ ℙ ↦ (𝑝 pCnt 𝑛)) ∈ V
6 1arith.1 . . . . 5 𝑀 = (𝑛 ∈ ℕ ↦ (𝑝 ∈ ℙ ↦ (𝑝 pCnt 𝑛)))
75, 6fnmpti 5918 . . . 4 𝑀 Fn ℕ
861arithlem3 15410 . . . . . . 7 (𝑥 ∈ ℕ → (𝑀𝑥):ℙ⟶ℕ0)
9 nn0ex 11142 . . . . . . . 8 0 ∈ V
109, 4elmap 7746 . . . . . . 7 ((𝑀𝑥) ∈ (ℕ0𝑚 ℙ) ↔ (𝑀𝑥):ℙ⟶ℕ0)
118, 10sylibr 222 . . . . . 6 (𝑥 ∈ ℕ → (𝑀𝑥) ∈ (ℕ0𝑚 ℙ))
12 fzfi 12585 . . . . . . 7 (1...𝑥) ∈ Fin
13 ffn 5941 . . . . . . . . . 10 ((𝑀𝑥):ℙ⟶ℕ0 → (𝑀𝑥) Fn ℙ)
14 elpreima 6227 . . . . . . . . . 10 ((𝑀𝑥) Fn ℙ → (𝑞 ∈ ((𝑀𝑥) “ ℕ) ↔ (𝑞 ∈ ℙ ∧ ((𝑀𝑥)‘𝑞) ∈ ℕ)))
158, 13, 143syl 18 . . . . . . . . 9 (𝑥 ∈ ℕ → (𝑞 ∈ ((𝑀𝑥) “ ℕ) ↔ (𝑞 ∈ ℙ ∧ ((𝑀𝑥)‘𝑞) ∈ ℕ)))
1661arithlem2 15409 . . . . . . . . . . . 12 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → ((𝑀𝑥)‘𝑞) = (𝑞 pCnt 𝑥))
1716eleq1d 2668 . . . . . . . . . . 11 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → (((𝑀𝑥)‘𝑞) ∈ ℕ ↔ (𝑞 pCnt 𝑥) ∈ ℕ))
18 id 22 . . . . . . . . . . . . 13 (𝑥 ∈ ℕ → 𝑥 ∈ ℕ)
19 dvdsle 14813 . . . . . . . . . . . . 13 ((𝑞 ∈ ℤ ∧ 𝑥 ∈ ℕ) → (𝑞𝑥𝑞𝑥))
202, 18, 19syl2anr 493 . . . . . . . . . . . 12 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → (𝑞𝑥𝑞𝑥))
21 pcelnn 15355 . . . . . . . . . . . . 13 ((𝑞 ∈ ℙ ∧ 𝑥 ∈ ℕ) → ((𝑞 pCnt 𝑥) ∈ ℕ ↔ 𝑞𝑥))
2221ancoms 467 . . . . . . . . . . . 12 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → ((𝑞 pCnt 𝑥) ∈ ℕ ↔ 𝑞𝑥))
23 prmnn 15169 . . . . . . . . . . . . . 14 (𝑞 ∈ ℙ → 𝑞 ∈ ℕ)
24 nnuz 11552 . . . . . . . . . . . . . 14 ℕ = (ℤ‘1)
2523, 24syl6eleq 2694 . . . . . . . . . . . . 13 (𝑞 ∈ ℙ → 𝑞 ∈ (ℤ‘1))
26 nnz 11229 . . . . . . . . . . . . 13 (𝑥 ∈ ℕ → 𝑥 ∈ ℤ)
27 elfz5 12157 . . . . . . . . . . . . 13 ((𝑞 ∈ (ℤ‘1) ∧ 𝑥 ∈ ℤ) → (𝑞 ∈ (1...𝑥) ↔ 𝑞𝑥))
2825, 26, 27syl2anr 493 . . . . . . . . . . . 12 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → (𝑞 ∈ (1...𝑥) ↔ 𝑞𝑥))
2920, 22, 283imtr4d 281 . . . . . . . . . . 11 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → ((𝑞 pCnt 𝑥) ∈ ℕ → 𝑞 ∈ (1...𝑥)))
3017, 29sylbid 228 . . . . . . . . . 10 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → (((𝑀𝑥)‘𝑞) ∈ ℕ → 𝑞 ∈ (1...𝑥)))
3130expimpd 626 . . . . . . . . 9 (𝑥 ∈ ℕ → ((𝑞 ∈ ℙ ∧ ((𝑀𝑥)‘𝑞) ∈ ℕ) → 𝑞 ∈ (1...𝑥)))
3215, 31sylbid 228 . . . . . . . 8 (𝑥 ∈ ℕ → (𝑞 ∈ ((𝑀𝑥) “ ℕ) → 𝑞 ∈ (1...𝑥)))
3332ssrdv 3570 . . . . . . 7 (𝑥 ∈ ℕ → ((𝑀𝑥) “ ℕ) ⊆ (1...𝑥))
34 ssfi 8039 . . . . . . 7 (((1...𝑥) ∈ Fin ∧ ((𝑀𝑥) “ ℕ) ⊆ (1...𝑥)) → ((𝑀𝑥) “ ℕ) ∈ Fin)
3512, 33, 34sylancr 693 . . . . . 6 (𝑥 ∈ ℕ → ((𝑀𝑥) “ ℕ) ∈ Fin)
36 cnveq 5203 . . . . . . . . 9 (𝑒 = (𝑀𝑥) → 𝑒 = (𝑀𝑥))
3736imaeq1d 5368 . . . . . . . 8 (𝑒 = (𝑀𝑥) → (𝑒 “ ℕ) = ((𝑀𝑥) “ ℕ))
3837eleq1d 2668 . . . . . . 7 (𝑒 = (𝑀𝑥) → ((𝑒 “ ℕ) ∈ Fin ↔ ((𝑀𝑥) “ ℕ) ∈ Fin))
39 1arith.2 . . . . . . 7 𝑅 = {𝑒 ∈ (ℕ0𝑚 ℙ) ∣ (𝑒 “ ℕ) ∈ Fin}
4038, 39elrab2 3329 . . . . . 6 ((𝑀𝑥) ∈ 𝑅 ↔ ((𝑀𝑥) ∈ (ℕ0𝑚 ℙ) ∧ ((𝑀𝑥) “ ℕ) ∈ Fin))
4111, 35, 40sylanbrc 694 . . . . 5 (𝑥 ∈ ℕ → (𝑀𝑥) ∈ 𝑅)
4241rgen 2902 . . . 4 𝑥 ∈ ℕ (𝑀𝑥) ∈ 𝑅
43 ffnfv 6277 . . . 4 (𝑀:ℕ⟶𝑅 ↔ (𝑀 Fn ℕ ∧ ∀𝑥 ∈ ℕ (𝑀𝑥) ∈ 𝑅))
447, 42, 43mpbir2an 956 . . 3 𝑀:ℕ⟶𝑅
4516adantlr 746 . . . . . . . 8 (((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) ∧ 𝑞 ∈ ℙ) → ((𝑀𝑥)‘𝑞) = (𝑞 pCnt 𝑥))
4661arithlem2 15409 . . . . . . . . 9 ((𝑦 ∈ ℕ ∧ 𝑞 ∈ ℙ) → ((𝑀𝑦)‘𝑞) = (𝑞 pCnt 𝑦))
4746adantll 745 . . . . . . . 8 (((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) ∧ 𝑞 ∈ ℙ) → ((𝑀𝑦)‘𝑞) = (𝑞 pCnt 𝑦))
4845, 47eqeq12d 2621 . . . . . . 7 (((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) ∧ 𝑞 ∈ ℙ) → (((𝑀𝑥)‘𝑞) = ((𝑀𝑦)‘𝑞) ↔ (𝑞 pCnt 𝑥) = (𝑞 pCnt 𝑦)))
4948ralbidva 2964 . . . . . 6 ((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) → (∀𝑞 ∈ ℙ ((𝑀𝑥)‘𝑞) = ((𝑀𝑦)‘𝑞) ↔ ∀𝑞 ∈ ℙ (𝑞 pCnt 𝑥) = (𝑞 pCnt 𝑦)))
5061arithlem3 15410 . . . . . . 7 (𝑦 ∈ ℕ → (𝑀𝑦):ℙ⟶ℕ0)
51 ffn 5941 . . . . . . . 8 ((𝑀𝑦):ℙ⟶ℕ0 → (𝑀𝑦) Fn ℙ)
52 eqfnfv 6201 . . . . . . . 8 (((𝑀𝑥) Fn ℙ ∧ (𝑀𝑦) Fn ℙ) → ((𝑀𝑥) = (𝑀𝑦) ↔ ∀𝑞 ∈ ℙ ((𝑀𝑥)‘𝑞) = ((𝑀𝑦)‘𝑞)))
5313, 51, 52syl2an 492 . . . . . . 7 (((𝑀𝑥):ℙ⟶ℕ0 ∧ (𝑀𝑦):ℙ⟶ℕ0) → ((𝑀𝑥) = (𝑀𝑦) ↔ ∀𝑞 ∈ ℙ ((𝑀𝑥)‘𝑞) = ((𝑀𝑦)‘𝑞)))
548, 50, 53syl2an 492 . . . . . 6 ((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) → ((𝑀𝑥) = (𝑀𝑦) ↔ ∀𝑞 ∈ ℙ ((𝑀𝑥)‘𝑞) = ((𝑀𝑦)‘𝑞)))
55 nnnn0 11143 . . . . . . 7 (𝑥 ∈ ℕ → 𝑥 ∈ ℕ0)
56 nnnn0 11143 . . . . . . 7 (𝑦 ∈ ℕ → 𝑦 ∈ ℕ0)
57 pc11 15365 . . . . . . 7 ((𝑥 ∈ ℕ0𝑦 ∈ ℕ0) → (𝑥 = 𝑦 ↔ ∀𝑞 ∈ ℙ (𝑞 pCnt 𝑥) = (𝑞 pCnt 𝑦)))
5855, 56, 57syl2an 492 . . . . . 6 ((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) → (𝑥 = 𝑦 ↔ ∀𝑞 ∈ ℙ (𝑞 pCnt 𝑥) = (𝑞 pCnt 𝑦)))
5949, 54, 583bitr4d 298 . . . . 5 ((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) → ((𝑀𝑥) = (𝑀𝑦) ↔ 𝑥 = 𝑦))
6059biimpd 217 . . . 4 ((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) → ((𝑀𝑥) = (𝑀𝑦) → 𝑥 = 𝑦))
6160rgen2a 2956 . . 3 𝑥 ∈ ℕ ∀𝑦 ∈ ℕ ((𝑀𝑥) = (𝑀𝑦) → 𝑥 = 𝑦)
62 dff13 6391 . . 3 (𝑀:ℕ–1-1𝑅 ↔ (𝑀:ℕ⟶𝑅 ∧ ∀𝑥 ∈ ℕ ∀𝑦 ∈ ℕ ((𝑀𝑥) = (𝑀𝑦) → 𝑥 = 𝑦)))
6344, 61, 62mpbir2an 956 . 2 𝑀:ℕ–1-1𝑅
64 eqid 2606 . . . . . 6 (𝑔 ∈ ℕ ↦ if(𝑔 ∈ ℙ, (𝑔↑(𝑓𝑔)), 1)) = (𝑔 ∈ ℕ ↦ if(𝑔 ∈ ℙ, (𝑔↑(𝑓𝑔)), 1))
65 cnveq 5203 . . . . . . . . . . . 12 (𝑒 = 𝑓𝑒 = 𝑓)
6665imaeq1d 5368 . . . . . . . . . . 11 (𝑒 = 𝑓 → (𝑒 “ ℕ) = (𝑓 “ ℕ))
6766eleq1d 2668 . . . . . . . . . 10 (𝑒 = 𝑓 → ((𝑒 “ ℕ) ∈ Fin ↔ (𝑓 “ ℕ) ∈ Fin))
6867, 39elrab2 3329 . . . . . . . . 9 (𝑓𝑅 ↔ (𝑓 ∈ (ℕ0𝑚 ℙ) ∧ (𝑓 “ ℕ) ∈ Fin))
6968simplbi 474 . . . . . . . 8 (𝑓𝑅𝑓 ∈ (ℕ0𝑚 ℙ))
709, 4elmap 7746 . . . . . . . 8 (𝑓 ∈ (ℕ0𝑚 ℙ) ↔ 𝑓:ℙ⟶ℕ0)
7169, 70sylib 206 . . . . . . 7 (𝑓𝑅𝑓:ℙ⟶ℕ0)
7271ad2antrr 757 . . . . . 6 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → 𝑓:ℙ⟶ℕ0)
73 simplr 787 . . . . . . . . 9 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → 𝑦 ∈ ℝ)
74 0re 9893 . . . . . . . . 9 0 ∈ ℝ
75 ifcl 4076 . . . . . . . . 9 ((𝑦 ∈ ℝ ∧ 0 ∈ ℝ) → if(0 ≤ 𝑦, 𝑦, 0) ∈ ℝ)
7673, 74, 75sylancl 692 . . . . . . . 8 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → if(0 ≤ 𝑦, 𝑦, 0) ∈ ℝ)
77 max1 11846 . . . . . . . . 9 ((0 ∈ ℝ ∧ 𝑦 ∈ ℝ) → 0 ≤ if(0 ≤ 𝑦, 𝑦, 0))
7874, 73, 77sylancr 693 . . . . . . . 8 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → 0 ≤ if(0 ≤ 𝑦, 𝑦, 0))
79 flge0nn0 12435 . . . . . . . 8 ((if(0 ≤ 𝑦, 𝑦, 0) ∈ ℝ ∧ 0 ≤ if(0 ≤ 𝑦, 𝑦, 0)) → (⌊‘if(0 ≤ 𝑦, 𝑦, 0)) ∈ ℕ0)
8076, 78, 79syl2anc 690 . . . . . . 7 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → (⌊‘if(0 ≤ 𝑦, 𝑦, 0)) ∈ ℕ0)
81 nn0p1nn 11176 . . . . . . 7 ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) ∈ ℕ0 → ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ∈ ℕ)
8280, 81syl 17 . . . . . 6 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ∈ ℕ)
8373adantr 479 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑦 ∈ ℝ)
8482adantr 479 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ∈ ℕ)
8584nnred 10879 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ∈ ℝ)
86 zssre 11214 . . . . . . . . . . . 12 ℤ ⊆ ℝ
873, 86sstri 3573 . . . . . . . . . . 11 ℙ ⊆ ℝ
88 simprl 789 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑞 ∈ ℙ)
8987, 88sseldi 3562 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑞 ∈ ℝ)
9076adantr 479 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → if(0 ≤ 𝑦, 𝑦, 0) ∈ ℝ)
91 max2 11848 . . . . . . . . . . . 12 ((0 ∈ ℝ ∧ 𝑦 ∈ ℝ) → 𝑦 ≤ if(0 ≤ 𝑦, 𝑦, 0))
9274, 83, 91sylancr 693 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑦 ≤ if(0 ≤ 𝑦, 𝑦, 0))
93 flltp1 12415 . . . . . . . . . . . 12 (if(0 ≤ 𝑦, 𝑦, 0) ∈ ℝ → if(0 ≤ 𝑦, 𝑦, 0) < ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1))
9490, 93syl 17 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → if(0 ≤ 𝑦, 𝑦, 0) < ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1))
9583, 90, 85, 92, 94lelttrd 10043 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑦 < ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1))
96 simprr 791 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)
9783, 85, 89, 95, 96ltletrd 10045 . . . . . . . . 9 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑦 < 𝑞)
9883, 89ltnled 10032 . . . . . . . . 9 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (𝑦 < 𝑞 ↔ ¬ 𝑞𝑦))
9997, 98mpbid 220 . . . . . . . 8 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ¬ 𝑞𝑦)
10088biantrurd 527 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((𝑓𝑞) ∈ ℕ ↔ (𝑞 ∈ ℙ ∧ (𝑓𝑞) ∈ ℕ)))
10172adantr 479 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑓:ℙ⟶ℕ0)
102 ffn 5941 . . . . . . . . . . 11 (𝑓:ℙ⟶ℕ0𝑓 Fn ℙ)
103 elpreima 6227 . . . . . . . . . . 11 (𝑓 Fn ℙ → (𝑞 ∈ (𝑓 “ ℕ) ↔ (𝑞 ∈ ℙ ∧ (𝑓𝑞) ∈ ℕ)))
104101, 102, 1033syl 18 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (𝑞 ∈ (𝑓 “ ℕ) ↔ (𝑞 ∈ ℙ ∧ (𝑓𝑞) ∈ ℕ)))
105100, 104bitr4d 269 . . . . . . . . 9 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((𝑓𝑞) ∈ ℕ ↔ 𝑞 ∈ (𝑓 “ ℕ)))
106 simplr 787 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦)
107 breq1 4577 . . . . . . . . . . 11 (𝑘 = 𝑞 → (𝑘𝑦𝑞𝑦))
108107rspccv 3275 . . . . . . . . . 10 (∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦 → (𝑞 ∈ (𝑓 “ ℕ) → 𝑞𝑦))
109106, 108syl 17 . . . . . . . . 9 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (𝑞 ∈ (𝑓 “ ℕ) → 𝑞𝑦))
110105, 109sylbid 228 . . . . . . . 8 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((𝑓𝑞) ∈ ℕ → 𝑞𝑦))
11199, 110mtod 187 . . . . . . 7 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ¬ (𝑓𝑞) ∈ ℕ)
112101, 88ffvelrnd 6250 . . . . . . . . 9 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (𝑓𝑞) ∈ ℕ0)
113 elnn0 11138 . . . . . . . . 9 ((𝑓𝑞) ∈ ℕ0 ↔ ((𝑓𝑞) ∈ ℕ ∨ (𝑓𝑞) = 0))
114112, 113sylib 206 . . . . . . . 8 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((𝑓𝑞) ∈ ℕ ∨ (𝑓𝑞) = 0))
115114ord 390 . . . . . . 7 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (¬ (𝑓𝑞) ∈ ℕ → (𝑓𝑞) = 0))
116111, 115mpd 15 . . . . . 6 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (𝑓𝑞) = 0)
1176, 64, 72, 82, 1161arithlem4 15411 . . . . 5 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → ∃𝑥 ∈ ℕ 𝑓 = (𝑀𝑥))
118 cnvimass 5388 . . . . . . 7 (𝑓 “ ℕ) ⊆ dom 𝑓
119 fdm 5947 . . . . . . . . 9 (𝑓:ℙ⟶ℕ0 → dom 𝑓 = ℙ)
12071, 119syl 17 . . . . . . . 8 (𝑓𝑅 → dom 𝑓 = ℙ)
121120, 87syl6eqss 3614 . . . . . . 7 (𝑓𝑅 → dom 𝑓 ⊆ ℝ)
122118, 121syl5ss 3575 . . . . . 6 (𝑓𝑅 → (𝑓 “ ℕ) ⊆ ℝ)
12368simprbi 478 . . . . . 6 (𝑓𝑅 → (𝑓 “ ℕ) ∈ Fin)
124 fimaxre2 10815 . . . . . 6 (((𝑓 “ ℕ) ⊆ ℝ ∧ (𝑓 “ ℕ) ∈ Fin) → ∃𝑦 ∈ ℝ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦)
125122, 123, 124syl2anc 690 . . . . 5 (𝑓𝑅 → ∃𝑦 ∈ ℝ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦)
126117, 125r19.29a 3056 . . . 4 (𝑓𝑅 → ∃𝑥 ∈ ℕ 𝑓 = (𝑀𝑥))
127126rgen 2902 . . 3 𝑓𝑅𝑥 ∈ ℕ 𝑓 = (𝑀𝑥)
128 dffo3 6264 . . 3 (𝑀:ℕ–onto𝑅 ↔ (𝑀:ℕ⟶𝑅 ∧ ∀𝑓𝑅𝑥 ∈ ℕ 𝑓 = (𝑀𝑥)))
12944, 127, 128mpbir2an 956 . 2 𝑀:ℕ–onto𝑅
130 df-f1o 5794 . 2 (𝑀:ℕ–1-1-onto𝑅 ↔ (𝑀:ℕ–1-1𝑅𝑀:ℕ–onto𝑅))
13163, 129, 130mpbir2an 956 1 𝑀:ℕ–1-1-onto𝑅
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 194  wo 381  wa 382   = wceq 1474  wcel 1976  wral 2892  wrex 2893  {crab 2896  wss 3536  ifcif 4032   class class class wbr 4574  cmpt 4634  ccnv 5024  dom cdm 5025  cima 5028   Fn wfn 5782  wf 5783  1-1wf1 5784  ontowfo 5785  1-1-ontowf1o 5786  cfv 5787  (class class class)co 6524  𝑚 cmap 7718  Fincfn 7815  cr 9788  0cc0 9789  1c1 9790   + caddc 9792   < clt 9927  cle 9928  cn 10864  0cn0 11136  cz 11207  cuz 11516  ...cfz 12149  cfl 12405  cexp 12674  cdvds 14764  cprime 15166   pCnt cpc 15322
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1712  ax-4 1727  ax-5 1826  ax-6 1874  ax-7 1921  ax-8 1978  ax-9 1985  ax-10 2005  ax-11 2020  ax-12 2032  ax-13 2229  ax-ext 2586  ax-rep 4690  ax-sep 4700  ax-nul 4709  ax-pow 4761  ax-pr 4825  ax-un 6821  ax-cnex 9845  ax-resscn 9846  ax-1cn 9847  ax-icn 9848  ax-addcl 9849  ax-addrcl 9850  ax-mulcl 9851  ax-mulrcl 9852  ax-mulcom 9853  ax-addass 9854  ax-mulass 9855  ax-distr 9856  ax-i2m1 9857  ax-1ne0 9858  ax-1rid 9859  ax-rnegex 9860  ax-rrecex 9861  ax-cnre 9862  ax-pre-lttri 9863  ax-pre-lttrn 9864  ax-pre-ltadd 9865  ax-pre-mulgt0 9866  ax-pre-sup 9867
This theorem depends on definitions:  df-bi 195  df-or 383  df-an 384  df-3or 1031  df-3an 1032  df-tru 1477  df-fal 1480  df-ex 1695  df-nf 1700  df-sb 1867  df-eu 2458  df-mo 2459  df-clab 2593  df-cleq 2599  df-clel 2602  df-nfc 2736  df-ne 2778  df-nel 2779  df-ral 2897  df-rex 2898  df-reu 2899  df-rmo 2900  df-rab 2901  df-v 3171  df-sbc 3399  df-csb 3496  df-dif 3539  df-un 3541  df-in 3543  df-ss 3550  df-pss 3552  df-nul 3871  df-if 4033  df-pw 4106  df-sn 4122  df-pr 4124  df-tp 4126  df-op 4128  df-uni 4364  df-int 4402  df-iun 4448  df-br 4575  df-opab 4635  df-mpt 4636  df-tr 4672  df-eprel 4936  df-id 4940  df-po 4946  df-so 4947  df-fr 4984  df-we 4986  df-xp 5031  df-rel 5032  df-cnv 5033  df-co 5034  df-dm 5035  df-rn 5036  df-res 5037  df-ima 5038  df-pred 5580  df-ord 5626  df-on 5627  df-lim 5628  df-suc 5629  df-iota 5751  df-fun 5789  df-fn 5790  df-f 5791  df-f1 5792  df-fo 5793  df-f1o 5794  df-fv 5795  df-riota 6486  df-ov 6527  df-oprab 6528  df-mpt2 6529  df-om 6932  df-1st 7033  df-2nd 7034  df-wrecs 7268  df-recs 7329  df-rdg 7367  df-1o 7421  df-2o 7422  df-oadd 7425  df-er 7603  df-map 7720  df-en 7816  df-dom 7817  df-sdom 7818  df-fin 7819  df-sup 8205  df-inf 8206  df-pnf 9929  df-mnf 9930  df-xr 9931  df-ltxr 9932  df-le 9933  df-sub 10116  df-neg 10117  df-div 10531  df-nn 10865  df-2 10923  df-3 10924  df-n0 11137  df-z 11208  df-uz 11517  df-q 11618  df-rp 11662  df-fz 12150  df-fl 12407  df-mod 12483  df-seq 12616  df-exp 12675  df-cj 13630  df-re 13631  df-im 13632  df-sqrt 13766  df-abs 13767  df-dvds 14765  df-gcd 14998  df-prm 15167  df-pc 15323
This theorem is referenced by:  1arith2  15413  sqff1o  24622
  Copyright terms: Public domain W3C validator