Theorem vdwpc 15522

Description: The predicate " The coloring 𝐹 contains a polychromatic 𝑀-tuple of AP's of length 𝐾". A polychromatic 𝑀-tuple of AP's is a set of AP's with the same base point but different step lengths, such that each individual AP is monochromatic, but the AP's all have mutually distinct colors. (The common basepoint is not required to have the same color as any of the AP's.) (Contributed by Mario Carneiro, 18-Aug-2014.)

Hypotheses

Ref	Expression
vdwmc.1	⊢ 𝑋 ∈ V
vdwmc.2	⊢ (𝜑 → 𝐾 ∈ ℕ0)
vdwmc.3	⊢ (𝜑 → 𝐹:𝑋⟶𝑅)
vdwpc.4	⊢ (𝜑 → 𝑀 ∈ ℕ)
vdwpc.5	⊢ 𝐽 = (1...𝑀)

Assertion

Ref	Expression
vdwpc	⊢ (𝜑 → (⟨𝑀, 𝐾⟩ PolyAP 𝐹 ↔ ∃𝑎 ∈ ℕ ∃𝑑 ∈ (ℕ ↑𝑚 𝐽)(∀𝑖 ∈ 𝐽 ((𝑎 + (𝑑‘𝑖))(AP‘𝐾)(𝑑‘𝑖)) ⊆ (◡𝐹 “ {(𝐹‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ 𝐽 ↦ (𝐹‘(𝑎 + (𝑑‘𝑖))))) = 𝑀)))

Distinct variable groups:   𝑎,𝑑,𝑖,𝐹   𝐾,𝑎,𝑑,𝑖   𝐽,𝑑,𝑖   𝑀,𝑎,𝑑,𝑖

Allowed substitution hints:   𝜑(𝑖,𝑎,𝑑)   𝑅(𝑖,𝑎,𝑑)   𝐽(𝑎)   𝑋(𝑖,𝑎,𝑑)

Proof of Theorem vdwpc

Dummy variables 𝑓 𝑘 𝑚 are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		vdwpc.4	. 2 ⊢ (𝜑 → 𝑀 ∈ ℕ)
2		vdwmc.2	. 2 ⊢ (𝜑 → 𝐾 ∈ ℕ0)
3		vdwmc.3	. . 3 ⊢ (𝜑 → 𝐹:𝑋⟶𝑅)
4		vdwmc.1	. . 3 ⊢ 𝑋 ∈ V
5		fex 6394	. . 3 ⊢ ((𝐹:𝑋⟶𝑅 ∧ 𝑋 ∈ V) → 𝐹 ∈ V)
6	3, 4, 5	sylancl 693	. 2 ⊢ (𝜑 → 𝐹 ∈ V)
7		df-br 4584	. . . 4 ⊢ (⟨𝑀, 𝐾⟩ PolyAP 𝐹 ↔ ⟨⟨𝑀, 𝐾⟩, 𝐹⟩ ∈ PolyAP )
8		df-vdwpc 15512	. . . . 5 ⊢ PolyAP = {⟨⟨𝑚, 𝑘⟩, 𝑓⟩ ∣ ∃𝑎 ∈ ℕ ∃𝑑 ∈ (ℕ ↑𝑚 (1...𝑚))(∀𝑖 ∈ (1...𝑚)((𝑎 + (𝑑‘𝑖))(AP‘𝑘)(𝑑‘𝑖)) ⊆ (◡𝑓 “ {(𝑓‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ (1...𝑚) ↦ (𝑓‘(𝑎 + (𝑑‘𝑖))))) = 𝑚)}
9	8	eleq2i 2680	. . . 4 ⊢ (⟨⟨𝑀, 𝐾⟩, 𝐹⟩ ∈ PolyAP ↔ ⟨⟨𝑀, 𝐾⟩, 𝐹⟩ ∈ {⟨⟨𝑚, 𝑘⟩, 𝑓⟩ ∣ ∃𝑎 ∈ ℕ ∃𝑑 ∈ (ℕ ↑𝑚 (1...𝑚))(∀𝑖 ∈ (1...𝑚)((𝑎 + (𝑑‘𝑖))(AP‘𝑘)(𝑑‘𝑖)) ⊆ (◡𝑓 “ {(𝑓‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ (1...𝑚) ↦ (𝑓‘(𝑎 + (𝑑‘𝑖))))) = 𝑚)})
10	7, 9	bitri 263	. . 3 ⊢ (⟨𝑀, 𝐾⟩ PolyAP 𝐹 ↔ ⟨⟨𝑀, 𝐾⟩, 𝐹⟩ ∈ {⟨⟨𝑚, 𝑘⟩, 𝑓⟩ ∣ ∃𝑎 ∈ ℕ ∃𝑑 ∈ (ℕ ↑𝑚 (1...𝑚))(∀𝑖 ∈ (1...𝑚)((𝑎 + (𝑑‘𝑖))(AP‘𝑘)(𝑑‘𝑖)) ⊆ (◡𝑓 “ {(𝑓‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ (1...𝑚) ↦ (𝑓‘(𝑎 + (𝑑‘𝑖))))) = 𝑚)})
11		simp1 1054	. . . . . . . . 9 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → 𝑚 = 𝑀)
12	11	oveq2d 6565	. . . . . . . 8 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (1...𝑚) = (1...𝑀))
13		vdwpc.5	. . . . . . . 8 ⊢ 𝐽 = (1...𝑀)
14	12, 13	syl6eqr 2662	. . . . . . 7 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (1...𝑚) = 𝐽)
15	14	oveq2d 6565	. . . . . 6 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (ℕ ↑𝑚 (1...𝑚)) = (ℕ ↑𝑚 𝐽))
16		simp2 1055	. . . . . . . . . . 11 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → 𝑘 = 𝐾)
17	16	fveq2d 6107	. . . . . . . . . 10 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (AP‘𝑘) = (AP‘𝐾))
18	17	oveqd 6566	. . . . . . . . 9 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → ((𝑎 + (𝑑‘𝑖))(AP‘𝑘)(𝑑‘𝑖)) = ((𝑎 + (𝑑‘𝑖))(AP‘𝐾)(𝑑‘𝑖)))
19		simp3 1056	. . . . . . . . . . 11 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → 𝑓 = 𝐹)
20	19	cnveqd 5220	. . . . . . . . . 10 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → ◡𝑓 = ◡𝐹)
21	19	fveq1d 6105	. . . . . . . . . . 11 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (𝑓‘(𝑎 + (𝑑‘𝑖))) = (𝐹‘(𝑎 + (𝑑‘𝑖))))
22	21	sneqd 4137	. . . . . . . . . 10 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → {(𝑓‘(𝑎 + (𝑑‘𝑖)))} = {(𝐹‘(𝑎 + (𝑑‘𝑖)))})
23	20, 22	imaeq12d 5386	. . . . . . . . 9 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (◡𝑓 “ {(𝑓‘(𝑎 + (𝑑‘𝑖)))}) = (◡𝐹 “ {(𝐹‘(𝑎 + (𝑑‘𝑖)))}))
24	18, 23	sseq12d 3597	. . . . . . . 8 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (((𝑎 + (𝑑‘𝑖))(AP‘𝑘)(𝑑‘𝑖)) ⊆ (◡𝑓 “ {(𝑓‘(𝑎 + (𝑑‘𝑖)))}) ↔ ((𝑎 + (𝑑‘𝑖))(AP‘𝐾)(𝑑‘𝑖)) ⊆ (◡𝐹 “ {(𝐹‘(𝑎 + (𝑑‘𝑖)))})))
25	14, 24	raleqbidv 3129	. . . . . . 7 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (∀𝑖 ∈ (1...𝑚)((𝑎 + (𝑑‘𝑖))(AP‘𝑘)(𝑑‘𝑖)) ⊆ (◡𝑓 “ {(𝑓‘(𝑎 + (𝑑‘𝑖)))}) ↔ ∀𝑖 ∈ 𝐽 ((𝑎 + (𝑑‘𝑖))(AP‘𝐾)(𝑑‘𝑖)) ⊆ (◡𝐹 “ {(𝐹‘(𝑎 + (𝑑‘𝑖)))})))
26	14, 21	mpteq12dv 4663	. . . . . . . . . 10 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (𝑖 ∈ (1...𝑚) ↦ (𝑓‘(𝑎 + (𝑑‘𝑖)))) = (𝑖 ∈ 𝐽 ↦ (𝐹‘(𝑎 + (𝑑‘𝑖)))))
27	26	rneqd 5274	. . . . . . . . 9 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → ran (𝑖 ∈ (1...𝑚) ↦ (𝑓‘(𝑎 + (𝑑‘𝑖)))) = ran (𝑖 ∈ 𝐽 ↦ (𝐹‘(𝑎 + (𝑑‘𝑖)))))
28	27	fveq2d 6107	. . . . . . . 8 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (#‘ran (𝑖 ∈ (1...𝑚) ↦ (𝑓‘(𝑎 + (𝑑‘𝑖))))) = (#‘ran (𝑖 ∈ 𝐽 ↦ (𝐹‘(𝑎 + (𝑑‘𝑖))))))
29	28, 11	eqeq12d 2625	. . . . . . 7 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → ((#‘ran (𝑖 ∈ (1...𝑚) ↦ (𝑓‘(𝑎 + (𝑑‘𝑖))))) = 𝑚 ↔ (#‘ran (𝑖 ∈ 𝐽 ↦ (𝐹‘(𝑎 + (𝑑‘𝑖))))) = 𝑀))
30	25, 29	anbi12d 743	. . . . . 6 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → ((∀𝑖 ∈ (1...𝑚)((𝑎 + (𝑑‘𝑖))(AP‘𝑘)(𝑑‘𝑖)) ⊆ (◡𝑓 “ {(𝑓‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ (1...𝑚) ↦ (𝑓‘(𝑎 + (𝑑‘𝑖))))) = 𝑚) ↔ (∀𝑖 ∈ 𝐽 ((𝑎 + (𝑑‘𝑖))(AP‘𝐾)(𝑑‘𝑖)) ⊆ (◡𝐹 “ {(𝐹‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ 𝐽 ↦ (𝐹‘(𝑎 + (𝑑‘𝑖))))) = 𝑀)))
31	15, 30	rexeqbidv 3130	. . . . 5 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (∃𝑑 ∈ (ℕ ↑𝑚 (1...𝑚))(∀𝑖 ∈ (1...𝑚)((𝑎 + (𝑑‘𝑖))(AP‘𝑘)(𝑑‘𝑖)) ⊆ (◡𝑓 “ {(𝑓‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ (1...𝑚) ↦ (𝑓‘(𝑎 + (𝑑‘𝑖))))) = 𝑚) ↔ ∃𝑑 ∈ (ℕ ↑𝑚 𝐽)(∀𝑖 ∈ 𝐽 ((𝑎 + (𝑑‘𝑖))(AP‘𝐾)(𝑑‘𝑖)) ⊆ (◡𝐹 “ {(𝐹‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ 𝐽 ↦ (𝐹‘(𝑎 + (𝑑‘𝑖))))) = 𝑀)))
32	31	rexbidv 3034	. . . 4 ⊢ ((𝑚 = 𝑀 ∧ 𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (∃𝑎 ∈ ℕ ∃𝑑 ∈ (ℕ ↑𝑚 (1...𝑚))(∀𝑖 ∈ (1...𝑚)((𝑎 + (𝑑‘𝑖))(AP‘𝑘)(𝑑‘𝑖)) ⊆ (◡𝑓 “ {(𝑓‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ (1...𝑚) ↦ (𝑓‘(𝑎 + (𝑑‘𝑖))))) = 𝑚) ↔ ∃𝑎 ∈ ℕ ∃𝑑 ∈ (ℕ ↑𝑚 𝐽)(∀𝑖 ∈ 𝐽 ((𝑎 + (𝑑‘𝑖))(AP‘𝐾)(𝑑‘𝑖)) ⊆ (◡𝐹 “ {(𝐹‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ 𝐽 ↦ (𝐹‘(𝑎 + (𝑑‘𝑖))))) = 𝑀)))
33	32	eloprabga 6645	. . 3 ⊢ ((𝑀 ∈ ℕ ∧ 𝐾 ∈ ℕ0 ∧ 𝐹 ∈ V) → (⟨⟨𝑀, 𝐾⟩, 𝐹⟩ ∈ {⟨⟨𝑚, 𝑘⟩, 𝑓⟩ ∣ ∃𝑎 ∈ ℕ ∃𝑑 ∈ (ℕ ↑𝑚 (1...𝑚))(∀𝑖 ∈ (1...𝑚)((𝑎 + (𝑑‘𝑖))(AP‘𝑘)(𝑑‘𝑖)) ⊆ (◡𝑓 “ {(𝑓‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ (1...𝑚) ↦ (𝑓‘(𝑎 + (𝑑‘𝑖))))) = 𝑚)} ↔ ∃𝑎 ∈ ℕ ∃𝑑 ∈ (ℕ ↑𝑚 𝐽)(∀𝑖 ∈ 𝐽 ((𝑎 + (𝑑‘𝑖))(AP‘𝐾)(𝑑‘𝑖)) ⊆ (◡𝐹 “ {(𝐹‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ 𝐽 ↦ (𝐹‘(𝑎 + (𝑑‘𝑖))))) = 𝑀)))
34	10, 33	syl5bb 271	. 2 ⊢ ((𝑀 ∈ ℕ ∧ 𝐾 ∈ ℕ0 ∧ 𝐹 ∈ V) → (⟨𝑀, 𝐾⟩ PolyAP 𝐹 ↔ ∃𝑎 ∈ ℕ ∃𝑑 ∈ (ℕ ↑𝑚 𝐽)(∀𝑖 ∈ 𝐽 ((𝑎 + (𝑑‘𝑖))(AP‘𝐾)(𝑑‘𝑖)) ⊆ (◡𝐹 “ {(𝐹‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ 𝐽 ↦ (𝐹‘(𝑎 + (𝑑‘𝑖))))) = 𝑀)))
35	1, 2, 6, 34	syl3anc 1318	1 ⊢ (𝜑 → (⟨𝑀, 𝐾⟩ PolyAP 𝐹 ↔ ∃𝑎 ∈ ℕ ∃𝑑 ∈ (ℕ ↑𝑚 𝐽)(∀𝑖 ∈ 𝐽 ((𝑎 + (𝑑‘𝑖))(AP‘𝐾)(𝑑‘𝑖)) ⊆ (◡𝐹 “ {(𝐹‘(𝑎 + (𝑑‘𝑖)))}) ∧ (#‘ran (𝑖 ∈ 𝐽 ↦ (𝐹‘(𝑎 + (𝑑‘𝑖))))) = 𝑀)))

Syntax hints:   → wi 4   ↔ wb 195   ∧ wa 383   ∧ w3a 1031   = wceq 1475   ∈ wcel 1977  ∀wral 2896  ∃wrex 2897  Vcvv 3173   ⊆ wss 3540  {csn 4125  ⟨cop 4131   class class class wbr 4583   ↦ cmpt 4643  ^◡ccnv 5037  ran crn 5039   “ cima 5041  ⟶wf 5800  ‘cfv 5804  (class class class)co 6549  {coprab 6550   ↑_𝑚 cmap 7744  1c1 9816   + caddc 9818  ℕcn 10897  ℕ₀cn0 11169  ...cfz 12197  #chash 12979  APcvdwa 15507   PolyAP cvdwp 15509

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1713  ax-4 1728  ax-5 1827  ax-6 1875  ax-7 1922  ax-9 1986  ax-10 2006  ax-11 2021  ax-12 2034  ax-13 2234  ax-ext 2590  ax-rep 4699  ax-sep 4709  ax-nul 4717  ax-pr 4833

This theorem depends on definitions:  df-bi 196  df-or 384  df-an 385  df-3an 1033  df-tru 1478  df-ex 1696  df-nf 1701  df-sb 1868  df-eu 2462  df-mo 2463  df-clab 2597  df-cleq 2603  df-clel 2606  df-nfc 2740  df-ne 2782  df-ral 2901  df-rex 2902  df-reu 2903  df-rab 2905  df-v 3175  df-sbc 3403  df-csb 3500  df-dif 3543  df-un 3545  df-in 3547  df-ss 3554  df-nul 3875  df-if 4037  df-sn 4126  df-pr 4128  df-op 4132  df-uni 4373  df-iun 4457  df-br 4584  df-opab 4644  df-mpt 4645  df-id 4953  df-xp 5044  df-rel 5045  df-cnv 5046  df-co 5047  df-dm 5048  df-rn 5049  df-res 5050  df-ima 5051  df-iota 5768  df-fun 5806  df-fn 5807  df-f 5808  df-f1 5809  df-fo 5810  df-f1o 5811  df-fv 5812  df-ov 6552  df-oprab 6553  df-vdwpc 15512

This theorem is referenced by:  vdwlem6  15528  vdwlem7  15529  vdwlem8  15530  vdwlem11  15533