Theorem vdwmc 15520

Description: The predicate " The ⟨𝑅, 𝑁⟩-coloring 𝐹 contains a monochromatic AP of length 𝐾". (Contributed by Mario Carneiro, 18-Aug-2014.)

Hypotheses

Ref	Expression
vdwmc.1	⊢ 𝑋 ∈ V
vdwmc.2	⊢ (𝜑 → 𝐾 ∈ ℕ0)
vdwmc.3	⊢ (𝜑 → 𝐹:𝑋⟶𝑅)

Assertion

Ref	Expression
vdwmc	⊢ (𝜑 → (𝐾 MonoAP 𝐹 ↔ ∃𝑐∃𝑎 ∈ ℕ ∃𝑑 ∈ ℕ (𝑎(AP‘𝐾)𝑑) ⊆ (◡𝐹 “ {𝑐})))

Distinct variable groups:   𝑎,𝑐,𝑑,𝐹   𝐾,𝑎,𝑐,𝑑   𝜑,𝑐

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

Proof of Theorem vdwmc

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

Step	Hyp	Ref	Expression
1		vdwmc.2	. . 3 ⊢ (𝜑 → 𝐾 ∈ ℕ0)
2		vdwmc.3	. . . 4 ⊢ (𝜑 → 𝐹:𝑋⟶𝑅)
3		vdwmc.1	. . . 4 ⊢ 𝑋 ∈ V
4		fex 6394	. . . 4 ⊢ ((𝐹:𝑋⟶𝑅 ∧ 𝑋 ∈ V) → 𝐹 ∈ V)
5	2, 3, 4	sylancl 693	. . 3 ⊢ (𝜑 → 𝐹 ∈ V)
6		fveq2 6103	. . . . . . . 8 ⊢ (𝑘 = 𝐾 → (AP‘𝑘) = (AP‘𝐾))
7	6	rneqd 5274	. . . . . . 7 ⊢ (𝑘 = 𝐾 → ran (AP‘𝑘) = ran (AP‘𝐾))
8		cnveq 5218	. . . . . . . . 9 ⊢ (𝑓 = 𝐹 → ◡𝑓 = ◡𝐹)
9	8	imaeq1d 5384	. . . . . . . 8 ⊢ (𝑓 = 𝐹 → (◡𝑓 “ {𝑐}) = (◡𝐹 “ {𝑐}))
10	9	pweqd 4113	. . . . . . 7 ⊢ (𝑓 = 𝐹 → 𝒫 (◡𝑓 “ {𝑐}) = 𝒫 (◡𝐹 “ {𝑐}))
11	7, 10	ineqan12d 3778	. . . . . 6 ⊢ ((𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (ran (AP‘𝑘) ∩ 𝒫 (◡𝑓 “ {𝑐})) = (ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})))
12	11	neeq1d 2841	. . . . 5 ⊢ ((𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → ((ran (AP‘𝑘) ∩ 𝒫 (◡𝑓 “ {𝑐})) ≠ ∅ ↔ (ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})) ≠ ∅))
13	12	exbidv 1837	. . . 4 ⊢ ((𝑘 = 𝐾 ∧ 𝑓 = 𝐹) → (∃𝑐(ran (AP‘𝑘) ∩ 𝒫 (◡𝑓 “ {𝑐})) ≠ ∅ ↔ ∃𝑐(ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})) ≠ ∅))
14		df-vdwmc 15511	. . . 4 ⊢ MonoAP = {⟨𝑘, 𝑓⟩ ∣ ∃𝑐(ran (AP‘𝑘) ∩ 𝒫 (◡𝑓 “ {𝑐})) ≠ ∅}
15	13, 14	brabga 4914	. . 3 ⊢ ((𝐾 ∈ ℕ0 ∧ 𝐹 ∈ V) → (𝐾 MonoAP 𝐹 ↔ ∃𝑐(ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})) ≠ ∅))
16	1, 5, 15	syl2anc 691	. 2 ⊢ (𝜑 → (𝐾 MonoAP 𝐹 ↔ ∃𝑐(ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})) ≠ ∅))
17		vdwapf 15514	. . . . 5 ⊢ (𝐾 ∈ ℕ0 → (AP‘𝐾):(ℕ × ℕ)⟶𝒫 ℕ)
18		ffn 5958	. . . . 5 ⊢ ((AP‘𝐾):(ℕ × ℕ)⟶𝒫 ℕ → (AP‘𝐾) Fn (ℕ × ℕ))
19		selpw 4115	. . . . . . 7 ⊢ (𝑧 ∈ 𝒫 (◡𝐹 “ {𝑐}) ↔ 𝑧 ⊆ (◡𝐹 “ {𝑐}))
20		sseq1 3589	. . . . . . 7 ⊢ (𝑧 = ((AP‘𝐾)‘𝑤) → (𝑧 ⊆ (◡𝐹 “ {𝑐}) ↔ ((AP‘𝐾)‘𝑤) ⊆ (◡𝐹 “ {𝑐})))
21	19, 20	syl5bb 271	. . . . . 6 ⊢ (𝑧 = ((AP‘𝐾)‘𝑤) → (𝑧 ∈ 𝒫 (◡𝐹 “ {𝑐}) ↔ ((AP‘𝐾)‘𝑤) ⊆ (◡𝐹 “ {𝑐})))
22	21	rexrn 6269	. . . . 5 ⊢ ((AP‘𝐾) Fn (ℕ × ℕ) → (∃𝑧 ∈ ran (AP‘𝐾)𝑧 ∈ 𝒫 (◡𝐹 “ {𝑐}) ↔ ∃𝑤 ∈ (ℕ × ℕ)((AP‘𝐾)‘𝑤) ⊆ (◡𝐹 “ {𝑐})))
23	1, 17, 18, 22	4syl 19	. . . 4 ⊢ (𝜑 → (∃𝑧 ∈ ran (AP‘𝐾)𝑧 ∈ 𝒫 (◡𝐹 “ {𝑐}) ↔ ∃𝑤 ∈ (ℕ × ℕ)((AP‘𝐾)‘𝑤) ⊆ (◡𝐹 “ {𝑐})))
24		elin 3758	. . . . . 6 ⊢ (𝑧 ∈ (ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})) ↔ (𝑧 ∈ ran (AP‘𝐾) ∧ 𝑧 ∈ 𝒫 (◡𝐹 “ {𝑐})))
25	24	exbii 1764	. . . . 5 ⊢ (∃𝑧 𝑧 ∈ (ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})) ↔ ∃𝑧(𝑧 ∈ ran (AP‘𝐾) ∧ 𝑧 ∈ 𝒫 (◡𝐹 “ {𝑐})))
26		n0 3890	. . . . 5 ⊢ ((ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})) ≠ ∅ ↔ ∃𝑧 𝑧 ∈ (ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})))
27		df-rex 2902	. . . . 5 ⊢ (∃𝑧 ∈ ran (AP‘𝐾)𝑧 ∈ 𝒫 (◡𝐹 “ {𝑐}) ↔ ∃𝑧(𝑧 ∈ ran (AP‘𝐾) ∧ 𝑧 ∈ 𝒫 (◡𝐹 “ {𝑐})))
28	25, 26, 27	3bitr4ri 292	. . . 4 ⊢ (∃𝑧 ∈ ran (AP‘𝐾)𝑧 ∈ 𝒫 (◡𝐹 “ {𝑐}) ↔ (ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})) ≠ ∅)
29		fveq2 6103	. . . . . . 7 ⊢ (𝑤 = ⟨𝑎, 𝑑⟩ → ((AP‘𝐾)‘𝑤) = ((AP‘𝐾)‘⟨𝑎, 𝑑⟩))
30		df-ov 6552	. . . . . . 7 ⊢ (𝑎(AP‘𝐾)𝑑) = ((AP‘𝐾)‘⟨𝑎, 𝑑⟩)
31	29, 30	syl6eqr 2662	. . . . . 6 ⊢ (𝑤 = ⟨𝑎, 𝑑⟩ → ((AP‘𝐾)‘𝑤) = (𝑎(AP‘𝐾)𝑑))
32	31	sseq1d 3595	. . . . 5 ⊢ (𝑤 = ⟨𝑎, 𝑑⟩ → (((AP‘𝐾)‘𝑤) ⊆ (◡𝐹 “ {𝑐}) ↔ (𝑎(AP‘𝐾)𝑑) ⊆ (◡𝐹 “ {𝑐})))
33	32	rexxp 5186	. . . 4 ⊢ (∃𝑤 ∈ (ℕ × ℕ)((AP‘𝐾)‘𝑤) ⊆ (◡𝐹 “ {𝑐}) ↔ ∃𝑎 ∈ ℕ ∃𝑑 ∈ ℕ (𝑎(AP‘𝐾)𝑑) ⊆ (◡𝐹 “ {𝑐}))
34	23, 28, 33	3bitr3g 301	. . 3 ⊢ (𝜑 → ((ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})) ≠ ∅ ↔ ∃𝑎 ∈ ℕ ∃𝑑 ∈ ℕ (𝑎(AP‘𝐾)𝑑) ⊆ (◡𝐹 “ {𝑐})))
35	34	exbidv 1837	. 2 ⊢ (𝜑 → (∃𝑐(ran (AP‘𝐾) ∩ 𝒫 (◡𝐹 “ {𝑐})) ≠ ∅ ↔ ∃𝑐∃𝑎 ∈ ℕ ∃𝑑 ∈ ℕ (𝑎(AP‘𝐾)𝑑) ⊆ (◡𝐹 “ {𝑐})))
36	16, 35	bitrd 267	1 ⊢ (𝜑 → (𝐾 MonoAP 𝐹 ↔ ∃𝑐∃𝑎 ∈ ℕ ∃𝑑 ∈ ℕ (𝑎(AP‘𝐾)𝑑) ⊆ (◡𝐹 “ {𝑐})))

