Mathbox for Stefan O'Rear < Previous   Next > Nearby theorems Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  eldiophb Structured version   Visualization version   GIF version

Theorem eldiophb 37637
 Description: Initial expression of Diophantine property of a set. (Contributed by Stefan O'Rear, 5-Oct-2014.) (Revised by Mario Carneiro, 22-Sep-2015.)
Assertion
Ref Expression
eldiophb (𝐷 ∈ (Dioph‘𝑁) ↔ (𝑁 ∈ ℕ0 ∧ ∃𝑘 ∈ (ℤ𝑁)∃𝑝 ∈ (mzPoly‘(1...𝑘))𝐷 = {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}))
Distinct variable groups:   𝐷,𝑘,𝑝   𝑘,𝑁,𝑝,𝑡,𝑢
Allowed substitution hints:   𝐷(𝑢,𝑡)

Proof of Theorem eldiophb
Dummy variables 𝑛 𝑑 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 df-dioph 37636 . . . 4 Dioph = (𝑛 ∈ ℕ0 ↦ ran (𝑘 ∈ (ℤ𝑛), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑛)) ∧ (𝑝𝑢) = 0)}))
21dmmptss 5669 . . 3 dom Dioph ⊆ ℕ0
3 elfvdm 6258 . . 3 (𝐷 ∈ (Dioph‘𝑁) → 𝑁 ∈ dom Dioph)
42, 3sseldi 3634 . 2 (𝐷 ∈ (Dioph‘𝑁) → 𝑁 ∈ ℕ0)
5 fveq2 6229 . . . . . . 7 (𝑛 = 𝑁 → (ℤ𝑛) = (ℤ𝑁))
6 eqidd 2652 . . . . . . 7 (𝑛 = 𝑁 → (mzPoly‘(1...𝑘)) = (mzPoly‘(1...𝑘)))
7 oveq2 6698 . . . . . . . . . . . 12 (𝑛 = 𝑁 → (1...𝑛) = (1...𝑁))
87reseq2d 5428 . . . . . . . . . . 11 (𝑛 = 𝑁 → (𝑢 ↾ (1...𝑛)) = (𝑢 ↾ (1...𝑁)))
98eqeq2d 2661 . . . . . . . . . 10 (𝑛 = 𝑁 → (𝑡 = (𝑢 ↾ (1...𝑛)) ↔ 𝑡 = (𝑢 ↾ (1...𝑁))))
109anbi1d 741 . . . . . . . . 9 (𝑛 = 𝑁 → ((𝑡 = (𝑢 ↾ (1...𝑛)) ∧ (𝑝𝑢) = 0) ↔ (𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)))
1110rexbidv 3081 . . . . . . . 8 (𝑛 = 𝑁 → (∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑛)) ∧ (𝑝𝑢) = 0) ↔ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)))
1211abbidv 2770 . . . . . . 7 (𝑛 = 𝑁 → {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑛)) ∧ (𝑝𝑢) = 0)} = {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)})
135, 6, 12mpt2eq123dv 6759 . . . . . 6 (𝑛 = 𝑁 → (𝑘 ∈ (ℤ𝑛), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑛)) ∧ (𝑝𝑢) = 0)}) = (𝑘 ∈ (ℤ𝑁), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}))
1413rneqd 5385 . . . . 5 (𝑛 = 𝑁 → ran (𝑘 ∈ (ℤ𝑛), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑛)) ∧ (𝑝𝑢) = 0)}) = ran (𝑘 ∈ (ℤ𝑁), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}))
15 ovex 6718 . . . . . . 7 (ℕ0𝑚 (1...𝑁)) ∈ V
1615pwex 4878 . . . . . 6 𝒫 (ℕ0𝑚 (1...𝑁)) ∈ V
17 eqid 2651 . . . . . . . 8 (𝑘 ∈ (ℤ𝑁), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}) = (𝑘 ∈ (ℤ𝑁), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)})
1817rnmpt2 6812 . . . . . . 7 ran (𝑘 ∈ (ℤ𝑁), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}) = {𝑑 ∣ ∃𝑘 ∈ (ℤ𝑁)∃𝑝 ∈ (mzPoly‘(1...𝑘))𝑑 = {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}}
19 elmapi 7921 . . . . . . . . . . . . . . . . 17 (𝑢 ∈ (ℕ0𝑚 (1...𝑘)) → 𝑢:(1...𝑘)⟶ℕ0)
20 fzss2 12419 . . . . . . . . . . . . . . . . 17 (𝑘 ∈ (ℤ𝑁) → (1...𝑁) ⊆ (1...𝑘))
21 fssres 6108 . . . . . . . . . . . . . . . . 17 ((𝑢:(1...𝑘)⟶ℕ0 ∧ (1...𝑁) ⊆ (1...𝑘)) → (𝑢 ↾ (1...𝑁)):(1...𝑁)⟶ℕ0)
2219, 20, 21syl2anr 494 . . . . . . . . . . . . . . . 16 ((𝑘 ∈ (ℤ𝑁) ∧ 𝑢 ∈ (ℕ0𝑚 (1...𝑘))) → (𝑢 ↾ (1...𝑁)):(1...𝑁)⟶ℕ0)
23 nn0ex 11336 . . . . . . . . . . . . . . . . 17 0 ∈ V
24 ovex 6718 . . . . . . . . . . . . . . . . 17 (1...𝑁) ∈ V
2523, 24elmap 7928 . . . . . . . . . . . . . . . 16 ((𝑢 ↾ (1...𝑁)) ∈ (ℕ0𝑚 (1...𝑁)) ↔ (𝑢 ↾ (1...𝑁)):(1...𝑁)⟶ℕ0)
2622, 25sylibr 224 . . . . . . . . . . . . . . 15 ((𝑘 ∈ (ℤ𝑁) ∧ 𝑢 ∈ (ℕ0𝑚 (1...𝑘))) → (𝑢 ↾ (1...𝑁)) ∈ (ℕ0𝑚 (1...𝑁)))
27 eleq1 2718 . . . . . . . . . . . . . . . 16 (𝑡 = (𝑢 ↾ (1...𝑁)) → (𝑡 ∈ (ℕ0𝑚 (1...𝑁)) ↔ (𝑢 ↾ (1...𝑁)) ∈ (ℕ0𝑚 (1...𝑁))))
2827adantr 480 . . . . . . . . . . . . . . 15 ((𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0) → (𝑡 ∈ (ℕ0𝑚 (1...𝑁)) ↔ (𝑢 ↾ (1...𝑁)) ∈ (ℕ0𝑚 (1...𝑁))))
2926, 28syl5ibrcom 237 . . . . . . . . . . . . . 14 ((𝑘 ∈ (ℤ𝑁) ∧ 𝑢 ∈ (ℕ0𝑚 (1...𝑘))) → ((𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0) → 𝑡 ∈ (ℕ0𝑚 (1...𝑁))))
3029rexlimdva 3060 . . . . . . . . . . . . 13 (𝑘 ∈ (ℤ𝑁) → (∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0) → 𝑡 ∈ (ℕ0𝑚 (1...𝑁))))
3130abssdv 3709 . . . . . . . . . . . 12 (𝑘 ∈ (ℤ𝑁) → {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)} ⊆ (ℕ0𝑚 (1...𝑁)))
3215elpw2 4858 . . . . . . . . . . . 12 ({𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)} ∈ 𝒫 (ℕ0𝑚 (1...𝑁)) ↔ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)} ⊆ (ℕ0𝑚 (1...𝑁)))
3331, 32sylibr 224 . . . . . . . . . . 11 (𝑘 ∈ (ℤ𝑁) → {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)} ∈ 𝒫 (ℕ0𝑚 (1...𝑁)))
34 eleq1 2718 . . . . . . . . . . 11 (𝑑 = {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)} → (𝑑 ∈ 𝒫 (ℕ0𝑚 (1...𝑁)) ↔ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)} ∈ 𝒫 (ℕ0𝑚 (1...𝑁))))
3533, 34syl5ibrcom 237 . . . . . . . . . 10 (𝑘 ∈ (ℤ𝑁) → (𝑑 = {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)} → 𝑑 ∈ 𝒫 (ℕ0𝑚 (1...𝑁))))
3635rexlimdvw 3063 . . . . . . . . 9 (𝑘 ∈ (ℤ𝑁) → (∃𝑝 ∈ (mzPoly‘(1...𝑘))𝑑 = {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)} → 𝑑 ∈ 𝒫 (ℕ0𝑚 (1...𝑁))))
3736rexlimiv 3056 . . . . . . . 8 (∃𝑘 ∈ (ℤ𝑁)∃𝑝 ∈ (mzPoly‘(1...𝑘))𝑑 = {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)} → 𝑑 ∈ 𝒫 (ℕ0𝑚 (1...𝑁)))
3837abssi 3710 . . . . . . 7 {𝑑 ∣ ∃𝑘 ∈ (ℤ𝑁)∃𝑝 ∈ (mzPoly‘(1...𝑘))𝑑 = {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}} ⊆ 𝒫 (ℕ0𝑚 (1...𝑁))
3918, 38eqsstri 3668 . . . . . 6 ran (𝑘 ∈ (ℤ𝑁), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}) ⊆ 𝒫 (ℕ0𝑚 (1...𝑁))
4016, 39ssexi 4836 . . . . 5 ran (𝑘 ∈ (ℤ𝑁), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}) ∈ V
4114, 1, 40fvmpt 6321 . . . 4 (𝑁 ∈ ℕ0 → (Dioph‘𝑁) = ran (𝑘 ∈ (ℤ𝑁), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}))
4241eleq2d 2716 . . 3 (𝑁 ∈ ℕ0 → (𝐷 ∈ (Dioph‘𝑁) ↔ 𝐷 ∈ ran (𝑘 ∈ (ℤ𝑁), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)})))
43 ovex 6718 . . . . . 6 (ℕ0𝑚 (1...𝑘)) ∈ V
4443abrexex 7183 . . . . 5 {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))𝑡 = (𝑢 ↾ (1...𝑁))} ∈ V
45 simpl 472 . . . . . . 7 ((𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0) → 𝑡 = (𝑢 ↾ (1...𝑁)))
4645reximi 3040 . . . . . 6 (∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0) → ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))𝑡 = (𝑢 ↾ (1...𝑁)))
4746ss2abi 3707 . . . . 5 {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)} ⊆ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))𝑡 = (𝑢 ↾ (1...𝑁))}
4844, 47ssexi 4836 . . . 4 {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)} ∈ V
4917, 48elrnmpt2 6815 . . 3 (𝐷 ∈ ran (𝑘 ∈ (ℤ𝑁), 𝑝 ∈ (mzPoly‘(1...𝑘)) ↦ {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}) ↔ ∃𝑘 ∈ (ℤ𝑁)∃𝑝 ∈ (mzPoly‘(1...𝑘))𝐷 = {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)})
5042, 49syl6bb 276 . 2 (𝑁 ∈ ℕ0 → (𝐷 ∈ (Dioph‘𝑁) ↔ ∃𝑘 ∈ (ℤ𝑁)∃𝑝 ∈ (mzPoly‘(1...𝑘))𝐷 = {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}))
514, 50biadan2 675 1 (𝐷 ∈ (Dioph‘𝑁) ↔ (𝑁 ∈ ℕ0 ∧ ∃𝑘 ∈ (ℤ𝑁)∃𝑝 ∈ (mzPoly‘(1...𝑘))𝐷 = {𝑡 ∣ ∃𝑢 ∈ (ℕ0𝑚 (1...𝑘))(𝑡 = (𝑢 ↾ (1...𝑁)) ∧ (𝑝𝑢) = 0)}))
 Colors of variables: wff setvar class Syntax hints:   ↔ wb 196   ∧ wa 383   = wceq 1523   ∈ wcel 2030  {cab 2637  ∃wrex 2942   ⊆ wss 3607  𝒫 cpw 4191  dom cdm 5143  ran crn 5144   ↾ cres 5145  ⟶wf 5922  ‘cfv 5926  (class class class)co 6690   ↦ cmpt2 6692   ↑𝑚 cmap 7899  0cc0 9974  1c1 9975  ℕ0cn0 11330  ℤ≥cuz 11725  ...cfz 12364  mzPolycmzp 37602  Diophcdioph 37635 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1762  ax-4 1777  ax-5 1879  ax-6 1945  ax-7 1981  ax-8 2032  ax-9 2039  ax-10 2059  ax-11 2074  ax-12 2087  ax-13 2282  ax-ext 2631  ax-rep 4804  ax-sep 4814  ax-nul 4822  ax-pow 4873  ax-pr 4936  ax-un 6991  ax-cnex 10030  ax-resscn 10031  ax-1cn 10032  ax-icn 10033  ax-addcl 10034  ax-addrcl 10035  ax-mulcl 10036  ax-mulrcl 10037  ax-i2m1 10042  ax-1ne0 10043  ax-rrecex 10046  ax-cnre 10047  ax-pre-lttri 10048  ax-pre-lttrn 10049 This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3or 1055  df-3an 1056  df-tru 1526  df-ex 1745  df-nf 1750  df-sb 1938  df-eu 2502  df-mo 2503  df-clab 2638  df-cleq 2644  df-clel 2647  df-nfc 2782  df-ne 2824  df-nel 2927  df-ral 2946  df-rex 2947  df-reu 2948  df-rab 2950  df-v 3233  df-sbc 3469  df-csb 3567  df-dif 3610  df-un 3612  df-in 3614  df-ss 3621  df-pss 3623  df-nul 3949  df-if 4120  df-pw 4193  df-sn 4211  df-pr 4213  df-tp 4215  df-op 4217  df-uni 4469  df-iun 4554  df-br 4686  df-opab 4746  df-mpt 4763  df-tr 4786  df-id 5053  df-eprel 5058  df-po 5064  df-so 5065  df-fr 5102  df-we 5104  df-xp 5149  df-rel 5150  df-cnv 5151  df-co 5152  df-dm 5153  df-rn 5154  df-res 5155  df-ima 5156  df-pred 5718  df-ord 5764  df-on 5765  df-lim 5766  df-suc 5767  df-iota 5889  df-fun 5928  df-fn 5929  df-f 5930  df-f1 5931  df-fo 5932  df-f1o 5933  df-fv 5934  df-ov 6693  df-oprab 6694  df-mpt2 6695  df-om 7108  df-1st 7210  df-2nd 7211  df-wrecs 7452  df-recs 7513  df-rdg 7551  df-er 7787  df-map 7901  df-en 7998  df-dom 7999  df-sdom 8000  df-pnf 10114  df-mnf 10115  df-xr 10116  df-ltxr 10117  df-le 10118  df-neg 10307  df-nn 11059  df-n0 11331  df-z 11416  df-uz 11726  df-fz 12365  df-dioph 37636 This theorem is referenced by:  eldioph  37638  eldioph2b  37643  eldiophelnn0  37644
 Copyright terms: Public domain W3C validator