Metamath Proof Explorer


Theorem vdwlem9

Description: Lemma for vdw . (Contributed by Mario Carneiro, 12-Sep-2014)

Ref Expression
Hypotheses vdw.r ⊢ φ → R ∈ Fin
vdwlem9.k ⊢ φ → K ∈ ℤ ≥ 2
vdwlem9.s ⊢ φ → ∀ s ∈ Fin ∃ n ∈ ℕ ∀ f ∈ s 1 … n K MonoAP f
vdwlem9.m ⊢ φ → M ∈ ℕ
vdwlem9.w ⊢ φ → W ∈ ℕ
vdwlem9.g ⊢ φ → ∀ g ∈ R 1 … W M K PolyAP g ∨ K + 1 MonoAP g
vdwlem9.v ⊢ φ → V ∈ ℕ
vdwlem9.a ⊢ φ → ∀ f ∈ R 1 … W 1 … V K MonoAP f
vdwlem9.h ⊢ φ → H : 1 … W ⁢ 2 ⁢ V ⟶ R
vdwlem9.f ⊢ F = x ∈ 1 … V ⟼ y ∈ 1 … W ⟼ H ⁡ y + W ⁢ x - 1 + V
Assertion vdwlem9 ⊢ φ → M + 1 K PolyAP H ∨ K + 1 MonoAP H

Proof

