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

Theorem smupvallem 15825
 Description: If 𝐴 only has elements less than 𝑁, then all elements of the partial sum sequence past 𝑁 already equal the final value. (Contributed by Mario Carneiro, 20-Sep-2016.)
Hypotheses
Ref Expression
smuval.a (𝜑𝐴 ⊆ ℕ0)
smuval.b (𝜑𝐵 ⊆ ℕ0)
smuval.p 𝑃 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚𝐴 ∧ (𝑛𝑚) ∈ 𝐵)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))
smuval.n (𝜑𝑁 ∈ ℕ0)
smupvallem.a (𝜑𝐴 ⊆ (0..^𝑁))
smupvallem.m (𝜑𝑀 ∈ (ℤ𝑁))
Assertion
Ref Expression
smupvallem (𝜑 → (𝑃𝑀) = (𝐴 smul 𝐵))
Distinct variable groups:   𝑚,𝑛,𝑝,𝐴   𝑛,𝑁   𝜑,𝑛   𝐵,𝑚,𝑛,𝑝
Allowed substitution hints:   𝜑(𝑚,𝑝)   𝑃(𝑚,𝑛,𝑝)   𝑀(𝑚,𝑛,𝑝)   𝑁(𝑚,𝑝)

Proof of Theorem smupvallem
Dummy variables 𝑘 𝑥 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 smuval.a . . . . . . 7 (𝜑𝐴 ⊆ ℕ0)
2 smuval.b . . . . . . 7 (𝜑𝐵 ⊆ ℕ0)
3 smuval.p . . . . . . 7 𝑃 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚𝐴 ∧ (𝑛𝑚) ∈ 𝐵)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))
41, 2, 3smupf 15820 . . . . . 6 (𝜑𝑃:ℕ0⟶𝒫 ℕ0)
5 smuval.n . . . . . . 7 (𝜑𝑁 ∈ ℕ0)
6 smupvallem.m . . . . . . 7 (𝜑𝑀 ∈ (ℤ𝑁))
7 eluznn0 12308 . . . . . . 7 ((𝑁 ∈ ℕ0𝑀 ∈ (ℤ𝑁)) → 𝑀 ∈ ℕ0)
85, 6, 7syl2anc 587 . . . . . 6 (𝜑𝑀 ∈ ℕ0)
94, 8ffvelrnd 6830 . . . . 5 (𝜑 → (𝑃𝑀) ∈ 𝒫 ℕ0)
109elpwid 4508 . . . 4 (𝜑 → (𝑃𝑀) ⊆ ℕ0)
1110sseld 3914 . . 3 (𝜑 → (𝑘 ∈ (𝑃𝑀) → 𝑘 ∈ ℕ0))
121, 2, 3smufval 15819 . . . . 5 (𝜑 → (𝐴 smul 𝐵) = {𝑘 ∈ ℕ0𝑘 ∈ (𝑃‘(𝑘 + 1))})
13 ssrab2 4007 . . . . 5 {𝑘 ∈ ℕ0𝑘 ∈ (𝑃‘(𝑘 + 1))} ⊆ ℕ0
1412, 13eqsstrdi 3969 . . . 4 (𝜑 → (𝐴 smul 𝐵) ⊆ ℕ0)
1514sseld 3914 . . 3 (𝜑 → (𝑘 ∈ (𝐴 smul 𝐵) → 𝑘 ∈ ℕ0))
161ad2antrr 725 . . . . . . 7 (((𝜑𝑘 ∈ ℕ0) ∧ 𝑁 ∈ (ℤ‘(𝑘 + 1))) → 𝐴 ⊆ ℕ0)
172ad2antrr 725 . . . . . . 7 (((𝜑𝑘 ∈ ℕ0) ∧ 𝑁 ∈ (ℤ‘(𝑘 + 1))) → 𝐵 ⊆ ℕ0)
18 simplr 768 . . . . . . 7 (((𝜑𝑘 ∈ ℕ0) ∧ 𝑁 ∈ (ℤ‘(𝑘 + 1))) → 𝑘 ∈ ℕ0)
196adantr 484 . . . . . . . 8 ((𝜑𝑘 ∈ ℕ0) → 𝑀 ∈ (ℤ𝑁))
20 uztrn 12252 . . . . . . . 8 ((𝑀 ∈ (ℤ𝑁) ∧ 𝑁 ∈ (ℤ‘(𝑘 + 1))) → 𝑀 ∈ (ℤ‘(𝑘 + 1)))
2119, 20sylan 583 . . . . . . 7 (((𝜑𝑘 ∈ ℕ0) ∧ 𝑁 ∈ (ℤ‘(𝑘 + 1))) → 𝑀 ∈ (ℤ‘(𝑘 + 1)))
2216, 17, 3, 18, 21smuval2 15824 . . . . . 6 (((𝜑𝑘 ∈ ℕ0) ∧ 𝑁 ∈ (ℤ‘(𝑘 + 1))) → (𝑘 ∈ (𝐴 smul 𝐵) ↔ 𝑘 ∈ (𝑃𝑀)))
2322bicomd 226 . . . . 5 (((𝜑𝑘 ∈ ℕ0) ∧ 𝑁 ∈ (ℤ‘(𝑘 + 1))) → (𝑘 ∈ (𝑃𝑀) ↔ 𝑘 ∈ (𝐴 smul 𝐵)))
246ad2antrr 725 . . . . . . . . 9 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → 𝑀 ∈ (ℤ𝑁))
25 simpll 766 . . . . . . . . 9 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → 𝜑)
26 fveqeq2 6655 . . . . . . . . . . 11 (𝑥 = 𝑁 → ((𝑃𝑥) = (𝑃𝑁) ↔ (𝑃𝑁) = (𝑃𝑁)))
2726imbi2d 344 . . . . . . . . . 10 (𝑥 = 𝑁 → ((𝜑 → (𝑃𝑥) = (𝑃𝑁)) ↔ (𝜑 → (𝑃𝑁) = (𝑃𝑁))))
28 fveqeq2 6655 . . . . . . . . . . 11 (𝑥 = 𝑘 → ((𝑃𝑥) = (𝑃𝑁) ↔ (𝑃𝑘) = (𝑃𝑁)))
2928imbi2d 344 . . . . . . . . . 10 (𝑥 = 𝑘 → ((𝜑 → (𝑃𝑥) = (𝑃𝑁)) ↔ (𝜑 → (𝑃𝑘) = (𝑃𝑁))))
30 fveqeq2 6655 . . . . . . . . . . 11 (𝑥 = (𝑘 + 1) → ((𝑃𝑥) = (𝑃𝑁) ↔ (𝑃‘(𝑘 + 1)) = (𝑃𝑁)))
3130imbi2d 344 . . . . . . . . . 10 (𝑥 = (𝑘 + 1) → ((𝜑 → (𝑃𝑥) = (𝑃𝑁)) ↔ (𝜑 → (𝑃‘(𝑘 + 1)) = (𝑃𝑁))))
32 fveqeq2 6655 . . . . . . . . . . 11 (𝑥 = 𝑀 → ((𝑃𝑥) = (𝑃𝑁) ↔ (𝑃𝑀) = (𝑃𝑁)))
3332imbi2d 344 . . . . . . . . . 10 (𝑥 = 𝑀 → ((𝜑 → (𝑃𝑥) = (𝑃𝑁)) ↔ (𝜑 → (𝑃𝑀) = (𝑃𝑁))))
34 eqidd 2799 . . . . . . . . . 10 (𝜑 → (𝑃𝑁) = (𝑃𝑁))
351adantr 484 . . . . . . . . . . . . . . . 16 ((𝜑𝑘 ∈ (ℤ𝑁)) → 𝐴 ⊆ ℕ0)
362adantr 484 . . . . . . . . . . . . . . . 16 ((𝜑𝑘 ∈ (ℤ𝑁)) → 𝐵 ⊆ ℕ0)
37 eluznn0 12308 . . . . . . . . . . . . . . . . 17 ((𝑁 ∈ ℕ0𝑘 ∈ (ℤ𝑁)) → 𝑘 ∈ ℕ0)
385, 37sylan 583 . . . . . . . . . . . . . . . 16 ((𝜑𝑘 ∈ (ℤ𝑁)) → 𝑘 ∈ ℕ0)
3935, 36, 3, 38smupp1 15822 . . . . . . . . . . . . . . 15 ((𝜑𝑘 ∈ (ℤ𝑁)) → (𝑃‘(𝑘 + 1)) = ((𝑃𝑘) sadd {𝑛 ∈ ℕ0 ∣ (𝑘𝐴 ∧ (𝑛𝑘) ∈ 𝐵)}))
405nn0red 11947 . . . . . . . . . . . . . . . . . . . . 21 (𝜑𝑁 ∈ ℝ)
4140adantr 484 . . . . . . . . . . . . . . . . . . . 20 ((𝜑𝑘 ∈ (ℤ𝑁)) → 𝑁 ∈ ℝ)
4238nn0red 11947 . . . . . . . . . . . . . . . . . . . 20 ((𝜑𝑘 ∈ (ℤ𝑁)) → 𝑘 ∈ ℝ)
43 eluzle 12247 . . . . . . . . . . . . . . . . . . . . 21 (𝑘 ∈ (ℤ𝑁) → 𝑁𝑘)
4443adantl 485 . . . . . . . . . . . . . . . . . . . 20 ((𝜑𝑘 ∈ (ℤ𝑁)) → 𝑁𝑘)
4541, 42, 44lensymd 10783 . . . . . . . . . . . . . . . . . . 19 ((𝜑𝑘 ∈ (ℤ𝑁)) → ¬ 𝑘 < 𝑁)
46 smupvallem.a . . . . . . . . . . . . . . . . . . . . . . 23 (𝜑𝐴 ⊆ (0..^𝑁))
4746adantr 484 . . . . . . . . . . . . . . . . . . . . . 22 ((𝜑𝑘 ∈ (ℤ𝑁)) → 𝐴 ⊆ (0..^𝑁))
4847sseld 3914 . . . . . . . . . . . . . . . . . . . . 21 ((𝜑𝑘 ∈ (ℤ𝑁)) → (𝑘𝐴𝑘 ∈ (0..^𝑁)))
49 elfzolt2 13045 . . . . . . . . . . . . . . . . . . . . 21 (𝑘 ∈ (0..^𝑁) → 𝑘 < 𝑁)
5048, 49syl6 35 . . . . . . . . . . . . . . . . . . . 20 ((𝜑𝑘 ∈ (ℤ𝑁)) → (𝑘𝐴𝑘 < 𝑁))
5150adantrd 495 . . . . . . . . . . . . . . . . . . 19 ((𝜑𝑘 ∈ (ℤ𝑁)) → ((𝑘𝐴 ∧ (𝑛𝑘) ∈ 𝐵) → 𝑘 < 𝑁))
5245, 51mtod 201 . . . . . . . . . . . . . . . . . 18 ((𝜑𝑘 ∈ (ℤ𝑁)) → ¬ (𝑘𝐴 ∧ (𝑛𝑘) ∈ 𝐵))
5352ralrimivw 3150 . . . . . . . . . . . . . . . . 17 ((𝜑𝑘 ∈ (ℤ𝑁)) → ∀𝑛 ∈ ℕ0 ¬ (𝑘𝐴 ∧ (𝑛𝑘) ∈ 𝐵))
54 rabeq0 4292 . . . . . . . . . . . . . . . . 17 ({𝑛 ∈ ℕ0 ∣ (𝑘𝐴 ∧ (𝑛𝑘) ∈ 𝐵)} = ∅ ↔ ∀𝑛 ∈ ℕ0 ¬ (𝑘𝐴 ∧ (𝑛𝑘) ∈ 𝐵))
5553, 54sylibr 237 . . . . . . . . . . . . . . . 16 ((𝜑𝑘 ∈ (ℤ𝑁)) → {𝑛 ∈ ℕ0 ∣ (𝑘𝐴 ∧ (𝑛𝑘) ∈ 𝐵)} = ∅)
5655oveq2d 7152 . . . . . . . . . . . . . . 15 ((𝜑𝑘 ∈ (ℤ𝑁)) → ((𝑃𝑘) sadd {𝑛 ∈ ℕ0 ∣ (𝑘𝐴 ∧ (𝑛𝑘) ∈ 𝐵)}) = ((𝑃𝑘) sadd ∅))
574adantr 484 . . . . . . . . . . . . . . . . . 18 ((𝜑𝑘 ∈ (ℤ𝑁)) → 𝑃:ℕ0⟶𝒫 ℕ0)
5857, 38ffvelrnd 6830 . . . . . . . . . . . . . . . . 17 ((𝜑𝑘 ∈ (ℤ𝑁)) → (𝑃𝑘) ∈ 𝒫 ℕ0)
5958elpwid 4508 . . . . . . . . . . . . . . . 16 ((𝜑𝑘 ∈ (ℤ𝑁)) → (𝑃𝑘) ⊆ ℕ0)
60 sadid1 15810 . . . . . . . . . . . . . . . 16 ((𝑃𝑘) ⊆ ℕ0 → ((𝑃𝑘) sadd ∅) = (𝑃𝑘))
6159, 60syl 17 . . . . . . . . . . . . . . 15 ((𝜑𝑘 ∈ (ℤ𝑁)) → ((𝑃𝑘) sadd ∅) = (𝑃𝑘))
6239, 56, 613eqtrd 2837 . . . . . . . . . . . . . 14 ((𝜑𝑘 ∈ (ℤ𝑁)) → (𝑃‘(𝑘 + 1)) = (𝑃𝑘))
6362eqeq1d 2800 . . . . . . . . . . . . 13 ((𝜑𝑘 ∈ (ℤ𝑁)) → ((𝑃‘(𝑘 + 1)) = (𝑃𝑁) ↔ (𝑃𝑘) = (𝑃𝑁)))
6463biimprd 251 . . . . . . . . . . . 12 ((𝜑𝑘 ∈ (ℤ𝑁)) → ((𝑃𝑘) = (𝑃𝑁) → (𝑃‘(𝑘 + 1)) = (𝑃𝑁)))
6564expcom 417 . . . . . . . . . . 11 (𝑘 ∈ (ℤ𝑁) → (𝜑 → ((𝑃𝑘) = (𝑃𝑁) → (𝑃‘(𝑘 + 1)) = (𝑃𝑁))))
6665a2d 29 . . . . . . . . . 10 (𝑘 ∈ (ℤ𝑁) → ((𝜑 → (𝑃𝑘) = (𝑃𝑁)) → (𝜑 → (𝑃‘(𝑘 + 1)) = (𝑃𝑁))))
6727, 29, 31, 33, 34, 66uzind4i 12301 . . . . . . . . 9 (𝑀 ∈ (ℤ𝑁) → (𝜑 → (𝑃𝑀) = (𝑃𝑁)))
6824, 25, 67sylc 65 . . . . . . . 8 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → (𝑃𝑀) = (𝑃𝑁))
69 simpr 488 . . . . . . . . 9 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → (𝑘 + 1) ∈ (ℤ𝑁))
7027, 29, 31, 31, 34, 66uzind4i 12301 . . . . . . . . 9 ((𝑘 + 1) ∈ (ℤ𝑁) → (𝜑 → (𝑃‘(𝑘 + 1)) = (𝑃𝑁)))
7169, 25, 70sylc 65 . . . . . . . 8 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → (𝑃‘(𝑘 + 1)) = (𝑃𝑁))
7268, 71eqtr4d 2836 . . . . . . 7 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → (𝑃𝑀) = (𝑃‘(𝑘 + 1)))
7372eleq2d 2875 . . . . . 6 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → (𝑘 ∈ (𝑃𝑀) ↔ 𝑘 ∈ (𝑃‘(𝑘 + 1))))
741ad2antrr 725 . . . . . . 7 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → 𝐴 ⊆ ℕ0)
752ad2antrr 725 . . . . . . 7 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → 𝐵 ⊆ ℕ0)
76 simplr 768 . . . . . . 7 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → 𝑘 ∈ ℕ0)
7774, 75, 3, 76smuval 15823 . . . . . 6 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → (𝑘 ∈ (𝐴 smul 𝐵) ↔ 𝑘 ∈ (𝑃‘(𝑘 + 1))))
7873, 77bitr4d 285 . . . . 5 (((𝜑𝑘 ∈ ℕ0) ∧ (𝑘 + 1) ∈ (ℤ𝑁)) → (𝑘 ∈ (𝑃𝑀) ↔ 𝑘 ∈ (𝐴 smul 𝐵)))
79 simpr 488 . . . . . . . 8 ((𝜑𝑘 ∈ ℕ0) → 𝑘 ∈ ℕ0)
8079nn0zd 12076 . . . . . . 7 ((𝜑𝑘 ∈ ℕ0) → 𝑘 ∈ ℤ)
8180peano2zd 12081 . . . . . 6 ((𝜑𝑘 ∈ ℕ0) → (𝑘 + 1) ∈ ℤ)
825nn0zd 12076 . . . . . . 7 (𝜑𝑁 ∈ ℤ)
8382adantr 484 . . . . . 6 ((𝜑𝑘 ∈ ℕ0) → 𝑁 ∈ ℤ)
84 uztric 12257 . . . . . 6 (((𝑘 + 1) ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑁 ∈ (ℤ‘(𝑘 + 1)) ∨ (𝑘 + 1) ∈ (ℤ𝑁)))
8581, 83, 84syl2anc 587 . . . . 5 ((𝜑𝑘 ∈ ℕ0) → (𝑁 ∈ (ℤ‘(𝑘 + 1)) ∨ (𝑘 + 1) ∈ (ℤ𝑁)))
8623, 78, 85mpjaodan 956 . . . 4 ((𝜑𝑘 ∈ ℕ0) → (𝑘 ∈ (𝑃𝑀) ↔ 𝑘 ∈ (𝐴 smul 𝐵)))
8786ex 416 . . 3 (𝜑 → (𝑘 ∈ ℕ0 → (𝑘 ∈ (𝑃𝑀) ↔ 𝑘 ∈ (𝐴 smul 𝐵))))
8811, 15, 87pm5.21ndd 384 . 2 (𝜑 → (𝑘 ∈ (𝑃𝑀) ↔ 𝑘 ∈ (𝐴 smul 𝐵)))
8988eqrdv 2796 1 (𝜑 → (𝑃𝑀) = (𝐴 smul 𝐵))