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

Theorem vdwnnlem1 16325
Description: Corollary of vdw 16324, and lemma for vdwnn 16328. If 𝐹 is a coloring of the integers, then there are arbitrarily long monochromatic APs in 𝐹. (Contributed by Mario Carneiro, 13-Sep-2014.)
Assertion
Ref Expression
vdwnnlem1 ((𝑅 ∈ Fin ∧ 𝐹:ℕ⟶𝑅𝐾 ∈ ℕ0) → ∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝐹 “ {𝑐}))
Distinct variable groups:   𝑎,𝑑,𝑚,𝑐,𝐾   𝑅,𝑎,𝑐,𝑑   𝐹,𝑎,𝑐,𝑑,𝑚
Allowed substitution hint:   𝑅(𝑚)

Proof of Theorem vdwnnlem1
Dummy variables 𝑓 𝑛 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 vdw 16324 . . 3 ((𝑅 ∈ Fin ∧ 𝐾 ∈ ℕ0) → ∃𝑛 ∈ ℕ ∀𝑓 ∈ (𝑅m (1...𝑛))∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝑓 “ {𝑐}))
213adant2 1128 . 2 ((𝑅 ∈ Fin ∧ 𝐹:ℕ⟶𝑅𝐾 ∈ ℕ0) → ∃𝑛 ∈ ℕ ∀𝑓 ∈ (𝑅m (1...𝑛))∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝑓 “ {𝑐}))
3 simpl2 1189 . . . . . . 7 (((𝑅 ∈ Fin ∧ 𝐹:ℕ⟶𝑅𝐾 ∈ ℕ0) ∧ 𝑛 ∈ ℕ) → 𝐹:ℕ⟶𝑅)
4 fz1ssnn 12938 . . . . . . 7 (1...𝑛) ⊆ ℕ
5 fssres 6532 . . . . . . 7 ((𝐹:ℕ⟶𝑅 ∧ (1...𝑛) ⊆ ℕ) → (𝐹 ↾ (1...𝑛)):(1...𝑛)⟶𝑅)
63, 4, 5sylancl 589 . . . . . 6 (((𝑅 ∈ Fin ∧ 𝐹:ℕ⟶𝑅𝐾 ∈ ℕ0) ∧ 𝑛 ∈ ℕ) → (𝐹 ↾ (1...𝑛)):(1...𝑛)⟶𝑅)
7 simpl1 1188 . . . . . . 7 (((𝑅 ∈ Fin ∧ 𝐹:ℕ⟶𝑅𝐾 ∈ ℕ0) ∧ 𝑛 ∈ ℕ) → 𝑅 ∈ Fin)
8 ovex 7178 . . . . . . 7 (1...𝑛) ∈ V
9 elmapg 8409 . . . . . . 7 ((𝑅 ∈ Fin ∧ (1...𝑛) ∈ V) → ((𝐹 ↾ (1...𝑛)) ∈ (𝑅m (1...𝑛)) ↔ (𝐹 ↾ (1...𝑛)):(1...𝑛)⟶𝑅))
107, 8, 9sylancl 589 . . . . . 6 (((𝑅 ∈ Fin ∧ 𝐹:ℕ⟶𝑅𝐾 ∈ ℕ0) ∧ 𝑛 ∈ ℕ) → ((𝐹 ↾ (1...𝑛)) ∈ (𝑅m (1...𝑛)) ↔ (𝐹 ↾ (1...𝑛)):(1...𝑛)⟶𝑅))
116, 10mpbird 260 . . . . 5 (((𝑅 ∈ Fin ∧ 𝐹:ℕ⟶𝑅𝐾 ∈ ℕ0) ∧ 𝑛 ∈ ℕ) → (𝐹 ↾ (1...𝑛)) ∈ (𝑅m (1...𝑛)))
12 cnveq 5731 . . . . . . . . . . 11 (𝑓 = (𝐹 ↾ (1...𝑛)) → 𝑓 = (𝐹 ↾ (1...𝑛)))
1312imaeq1d 5915 . . . . . . . . . 10 (𝑓 = (𝐹 ↾ (1...𝑛)) → (𝑓 “ {𝑐}) = ((𝐹 ↾ (1...𝑛)) “ {𝑐}))
1413eleq2d 2901 . . . . . . . . 9 (𝑓 = (𝐹 ↾ (1...𝑛)) → ((𝑎 + (𝑚 · 𝑑)) ∈ (𝑓 “ {𝑐}) ↔ (𝑎 + (𝑚 · 𝑑)) ∈ ((𝐹 ↾ (1...𝑛)) “ {𝑐})))
1514ralbidv 3192 . . . . . . . 8 (𝑓 = (𝐹 ↾ (1...𝑛)) → (∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝑓 “ {𝑐}) ↔ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ ((𝐹 ↾ (1...𝑛)) “ {𝑐})))
16152rexbidv 3293 . . . . . . 7 (𝑓 = (𝐹 ↾ (1...𝑛)) → (∃𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝑓 “ {𝑐}) ↔ ∃𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ ((𝐹 ↾ (1...𝑛)) “ {𝑐})))
1716rexbidv 3290 . . . . . 6 (𝑓 = (𝐹 ↾ (1...𝑛)) → (∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝑓 “ {𝑐}) ↔ ∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ ((𝐹 ↾ (1...𝑛)) “ {𝑐})))
1817rspcv 3604 . . . . 5 ((𝐹 ↾ (1...𝑛)) ∈ (𝑅m (1...𝑛)) → (∀𝑓 ∈ (𝑅m (1...𝑛))∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝑓 “ {𝑐}) → ∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ ((𝐹 ↾ (1...𝑛)) “ {𝑐})))
1911, 18syl 17 . . . 4 (((𝑅 ∈ Fin ∧ 𝐹:ℕ⟶𝑅𝐾 ∈ ℕ0) ∧ 𝑛 ∈ ℕ) → (∀𝑓 ∈ (𝑅m (1...𝑛))∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝑓 “ {𝑐}) → ∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ ((𝐹 ↾ (1...𝑛)) “ {𝑐})))
20 resss 5865 . . . . . . . . . 10 (𝐹 ↾ (1...𝑛)) ⊆ 𝐹
21 cnvss 5730 . . . . . . . . . 10 ((𝐹 ↾ (1...𝑛)) ⊆ 𝐹(𝐹 ↾ (1...𝑛)) ⊆ 𝐹)
22 imass1 5951 . . . . . . . . . 10 ((𝐹 ↾ (1...𝑛)) ⊆ 𝐹 → ((𝐹 ↾ (1...𝑛)) “ {𝑐}) ⊆ (𝐹 “ {𝑐}))
2320, 21, 22mp2b 10 . . . . . . . . 9 ((𝐹 ↾ (1...𝑛)) “ {𝑐}) ⊆ (𝐹 “ {𝑐})
2423sseli 3948 . . . . . . . 8 ((𝑎 + (𝑚 · 𝑑)) ∈ ((𝐹 ↾ (1...𝑛)) “ {𝑐}) → (𝑎 + (𝑚 · 𝑑)) ∈ (𝐹 “ {𝑐}))
2524ralimi 3155 . . . . . . 7 (∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ ((𝐹 ↾ (1...𝑛)) “ {𝑐}) → ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝐹 “ {𝑐}))
2625reximi 3238 . . . . . 6 (∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ ((𝐹 ↾ (1...𝑛)) “ {𝑐}) → ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝐹 “ {𝑐}))
2726reximi 3238 . . . . 5 (∃𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ ((𝐹 ↾ (1...𝑛)) “ {𝑐}) → ∃𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝐹 “ {𝑐}))
2827reximi 3238 . . . 4 (∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ ((𝐹 ↾ (1...𝑛)) “ {𝑐}) → ∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝐹 “ {𝑐}))
2919, 28syl6 35 . . 3 (((𝑅 ∈ Fin ∧ 𝐹:ℕ⟶𝑅𝐾 ∈ ℕ0) ∧ 𝑛 ∈ ℕ) → (∀𝑓 ∈ (𝑅m (1...𝑛))∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝑓 “ {𝑐}) → ∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝐹 “ {𝑐})))
3029rexlimdva 3277 . 2 ((𝑅 ∈ Fin ∧ 𝐹:ℕ⟶𝑅𝐾 ∈ ℕ0) → (∃𝑛 ∈ ℕ ∀𝑓 ∈ (𝑅m (1...𝑛))∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝑓 “ {𝑐}) → ∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝐹 “ {𝑐})))
312, 30mpd 15 1 ((𝑅 ∈ Fin ∧ 𝐹:ℕ⟶𝑅𝐾 ∈ ℕ0) → ∃𝑐𝑅𝑎 ∈ ℕ ∃𝑑 ∈ ℕ ∀𝑚 ∈ (0...(𝐾 − 1))(𝑎 + (𝑚 · 𝑑)) ∈ (𝐹 “ {𝑐}))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 209  wa 399  w3a 1084   = wceq 1538  wcel 2115  wral 3133  wrex 3134  Vcvv 3480  wss 3919  {csn 4549  ccnv 5541  cres 5544  cima 5545  wf 6339  (class class class)co 7145  m cmap 8396  Fincfn 8499  0cc0 10529  1c1 10530   + caddc 10532   · cmul 10534  cmin 10862  cn 11630  0cn0 11890  ...cfz 12890
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1912  ax-6 1971  ax-7 2016  ax-8 2117  ax-9 2125  ax-10 2146  ax-11 2162  ax-12 2179  ax-ext 2796  ax-rep 5176  ax-sep 5189  ax-nul 5196  ax-pow 5253  ax-pr 5317  ax-un 7451  ax-cnex 10585  ax-resscn 10586  ax-1cn 10587  ax-icn 10588  ax-addcl 10589  ax-addrcl 10590  ax-mulcl 10591  ax-mulrcl 10592  ax-mulcom 10593  ax-addass 10594  ax-mulass 10595  ax-distr 10596  ax-i2m1 10597  ax-1ne0 10598  ax-1rid 10599  ax-rnegex 10600  ax-rrecex 10601  ax-cnre 10602  ax-pre-lttri 10603  ax-pre-lttrn 10604  ax-pre-ltadd 10605  ax-pre-mulgt0 10606
This theorem depends on definitions:  df-bi 210  df-an 400  df-or 845  df-3or 1085  df-3an 1086  df-tru 1541  df-ex 1782  df-nf 1786  df-sb 2071  df-mo 2624  df-eu 2655  df-clab 2803  df-cleq 2817  df-clel 2896  df-nfc 2964  df-ne 3015  df-nel 3119  df-ral 3138  df-rex 3139  df-reu 3140  df-rmo 3141  df-rab 3142  df-v 3482  df-sbc 3759  df-csb 3867  df-dif 3922  df-un 3924  df-in 3926  df-ss 3936  df-pss 3938  df-nul 4276  df-if 4450  df-pw 4523  df-sn 4550  df-pr 4552  df-tp 4554  df-op 4556  df-uni 4825  df-int 4863  df-iun 4907  df-br 5053  df-opab 5115  df-mpt 5133  df-tr 5159  df-id 5447  df-eprel 5452  df-po 5461  df-so 5462  df-fr 5501  df-we 5503  df-xp 5548  df-rel 5549  df-cnv 5550  df-co 5551  df-dm 5552  df-rn 5553  df-res 5554  df-ima 5555  df-pred 6135  df-ord 6181  df-on 6182  df-lim 6183  df-suc 6184  df-iota 6302  df-fun 6345  df-fn 6346  df-f 6347  df-f1 6348  df-fo 6349  df-f1o 6350  df-fv 6351  df-riota 7103  df-ov 7148  df-oprab 7149  df-mpo 7150  df-om 7571  df-1st 7679  df-2nd 7680  df-wrecs 7937  df-recs 7998  df-rdg 8036  df-1o 8092  df-2o 8093  df-oadd 8096  df-er 8279  df-map 8398  df-pm 8399  df-en 8500  df-dom 8501  df-sdom 8502  df-fin 8503  df-dju 9321  df-card 9359  df-pnf 10669  df-mnf 10670  df-xr 10671  df-ltxr 10672  df-le 10673  df-sub 10864  df-neg 10865  df-nn 11631  df-2 11693  df-n0 11891  df-xnn0 11961  df-z 11975  df-uz 12237  df-rp 12383  df-fz 12891  df-hash 13692  df-vdwap 16298  df-vdwmc 16299  df-vdwpc 16300
This theorem is referenced by:  vdwnnlem3  16327
  Copyright terms: Public domain W3C validator