Step Hyp Ref Expression
1 vdw.r ⊢ φ → R ∈ Fin
2 vdwlem9.k ⊢ φ → K ∈ ℤ ≥ 2
3 vdwlem9.s ⊢ φ → ∀ s ∈ Fin ∃ n ∈ ℕ ∀ f ∈ s 1 … n K MonoAP f
4 vdwlem9.m ⊢ φ → M ∈ ℕ
5 vdwlem9.w ⊢ φ → W ∈ ℕ
6 vdwlem9.g ⊢ φ → ∀ g ∈ R 1 … W M K PolyAP g ∨ K + 1 MonoAP g
7 vdwlem9.v ⊢ φ → V ∈ ℕ
8 vdwlem9.a ⊢ φ → ∀ f ∈ R 1 … W 1 … V K MonoAP f
9 vdwlem9.h ⊢ φ → H : 1 … W ⁢ 2 ⁢ V ⟶ R
10 vdwlem9.f ⊢ F = x ∈ 1 … V ⟼ y ∈ 1 … W ⟼ H ⁡ y + W ⁢ x - 1 + V
11 breq2 ⊢ f = F → K MonoAP f ↔ K MonoAP F
12 7 5 1 9 10 vdwlem4 ⊢ φ → F : 1 … V ⟶ R 1 … W
13 ovex ⊢ R 1 … W ∈ V
14 ovex ⊢ 1 … V ∈ V
15 13 14 elmap ⊢ F ∈ R 1 … W 1 … V ↔ F : 1 … V ⟶ R 1 … W
16 12 15 sylibr ⊢ φ → F ∈ R 1 … W 1 … V
17 11 8 16 rspcdva ⊢ φ → K MonoAP F
18 eluz2nn ⊢ K ∈ ℤ ≥ 2 → K ∈ ℕ
19 2 18 syl ⊢ φ → K ∈ ℕ
20 19 nnnn0d ⊢ φ → K ∈ ℕ 0
21 14 20 12 vdwmc ⊢ φ → K MonoAP F ↔ ∃ g ∃ a ∈ ℕ ∃ d ∈ ℕ a AP ⁡ K d ⊆ F -1 g
22 6 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → ∀ g ∈ R 1 … W M K PolyAP g ∨ K + 1 MonoAP g
23 simprr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a AP ⁡ K d ⊆ F -1 g
24 19 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → K ∈ ℕ
25 simprll ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a ∈ ℕ
26 simprlr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → d ∈ ℕ
27 vdwapid1 ⊢ K ∈ ℕ ∧ a ∈ ℕ ∧ d ∈ ℕ → a ∈ a AP ⁡ K d
28 24 25 26 27 syl3anc ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a ∈ a AP ⁡ K d
29 23 28 sseldd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a ∈ F -1 g
30 12 ffnd ⊢ φ → F Fn 1 … V
31 30 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → F Fn 1 … V
32 fniniseg ⊢ F Fn 1 … V → a ∈ F -1 g ↔ a ∈ 1 … V ∧ F ⁡ a = g
33 31 32 syl ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a ∈ F -1 g ↔ a ∈ 1 … V ∧ F ⁡ a = g
34 29 33 mpbid ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a ∈ 1 … V ∧ F ⁡ a = g
35 34 simprd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → F ⁡ a = g
36 12 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → F : 1 … V ⟶ R 1 … W
37 34 simpld ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a ∈ 1 … V
38 36 37 ffvelcdmd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → F ⁡ a ∈ R 1 … W
39 35 38 eqeltrrd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → g ∈ R 1 … W
40 rsp ⊢ ∀ g ∈ R 1 … W M K PolyAP g ∨ K + 1 MonoAP g → g ∈ R 1 … W → M K PolyAP g ∨ K + 1 MonoAP g
41 22 39 40 sylc ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → M K PolyAP g ∨ K + 1 MonoAP g
42 7 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → V ∈ ℕ
43 5 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ∈ ℕ
44 1 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → R ∈ Fin
45 9 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → H : 1 … W ⁢ 2 ⁢ V ⟶ R
46 4 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → M ∈ ℕ
47 ovex ⊢ 1 … W ∈ V
48 elmapg ⊢ R ∈ Fin ∧ 1 … W ∈ V → g ∈ R 1 … W ↔ g : 1 … W ⟶ R
49 44 47 48 sylancl ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → g ∈ R 1 … W ↔ g : 1 … W ⟶ R
50 39 49 mpbid ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → g : 1 … W ⟶ R
51 2 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → K ∈ ℤ ≥ 2
52 42 43 44 45 10 46 50 51 25 26 23 vdwlem7 ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → M K PolyAP g → M + 1 K PolyAP H ∨ K + 1 MonoAP g
53 olc ⊢ K + 1 MonoAP g → M + 1 K PolyAP H ∨ K + 1 MonoAP g
54 53 a1i ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → K + 1 MonoAP g → M + 1 K PolyAP H ∨ K + 1 MonoAP g
55 52 54 jaod ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → M K PolyAP g ∨ K + 1 MonoAP g → M + 1 K PolyAP H ∨ K + 1 MonoAP g
56 oveq1 ⊢ x = a → x − 1 = a − 1
57 56 oveq1d ⊢ x = a → x - 1 + V = a - 1 + V
58 57 oveq2d ⊢ x = a → W ⁢ x - 1 + V = W ⁢ a - 1 + V
59 58 oveq2d ⊢ x = a → y + W ⁢ x - 1 + V = y + W ⁢ a - 1 + V
60 59 fveq2d ⊢ x = a → H ⁡ y + W ⁢ x - 1 + V = H ⁡ y + W ⁢ a - 1 + V
61 60 mpteq2dv ⊢ x = a → y ∈ 1 … W ⟼ H ⁡ y + W ⁢ x - 1 + V = y ∈ 1 … W ⟼ H ⁡ y + W ⁢ a - 1 + V
62 47 mptex ⊢ y ∈ 1 … W ⟼ H ⁡ y + W ⁢ a - 1 + V ∈ V
63 61 10 62 fvmpt ⊢ a ∈ 1 … V → F ⁡ a = y ∈ 1 … W ⟼ H ⁡ y + W ⁢ a - 1 + V
64 37 63 syl ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → F ⁡ a = y ∈ 1 … W ⟼ H ⁡ y + W ⁢ a - 1 + V
65 64 35 eqtr3d ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → y ∈ 1 … W ⟼ H ⁡ y + W ⁢ a - 1 + V = g
66 65 breq2d ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → K + 1 MonoAP y ∈ 1 … W ⟼ H ⁡ y + W ⁢ a - 1 + V ↔ K + 1 MonoAP g
67 20 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → K ∈ ℕ 0
68 peano2nn0 ⊢ K ∈ ℕ 0 → K + 1 ∈ ℕ 0
69 67 68 syl ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → K + 1 ∈ ℕ 0
70 nnm1nn0 ⊢ a ∈ ℕ → a − 1 ∈ ℕ 0
71 25 70 syl ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a − 1 ∈ ℕ 0
72 nn0nnaddcl ⊢ a − 1 ∈ ℕ 0 ∧ V ∈ ℕ → a - 1 + V ∈ ℕ
73 71 42 72 syl2anc ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a - 1 + V ∈ ℕ
74 43 73 nnmulcld ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⁢ a - 1 + V ∈ ℕ
75 25 42 nnaddcld ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a + V ∈ ℕ
76 43 75 nnmulcld ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⁢ a + V ∈ ℕ
77 76 nnzd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⁢ a + V ∈ ℤ
78 2nn ⊢ 2 ∈ ℕ
79 nnmulcl ⊢ 2 ∈ ℕ ∧ V ∈ ℕ → 2 ⁢ V ∈ ℕ
80 78 7 79 sylancr ⊢ φ → 2 ⁢ V ∈ ℕ
81 5 80 nnmulcld ⊢ φ → W ⁢ 2 ⁢ V ∈ ℕ
82 81 nnzd ⊢ φ → W ⁢ 2 ⁢ V ∈ ℤ
83 82 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⁢ 2 ⁢ V ∈ ℤ
84 25 nnred ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a ∈ ℝ
85 42 nnred ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → V ∈ ℝ
86 elfzle2 ⊢ a ∈ 1 … V → a ≤ V
87 37 86 syl ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a ≤ V
88 84 85 85 87 leadd1dd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a + V ≤ V + V
89 42 nncnd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → V ∈ ℂ
90 89 2timesd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → 2 ⁢ V = V + V
91 88 90 breqtrrd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a + V ≤ 2 ⁢ V
92 75 nnred ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a + V ∈ ℝ
93 80 nnred ⊢ φ → 2 ⁢ V ∈ ℝ
94 93 adantr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → 2 ⁢ V ∈ ℝ
95 43 nnred ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ∈ ℝ
96 43 nngt0d ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → 0 < W
97 lemul2 ⊢ a + V ∈ ℝ ∧ 2 ⁢ V ∈ ℝ ∧ W ∈ ℝ ∧ 0 < W → a + V ≤ 2 ⁢ V ↔ W ⁢ a + V ≤ W ⁢ 2 ⁢ V
98 92 94 95 96 97 syl112anc ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a + V ≤ 2 ⁢ V ↔ W ⁢ a + V ≤ W ⁢ 2 ⁢ V
99 91 98 mpbid ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⁢ a + V ≤ W ⁢ 2 ⁢ V
100 eluz2 ⊢ W ⁢ 2 ⁢ V ∈ ℤ ≥ W ⁢ a + V ↔ W ⁢ a + V ∈ ℤ ∧ W ⁢ 2 ⁢ V ∈ ℤ ∧ W ⁢ a + V ≤ W ⁢ 2 ⁢ V
101 77 83 99 100 syl3anbrc ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⁢ 2 ⁢ V ∈ ℤ ≥ W ⁢ a + V
102 43 nncnd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ∈ ℂ
103 1cnd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → 1 ∈ ℂ
104 71 nn0cnd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a − 1 ∈ ℂ
105 104 89 addcld ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a - 1 + V ∈ ℂ
106 102 103 105 adddid ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⁢ 1 + a − 1 + V = W ⋅ 1 + W ⁢ a - 1 + V
107 103 104 89 addassd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → 1 + a − 1 + V = 1 + a − 1 + V
108 ax-1cn ⊢ 1 ∈ ℂ
109 25 nncnd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → a ∈ ℂ
110 pncan3 ⊢ 1 ∈ ℂ ∧ a ∈ ℂ → 1 + a - 1 = a
111 108 109 110 sylancr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → 1 + a - 1 = a
112 111 oveq1d ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → 1 + a − 1 + V = a + V
113 107 112 eqtr3d ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → 1 + a − 1 + V = a + V
114 113 oveq2d ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⁢ 1 + a − 1 + V = W ⁢ a + V
115 102 mulridd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⋅ 1 = W
116 115 oveq1d ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⋅ 1 + W ⁢ a - 1 + V = W + W ⁢ a - 1 + V
117 106 114 116 3eqtr3d ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⁢ a + V = W + W ⁢ a - 1 + V
118 117 fveq2d ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → ℤ ≥ W ⁢ a + V = ℤ ≥ W + W ⁢ a - 1 + V
119 101 118 eleqtrd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → W ⁢ 2 ⁢ V ∈ ℤ ≥ W + W ⁢ a - 1 + V
120 fvoveq1 ⊢ y = z → H ⁡ y + W ⁢ a - 1 + V = H ⁡ z + W ⁢ a - 1 + V
121 120 cbvmptv ⊢ y ∈ 1 … W ⟼ H ⁡ y + W ⁢ a - 1 + V = z ∈ 1 … W ⟼ H ⁡ z + W ⁢ a - 1 + V
122 44 69 43 74 45 119 121 vdwlem2 ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → K + 1 MonoAP y ∈ 1 … W ⟼ H ⁡ y + W ⁢ a - 1 + V → K + 1 MonoAP H
123 66 122 sylbird ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → K + 1 MonoAP g → K + 1 MonoAP H
124 123 orim2d ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → M + 1 K PolyAP H ∨ K + 1 MonoAP g → M + 1 K PolyAP H ∨ K + 1 MonoAP H
125 55 124 syld ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → M K PolyAP g ∨ K + 1 MonoAP g → M + 1 K PolyAP H ∨ K + 1 MonoAP H
126 41 125 mpd ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ ∧ a AP ⁡ K d ⊆ F -1 g → M + 1 K PolyAP H ∨ K + 1 MonoAP H
127 126 expr ⊢ φ ∧ a ∈ ℕ ∧ d ∈ ℕ → a AP ⁡ K d ⊆ F -1 g → M + 1 K PolyAP H ∨ K + 1 MonoAP H
128 127 rexlimdvva ⊢ φ → ∃ a ∈ ℕ ∃ d ∈ ℕ a AP ⁡ K d ⊆ F -1 g → M + 1 K PolyAP H ∨ K + 1 MonoAP H
129 128 exlimdv ⊢ φ → ∃ g ∃ a ∈ ℕ ∃ d ∈ ℕ a AP ⁡ K d ⊆ F -1 g → M + 1 K PolyAP H ∨ K + 1 MonoAP H
130 21 129 sylbid ⊢ φ → K MonoAP F → M + 1 K PolyAP H ∨ K + 1 MonoAP H
131 17 130 mpd ⊢ φ → M + 1 K PolyAP H ∨ K + 1 MonoAP H