/
Strict.lean
451 lines (337 loc) Β· 17.9 KB
/
Strict.lean
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
/-
Copyright (c) 2021 YaΓ«l Dillies. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: YaΓ«l Dillies
-/
import Mathlib.Analysis.Convex.Basic
import Mathlib.Topology.Algebra.Group.Basic
import Mathlib.Topology.Order.Basic
#align_import analysis.convex.strict from "leanprover-community/mathlib"@"84dc0bd6619acaea625086d6f53cb35cdd554219"
/-!
# Strictly convex sets
This file defines strictly convex sets.
A set is strictly convex if the open segment between any two distinct points lies in its interior.
-/
open Set
open Convex Pointwise
variable {π π E F Ξ² : Type*}
open Function Set
open Convex
section OrderedSemiring
variable [OrderedSemiring π] [TopologicalSpace E] [TopologicalSpace F]
section AddCommMonoid
variable [AddCommMonoid E] [AddCommMonoid F]
section SMul
variable (π)
variable [SMul π E] [SMul π F] (s : Set E)
/-- A set is strictly convex if the open segment between any two distinct points lies is in its
interior. This basically means "convex and not flat on the boundary". -/
def StrictConvex : Prop :=
s.Pairwise fun x y => β β¦a b : πβ¦, 0 < a β 0 < b β a + b = 1 β a β’ x + b β’ y β interior s
#align strict_convex StrictConvex
variable {π s}
variable {x y : E} {a b : π}
theorem strictConvex_iff_openSegment_subset :
StrictConvex π s β s.Pairwise fun x y => openSegment π x y β interior s :=
forallβ
_congr fun _ _ _ _ _ => (openSegment_subset_iff π).symm
#align strict_convex_iff_open_segment_subset strictConvex_iff_openSegment_subset
theorem StrictConvex.openSegment_subset (hs : StrictConvex π s) (hx : x β s) (hy : y β s)
(h : x β y) : openSegment π x y β interior s :=
strictConvex_iff_openSegment_subset.1 hs hx hy h
#align strict_convex.open_segment_subset StrictConvex.openSegment_subset
theorem strictConvex_empty : StrictConvex π (β
: Set E) :=
pairwise_empty _
#align strict_convex_empty strictConvex_empty
theorem strictConvex_univ : StrictConvex π (univ : Set E) := by
intro x _ y _ _ a b _ _ _
rw [interior_univ]
exact mem_univ _
#align strict_convex_univ strictConvex_univ
protected nonrec theorem StrictConvex.eq (hs : StrictConvex π s) (hx : x β s) (hy : y β s)
(ha : 0 < a) (hb : 0 < b) (hab : a + b = 1) (h : a β’ x + b β’ y β interior s) : x = y :=
hs.eq hx hy fun H => h <| H ha hb hab
#align strict_convex.eq StrictConvex.eq
protected theorem StrictConvex.inter {t : Set E} (hs : StrictConvex π s) (ht : StrictConvex π t) :
StrictConvex π (s β© t) := by
intro x hx y hy hxy a b ha hb hab
rw [interior_inter]
exact β¨hs hx.1 hy.1 hxy ha hb hab, ht hx.2 hy.2 hxy ha hb habβ©
#align strict_convex.inter StrictConvex.inter
theorem Directed.strictConvex_iUnion {ΞΉ : Sort*} {s : ΞΉ β Set E} (hdir : Directed (Β· β Β·) s)
(hs : β β¦i : ΞΉβ¦, StrictConvex π (s i)) : StrictConvex π (β i, s i) := by
rintro x hx y hy hxy a b ha hb hab
rw [mem_iUnion] at hx hy
obtain β¨i, hxβ© := hx
obtain β¨j, hyβ© := hy
obtain β¨k, hik, hjkβ© := hdir i j
exact interior_mono (subset_iUnion s k) (hs (hik hx) (hjk hy) hxy ha hb hab)
#align directed.strict_convex_Union Directed.strictConvex_iUnion
theorem DirectedOn.strictConvex_sUnion {S : Set (Set E)} (hdir : DirectedOn (Β· β Β·) S)
(hS : β s β S, StrictConvex π s) : StrictConvex π (ββ S) := by
rw [sUnion_eq_iUnion]
exact (directedOn_iff_directed.1 hdir).strictConvex_iUnion fun s => hS _ s.2
#align directed_on.strict_convex_sUnion DirectedOn.strictConvex_sUnion
end SMul
section Module
variable [Module π E] [Module π F] {s : Set E}
protected theorem StrictConvex.convex (hs : StrictConvex π s) : Convex π s :=
convex_iff_pairwise_pos.2 fun _ hx _ hy hxy _ _ ha hb hab =>
interior_subset <| hs hx hy hxy ha hb hab
#align strict_convex.convex StrictConvex.convex
/-- An open convex set is strictly convex. -/
protected theorem Convex.strictConvex_of_isOpen (h : IsOpen s) (hs : Convex π s) :
StrictConvex π s :=
fun _ hx _ hy _ _ _ ha hb hab => h.interior_eq.symm βΈ hs hx hy ha.le hb.le hab
#align convex.strict_convex_of_open Convex.strictConvex_of_isOpen
theorem IsOpen.strictConvex_iff (h : IsOpen s) : StrictConvex π s β Convex π s :=
β¨StrictConvex.convex, Convex.strictConvex_of_isOpen hβ©
#align is_open.strict_convex_iff IsOpen.strictConvex_iff
theorem strictConvex_singleton (c : E) : StrictConvex π ({c} : Set E) :=
pairwise_singleton _ _
#align strict_convex_singleton strictConvex_singleton
theorem Set.Subsingleton.strictConvex (hs : s.Subsingleton) : StrictConvex π s :=
hs.pairwise _
#align set.subsingleton.strict_convex Set.Subsingleton.strictConvex
theorem StrictConvex.linear_image [Semiring π] [Module π E] [Module π F]
[LinearMap.CompatibleSMul E F π π] (hs : StrictConvex π s) (f : E ββ[π] F) (hf : IsOpenMap f) :
StrictConvex π (f '' s) := by
rintro _ β¨x, hx, rflβ© _ β¨y, hy, rflβ© hxy a b ha hb hab
refine' hf.image_interior_subset _ β¨a β’ x + b β’ y, hs hx hy (ne_of_apply_ne _ hxy) ha hb hab, _β©
rw [map_add, f.map_smul_of_tower a, f.map_smul_of_tower b]
#align strict_convex.linear_image StrictConvex.linear_image
theorem StrictConvex.is_linear_image (hs : StrictConvex π s) {f : E β F} (h : IsLinearMap π f)
(hf : IsOpenMap f) : StrictConvex π (f '' s) :=
hs.linear_image (h.mk' f) hf
#align strict_convex.is_linear_image StrictConvex.is_linear_image
theorem StrictConvex.linear_preimage {s : Set F} (hs : StrictConvex π s) (f : E ββ[π] F)
(hf : Continuous f) (hfinj : Injective f) : StrictConvex π (s.preimage f) := by
intro x hx y hy hxy a b ha hb hab
refine' preimage_interior_subset_interior_preimage hf _
rw [mem_preimage, f.map_add, f.map_smul, f.map_smul]
exact hs hx hy (hfinj.ne hxy) ha hb hab
#align strict_convex.linear_preimage StrictConvex.linear_preimage
theorem StrictConvex.is_linear_preimage {s : Set F} (hs : StrictConvex π s) {f : E β F}
(h : IsLinearMap π f) (hf : Continuous f) (hfinj : Injective f) :
StrictConvex π (s.preimage f) :=
hs.linear_preimage (h.mk' f) hf hfinj
#align strict_convex.is_linear_preimage StrictConvex.is_linear_preimage
section LinearOrderedCancelAddCommMonoid
variable [TopologicalSpace Ξ²] [LinearOrderedCancelAddCommMonoid Ξ²] [OrderTopology Ξ²] [Module π Ξ²]
[OrderedSMul π Ξ²]
protected theorem Set.OrdConnected.strictConvex {s : Set Ξ²} (hs : OrdConnected s) :
StrictConvex π s := by
refine' strictConvex_iff_openSegment_subset.2 fun x hx y hy hxy => _
cases' hxy.lt_or_lt with hlt hlt <;> [skip; rw [openSegment_symm]] <;>
exact
(openSegment_subset_Ioo hlt).trans
(isOpen_Ioo.subset_interior_iff.2 <| Ioo_subset_Icc_self.trans <| hs.out βΉ_βΊ βΉ_βΊ)
#align set.ord_connected.strict_convex Set.OrdConnected.strictConvex
theorem strictConvex_Iic (r : Ξ²) : StrictConvex π (Iic r) :=
ordConnected_Iic.strictConvex
#align strict_convex_Iic strictConvex_Iic
theorem strictConvex_Ici (r : Ξ²) : StrictConvex π (Ici r) :=
ordConnected_Ici.strictConvex
#align strict_convex_Ici strictConvex_Ici
theorem strictConvex_Iio (r : Ξ²) : StrictConvex π (Iio r) :=
ordConnected_Iio.strictConvex
#align strict_convex_Iio strictConvex_Iio
theorem strictConvex_Ioi (r : Ξ²) : StrictConvex π (Ioi r) :=
ordConnected_Ioi.strictConvex
#align strict_convex_Ioi strictConvex_Ioi
theorem strictConvex_Icc (r s : Ξ²) : StrictConvex π (Icc r s) :=
ordConnected_Icc.strictConvex
#align strict_convex_Icc strictConvex_Icc
theorem strictConvex_Ioo (r s : Ξ²) : StrictConvex π (Ioo r s) :=
ordConnected_Ioo.strictConvex
#align strict_convex_Ioo strictConvex_Ioo
theorem strictConvex_Ico (r s : Ξ²) : StrictConvex π (Ico r s) :=
ordConnected_Ico.strictConvex
#align strict_convex_Ico strictConvex_Ico
theorem strictConvex_Ioc (r s : Ξ²) : StrictConvex π (Ioc r s) :=
ordConnected_Ioc.strictConvex
#align strict_convex_Ioc strictConvex_Ioc
theorem strictConvex_uIcc (r s : Ξ²) : StrictConvex π (uIcc r s) :=
strictConvex_Icc _ _
#align strict_convex_uIcc strictConvex_uIcc
theorem strictConvex_uIoc (r s : Ξ²) : StrictConvex π (uIoc r s) :=
strictConvex_Ioc _ _
#align strict_convex_uIoc strictConvex_uIoc
end LinearOrderedCancelAddCommMonoid
end Module
end AddCommMonoid
section AddCancelCommMonoid
variable [AddCancelCommMonoid E] [ContinuousAdd E] [Module π E] {s : Set E}
/-- The translation of a strictly convex set is also strictly convex. -/
theorem StrictConvex.preimage_add_right (hs : StrictConvex π s) (z : E) :
StrictConvex π ((fun x => z + x) β»ΒΉ' s) := by
intro x hx y hy hxy a b ha hb hab
refine' preimage_interior_subset_interior_preimage (continuous_add_left _) _
have h := hs hx hy ((add_right_injective _).ne hxy) ha hb hab
rwa [smul_add, smul_add, add_add_add_comm, β _root_.add_smul, hab, one_smul] at h
#align strict_convex.preimage_add_right StrictConvex.preimage_add_right
/-- The translation of a strictly convex set is also strictly convex. -/
theorem StrictConvex.preimage_add_left (hs : StrictConvex π s) (z : E) :
StrictConvex π ((fun x => x + z) β»ΒΉ' s) := by
simpa only [add_comm] using hs.preimage_add_right z
#align strict_convex.preimage_add_left StrictConvex.preimage_add_left
end AddCancelCommMonoid
section AddCommGroup
variable [AddCommGroup E] [AddCommGroup F] [Module π E] [Module π F]
section continuous_add
variable [ContinuousAdd E] {s t : Set E}
theorem StrictConvex.add (hs : StrictConvex π s) (ht : StrictConvex π t) :
StrictConvex π (s + t) := by
rintro _ β¨v, hv, w, hw, rflβ© _ β¨x, hx, y, hy, rflβ© h a b ha hb hab
rw [smul_add, smul_add, add_add_add_comm]
obtain rfl | hvx := eq_or_ne v x
Β· refine' interior_mono (add_subset_add (singleton_subset_iff.2 hv) Subset.rfl) _
rw [Convex.combo_self hab, singleton_add]
exact
(isOpenMap_add_left _).image_interior_subset _
(mem_image_of_mem _ <| ht hw hy (ne_of_apply_ne _ h) ha hb hab)
exact
subset_interior_add_left
(add_mem_add (hs hv hx hvx ha hb hab) <| ht.convex hw hy ha.le hb.le hab)
#align strict_convex.add StrictConvex.add
theorem StrictConvex.add_left (hs : StrictConvex π s) (z : E) :
StrictConvex π ((fun x => z + x) '' s) := by
simpa only [singleton_add] using (strictConvex_singleton z).add hs
#align strict_convex.add_left StrictConvex.add_left
theorem StrictConvex.add_right (hs : StrictConvex π s) (z : E) :
StrictConvex π ((fun x => x + z) '' s) := by simpa only [add_comm] using hs.add_left z
#align strict_convex.add_right StrictConvex.add_right
/-- The translation of a strictly convex set is also strictly convex. -/
theorem StrictConvex.vadd (hs : StrictConvex π s) (x : E) : StrictConvex π (x +α΅₯ s) :=
hs.add_left x
#align strict_convex.vadd StrictConvex.vadd
end continuous_add
section ContinuousSMul
variable [LinearOrderedField π] [Module π E] [ContinuousConstSMul π E]
[LinearMap.CompatibleSMul E E π π] {s : Set E} {x : E}
theorem StrictConvex.smul (hs : StrictConvex π s) (c : π) : StrictConvex π (c β’ s) := by
obtain rfl | hc := eq_or_ne c 0
Β· exact (subsingleton_zero_smul_set _).strictConvex
Β· exact hs.linear_image (LinearMap.lsmul _ _ c) (isOpenMap_smulβ hc)
#align strict_convex.smul StrictConvex.smul
theorem StrictConvex.affinity [ContinuousAdd E] (hs : StrictConvex π s) (z : E) (c : π) :
StrictConvex π (z +α΅₯ c β’ s) :=
(hs.smul c).vadd z
#align strict_convex.affinity StrictConvex.affinity
end ContinuousSMul
end AddCommGroup
end OrderedSemiring
section OrderedCommSemiring
variable [OrderedCommSemiring π] [TopologicalSpace E]
section AddCommGroup
variable [AddCommGroup E] [Module π E] [NoZeroSMulDivisors π E] [ContinuousConstSMul π E]
{s : Set E}
theorem StrictConvex.preimage_smul (hs : StrictConvex π s) (c : π) :
StrictConvex π ((fun z => c β’ z) β»ΒΉ' s) := by
classical
obtain rfl | hc := eq_or_ne c 0
Β· simp_rw [zero_smul, preimage_const]
split_ifs
Β· exact strictConvex_univ
Β· exact strictConvex_empty
refine' hs.linear_preimage (LinearMap.lsmul _ _ c) _ (smul_right_injective E hc)
unfold LinearMap.lsmul LinearMap.mkβ LinearMap.mkβ' LinearMap.mkβ'ββ
exact continuous_const_smul _
#align strict_convex.preimage_smul StrictConvex.preimage_smul
end AddCommGroup
end OrderedCommSemiring
section OrderedRing
variable [OrderedRing π] [TopologicalSpace E] [TopologicalSpace F]
section AddCommGroup
variable [AddCommGroup E] [AddCommGroup F] [Module π E] [Module π F] {s t : Set E} {x y : E}
theorem StrictConvex.eq_of_openSegment_subset_frontier [Nontrivial π] [DenselyOrdered π]
(hs : StrictConvex π s) (hx : x β s) (hy : y β s) (h : openSegment π x y β frontier s) :
x = y := by
obtain β¨a, haβ, haββ© := DenselyOrdered.dense (0 : π) 1 zero_lt_one
classical
by_contra hxy
exact
(h β¨a, 1 - a, haβ, sub_pos_of_lt haβ, add_sub_cancel _ _, rflβ©).2
(hs hx hy hxy haβ (sub_pos_of_lt haβ) <| add_sub_cancel _ _)
#align strict_convex.eq_of_open_segment_subset_frontier StrictConvex.eq_of_openSegment_subset_frontier
theorem StrictConvex.add_smul_mem (hs : StrictConvex π s) (hx : x β s) (hxy : x + y β s)
(hy : y β 0) {t : π} (htβ : 0 < t) (htβ : t < 1) : x + t β’ y β interior s := by
have h : x + t β’ y = (1 - t) β’ x + t β’ (x + y) := by
rw [smul_add, β add_assoc, β _root_.add_smul, sub_add_cancel, one_smul]
rw [h]
refine' hs hx hxy (fun h => hy <| add_left_cancel _) (sub_pos_of_lt htβ) htβ (sub_add_cancel _ _)
rw [β h, add_zero]
#align strict_convex.add_smul_mem StrictConvex.add_smul_mem
theorem StrictConvex.smul_mem_of_zero_mem (hs : StrictConvex π s) (zero_mem : (0 : E) β s)
(hx : x β s) (hxβ : x β 0) {t : π} (htβ : 0 < t) (htβ : t < 1) : t β’ x β interior s := by
simpa using hs.add_smul_mem zero_mem (by simpa using hx) hxβ htβ htβ
#align strict_convex.smul_mem_of_zero_mem StrictConvex.smul_mem_of_zero_mem
theorem StrictConvex.add_smul_sub_mem (h : StrictConvex π s) (hx : x β s) (hy : y β s) (hxy : x β y)
{t : π} (htβ : 0 < t) (htβ : t < 1) : x + t β’ (y - x) β interior s := by
apply h.openSegment_subset hx hy hxy
rw [openSegment_eq_image']
exact mem_image_of_mem _ β¨htβ, htββ©
#align strict_convex.add_smul_sub_mem StrictConvex.add_smul_sub_mem
/-- The preimage of a strictly convex set under an affine map is strictly convex. -/
theorem StrictConvex.affine_preimage {s : Set F} (hs : StrictConvex π s) {f : E βα΅[π] F}
(hf : Continuous f) (hfinj : Injective f) : StrictConvex π (f β»ΒΉ' s) := by
intro x hx y hy hxy a b ha hb hab
refine' preimage_interior_subset_interior_preimage hf _
rw [mem_preimage, Convex.combo_affine_apply hab]
exact hs hx hy (hfinj.ne hxy) ha hb hab
#align strict_convex.affine_preimage StrictConvex.affine_preimage
/-- The image of a strictly convex set under an affine map is strictly convex. -/
theorem StrictConvex.affine_image (hs : StrictConvex π s) {f : E βα΅[π] F} (hf : IsOpenMap f) :
StrictConvex π (f '' s) := by
rintro _ β¨x, hx, rflβ© _ β¨y, hy, rflβ© hxy a b ha hb hab
exact
hf.image_interior_subset _
β¨a β’ x + b β’ y, β¨hs hx hy (ne_of_apply_ne _ hxy) ha hb hab, Convex.combo_affine_apply habβ©β©
#align strict_convex.affine_image StrictConvex.affine_image
variable [TopologicalAddGroup E]
theorem StrictConvex.neg (hs : StrictConvex π s) : StrictConvex π (-s) :=
hs.is_linear_preimage IsLinearMap.isLinearMap_neg continuous_id.neg neg_injective
#align strict_convex.neg StrictConvex.neg
theorem StrictConvex.sub (hs : StrictConvex π s) (ht : StrictConvex π t) : StrictConvex π (s - t) :=
(sub_eq_add_neg s t).symm βΈ hs.add ht.neg
#align strict_convex.sub StrictConvex.sub
end AddCommGroup
end OrderedRing
section LinearOrderedField
variable [LinearOrderedField π] [TopologicalSpace E]
section AddCommGroup
variable [AddCommGroup E] [AddCommGroup F] [Module π E] [Module π F] {s : Set E} {x : E}
/-- Alternative definition of set strict convexity, using division. -/
theorem strictConvex_iff_div :
StrictConvex π s β
s.Pairwise fun x y =>
β β¦a b : πβ¦, 0 < a β 0 < b β (a / (a + b)) β’ x + (b / (a + b)) β’ y β interior s :=
β¨fun h x hx y hy hxy a b ha hb => by
apply h hx hy hxy (div_pos ha <| add_pos ha hb) (div_pos hb <| add_pos ha hb)
rw [β add_div]
exact div_self (add_pos ha hb).ne', fun h x hx y hy hxy a b ha hb hab => by
convert h hx hy hxy ha hb <;> rw [hab, div_one]β©
#align strict_convex_iff_div strictConvex_iff_div
theorem StrictConvex.mem_smul_of_zero_mem (hs : StrictConvex π s) (zero_mem : (0 : E) β s)
(hx : x β s) (hxβ : x β 0) {t : π} (ht : 1 < t) : x β t β’ interior s := by
rw [mem_smul_set_iff_inv_smul_memβ (zero_lt_one.trans ht).ne']
exact hs.smul_mem_of_zero_mem zero_mem hx hxβ (inv_pos.2 <| zero_lt_one.trans ht) (inv_lt_one ht)
#align strict_convex.mem_smul_of_zero_mem StrictConvex.mem_smul_of_zero_mem
end AddCommGroup
end LinearOrderedField
/-!
#### Convex sets in an ordered space
Relates `Convex` and `Set.OrdConnected`.
-/
section
variable [LinearOrderedField π] [TopologicalSpace π] [OrderTopology π] {s : Set π}
/-- A set in a linear ordered field is strictly convex if and only if it is convex. -/
@[simp]
theorem strictConvex_iff_convex : StrictConvex π s β Convex π s :=
β¨StrictConvex.convex, fun hs => hs.ordConnected.strictConvexβ©
#align strict_convex_iff_convex strictConvex_iff_convex
theorem strictConvex_iff_ordConnected : StrictConvex π s β s.OrdConnected :=
strictConvex_iff_convex.trans convex_iff_ordConnected
#align strict_convex_iff_ord_connected strictConvex_iff_ordConnected
alias β¨StrictConvex.ordConnected, _β© := strictConvex_iff_ordConnected
#align strict_convex.ord_connected StrictConvex.ordConnected
end