Syntax hints:   → wi 4   ↔ wb 195   ∧ wa 383   = wceq 1475  ∃wex 1695   ∈ wcel 1977   ≠ wne 2780  ∃wrex 2897  Vcvv 3173   ∩ cin 3539   ⊆ wss 3540  ∅c0 3874  𝒫 cpw 4108  {csn 4125  ⟨cop 4131   class class class wbr 4583   × cxp 5036  ^◡ccnv 5037  ran crn 5039   “ cima 5041   Fn wfn 5799  ⟶wf 5800  ‘cfv 5804  (class class class)co 6549  ℕcn 10897  ℕ₀cn0 11169  APcvdwa 15507   MonoAP cvdwm 15508

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-8 1979  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-pow 4769  ax-pr 4833  ax-un 6847  ax-cnex 9871  ax-resscn 9872  ax-1cn 9873  ax-icn 9874  ax-addcl 9875  ax-addrcl 9876  ax-mulcl 9877  ax-mulrcl 9878  ax-mulcom 9879  ax-addass 9880  ax-mulass 9881  ax-distr 9882  ax-i2m1 9883  ax-1ne0 9884  ax-1rid 9885  ax-rnegex 9886  ax-rrecex 9887  ax-cnre 9888  ax-pre-lttri 9889  ax-pre-lttrn 9890  ax-pre-ltadd 9891  ax-pre-mulgt0 9892

This theorem depends on definitions:  df-bi 196  df-or 384  df-an 385  df-3or 1032  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-nel 2783  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-pss 3556  df-nul 3875  df-if 4037  df-pw 4110  df-sn 4126  df-pr 4128  df-tp 4130  df-op 4132  df-uni 4373  df-iun 4457  df-br 4584  df-opab 4644  df-mpt 4645  df-tr 4681  df-eprel 4949  df-id 4953  df-po 4959  df-so 4960  df-fr 4997  df-we 4999  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-pred 5597  df-ord 5643  df-on 5644  df-lim 5645  df-suc 5646  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-riota 6511  df-ov 6552  df-oprab 6553  df-mpt2 6554  df-om 6958  df-1st 7059  df-2nd 7060  df-wrecs 7294  df-recs 7355  df-rdg 7393  df-er 7629  df-en 7842  df-dom 7843  df-sdom 7844  df-pnf 9955  df-mnf 9956  df-xr 9957  df-ltxr 9958  df-le 9959  df-sub 10147  df-neg 10148  df-nn 10898  df-n0 11170  df-z 11255  df-uz 11564  df-fz 12198  df-vdwap 15510  df-vdwmc 15511

This theorem is referenced by:  vdwmc2  15521  vdwlem1  15523  vdwlem2  15524  vdwlem9  15531  vdwlem10  15532  vdwlem12  15534  vdwlem13  15535