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

Theorem prmreclem5 15995
 Description: Lemma for prmrec 15997. Here we show the inequality 𝑁 / 2 < ♯𝑀 by decomposing the set (1...𝑁) into the disjoint union of the set 𝑀 of those numbers that are not divisible by any "large" primes (above 𝐾) and the indexed union over 𝐾 < 𝑘 of the numbers 𝑊‘𝑘 that divide the prime 𝑘. By prmreclem4 15994 the second of these has size less than 𝑁 times the prime reciprocal series, which is less than 1 / 2 by assumption, we find that the complementary part 𝑀 must be at least 𝑁 / 2 large. (Contributed by Mario Carneiro, 6-Aug-2014.)
Hypotheses
Ref Expression
prmrec.1 𝐹 = (𝑛 ∈ ℕ ↦ if(𝑛 ∈ ℙ, (1 / 𝑛), 0))
prmrec.2 (𝜑𝐾 ∈ ℕ)
prmrec.3 (𝜑𝑁 ∈ ℕ)
prmrec.4 𝑀 = {𝑛 ∈ (1...𝑁) ∣ ∀𝑝 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑝𝑛}
prmrec.5 (𝜑 → seq1( + , 𝐹) ∈ dom ⇝ )
prmrec.6 (𝜑 → Σ𝑘 ∈ (ℤ‘(𝐾 + 1))if(𝑘 ∈ ℙ, (1 / 𝑘), 0) < (1 / 2))
prmrec.7 𝑊 = (𝑝 ∈ ℕ ↦ {𝑛 ∈ (1...𝑁) ∣ (𝑝 ∈ ℙ ∧ 𝑝𝑛)})
Assertion
Ref Expression
prmreclem5 (𝜑 → (𝑁 / 2) < ((2↑𝐾) · (√‘𝑁)))
Distinct variable groups:   𝑘,𝑛,𝑝,𝐹   𝑘,𝐾,𝑛,𝑝   𝑘,𝑀,𝑛,𝑝   𝜑,𝑘,𝑛,𝑝   𝑘,𝑊   𝑘,𝑁,𝑛,𝑝
Allowed substitution hints:   𝑊(𝑛,𝑝)

