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

Theorem 1arith 16965
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 𝑅 = {𝑒 ∈ (ℕ0m ℙ) ∣ (𝑒 “ ℕ) ∈ 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 prmex 16714 . . . . . 6 ℙ ∈ V
21mptex 7243 . . . . 5 (𝑝 ∈ ℙ ↦ (𝑝 pCnt 𝑛)) ∈ V
3 1arith.1 . . . . 5 𝑀 = (𝑛 ∈ ℕ ↦ (𝑝 ∈ ℙ ↦ (𝑝 pCnt 𝑛)))
42, 3fnmpti 6711 . . . 4 𝑀 Fn ℕ
531arithlem3 16963 . . . . . . 7 (𝑥 ∈ ℕ → (𝑀𝑥):ℙ⟶ℕ0)
6 nn0ex 12532 . . . . . . . 8 0 ∈ V
76, 1elmap 8911 . . . . . . 7 ((𝑀𝑥) ∈ (ℕ0m ℙ) ↔ (𝑀𝑥):ℙ⟶ℕ0)
85, 7sylibr 234 . . . . . 6 (𝑥 ∈ ℕ → (𝑀𝑥) ∈ (ℕ0m ℙ))
9 fzfi 14013 . . . . . . 7 (1...𝑥) ∈ Fin
10 ffn 6736 . . . . . . . . . 10 ((𝑀𝑥):ℙ⟶ℕ0 → (𝑀𝑥) Fn ℙ)
11 elpreima 7078 . . . . . . . . . 10 ((𝑀𝑥) Fn ℙ → (𝑞 ∈ ((𝑀𝑥) “ ℕ) ↔ (𝑞 ∈ ℙ ∧ ((𝑀𝑥)‘𝑞) ∈ ℕ)))
125, 10, 113syl 18 . . . . . . . . 9 (𝑥 ∈ ℕ → (𝑞 ∈ ((𝑀𝑥) “ ℕ) ↔ (𝑞 ∈ ℙ ∧ ((𝑀𝑥)‘𝑞) ∈ ℕ)))
1331arithlem2 16962 . . . . . . . . . . . 12 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → ((𝑀𝑥)‘𝑞) = (𝑞 pCnt 𝑥))
1413eleq1d 2826 . . . . . . . . . . 11 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → (((𝑀𝑥)‘𝑞) ∈ ℕ ↔ (𝑞 pCnt 𝑥) ∈ ℕ))
15 prmz 16712 . . . . . . . . . . . . 13 (𝑞 ∈ ℙ → 𝑞 ∈ ℤ)
16 id 22 . . . . . . . . . . . . 13 (𝑥 ∈ ℕ → 𝑥 ∈ ℕ)
17 dvdsle 16347 . . . . . . . . . . . . 13 ((𝑞 ∈ ℤ ∧ 𝑥 ∈ ℕ) → (𝑞𝑥𝑞𝑥))
1815, 16, 17syl2anr 597 . . . . . . . . . . . 12 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → (𝑞𝑥𝑞𝑥))
19 pcelnn 16908 . . . . . . . . . . . . 13 ((𝑞 ∈ ℙ ∧ 𝑥 ∈ ℕ) → ((𝑞 pCnt 𝑥) ∈ ℕ ↔ 𝑞𝑥))
2019ancoms 458 . . . . . . . . . . . 12 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → ((𝑞 pCnt 𝑥) ∈ ℕ ↔ 𝑞𝑥))
21 prmnn 16711 . . . . . . . . . . . . . 14 (𝑞 ∈ ℙ → 𝑞 ∈ ℕ)
22 nnuz 12921 . . . . . . . . . . . . . 14 ℕ = (ℤ‘1)
2321, 22eleqtrdi 2851 . . . . . . . . . . . . 13 (𝑞 ∈ ℙ → 𝑞 ∈ (ℤ‘1))
24 nnz 12634 . . . . . . . . . . . . 13 (𝑥 ∈ ℕ → 𝑥 ∈ ℤ)
25 elfz5 13556 . . . . . . . . . . . . 13 ((𝑞 ∈ (ℤ‘1) ∧ 𝑥 ∈ ℤ) → (𝑞 ∈ (1...𝑥) ↔ 𝑞𝑥))
2623, 24, 25syl2anr 597 . . . . . . . . . . . 12 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → (𝑞 ∈ (1...𝑥) ↔ 𝑞𝑥))
2718, 20, 263imtr4d 294 . . . . . . . . . . 11 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → ((𝑞 pCnt 𝑥) ∈ ℕ → 𝑞 ∈ (1...𝑥)))
2814, 27sylbid 240 . . . . . . . . . 10 ((𝑥 ∈ ℕ ∧ 𝑞 ∈ ℙ) → (((𝑀𝑥)‘𝑞) ∈ ℕ → 𝑞 ∈ (1...𝑥)))
2928expimpd 453 . . . . . . . . 9 (𝑥 ∈ ℕ → ((𝑞 ∈ ℙ ∧ ((𝑀𝑥)‘𝑞) ∈ ℕ) → 𝑞 ∈ (1...𝑥)))
3012, 29sylbid 240 . . . . . . . 8 (𝑥 ∈ ℕ → (𝑞 ∈ ((𝑀𝑥) “ ℕ) → 𝑞 ∈ (1...𝑥)))
3130ssrdv 3989 . . . . . . 7 (𝑥 ∈ ℕ → ((𝑀𝑥) “ ℕ) ⊆ (1...𝑥))
32 ssfi 9213 . . . . . . 7 (((1...𝑥) ∈ Fin ∧ ((𝑀𝑥) “ ℕ) ⊆ (1...𝑥)) → ((𝑀𝑥) “ ℕ) ∈ Fin)
339, 31, 32sylancr 587 . . . . . 6 (𝑥 ∈ ℕ → ((𝑀𝑥) “ ℕ) ∈ Fin)
34 cnveq 5884 . . . . . . . . 9 (𝑒 = (𝑀𝑥) → 𝑒 = (𝑀𝑥))
3534imaeq1d 6077 . . . . . . . 8 (𝑒 = (𝑀𝑥) → (𝑒 “ ℕ) = ((𝑀𝑥) “ ℕ))
3635eleq1d 2826 . . . . . . 7 (𝑒 = (𝑀𝑥) → ((𝑒 “ ℕ) ∈ Fin ↔ ((𝑀𝑥) “ ℕ) ∈ Fin))
37 1arith.2 . . . . . . 7 𝑅 = {𝑒 ∈ (ℕ0m ℙ) ∣ (𝑒 “ ℕ) ∈ Fin}
3836, 37elrab2 3695 . . . . . 6 ((𝑀𝑥) ∈ 𝑅 ↔ ((𝑀𝑥) ∈ (ℕ0m ℙ) ∧ ((𝑀𝑥) “ ℕ) ∈ Fin))
398, 33, 38sylanbrc 583 . . . . 5 (𝑥 ∈ ℕ → (𝑀𝑥) ∈ 𝑅)
4039rgen 3063 . . . 4 𝑥 ∈ ℕ (𝑀𝑥) ∈ 𝑅
41 ffnfv 7139 . . . 4 (𝑀:ℕ⟶𝑅 ↔ (𝑀 Fn ℕ ∧ ∀𝑥 ∈ ℕ (𝑀𝑥) ∈ 𝑅))
424, 40, 41mpbir2an 711 . . 3 𝑀:ℕ⟶𝑅
4313adantlr 715 . . . . . . . 8 (((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) ∧ 𝑞 ∈ ℙ) → ((𝑀𝑥)‘𝑞) = (𝑞 pCnt 𝑥))
4431arithlem2 16962 . . . . . . . . 9 ((𝑦 ∈ ℕ ∧ 𝑞 ∈ ℙ) → ((𝑀𝑦)‘𝑞) = (𝑞 pCnt 𝑦))
4544adantll 714 . . . . . . . 8 (((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) ∧ 𝑞 ∈ ℙ) → ((𝑀𝑦)‘𝑞) = (𝑞 pCnt 𝑦))
4643, 45eqeq12d 2753 . . . . . . 7 (((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) ∧ 𝑞 ∈ ℙ) → (((𝑀𝑥)‘𝑞) = ((𝑀𝑦)‘𝑞) ↔ (𝑞 pCnt 𝑥) = (𝑞 pCnt 𝑦)))
4746ralbidva 3176 . . . . . 6 ((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) → (∀𝑞 ∈ ℙ ((𝑀𝑥)‘𝑞) = ((𝑀𝑦)‘𝑞) ↔ ∀𝑞 ∈ ℙ (𝑞 pCnt 𝑥) = (𝑞 pCnt 𝑦)))
4831arithlem3 16963 . . . . . . 7 (𝑦 ∈ ℕ → (𝑀𝑦):ℙ⟶ℕ0)
49 ffn 6736 . . . . . . . 8 ((𝑀𝑦):ℙ⟶ℕ0 → (𝑀𝑦) Fn ℙ)
50 eqfnfv 7051 . . . . . . . 8 (((𝑀𝑥) Fn ℙ ∧ (𝑀𝑦) Fn ℙ) → ((𝑀𝑥) = (𝑀𝑦) ↔ ∀𝑞 ∈ ℙ ((𝑀𝑥)‘𝑞) = ((𝑀𝑦)‘𝑞)))
5110, 49, 50syl2an 596 . . . . . . 7 (((𝑀𝑥):ℙ⟶ℕ0 ∧ (𝑀𝑦):ℙ⟶ℕ0) → ((𝑀𝑥) = (𝑀𝑦) ↔ ∀𝑞 ∈ ℙ ((𝑀𝑥)‘𝑞) = ((𝑀𝑦)‘𝑞)))
525, 48, 51syl2an 596 . . . . . 6 ((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) → ((𝑀𝑥) = (𝑀𝑦) ↔ ∀𝑞 ∈ ℙ ((𝑀𝑥)‘𝑞) = ((𝑀𝑦)‘𝑞)))
53 nnnn0 12533 . . . . . . 7 (𝑥 ∈ ℕ → 𝑥 ∈ ℕ0)
54 nnnn0 12533 . . . . . . 7 (𝑦 ∈ ℕ → 𝑦 ∈ ℕ0)
55 pc11 16918 . . . . . . 7 ((𝑥 ∈ ℕ0𝑦 ∈ ℕ0) → (𝑥 = 𝑦 ↔ ∀𝑞 ∈ ℙ (𝑞 pCnt 𝑥) = (𝑞 pCnt 𝑦)))
5653, 54, 55syl2an 596 . . . . . 6 ((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) → (𝑥 = 𝑦 ↔ ∀𝑞 ∈ ℙ (𝑞 pCnt 𝑥) = (𝑞 pCnt 𝑦)))
5747, 52, 563bitr4d 311 . . . . 5 ((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) → ((𝑀𝑥) = (𝑀𝑦) ↔ 𝑥 = 𝑦))
5857biimpd 229 . . . 4 ((𝑥 ∈ ℕ ∧ 𝑦 ∈ ℕ) → ((𝑀𝑥) = (𝑀𝑦) → 𝑥 = 𝑦))
5958rgen2 3199 . . 3 𝑥 ∈ ℕ ∀𝑦 ∈ ℕ ((𝑀𝑥) = (𝑀𝑦) → 𝑥 = 𝑦)
60 dff13 7275 . . 3 (𝑀:ℕ–1-1𝑅 ↔ (𝑀:ℕ⟶𝑅 ∧ ∀𝑥 ∈ ℕ ∀𝑦 ∈ ℕ ((𝑀𝑥) = (𝑀𝑦) → 𝑥 = 𝑦)))
6142, 59, 60mpbir2an 711 . 2 𝑀:ℕ–1-1𝑅
62 eqid 2737 . . . . . 6 (𝑔 ∈ ℕ ↦ if(𝑔 ∈ ℙ, (𝑔↑(𝑓𝑔)), 1)) = (𝑔 ∈ ℕ ↦ if(𝑔 ∈ ℙ, (𝑔↑(𝑓𝑔)), 1))
63 cnveq 5884 . . . . . . . . . . . 12 (𝑒 = 𝑓𝑒 = 𝑓)
6463imaeq1d 6077 . . . . . . . . . . 11 (𝑒 = 𝑓 → (𝑒 “ ℕ) = (𝑓 “ ℕ))
6564eleq1d 2826 . . . . . . . . . 10 (𝑒 = 𝑓 → ((𝑒 “ ℕ) ∈ Fin ↔ (𝑓 “ ℕ) ∈ Fin))
6665, 37elrab2 3695 . . . . . . . . 9 (𝑓𝑅 ↔ (𝑓 ∈ (ℕ0m ℙ) ∧ (𝑓 “ ℕ) ∈ Fin))
6766simplbi 497 . . . . . . . 8 (𝑓𝑅𝑓 ∈ (ℕ0m ℙ))
686, 1elmap 8911 . . . . . . . 8 (𝑓 ∈ (ℕ0m ℙ) ↔ 𝑓:ℙ⟶ℕ0)
6967, 68sylib 218 . . . . . . 7 (𝑓𝑅𝑓:ℙ⟶ℕ0)
7069ad2antrr 726 . . . . . 6 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → 𝑓:ℙ⟶ℕ0)
71 simplr 769 . . . . . . . . 9 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → 𝑦 ∈ ℝ)
72 0re 11263 . . . . . . . . 9 0 ∈ ℝ
73 ifcl 4571 . . . . . . . . 9 ((𝑦 ∈ ℝ ∧ 0 ∈ ℝ) → if(0 ≤ 𝑦, 𝑦, 0) ∈ ℝ)
7471, 72, 73sylancl 586 . . . . . . . 8 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → if(0 ≤ 𝑦, 𝑦, 0) ∈ ℝ)
75 max1 13227 . . . . . . . . 9 ((0 ∈ ℝ ∧ 𝑦 ∈ ℝ) → 0 ≤ if(0 ≤ 𝑦, 𝑦, 0))
7672, 71, 75sylancr 587 . . . . . . . 8 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → 0 ≤ if(0 ≤ 𝑦, 𝑦, 0))
77 flge0nn0 13860 . . . . . . . 8 ((if(0 ≤ 𝑦, 𝑦, 0) ∈ ℝ ∧ 0 ≤ if(0 ≤ 𝑦, 𝑦, 0)) → (⌊‘if(0 ≤ 𝑦, 𝑦, 0)) ∈ ℕ0)
7874, 76, 77syl2anc 584 . . . . . . 7 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → (⌊‘if(0 ≤ 𝑦, 𝑦, 0)) ∈ ℕ0)
79 nn0p1nn 12565 . . . . . . 7 ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) ∈ ℕ0 → ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ∈ ℕ)
8078, 79syl 17 . . . . . 6 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ∈ ℕ)
8171adantr 480 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑦 ∈ ℝ)
8280adantr 480 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ∈ ℕ)
8382nnred 12281 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ∈ ℝ)
8415ssriv 3987 . . . . . . . . . . . 12 ℙ ⊆ ℤ
85 zssre 12620 . . . . . . . . . . . 12 ℤ ⊆ ℝ
8684, 85sstri 3993 . . . . . . . . . . 11 ℙ ⊆ ℝ
87 simprl 771 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑞 ∈ ℙ)
8886, 87sselid 3981 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑞 ∈ ℝ)
8974adantr 480 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → if(0 ≤ 𝑦, 𝑦, 0) ∈ ℝ)
90 max2 13229 . . . . . . . . . . . 12 ((0 ∈ ℝ ∧ 𝑦 ∈ ℝ) → 𝑦 ≤ if(0 ≤ 𝑦, 𝑦, 0))
9172, 81, 90sylancr 587 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑦 ≤ if(0 ≤ 𝑦, 𝑦, 0))
92 flltp1 13840 . . . . . . . . . . . 12 (if(0 ≤ 𝑦, 𝑦, 0) ∈ ℝ → if(0 ≤ 𝑦, 𝑦, 0) < ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1))
9389, 92syl 17 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → if(0 ≤ 𝑦, 𝑦, 0) < ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1))
9481, 89, 83, 91, 93lelttrd 11419 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑦 < ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1))
95 simprr 773 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)
9681, 83, 88, 94, 95ltletrd 11421 . . . . . . . . 9 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑦 < 𝑞)
9781, 88ltnled 11408 . . . . . . . . 9 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (𝑦 < 𝑞 ↔ ¬ 𝑞𝑦))
9896, 97mpbid 232 . . . . . . . 8 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ¬ 𝑞𝑦)
9987biantrurd 532 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((𝑓𝑞) ∈ ℕ ↔ (𝑞 ∈ ℙ ∧ (𝑓𝑞) ∈ ℕ)))
10070adantr 480 . . . . . . . . . . 11 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → 𝑓:ℙ⟶ℕ0)
101 ffn 6736 . . . . . . . . . . 11 (𝑓:ℙ⟶ℕ0𝑓 Fn ℙ)
102 elpreima 7078 . . . . . . . . . . 11 (𝑓 Fn ℙ → (𝑞 ∈ (𝑓 “ ℕ) ↔ (𝑞 ∈ ℙ ∧ (𝑓𝑞) ∈ ℕ)))
103100, 101, 1023syl 18 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (𝑞 ∈ (𝑓 “ ℕ) ↔ (𝑞 ∈ ℙ ∧ (𝑓𝑞) ∈ ℕ)))
10499, 103bitr4d 282 . . . . . . . . 9 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((𝑓𝑞) ∈ ℕ ↔ 𝑞 ∈ (𝑓 “ ℕ)))
105 simplr 769 . . . . . . . . . 10 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦)
106 breq1 5146 . . . . . . . . . . 11 (𝑘 = 𝑞 → (𝑘𝑦𝑞𝑦))
107106rspccv 3619 . . . . . . . . . 10 (∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦 → (𝑞 ∈ (𝑓 “ ℕ) → 𝑞𝑦))
108105, 107syl 17 . . . . . . . . 9 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (𝑞 ∈ (𝑓 “ ℕ) → 𝑞𝑦))
109104, 108sylbid 240 . . . . . . . 8 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((𝑓𝑞) ∈ ℕ → 𝑞𝑦))
11098, 109mtod 198 . . . . . . 7 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ¬ (𝑓𝑞) ∈ ℕ)
111100, 87ffvelcdmd 7105 . . . . . . . . 9 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (𝑓𝑞) ∈ ℕ0)
112 elnn0 12528 . . . . . . . . 9 ((𝑓𝑞) ∈ ℕ0 ↔ ((𝑓𝑞) ∈ ℕ ∨ (𝑓𝑞) = 0))
113111, 112sylib 218 . . . . . . . 8 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → ((𝑓𝑞) ∈ ℕ ∨ (𝑓𝑞) = 0))
114113ord 865 . . . . . . 7 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (¬ (𝑓𝑞) ∈ ℕ → (𝑓𝑞) = 0))
115110, 114mpd 15 . . . . . 6 ((((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) ∧ (𝑞 ∈ ℙ ∧ ((⌊‘if(0 ≤ 𝑦, 𝑦, 0)) + 1) ≤ 𝑞)) → (𝑓𝑞) = 0)
1163, 62, 70, 80, 1151arithlem4 16964 . . . . 5 (((𝑓𝑅𝑦 ∈ ℝ) ∧ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦) → ∃𝑥 ∈ ℕ 𝑓 = (𝑀𝑥))
117 cnvimass 6100 . . . . . . 7 (𝑓 “ ℕ) ⊆ dom 𝑓
11869fdmd 6746 . . . . . . . 8 (𝑓𝑅 → dom 𝑓 = ℙ)
119118, 86eqsstrdi 4028 . . . . . . 7 (𝑓𝑅 → dom 𝑓 ⊆ ℝ)
120117, 119sstrid 3995 . . . . . 6 (𝑓𝑅 → (𝑓 “ ℕ) ⊆ ℝ)
12166simprbi 496 . . . . . 6 (𝑓𝑅 → (𝑓 “ ℕ) ∈ Fin)
122 fimaxre2 12213 . . . . . 6 (((𝑓 “ ℕ) ⊆ ℝ ∧ (𝑓 “ ℕ) ∈ Fin) → ∃𝑦 ∈ ℝ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦)
123120, 121, 122syl2anc 584 . . . . 5 (𝑓𝑅 → ∃𝑦 ∈ ℝ ∀𝑘 ∈ (𝑓 “ ℕ)𝑘𝑦)
124116, 123r19.29a 3162 . . . 4 (𝑓𝑅 → ∃𝑥 ∈ ℕ 𝑓 = (𝑀𝑥))
125124rgen 3063 . . 3 𝑓𝑅𝑥 ∈ ℕ 𝑓 = (𝑀𝑥)
126 dffo3 7122 . . 3 (𝑀:ℕ–onto𝑅 ↔ (𝑀:ℕ⟶𝑅 ∧ ∀𝑓𝑅𝑥 ∈ ℕ 𝑓 = (𝑀𝑥)))
12742, 125, 126mpbir2an 711 . 2 𝑀:ℕ–onto𝑅
128 df-f1o 6568 . 2 (𝑀:ℕ–1-1-onto𝑅 ↔ (𝑀:ℕ–1-1𝑅𝑀:ℕ–onto𝑅))
12961, 127, 128mpbir2an 711 1 𝑀:ℕ–1-1-onto𝑅
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 206  wa 395  wo 848   = wceq 1540  wcel 2108  wral 3061  wrex 3070  {crab 3436  wss 3951  ifcif 4525   class class class wbr 5143  cmpt 5225  ccnv 5684  dom cdm 5685  cima 5688   Fn wfn 6556  wf 6557  1-1wf1 6558  ontowfo 6559  1-1-ontowf1o 6560  cfv 6561  (class class class)co 7431  m cmap 8866  Fincfn 8985  cr 11154  0cc0 11155  1c1 11156   + caddc 11158   < clt 11295  cle 11296  cn 12266  0cn0 12526  cz 12613  cuz 12878  ...cfz 13547  cfl 13830  cexp 14102  cdvds 16290  cprime 16708   pCnt cpc 16874
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 2007  ax-8 2110  ax-9 2118  ax-10 2141  ax-11 2157  ax-12 2177  ax-ext 2708  ax-rep 5279  ax-sep 5296  ax-nul 5306  ax-pow 5365  ax-pr 5432  ax-un 7755  ax-cnex 11211  ax-resscn 11212  ax-1cn 11213  ax-icn 11214  ax-addcl 11215  ax-addrcl 11216  ax-mulcl 11217  ax-mulrcl 11218  ax-mulcom 11219  ax-addass 11220  ax-mulass 11221  ax-distr 11222  ax-i2m1 11223  ax-1ne0 11224  ax-1rid 11225  ax-rnegex 11226  ax-rrecex 11227  ax-cnre 11228  ax-pre-lttri 11229  ax-pre-lttrn 11230  ax-pre-ltadd 11231  ax-pre-mulgt0 11232  ax-pre-sup 11233
This theorem depends on definitions:  df-bi 207  df-an 396  df-or 849  df-3or 1088  df-3an 1089  df-tru 1543  df-fal 1553  df-ex 1780  df-nf 1784  df-sb 2065  df-mo 2540  df-eu 2569  df-clab 2715  df-cleq 2729  df-clel 2816  df-nfc 2892  df-ne 2941  df-nel 3047  df-ral 3062  df-rex 3071  df-rmo 3380  df-reu 3381  df-rab 3437  df-v 3482  df-sbc 3789  df-csb 3900  df-dif 3954  df-un 3956  df-in 3958  df-ss 3968  df-pss 3971  df-nul 4334  df-if 4526  df-pw 4602  df-sn 4627  df-pr 4629  df-op 4633  df-uni 4908  df-iun 4993  df-br 5144  df-opab 5206  df-mpt 5226  df-tr 5260  df-id 5578  df-eprel 5584  df-po 5592  df-so 5593  df-fr 5637  df-we 5639  df-xp 5691  df-rel 5692  df-cnv 5693  df-co 5694  df-dm 5695  df-rn 5696  df-res 5697  df-ima 5698  df-pred 6321  df-ord 6387  df-on 6388  df-lim 6389  df-suc 6390  df-iota 6514  df-fun 6563  df-fn 6564  df-f 6565  df-f1 6566  df-fo 6567  df-f1o 6568  df-fv 6569  df-riota 7388  df-ov 7434  df-oprab 7435  df-mpo 7436  df-om 7888  df-1st 8014  df-2nd 8015  df-frecs 8306  df-wrecs 8337  df-recs 8411  df-rdg 8450  df-1o 8506  df-2o 8507  df-er 8745  df-map 8868  df-en 8986  df-dom 8987  df-sdom 8988  df-fin 8989  df-sup 9482  df-inf 9483  df-pnf 11297  df-mnf 11298  df-xr 11299  df-ltxr 11300  df-le 11301  df-sub 11494  df-neg 11495  df-div 11921  df-nn 12267  df-2 12329  df-3 12330  df-n0 12527  df-z 12614  df-uz 12879  df-q 12991  df-rp 13035  df-fz 13548  df-fl 13832  df-mod 13910  df-seq 14043  df-exp 14103  df-cj 15138  df-re 15139  df-im 15140  df-sqrt 15274  df-abs 15275  df-dvds 16291  df-gcd 16532  df-prm 16709  df-pc 16875
This theorem is referenced by:  1arith2  16966  sqff1o  27225
  Copyright terms: Public domain W3C validator