Proof of Theorem prmreclem5
Dummy variables 𝑟 𝑥 𝑞 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 prmrec.3 . . . 4 (𝜑𝑁 ∈ ℕ)
21nnred 11367 . . 3 (𝜑𝑁 ∈ ℝ)
32rehalfcld 11605 . 2 (𝜑 → (𝑁 / 2) ∈ ℝ)
4 fzfi 13066 . . . . . 6 (1...𝑁) ∈ Fin
5 prmrec.4 . . . . . . 7 𝑀 = {𝑛 ∈ (1...𝑁) ∣ ∀𝑝 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑝𝑛}
6 ssrab2 3912 . . . . . . 7 {𝑛 ∈ (1...𝑁) ∣ ∀𝑝 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑝𝑛} ⊆ (1...𝑁)
75, 6eqsstri 3860 . . . . . 6 𝑀 ⊆ (1...𝑁)
8 ssfi 8449 . . . . . 6 (((1...𝑁) ∈ Fin ∧ 𝑀 ⊆ (1...𝑁)) → 𝑀 ∈ Fin)
94, 7, 8mp2an 683 . . . . 5 𝑀 ∈ Fin
10 hashcl 13437 . . . . 5 (𝑀 ∈ Fin → (♯‘𝑀) ∈ ℕ0)
119, 10ax-mp 5 . . . 4 (♯‘𝑀) ∈ ℕ0
1211nn0rei 11630 . . 3 (♯‘𝑀) ∈ ℝ
1312a1i 11 . 2 (𝜑 → (♯‘𝑀) ∈ ℝ)
14 2nn 11424 . . . . 5 2 ∈ ℕ
15 prmrec.2 . . . . . 6 (𝜑𝐾 ∈ ℕ)
1615nnnn0d 11678 . . . . 5 (𝜑𝐾 ∈ ℕ0)
17 nnexpcl 13167 . . . . 5 ((2 ∈ ℕ ∧ 𝐾 ∈ ℕ0) → (2↑𝐾) ∈ ℕ)
1814, 16, 17sylancr 581 . . . 4 (𝜑 → (2↑𝐾) ∈ ℕ)
1918nnred 11367 . . 3 (𝜑 → (2↑𝐾) ∈ ℝ)
201nnrpd 12154 . . . . 5 (𝜑𝑁 ∈ ℝ+)
2120rpsqrtcld 14527 . . . 4 (𝜑 → (√‘𝑁) ∈ ℝ+)
2221rpred 12156 . . 3 (𝜑 → (√‘𝑁) ∈ ℝ)
2319, 22remulcld 10387 . 2 (𝜑 → ((2↑𝐾) · (√‘𝑁)) ∈ ℝ)
242recnd 10385 . . . . . 6 (𝜑𝑁 ∈ ℂ)
25242halvesd 11604 . . . . 5 (𝜑 → ((𝑁 / 2) + (𝑁 / 2)) = 𝑁)
267a1i 11 . . . . . . . . 9 (𝜑𝑀 ⊆ (1...𝑁))
2715peano2nnd 11369 . . . . . . . . . . . . 13 (𝜑 → (𝐾 + 1) ∈ ℕ)
28 elfzuz 12631 . . . . . . . . . . . . 13 (𝑘 ∈ ((𝐾 + 1)...𝑁) → 𝑘 ∈ (ℤ‘(𝐾 + 1)))
29 eluznn 12041 . . . . . . . . . . . . 13 (((𝐾 + 1) ∈ ℕ ∧ 𝑘 ∈ (ℤ‘(𝐾 + 1))) → 𝑘 ∈ ℕ)
3027, 28, 29syl2an 589 . . . . . . . . . . . 12 ((𝜑𝑘 ∈ ((𝐾 + 1)...𝑁)) → 𝑘 ∈ ℕ)
31 eleq1w 2889 . . . . . . . . . . . . . . . . 17 (𝑝 = 𝑘 → (𝑝 ∈ ℙ ↔ 𝑘 ∈ ℙ))
32 breq1 4876 . . . . . . . . . . . . . . . . 17 (𝑝 = 𝑘 → (𝑝𝑛𝑘𝑛))
3331, 32anbi12d 624 . . . . . . . . . . . . . . . 16 (𝑝 = 𝑘 → ((𝑝 ∈ ℙ ∧ 𝑝𝑛) ↔ (𝑘 ∈ ℙ ∧ 𝑘𝑛)))
3433rabbidv 3402 . . . . . . . . . . . . . . 15 (𝑝 = 𝑘 → {𝑛 ∈ (1...𝑁) ∣ (𝑝 ∈ ℙ ∧ 𝑝𝑛)} = {𝑛 ∈ (1...𝑁) ∣ (𝑘 ∈ ℙ ∧ 𝑘𝑛)})
35 prmrec.7 . . . . . . . . . . . . . . 15 𝑊 = (𝑝 ∈ ℕ ↦ {𝑛 ∈ (1...𝑁) ∣ (𝑝 ∈ ℙ ∧ 𝑝𝑛)})
36 ovex 6937 . . . . . . . . . . . . . . . 16 (1...𝑁) ∈ V
3736rabex 5037 . . . . . . . . . . . . . . 15 {𝑛 ∈ (1...𝑁) ∣ (𝑘 ∈ ℙ ∧ 𝑘𝑛)} ∈ V
3834, 35, 37fvmpt 6529 . . . . . . . . . . . . . 14 (𝑘 ∈ ℕ → (𝑊𝑘) = {𝑛 ∈ (1...𝑁) ∣ (𝑘 ∈ ℙ ∧ 𝑘𝑛)})
3938adantl 475 . . . . . . . . . . . . 13 ((𝜑𝑘 ∈ ℕ) → (𝑊𝑘) = {𝑛 ∈ (1...𝑁) ∣ (𝑘 ∈ ℙ ∧ 𝑘𝑛)})
40 ssrab2 3912 . . . . . . . . . . . . 13 {𝑛 ∈ (1...𝑁) ∣ (𝑘 ∈ ℙ ∧ 𝑘𝑛)} ⊆ (1...𝑁)
4139, 40syl6eqss 3880 . . . . . . . . . . . 12 ((𝜑𝑘 ∈ ℕ) → (𝑊𝑘) ⊆ (1...𝑁))
4230, 41syldan 585 . . . . . . . . . . 11 ((𝜑𝑘 ∈ ((𝐾 + 1)...𝑁)) → (𝑊𝑘) ⊆ (1...𝑁))
4342ralrimiva 3175 . . . . . . . . . 10 (𝜑 → ∀𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) ⊆ (1...𝑁))
44 iunss 4781 . . . . . . . . . 10 ( 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) ⊆ (1...𝑁) ↔ ∀𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) ⊆ (1...𝑁))
4543, 44sylibr 226 . . . . . . . . 9 (𝜑 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) ⊆ (1...𝑁))
4626, 45unssd 4016 . . . . . . . 8 (𝜑 → (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) ⊆ (1...𝑁))
47 breq1 4876 . . . . . . . . . . . . . . . 16 (𝑝 = 𝑞 → (𝑝𝑛𝑞𝑛))
4847notbid 310 . . . . . . . . . . . . . . 15 (𝑝 = 𝑞 → (¬ 𝑝𝑛 ↔ ¬ 𝑞𝑛))
4948cbvralv 3383 . . . . . . . . . . . . . 14 (∀𝑝 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑝𝑛 ↔ ∀𝑞 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑞𝑛)
50 breq2 4877 . . . . . . . . . . . . . . . 16 (𝑛 = 𝑥 → (𝑞𝑛𝑞𝑥))
5150notbid 310 . . . . . . . . . . . . . . 15 (𝑛 = 𝑥 → (¬ 𝑞𝑛 ↔ ¬ 𝑞𝑥))
5251ralbidv 3195 . . . . . . . . . . . . . 14 (𝑛 = 𝑥 → (∀𝑞 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑞𝑛 ↔ ∀𝑞 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑞𝑥))
5349, 52syl5bb 275 . . . . . . . . . . . . 13 (𝑛 = 𝑥 → (∀𝑝 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑝𝑛 ↔ ∀𝑞 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑞𝑥))
5453, 5elrab2 3589 . . . . . . . . . . . 12 (𝑥𝑀 ↔ (𝑥 ∈ (1...𝑁) ∧ ∀𝑞 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑞𝑥))
55 elun1 4007 . . . . . . . . . . . 12 (𝑥𝑀𝑥 ∈ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)))
5654, 55sylbir 227 . . . . . . . . . . 11 ((𝑥 ∈ (1...𝑁) ∧ ∀𝑞 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑞𝑥) → 𝑥 ∈ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)))
5756ex 403 . . . . . . . . . 10 (𝑥 ∈ (1...𝑁) → (∀𝑞 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑞𝑥𝑥 ∈ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))))
5857adantl 475 . . . . . . . . 9 ((𝜑𝑥 ∈ (1...𝑁)) → (∀𝑞 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑞𝑥𝑥 ∈ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))))
59 dfrex2 3204 . . . . . . . . . 10 (∃𝑞 ∈ (ℙ ∖ (1...𝐾))𝑞𝑥 ↔ ¬ ∀𝑞 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑞𝑥)
60 eldifn 3960 . . . . . . . . . . . . . . . . . 18 (𝑞 ∈ (ℙ ∖ (1...𝐾)) → ¬ 𝑞 ∈ (1...𝐾))
6160ad2antrl 719 . . . . . . . . . . . . . . . . 17 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → ¬ 𝑞 ∈ (1...𝐾))
62 eldifi 3959 . . . . . . . . . . . . . . . . . . . . 21 (𝑞 ∈ (ℙ ∖ (1...𝐾)) → 𝑞 ∈ ℙ)
6362ad2antrl 719 . . . . . . . . . . . . . . . . . . . 20 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑞 ∈ ℙ)
64 prmnn 15760 . . . . . . . . . . . . . . . . . . . 20 (𝑞 ∈ ℙ → 𝑞 ∈ ℕ)
6563, 64syl 17 . . . . . . . . . . . . . . . . . . 19 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑞 ∈ ℕ)
66 nnuz 12005 . . . . . . . . . . . . . . . . . . 19 ℕ = (ℤ‘1)
6765, 66syl6eleq 2916 . . . . . . . . . . . . . . . . . 18 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑞 ∈ (ℤ‘1))
6815nnzd 11809 . . . . . . . . . . . . . . . . . . 19 (𝜑𝐾 ∈ ℤ)
6968ad2antrr 717 . . . . . . . . . . . . . . . . . 18 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝐾 ∈ ℤ)
70 elfz5 12627 . . . . . . . . . . . . . . . . . 18 ((𝑞 ∈ (ℤ‘1) ∧ 𝐾 ∈ ℤ) → (𝑞 ∈ (1...𝐾) ↔ 𝑞𝐾))
7167, 69, 70syl2anc 579 . . . . . . . . . . . . . . . . 17 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → (𝑞 ∈ (1...𝐾) ↔ 𝑞𝐾))
7261, 71mtbid 316 . . . . . . . . . . . . . . . 16 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → ¬ 𝑞𝐾)
7315nnred 11367 . . . . . . . . . . . . . . . . . 18 (𝜑𝐾 ∈ ℝ)
7473ad2antrr 717 . . . . . . . . . . . . . . . . 17 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝐾 ∈ ℝ)
7565nnred 11367 . . . . . . . . . . . . . . . . 17 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑞 ∈ ℝ)
7674, 75ltnled 10503 . . . . . . . . . . . . . . . 16 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → (𝐾 < 𝑞 ↔ ¬ 𝑞𝐾))
7772, 76mpbird 249 . . . . . . . . . . . . . . 15 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝐾 < 𝑞)
78 prmz 15761 . . . . . . . . . . . . . . . . 17 (𝑞 ∈ ℙ → 𝑞 ∈ ℤ)
7963, 78syl 17 . . . . . . . . . . . . . . . 16 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑞 ∈ ℤ)
80 zltp1le 11755 . . . . . . . . . . . . . . . 16 ((𝐾 ∈ ℤ ∧ 𝑞 ∈ ℤ) → (𝐾 < 𝑞 ↔ (𝐾 + 1) ≤ 𝑞))
8169, 79, 80syl2anc 579 . . . . . . . . . . . . . . 15 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → (𝐾 < 𝑞 ↔ (𝐾 + 1) ≤ 𝑞))
8277, 81mpbid 224 . . . . . . . . . . . . . 14 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → (𝐾 + 1) ≤ 𝑞)
83 elfznn 12663 . . . . . . . . . . . . . . . . 17 (𝑥 ∈ (1...𝑁) → 𝑥 ∈ ℕ)
8483ad2antlr 718 . . . . . . . . . . . . . . . 16 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑥 ∈ ℕ)
8584nnred 11367 . . . . . . . . . . . . . . 15 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑥 ∈ ℝ)
862ad2antrr 717 . . . . . . . . . . . . . . 15 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑁 ∈ ℝ)
87 simprr 789 . . . . . . . . . . . . . . . 16 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑞𝑥)
88 dvdsle 15409 . . . . . . . . . . . . . . . . 17 ((𝑞 ∈ ℤ ∧ 𝑥 ∈ ℕ) → (𝑞𝑥𝑞𝑥))
8979, 84, 88syl2anc 579 . . . . . . . . . . . . . . . 16 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → (𝑞𝑥𝑞𝑥))
9087, 89mpd 15 . . . . . . . . . . . . . . 15 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑞𝑥)
91 elfzle2 12638 . . . . . . . . . . . . . . . 16 (𝑥 ∈ (1...𝑁) → 𝑥𝑁)
9291ad2antlr 718 . . . . . . . . . . . . . . 15 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑥𝑁)
9375, 85, 86, 90, 92letrd 10513 . . . . . . . . . . . . . 14 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑞𝑁)
9468peano2zd 11813 . . . . . . . . . . . . . . . 16 (𝜑 → (𝐾 + 1) ∈ ℤ)
9594ad2antrr 717 . . . . . . . . . . . . . . 15 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → (𝐾 + 1) ∈ ℤ)
961nnzd 11809 . . . . . . . . . . . . . . . 16 (𝜑𝑁 ∈ ℤ)
9796ad2antrr 717 . . . . . . . . . . . . . . 15 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑁 ∈ ℤ)
98 elfz 12625 . . . . . . . . . . . . . . 15 ((𝑞 ∈ ℤ ∧ (𝐾 + 1) ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑞 ∈ ((𝐾 + 1)...𝑁) ↔ ((𝐾 + 1) ≤ 𝑞𝑞𝑁)))
9979, 95, 97, 98syl3anc 1494 . . . . . . . . . . . . . 14 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → (𝑞 ∈ ((𝐾 + 1)...𝑁) ↔ ((𝐾 + 1) ≤ 𝑞𝑞𝑁)))
10082, 93, 99mpbir2and 704 . . . . . . . . . . . . 13 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑞 ∈ ((𝐾 + 1)...𝑁))
101 simplr 785 . . . . . . . . . . . . . . 15 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑥 ∈ (1...𝑁))
10263, 87jca 507 . . . . . . . . . . . . . . 15 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → (𝑞 ∈ ℙ ∧ 𝑞𝑥))
10350anbi2d 622 . . . . . . . . . . . . . . . 16 (𝑛 = 𝑥 → ((𝑞 ∈ ℙ ∧ 𝑞𝑛) ↔ (𝑞 ∈ ℙ ∧ 𝑞𝑥)))
104103elrab 3585 . . . . . . . . . . . . . . 15 (𝑥 ∈ {𝑛 ∈ (1...𝑁) ∣ (𝑞 ∈ ℙ ∧ 𝑞𝑛)} ↔ (𝑥 ∈ (1...𝑁) ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑥)))
105101, 102, 104sylanbrc 578 . . . . . . . . . . . . . 14 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑥 ∈ {𝑛 ∈ (1...𝑁) ∣ (𝑞 ∈ ℙ ∧ 𝑞𝑛)})
106 eleq1w 2889 . . . . . . . . . . . . . . . . . 18 (𝑝 = 𝑞 → (𝑝 ∈ ℙ ↔ 𝑞 ∈ ℙ))
107106, 47anbi12d 624 . . . . . . . . . . . . . . . . 17 (𝑝 = 𝑞 → ((𝑝 ∈ ℙ ∧ 𝑝𝑛) ↔ (𝑞 ∈ ℙ ∧ 𝑞𝑛)))
108107rabbidv 3402 . . . . . . . . . . . . . . . 16 (𝑝 = 𝑞 → {𝑛 ∈ (1...𝑁) ∣ (𝑝 ∈ ℙ ∧ 𝑝𝑛)} = {𝑛 ∈ (1...𝑁) ∣ (𝑞 ∈ ℙ ∧ 𝑞𝑛)})
10936rabex 5037 . . . . . . . . . . . . . . . 16 {𝑛 ∈ (1...𝑁) ∣ (𝑞 ∈ ℙ ∧ 𝑞𝑛)} ∈ V
110108, 35, 109fvmpt 6529 . . . . . . . . . . . . . . 15 (𝑞 ∈ ℕ → (𝑊𝑞) = {𝑛 ∈ (1...𝑁) ∣ (𝑞 ∈ ℙ ∧ 𝑞𝑛)})
11165, 110syl 17 . . . . . . . . . . . . . 14 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → (𝑊𝑞) = {𝑛 ∈ (1...𝑁) ∣ (𝑞 ∈ ℙ ∧ 𝑞𝑛)})
112105, 111eleqtrrd 2909 . . . . . . . . . . . . 13 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑥 ∈ (𝑊𝑞))
113 fveq2 6433 . . . . . . . . . . . . . 14 (𝑘 = 𝑞 → (𝑊𝑘) = (𝑊𝑞))
114113eliuni 4746 . . . . . . . . . . . . 13 ((𝑞 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑥 ∈ (𝑊𝑞)) → 𝑥 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))
115100, 112, 114syl2anc 579 . . . . . . . . . . . 12 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑥 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))
116 elun2 4008 . . . . . . . . . . . 12 (𝑥 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) → 𝑥 ∈ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)))
117115, 116syl 17 . . . . . . . . . . 11 (((𝜑𝑥 ∈ (1...𝑁)) ∧ (𝑞 ∈ (ℙ ∖ (1...𝐾)) ∧ 𝑞𝑥)) → 𝑥 ∈ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)))
118117rexlimdvaa 3241 . . . . . . . . . 10 ((𝜑𝑥 ∈ (1...𝑁)) → (∃𝑞 ∈ (ℙ ∖ (1...𝐾))𝑞𝑥𝑥 ∈ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))))
11959, 118syl5bir 235 . . . . . . . . 9 ((𝜑𝑥 ∈ (1...𝑁)) → (¬ ∀𝑞 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑞𝑥𝑥 ∈ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))))
12058, 119pm2.61d 172 . . . . . . . 8 ((𝜑𝑥 ∈ (1...𝑁)) → 𝑥 ∈ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)))
12146, 120eqelssd 3847 . . . . . . 7 (𝜑 → (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) = (1...𝑁))
122121fveq2d 6437 . . . . . 6 (𝜑 → (♯‘(𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))) = (♯‘(1...𝑁)))
1231nnnn0d 11678 . . . . . . 7 (𝜑𝑁 ∈ ℕ0)
124 hashfz1 13426 . . . . . . 7 (𝑁 ∈ ℕ0 → (♯‘(1...𝑁)) = 𝑁)
125123, 124syl 17 . . . . . 6 (𝜑 → (♯‘(1...𝑁)) = 𝑁)
126122, 125eqtr2d 2862 . . . . 5 (𝜑𝑁 = (♯‘(𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))))
1279a1i 11 . . . . . 6 (𝜑𝑀 ∈ Fin)
128 ssfi 8449 . . . . . . 7 (((1...𝑁) ∈ Fin ∧ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) ⊆ (1...𝑁)) → 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) ∈ Fin)
1294, 45, 128sylancr 581 . . . . . 6 (𝜑 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) ∈ Fin)
130 breq1 4876 . . . . . . . . . . . . . . . . 17 (𝑝 = 𝑘 → (𝑝𝑥𝑘𝑥))
131130notbid 310 . . . . . . . . . . . . . . . 16 (𝑝 = 𝑘 → (¬ 𝑝𝑥 ↔ ¬ 𝑘𝑥))
132 breq2 4877 . . . . . . . . . . . . . . . . . . . . 21 (𝑛 = 𝑥 → (𝑝𝑛𝑝𝑥))
133132notbid 310 . . . . . . . . . . . . . . . . . . . 20 (𝑛 = 𝑥 → (¬ 𝑝𝑛 ↔ ¬ 𝑝𝑥))
134133ralbidv 3195 . . . . . . . . . . . . . . . . . . 19 (𝑛 = 𝑥 → (∀𝑝 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑝𝑛 ↔ ∀𝑝 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑝𝑥))
135134, 5elrab2 3589 . . . . . . . . . . . . . . . . . 18 (𝑥𝑀 ↔ (𝑥 ∈ (1...𝑁) ∧ ∀𝑝 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑝𝑥))
136135simprbi 492 . . . . . . . . . . . . . . . . 17 (𝑥𝑀 → ∀𝑝 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑝𝑥)
137136ad2antlr 718 . . . . . . . . . . . . . . . 16 (((𝜑𝑥𝑀) ∧ (𝑘 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑘 ∈ ℙ)) → ∀𝑝 ∈ (ℙ ∖ (1...𝐾)) ¬ 𝑝𝑥)
138 simprr 789 . . . . . . . . . . . . . . . . 17 (((𝜑𝑥𝑀) ∧ (𝑘 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑘 ∈ ℙ)) → 𝑘 ∈ ℙ)
139 noel 4148 . . . . . . . . . . . . . . . . . 18 ¬ 𝑘 ∈ ∅
140 simprl 787 . . . . . . . . . . . . . . . . . . . . 21 (((𝜑𝑥𝑀) ∧ (𝑘 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑘 ∈ ℙ)) → 𝑘 ∈ ((𝐾 + 1)...𝑁))
141140biantrud 527 . . . . . . . . . . . . . . . . . . . 20 (((𝜑𝑥𝑀) ∧ (𝑘 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑘 ∈ ℙ)) → (𝑘 ∈ (1...𝐾) ↔ (𝑘 ∈ (1...𝐾) ∧ 𝑘 ∈ ((𝐾 + 1)...𝑁))))
142 elin 4023 . . . . . . . . . . . . . . . . . . . 20 (𝑘 ∈ ((1...𝐾) ∩ ((𝐾 + 1)...𝑁)) ↔ (𝑘 ∈ (1...𝐾) ∧ 𝑘 ∈ ((𝐾 + 1)...𝑁)))
143141, 142syl6bbr 281 . . . . . . . . . . . . . . . . . . 19 (((𝜑𝑥𝑀) ∧ (𝑘 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑘 ∈ ℙ)) → (𝑘 ∈ (1...𝐾) ↔ 𝑘 ∈ ((1...𝐾) ∩ ((𝐾 + 1)...𝑁))))
14473ltp1d 11284 . . . . . . . . . . . . . . . . . . . . . 22 (𝜑𝐾 < (𝐾 + 1))
145 fzdisj 12661 . . . . . . . . . . . . . . . . . . . . . 22 (𝐾 < (𝐾 + 1) → ((1...𝐾) ∩ ((𝐾 + 1)...𝑁)) = ∅)
146144, 145syl 17 . . . . . . . . . . . . . . . . . . . . 21 (𝜑 → ((1...𝐾) ∩ ((𝐾 + 1)...𝑁)) = ∅)
147146ad2antrr 717 . . . . . . . . . . . . . . . . . . . 20 (((𝜑𝑥𝑀) ∧ (𝑘 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑘 ∈ ℙ)) → ((1...𝐾) ∩ ((𝐾 + 1)...𝑁)) = ∅)
148147eleq2d 2892 . . . . . . . . . . . . . . . . . . 19 (((𝜑𝑥𝑀) ∧ (𝑘 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑘 ∈ ℙ)) → (𝑘 ∈ ((1...𝐾) ∩ ((𝐾 + 1)...𝑁)) ↔ 𝑘 ∈ ∅))
149143, 148bitrd 271 . . . . . . . . . . . . . . . . . 18 (((𝜑𝑥𝑀) ∧ (𝑘 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑘 ∈ ℙ)) → (𝑘 ∈ (1...𝐾) ↔ 𝑘 ∈ ∅))
150139, 149mtbiri 319 . . . . . . . . . . . . . . . . 17 (((𝜑𝑥𝑀) ∧ (𝑘 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑘 ∈ ℙ)) → ¬ 𝑘 ∈ (1...𝐾))
151138, 150eldifd 3809 . . . . . . . . . . . . . . . 16 (((𝜑𝑥𝑀) ∧ (𝑘 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑘 ∈ ℙ)) → 𝑘 ∈ (ℙ ∖ (1...𝐾)))
152131, 137, 151rspcdva 3532 . . . . . . . . . . . . . . 15 (((𝜑𝑥𝑀) ∧ (𝑘 ∈ ((𝐾 + 1)...𝑁) ∧ 𝑘 ∈ ℙ)) → ¬ 𝑘𝑥)
153152expr 450 . . . . . . . . . . . . . 14 (((𝜑𝑥𝑀) ∧ 𝑘 ∈ ((𝐾 + 1)...𝑁)) → (𝑘 ∈ ℙ → ¬ 𝑘𝑥))
154 imnan 390 . . . . . . . . . . . . . 14 ((𝑘 ∈ ℙ → ¬ 𝑘𝑥) ↔ ¬ (𝑘 ∈ ℙ ∧ 𝑘𝑥))
155153, 154sylib 210 . . . . . . . . . . . . 13 (((𝜑𝑥𝑀) ∧ 𝑘 ∈ ((𝐾 + 1)...𝑁)) → ¬ (𝑘 ∈ ℙ ∧ 𝑘𝑥))
15630adantlr 706 . . . . . . . . . . . . . . . 16 (((𝜑𝑥𝑀) ∧ 𝑘 ∈ ((𝐾 + 1)...𝑁)) → 𝑘 ∈ ℕ)
157156, 38syl 17 . . . . . . . . . . . . . . 15 (((𝜑𝑥𝑀) ∧ 𝑘 ∈ ((𝐾 + 1)...𝑁)) → (𝑊𝑘) = {𝑛 ∈ (1...𝑁) ∣ (𝑘 ∈ ℙ ∧ 𝑘𝑛)})
158157eleq2d 2892 . . . . . . . . . . . . . 14 (((𝜑𝑥𝑀) ∧ 𝑘 ∈ ((𝐾 + 1)...𝑁)) → (𝑥 ∈ (𝑊𝑘) ↔ 𝑥 ∈ {𝑛 ∈ (1...𝑁) ∣ (𝑘 ∈ ℙ ∧ 𝑘𝑛)}))
159 breq2 4877 . . . . . . . . . . . . . . . . 17 (𝑛 = 𝑥 → (𝑘𝑛𝑘𝑥))
160159anbi2d 622 . . . . . . . . . . . . . . . 16 (𝑛 = 𝑥 → ((𝑘 ∈ ℙ ∧ 𝑘𝑛) ↔ (𝑘 ∈ ℙ ∧ 𝑘𝑥)))
161160elrab 3585 . . . . . . . . . . . . . . 15 (𝑥 ∈ {𝑛 ∈ (1...𝑁) ∣ (𝑘 ∈ ℙ ∧ 𝑘𝑛)} ↔ (𝑥 ∈ (1...𝑁) ∧ (𝑘 ∈ ℙ ∧ 𝑘𝑥)))
162161simprbi 492 . . . . . . . . . . . . . 14 (𝑥 ∈ {𝑛 ∈ (1...𝑁) ∣ (𝑘 ∈ ℙ ∧ 𝑘𝑛)} → (𝑘 ∈ ℙ ∧ 𝑘𝑥))
163158, 162syl6bi 245 . . . . . . . . . . . . 13 (((𝜑𝑥𝑀) ∧ 𝑘 ∈ ((𝐾 + 1)...𝑁)) → (𝑥 ∈ (𝑊𝑘) → (𝑘 ∈ ℙ ∧ 𝑘𝑥)))
164155, 163mtod 190 . . . . . . . . . . . 12 (((𝜑𝑥𝑀) ∧ 𝑘 ∈ ((𝐾 + 1)...𝑁)) → ¬ 𝑥 ∈ (𝑊𝑘))
165164nrexdv 3209 . . . . . . . . . . 11 ((𝜑𝑥𝑀) → ¬ ∃𝑘 ∈ ((𝐾 + 1)...𝑁)𝑥 ∈ (𝑊𝑘))
166 eliun 4744 . . . . . . . . . . 11 (𝑥 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) ↔ ∃𝑘 ∈ ((𝐾 + 1)...𝑁)𝑥 ∈ (𝑊𝑘))
167165, 166sylnibr 321 . . . . . . . . . 10 ((𝜑𝑥𝑀) → ¬ 𝑥 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))
168167ex 403 . . . . . . . . 9 (𝜑 → (𝑥𝑀 → ¬ 𝑥 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)))
169 imnan 390 . . . . . . . . 9 ((𝑥𝑀 → ¬ 𝑥 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) ↔ ¬ (𝑥𝑀𝑥 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)))
170168, 169sylib 210 . . . . . . . 8 (𝜑 → ¬ (𝑥𝑀𝑥 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)))
171 elin 4023 . . . . . . . 8 (𝑥 ∈ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) ↔ (𝑥𝑀𝑥 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)))
172170, 171sylnibr 321 . . . . . . 7 (𝜑 → ¬ 𝑥 ∈ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)))
173172eq0rdv 4204 . . . . . 6 (𝜑 → (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) = ∅)
174 hashun 13461 . . . . . 6 ((𝑀 ∈ Fin ∧ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) ∈ Fin ∧ (𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) = ∅) → (♯‘(𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))) = ((♯‘𝑀) + (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))))
175127, 129, 173, 174syl3anc 1494 . . . . 5 (𝜑 → (♯‘(𝑀 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))) = ((♯‘𝑀) + (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))))
17625, 126, 1753eqtrd 2865 . . . 4 (𝜑 → ((𝑁 / 2) + (𝑁 / 2)) = ((♯‘𝑀) + (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))))
177 hashcl 13437 . . . . . . 7 ( 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) ∈ Fin → (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) ∈ ℕ0)
178129, 177syl 17 . . . . . 6 (𝜑 → (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) ∈ ℕ0)
179178nn0red 11679 . . . . 5 (𝜑 → (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) ∈ ℝ)
180 fzfid 13067 . . . . . . . 8 (𝜑 → ((𝐾 + 1)...𝑁) ∈ Fin)
18127, 29sylan 575 . . . . . . . . . 10 ((𝜑𝑘 ∈ (ℤ‘(𝐾 + 1))) → 𝑘 ∈ ℕ)
182 nnrecre 11393 . . . . . . . . . . 11 (𝑘 ∈ ℕ → (1 / 𝑘) ∈ ℝ)
183 0re 10358 . . . . . . . . . . 11 0 ∈ ℝ
184 ifcl 4350 . . . . . . . . . . 11 (((1 / 𝑘) ∈ ℝ ∧ 0 ∈ ℝ) → if(𝑘 ∈ ℙ, (1 / 𝑘), 0) ∈ ℝ)
185182, 183, 184sylancl 580 . . . . . . . . . 10 (𝑘 ∈ ℕ → if(𝑘 ∈ ℙ, (1 / 𝑘), 0) ∈ ℝ)
186181, 185syl 17 . . . . . . . . 9 ((𝜑𝑘 ∈ (ℤ‘(𝐾 + 1))) → if(𝑘 ∈ ℙ, (1 / 𝑘), 0) ∈ ℝ)
18728, 186sylan2 586 . . . . . . . 8 ((𝜑𝑘 ∈ ((𝐾 + 1)...𝑁)) → if(𝑘 ∈ ℙ, (1 / 𝑘), 0) ∈ ℝ)
188180, 187fsumrecl 14842 . . . . . . 7 (𝜑 → Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0) ∈ ℝ)
1892, 188remulcld 10387 . . . . . 6 (𝜑 → (𝑁 · Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0)) ∈ ℝ)
190 prmrec.1 . . . . . . . 8 𝐹 = (𝑛 ∈ ℕ ↦ if(𝑛 ∈ ℙ, (1 / 𝑛), 0))
191 prmrec.5 . . . . . . . 8 (𝜑 → seq1( + , 𝐹) ∈ dom ⇝ )
192 prmrec.6 . . . . . . . 8 (𝜑 → Σ𝑘 ∈ (ℤ‘(𝐾 + 1))if(𝑘 ∈ ℙ, (1 / 𝑘), 0) < (1 / 2))
193190, 15, 1, 5, 191, 192, 35prmreclem4 15994 . . . . . . 7 (𝜑 → (𝑁 ∈ (ℤ𝐾) → (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) ≤ (𝑁 · Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0))))
194 eluz 11982 . . . . . . . . . 10 ((𝑁 ∈ ℤ ∧ 𝐾 ∈ ℤ) → (𝐾 ∈ (ℤ𝑁) ↔ 𝑁𝐾))
19596, 68, 194syl2anc 579 . . . . . . . . 9 (𝜑 → (𝐾 ∈ (ℤ𝑁) ↔ 𝑁𝐾))
196 nnleltp1 11760 . . . . . . . . . 10 ((𝑁 ∈ ℕ ∧ 𝐾 ∈ ℕ) → (𝑁𝐾𝑁 < (𝐾 + 1)))
1971, 15, 196syl2anc 579 . . . . . . . . 9 (𝜑 → (𝑁𝐾𝑁 < (𝐾 + 1)))
198 fzn 12650 . . . . . . . . . 10 (((𝐾 + 1) ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑁 < (𝐾 + 1) ↔ ((𝐾 + 1)...𝑁) = ∅))
19994, 96, 198syl2anc 579 . . . . . . . . 9 (𝜑 → (𝑁 < (𝐾 + 1) ↔ ((𝐾 + 1)...𝑁) = ∅))
200195, 197, 1993bitrd 297 . . . . . . . 8 (𝜑 → (𝐾 ∈ (ℤ𝑁) ↔ ((𝐾 + 1)...𝑁) = ∅))
201 0le0 11459 . . . . . . . . . 10 0 ≤ 0
20224mul01d 10554 . . . . . . . . . 10 (𝜑 → (𝑁 · 0) = 0)
203201, 202syl5breqr 4911 . . . . . . . . 9 (𝜑 → 0 ≤ (𝑁 · 0))
204 iuneq1 4754 . . . . . . . . . . . . 13 (((𝐾 + 1)...𝑁) = ∅ → 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) = 𝑘 ∈ ∅ (𝑊𝑘))
205 0iun 4797 . . . . . . . . . . . . 13 𝑘 ∈ ∅ (𝑊𝑘) = ∅
206204, 205syl6eq 2877 . . . . . . . . . . . 12 (((𝐾 + 1)...𝑁) = ∅ → 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘) = ∅)
207206fveq2d 6437 . . . . . . . . . . 11 (((𝐾 + 1)...𝑁) = ∅ → (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) = (♯‘∅))
208 hash0 13448 . . . . . . . . . . 11 (♯‘∅) = 0
209207, 208syl6eq 2877 . . . . . . . . . 10 (((𝐾 + 1)...𝑁) = ∅ → (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) = 0)
210 sumeq1 14796 . . . . . . . . . . . 12 (((𝐾 + 1)...𝑁) = ∅ → Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0) = Σ𝑘 ∈ ∅ if(𝑘 ∈ ℙ, (1 / 𝑘), 0))
211 sum0 14829 . . . . . . . . . . . 12 Σ𝑘 ∈ ∅ if(𝑘 ∈ ℙ, (1 / 𝑘), 0) = 0
212210, 211syl6eq 2877 . . . . . . . . . . 11 (((𝐾 + 1)...𝑁) = ∅ → Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0) = 0)
213212oveq2d 6921 . . . . . . . . . 10 (((𝐾 + 1)...𝑁) = ∅ → (𝑁 · Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0)) = (𝑁 · 0))
214209, 213breq12d 4886 . . . . . . . . 9 (((𝐾 + 1)...𝑁) = ∅ → ((♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) ≤ (𝑁 · Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0)) ↔ 0 ≤ (𝑁 · 0)))
215203, 214syl5ibrcom 239 . . . . . . . 8 (𝜑 → (((𝐾 + 1)...𝑁) = ∅ → (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) ≤ (𝑁 · Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0))))
216200, 215sylbid 232 . . . . . . 7 (𝜑 → (𝐾 ∈ (ℤ𝑁) → (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) ≤ (𝑁 · Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0))))
217 uztric 11990 . . . . . . . 8 ((𝐾 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑁 ∈ (ℤ𝐾) ∨ 𝐾 ∈ (ℤ𝑁)))
21868, 96, 217syl2anc 579 . . . . . . 7 (𝜑 → (𝑁 ∈ (ℤ𝐾) ∨ 𝐾 ∈ (ℤ𝑁)))
219193, 216, 218mpjaod 891 . . . . . 6 (𝜑 → (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) ≤ (𝑁 · Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0)))
220 eqid 2825 . . . . . . . . . 10 (ℤ‘(𝐾 + 1)) = (ℤ‘(𝐾 + 1))
221 eleq1w 2889 . . . . . . . . . . . . 13 (𝑛 = 𝑘 → (𝑛 ∈ ℙ ↔ 𝑘 ∈ ℙ))
222 oveq2 6913 . . . . . . . . . . . . 13 (𝑛 = 𝑘 → (1 / 𝑛) = (1 / 𝑘))
223221, 222ifbieq1d 4329 . . . . . . . . . . . 12 (𝑛 = 𝑘 → if(𝑛 ∈ ℙ, (1 / 𝑛), 0) = if(𝑘 ∈ ℙ, (1 / 𝑘), 0))
224 ovex 6937 . . . . . . . . . . . . 13 (1 / 𝑘) ∈ V
225 c0ex 10350 . . . . . . . . . . . . 13 0 ∈ V
226224, 225ifex 4354 . . . . . . . . . . . 12 if(𝑘 ∈ ℙ, (1 / 𝑘), 0) ∈ V
227223, 190, 226fvmpt 6529 . . . . . . . . . . 11 (𝑘 ∈ ℕ → (𝐹𝑘) = if(𝑘 ∈ ℙ, (1 / 𝑘), 0))
228181, 227syl 17 . . . . . . . . . 10 ((𝜑𝑘 ∈ (ℤ‘(𝐾 + 1))) → (𝐹𝑘) = if(𝑘 ∈ ℙ, (1 / 𝑘), 0))
229185recnd 10385 . . . . . . . . . . . . . 14 (𝑘 ∈ ℕ → if(𝑘 ∈ ℙ, (1 / 𝑘), 0) ∈ ℂ)
230227, 229eqeltrd 2906 . . . . . . . . . . . . 13 (𝑘 ∈ ℕ → (𝐹𝑘) ∈ ℂ)
231230adantl 475 . . . . . . . . . . . 12 ((𝜑𝑘 ∈ ℕ) → (𝐹𝑘) ∈ ℂ)
23266, 27, 231iserex 14764 . . . . . . . . . . 11 (𝜑 → (seq1( + , 𝐹) ∈ dom ⇝ ↔ seq(𝐾 + 1)( + , 𝐹) ∈ dom ⇝ ))
233191, 232mpbid 224 . . . . . . . . . 10 (𝜑 → seq(𝐾 + 1)( + , 𝐹) ∈ dom ⇝ )
234220, 94, 228, 186, 233isumrecl 14871 . . . . . . . . 9 (𝜑 → Σ𝑘 ∈ (ℤ‘(𝐾 + 1))if(𝑘 ∈ ℙ, (1 / 𝑘), 0) ∈ ℝ)
235 halfre 11572 . . . . . . . . . 10 (1 / 2) ∈ ℝ
236235a1i 11 . . . . . . . . 9 (𝜑 → (1 / 2) ∈ ℝ)
237 fzssuz 12675 . . . . . . . . . . 11 ((𝐾 + 1)...𝑁) ⊆ (ℤ‘(𝐾 + 1))
238237a1i 11 . . . . . . . . . 10 (𝜑 → ((𝐾 + 1)...𝑁) ⊆ (ℤ‘(𝐾 + 1)))
239 nnrp 12125 . . . . . . . . . . . . . 14 (𝑘 ∈ ℕ → 𝑘 ∈ ℝ+)
240239rpreccld 12166 . . . . . . . . . . . . 13 (𝑘 ∈ ℕ → (1 / 𝑘) ∈ ℝ+)
241240rpge0d 12160 . . . . . . . . . . . 12 (𝑘 ∈ ℕ → 0 ≤ (1 / 𝑘))
242 breq2 4877 . . . . . . . . . . . . 13 ((1 / 𝑘) = if(𝑘 ∈ ℙ, (1 / 𝑘), 0) → (0 ≤ (1 / 𝑘) ↔ 0 ≤ if(𝑘 ∈ ℙ, (1 / 𝑘), 0)))
243 breq2 4877 . . . . . . . . . . . . 13 (0 = if(𝑘 ∈ ℙ, (1 / 𝑘), 0) → (0 ≤ 0 ↔ 0 ≤ if(𝑘 ∈ ℙ, (1 / 𝑘), 0)))
244242, 243ifboth 4344 . . . . . . . . . . . 12 ((0 ≤ (1 / 𝑘) ∧ 0 ≤ 0) → 0 ≤ if(𝑘 ∈ ℙ, (1 / 𝑘), 0))
245241, 201, 244sylancl 580 . . . . . . . . . . 11 (𝑘 ∈ ℕ → 0 ≤ if(𝑘 ∈ ℙ, (1 / 𝑘), 0))
246181, 245syl 17 . . . . . . . . . 10 ((𝜑𝑘 ∈ (ℤ‘(𝐾 + 1))) → 0 ≤ if(𝑘 ∈ ℙ, (1 / 𝑘), 0))
247220, 94, 180, 238, 228, 186, 246, 233isumless 14951 . . . . . . . . 9 (𝜑 → Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0) ≤ Σ𝑘 ∈ (ℤ‘(𝐾 + 1))if(𝑘 ∈ ℙ, (1 / 𝑘), 0))
248188, 234, 236, 247, 192lelttrd 10514 . . . . . . . 8 (𝜑 → Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0) < (1 / 2))
2491nngt0d 11400 . . . . . . . . 9 (𝜑 → 0 < 𝑁)
250 ltmul2 11204 . . . . . . . . 9 ((Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0) ∈ ℝ ∧ (1 / 2) ∈ ℝ ∧ (𝑁 ∈ ℝ ∧ 0 < 𝑁)) → (Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0) < (1 / 2) ↔ (𝑁 · Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0)) < (𝑁 · (1 / 2))))
251188, 236, 2, 249, 250syl112anc 1497 . . . . . . . 8 (𝜑 → (Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0) < (1 / 2) ↔ (𝑁 · Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0)) < (𝑁 · (1 / 2))))
252248, 251mpbid 224 . . . . . . 7 (𝜑 → (𝑁 · Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0)) < (𝑁 · (1 / 2)))
253 2cn 11426 . . . . . . . . 9 2 ∈ ℂ
254 2ne0 11462 . . . . . . . . 9 2 ≠ 0
255 divrec 11026 . . . . . . . . 9 ((𝑁 ∈ ℂ ∧ 2 ∈ ℂ ∧ 2 ≠ 0) → (𝑁 / 2) = (𝑁 · (1 / 2)))
256253, 254, 255mp3an23 1581 . . . . . . . 8 (𝑁 ∈ ℂ → (𝑁 / 2) = (𝑁 · (1 / 2)))
25724, 256syl 17 . . . . . . 7 (𝜑 → (𝑁 / 2) = (𝑁 · (1 / 2)))
258252, 257breqtrrd 4901 . . . . . 6 (𝜑 → (𝑁 · Σ𝑘 ∈ ((𝐾 + 1)...𝑁)if(𝑘 ∈ ℙ, (1 / 𝑘), 0)) < (𝑁 / 2))
259179, 189, 3, 219, 258lelttrd 10514 . . . . 5 (𝜑 → (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘)) < (𝑁 / 2))
260179, 3, 13, 259ltadd2dd 10515 . . . 4 (𝜑 → ((♯‘𝑀) + (♯‘ 𝑘 ∈ ((𝐾 + 1)...𝑁)(𝑊𝑘))) < ((♯‘𝑀) + (𝑁 / 2)))
261176, 260eqbrtrd 4895 . . 3 (𝜑 → ((𝑁 / 2) + (𝑁 / 2)) < ((♯‘𝑀) + (𝑁 / 2)))
2623, 13, 3ltadd1d 10945 . . 3 (𝜑 → ((𝑁 / 2) < (♯‘𝑀) ↔ ((𝑁 / 2) + (𝑁 / 2)) < ((♯‘𝑀) + (𝑁 / 2))))
263261, 262mpbird 249 . 2 (𝜑 → (𝑁 / 2) < (♯‘𝑀))
264 oveq1 6912 . . . . . . . 8 (𝑘 = 𝑟 → (𝑘↑2) = (𝑟↑2))
265264breq1d 4883 . . . . . . 7 (𝑘 = 𝑟 → ((𝑘↑2) ∥ 𝑥 ↔ (𝑟↑2) ∥ 𝑥))
266265cbvrabv 3412 . . . . . 6 {𝑘 ∈ ℕ ∣ (𝑘↑2) ∥ 𝑥} = {𝑟 ∈ ℕ ∣ (𝑟↑2) ∥ 𝑥}
267 breq2 4877 . . . . . . 7 (𝑥 = 𝑛 → ((𝑟↑2) ∥ 𝑥 ↔ (𝑟↑2) ∥ 𝑛))
268267rabbidv 3402 . . . . . 6 (𝑥 = 𝑛 → {𝑟 ∈ ℕ ∣ (𝑟↑2) ∥ 𝑥} = {𝑟 ∈ ℕ ∣ (𝑟↑2) ∥ 𝑛})
269266, 268syl5eq 2873 . . . . 5 (𝑥 = 𝑛 → {𝑘 ∈ ℕ ∣ (𝑘↑2) ∥ 𝑥} = {𝑟 ∈ ℕ ∣ (𝑟↑2) ∥ 𝑛})
270269supeq1d 8621 . . . 4 (𝑥 = 𝑛 → sup({𝑘 ∈ ℕ ∣ (𝑘↑2) ∥ 𝑥}, ℝ, < ) = sup({𝑟 ∈ ℕ ∣ (𝑟↑2) ∥ 𝑛}, ℝ, < ))
271270cbvmptv 4973 . . 3 (𝑥 ∈ ℕ ↦ sup({𝑘 ∈ ℕ ∣ (𝑘↑2) ∥ 𝑥}, ℝ, < )) = (𝑛 ∈ ℕ ↦ sup({𝑟 ∈ ℕ ∣ (𝑟↑2) ∥ 𝑛}, ℝ, < ))
272190, 15, 1, 5, 271prmreclem3 15993 . 2 (𝜑 → (♯‘𝑀) ≤ ((2↑𝐾) · (√‘𝑁)))
2733, 13, 23, 263, 272ltletrd 10516 1 (𝜑 → (𝑁 / 2) < ((2↑𝐾) · (√‘𝑁)))
 Colors of variables: wff setvar class Syntax hints:  ¬ wn 3   → wi 4   ↔ wb 198   ∧ wa 386   ∨ wo 878   = wceq 1656   ∈ wcel 2164   ≠ wne 2999  ∀wral 3117  ∃wrex 3118  {crab 3121   ∖ cdif 3795   ∪ cun 3796   ∩ cin 3797   ⊆ wss 3798  ∅c0 4144  ifcif 4306  ∪ ciun 4740   class class class wbr 4873   ↦ cmpt 4952  dom cdm 5342  ‘cfv 6123  (class class class)co 6905  Fincfn 8222  supcsup 8615  ℂcc 10250  ℝcr 10251  0cc0 10252  1c1 10253   + caddc 10255   · cmul 10257   < clt 10391   ≤ cle 10392   / cdiv 11009  ℕcn 11350  2c2 11406  ℕ0cn0 11618  ℤcz 11704  ℤ≥cuz 11968  ...cfz 12619  seqcseq 13095  ↑cexp 13154  ♯chash 13410  √csqrt 14350   ⇝ cli 14592  Σcsu 14793   ∥ cdvds 15357  ℙcprime 15757 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1894  ax-4 1908  ax-5 2009  ax-6 2075  ax-7 2112  ax-8 2166  ax-9 2173  ax-10 2192  ax-11 2207  ax-12 2220  ax-13 2389  ax-ext 2803  ax-rep 4994  ax-sep 5005  ax-nul 5013  ax-pow 5065  ax-pr 5127  ax-un 7209  ax-inf2 8815  ax-cnex 10308  ax-resscn 10309  ax-1cn 10310  ax-icn 10311  ax-addcl 10312  ax-addrcl 10313  ax-mulcl 10314  ax-mulrcl 10315  ax-mulcom 10316  ax-addass 10317  ax-mulass 10318  ax-distr 10319  ax-i2m1 10320  ax-1ne0 10321  ax-1rid 10322  ax-rnegex 10323  ax-rrecex 10324  ax-cnre 10325  ax-pre-lttri 10326  ax-pre-lttrn 10327  ax-pre-ltadd 10328  ax-pre-mulgt0 10329  ax-pre-sup 10330 This theorem depends on definitions:  df-bi 199  df-an 387  df-or 879  df-3or 1112  df-3an 1113  df-tru 1660  df-fal 1670  df-ex 1879  df-nf 1883  df-sb 2068  df-mo 2605  df-eu 2640  df-clab 2812  df-cleq 2818  df-clel 2821  df-nfc 2958  df-ne 3000  df-nel 3103  df-ral 3122  df-rex 3123  df-reu 3124  df-rmo 3125  df-rab 3126  df-v 3416  df-sbc 3663  df-csb 3758  df-dif 3801  df-un 3803  df-in 3805  df-ss 3812  df-pss 3814  df-nul 4145  df-if 4307  df-pw 4380  df-sn 4398  df-pr 4400  df-tp 4402  df-op 4404  df-uni 4659  df-int 4698  df-iun 4742  df-br 4874  df-opab 4936  df-mpt 4953  df-tr 4976  df-id 5250  df-eprel 5255  df-po 5263  df-so 5264  df-fr 5301  df-se 5302  df-we 5303  df-xp 5348  df-rel 5349  df-cnv 5350  df-co 5351  df-dm 5352  df-rn 5353  df-res 5354  df-ima 5355  df-pred 5920  df-ord 5966  df-on 5967  df-lim 5968  df-suc 5969  df-iota 6086  df-fun 6125  df-fn 6126  df-f 6127  df-f1 6128  df-fo 6129  df-f1o 6130  df-fv 6131  df-isom 6132  df-riota 6866  df-ov 6908  df-oprab 6909  df-mpt2 6910  df-om 7327  df-1st 7428  df-2nd 7429  df-wrecs 7672  df-recs 7734  df-rdg 7772  df-1o 7826  df-2o 7827  df-oadd 7830  df-er 8009  df-map 8124  df-pm 8125  df-en 8223  df-dom 8224  df-sdom 8225  df-fin 8226  df-sup 8617  df-inf 8618  df-oi 8684  df-card 9078  df-cda 9305  df-pnf 10393  df-mnf 10394  df-xr 10395  df-ltxr 10396  df-le 10397  df-sub 10587  df-neg 10588  df-div 11010  df-nn 11351  df-2 11414  df-3 11415  df-n0 11619  df-xnn0 11691  df-z 11705  df-uz 11969  df-q 12072  df-rp 12113  df-fz 12620  df-fzo 12761  df-fl 12888  df-mod 12964  df-seq 13096  df-exp 13155  df-hash 13411  df-cj 14216  df-re 14217  df-im 14218  df-sqrt 14352  df-abs 14353  df-clim 14596  df-rlim 14597  df-sum 14794  df-dvds 15358  df-gcd 15590  df-prm 15758  df-pc 15913 This theorem is referenced by:  prmreclem6  15996
 Copyright terms: Public domain W3C validator