60 -- {* and @{text f} a linear form on @{text F} such that @{text f} is bounded by @{text p}, *} |
60 -- {* and @{text f} a linear form on @{text F} such that @{text f} is bounded by @{text p}, *} |
61 -- {* then @{text f} can be extended to a linear form @{text h} on @{text E} in a norm-preserving way. \skp *} |
61 -- {* then @{text f} can be extended to a linear form @{text h} on @{text E} in a norm-preserving way. \skp *} |
62 proof - |
62 proof - |
63 def M \<equiv> "norm_pres_extensions E p F f" |
63 def M \<equiv> "norm_pres_extensions E p F f" |
64 hence M: "M = \<dots>" by (simp only:) |
64 hence M: "M = \<dots>" by (simp only:) |
65 have E: "vectorspace E" . |
65 note E = `vectorspace E` |
66 have F: "vectorspace F" .. |
66 then have F: "vectorspace F" .. |
|
67 note FE = `F \<unlhd> E` |
67 { |
68 { |
68 fix c assume cM: "c \<in> chain M" and ex: "\<exists>x. x \<in> c" |
69 fix c assume cM: "c \<in> chain M" and ex: "\<exists>x. x \<in> c" |
69 have "\<Union>c \<in> M" |
70 have "\<Union>c \<in> M" |
70 -- {* Show that every non-empty chain @{text c} of @{text M} has an upper bound in @{text M}: *} |
71 -- {* Show that every non-empty chain @{text c} of @{text M} has an upper bound in @{text M}: *} |
71 -- {* @{text "\<Union>c"} is greater than any element of the chain @{text c}, so it suffices to show @{text "\<Union>c \<in> M"}. *} |
72 -- {* @{text "\<Union>c"} is greater than any element of the chain @{text c}, so it suffices to show @{text "\<Union>c \<in> M"}. *} |
78 fix x y z assume "(x, y) \<in> \<Union>c" and "(x, z) \<in> \<Union>c" |
79 fix x y z assume "(x, y) \<in> \<Union>c" and "(x, z) \<in> \<Union>c" |
79 with M_def cM show "z = y" by (rule sup_definite) |
80 with M_def cM show "z = y" by (rule sup_definite) |
80 qed |
81 qed |
81 moreover from M cM a have "linearform ?H ?h" |
82 moreover from M cM a have "linearform ?H ?h" |
82 by (rule sup_lf) |
83 by (rule sup_lf) |
83 moreover from a M cM ex have "?H \<unlhd> E" |
84 moreover from a M cM ex FE E have "?H \<unlhd> E" |
84 by (rule sup_subE) |
85 by (rule sup_subE) |
85 moreover from a M cM ex have "F \<unlhd> ?H" |
86 moreover from a M cM ex FE have "F \<unlhd> ?H" |
86 by (rule sup_supF) |
87 by (rule sup_supF) |
87 moreover from a M cM ex have "graph F f \<subseteq> graph ?H ?h" |
88 moreover from a M cM ex have "graph F f \<subseteq> graph ?H ?h" |
88 by (rule sup_ext) |
89 by (rule sup_ext) |
89 moreover from a M cM have "\<forall>x \<in> ?H. ?h x \<le> p x" |
90 moreover from a M cM have "\<forall>x \<in> ?H. ?h x \<le> p x" |
90 by (rule sup_norm_pres) |
91 by (rule sup_norm_pres) |
100 -- {* With Zorn's Lemma we can conclude that there is a maximal element in @{text M}. \skp *} |
101 -- {* With Zorn's Lemma we can conclude that there is a maximal element in @{text M}. \skp *} |
101 proof (rule Zorn's_Lemma) |
102 proof (rule Zorn's_Lemma) |
102 -- {* We show that @{text M} is non-empty: *} |
103 -- {* We show that @{text M} is non-empty: *} |
103 show "graph F f \<in> M" |
104 show "graph F f \<in> M" |
104 proof (unfold M_def, rule norm_pres_extensionI2) |
105 proof (unfold M_def, rule norm_pres_extensionI2) |
105 show "linearform F f" . |
106 show "linearform F f" by fact |
106 show "F \<unlhd> E" . |
107 show "F \<unlhd> E" by fact |
107 from F show "F \<unlhd> F" by (rule vectorspace.subspace_refl) |
108 from F show "F \<unlhd> F" by (rule vectorspace.subspace_refl) |
108 show "graph F f \<subseteq> graph F f" .. |
109 show "graph F f \<subseteq> graph F f" .. |
109 show "\<forall>x\<in>F. f x \<le> p x" . |
110 show "\<forall>x\<in>F. f x \<le> p x" by fact |
110 qed |
111 qed |
111 qed |
112 qed |
112 then obtain g where gM: "g \<in> M" and "\<forall>x \<in> M. g \<subseteq> x \<longrightarrow> g = x" |
113 then obtain g where gM: "g \<in> M" and gx: "\<forall>x \<in> M. g \<subseteq> x \<longrightarrow> g = x" |
113 by blast |
114 by blast |
114 from gM [unfolded M_def] obtain H h where |
115 from gM [unfolded M_def] obtain H h where |
115 g_rep: "g = graph H h" |
116 g_rep: "g = graph H h" |
116 and linearform: "linearform H h" |
117 and linearform: "linearform H h" |
117 and HE: "H \<unlhd> E" and FH: "F \<unlhd> H" |
118 and HE: "H \<unlhd> E" and FH: "F \<unlhd> H" |
118 and graphs: "graph F f \<subseteq> graph H h" |
119 and graphs: "graph F f \<subseteq> graph H h" |
119 and hp: "\<forall>x \<in> H. h x \<le> p x" .. |
120 and hp: "\<forall>x \<in> H. h x \<le> p x" .. |
120 -- {* @{text g} is a norm-preserving extension of @{text f}, in other words: *} |
121 -- {* @{text g} is a norm-preserving extension of @{text f}, in other words: *} |
121 -- {* @{text g} is the graph of some linear form @{text h} defined on a subspace @{text H} of @{text E}, *} |
122 -- {* @{text g} is the graph of some linear form @{text h} defined on a subspace @{text H} of @{text E}, *} |
122 -- {* and @{text h} is an extension of @{text f} that is again bounded by @{text p}. \skp *} |
123 -- {* and @{text h} is an extension of @{text f} that is again bounded by @{text p}. \skp *} |
123 from HE have H: "vectorspace H" |
124 from HE E have H: "vectorspace H" |
124 by (rule subspace.vectorspace) |
125 by (rule subspace.vectorspace) |
125 |
126 |
126 have HE_eq: "H = E" |
127 have HE_eq: "H = E" |
127 -- {* We show that @{text h} is defined on whole @{text E} by classical contradiction. \skp *} |
128 -- {* We show that @{text h} is defined on whole @{text E} by classical contradiction. \skp *} |
128 proof (rule classical) |
129 proof (rule classical) |
137 proof |
138 proof |
138 show "x' \<noteq> 0" |
139 show "x' \<noteq> 0" |
139 proof |
140 proof |
140 assume "x' = 0" |
141 assume "x' = 0" |
141 with H have "x' \<in> H" by (simp only: vectorspace.zero) |
142 with H have "x' \<in> H" by (simp only: vectorspace.zero) |
142 then show False by contradiction |
143 with `x' \<notin> H` show False by contradiction |
143 qed |
144 qed |
144 qed |
145 qed |
145 |
146 |
146 def H' \<equiv> "H + lin x'" |
147 def H' \<equiv> "H + lin x'" |
147 -- {* Define @{text H'} as the direct sum of @{text H} and the linear closure of @{text x'}. \skp *} |
148 -- {* Define @{text H'} as the direct sum of @{text H} and the linear closure of @{text x'}. \skp *} |
148 have HH': "H \<unlhd> H'" |
149 have HH': "H \<unlhd> H'" |
149 proof (unfold H'_def) |
150 proof (unfold H'_def) |
150 have "vectorspace (lin x')" .. |
151 from x'E have "vectorspace (lin x')" .. |
151 with H show "H \<unlhd> H + lin x'" .. |
152 with H show "H \<unlhd> H + lin x'" .. |
152 qed |
153 qed |
153 |
154 |
154 obtain xi where |
155 obtain xi where |
155 "\<forall>y \<in> H. - p (y + x') - h y \<le> xi |
156 xi: "\<forall>y \<in> H. - p (y + x') - h y \<le> xi |
156 \<and> xi \<le> p (y + x') - h y" |
157 \<and> xi \<le> p (y + x') - h y" |
157 -- {* Pick a real number @{text \<xi>} that fulfills certain inequations; this will *} |
158 -- {* Pick a real number @{text \<xi>} that fulfills certain inequations; this will *} |
158 -- {* be used to establish that @{text h'} is a norm-preserving extension of @{text h}. |
159 -- {* be used to establish that @{text h'} is a norm-preserving extension of @{text h}. |
159 \label{ex-xi-use}\skp *} |
160 \label{ex-xi-use}\skp *} |
160 proof - |
161 proof - |
176 also from x'E uE vE E have "p \<dots> \<le> p (v + x') + p (u + x')" |
177 also from x'E uE vE E have "p \<dots> \<le> p (v + x') + p (u + x')" |
177 by (simp add: diff_subadditive) |
178 by (simp add: diff_subadditive) |
178 finally have "h v - h u \<le> p (v + x') + p (u + x')" . |
179 finally have "h v - h u \<le> p (v + x') + p (u + x')" . |
179 then show "- p (u + x') - h u \<le> p (v + x') - h v" by simp |
180 then show "- p (u + x') - h u \<le> p (v + x') - h v" by simp |
180 qed |
181 qed |
181 then show ?thesis .. |
182 then show thesis by (blast intro: that) |
182 qed |
183 qed |
183 |
184 |
184 def h' \<equiv> "\<lambda>x. let (y, a) = |
185 def h' \<equiv> "\<lambda>x. let (y, a) = |
185 SOME (y, a). x = y + a \<cdot> x' \<and> y \<in> H in h y + a * xi" |
186 SOME (y, a). x = y + a \<cdot> x' \<and> y \<in> H in h y + a * xi" |
186 -- {* Define the extension @{text h'} of @{text h} to @{text H'} using @{text \<xi>}. \skp *} |
187 -- {* Define the extension @{text h'} of @{text h} to @{text H'} using @{text \<xi>}. \skp *} |
191 show "g \<subseteq> graph H' h'" |
192 show "g \<subseteq> graph H' h'" |
192 proof - |
193 proof - |
193 have "graph H h \<subseteq> graph H' h'" |
194 have "graph H h \<subseteq> graph H' h'" |
194 proof (rule graph_extI) |
195 proof (rule graph_extI) |
195 fix t assume t: "t \<in> H" |
196 fix t assume t: "t \<in> H" |
196 have "(SOME (y, a). t = y + a \<cdot> x' \<and> y \<in> H) = (t, 0)" |
197 from E HE t have "(SOME (y, a). t = y + a \<cdot> x' \<and> y \<in> H) = (t, 0)" |
197 by (rule decomp_H'_H) |
198 using `x' \<notin> H` `x' \<in> E` `x' \<noteq> 0` by (rule decomp_H'_H) |
198 with h'_def show "h t = h' t" by (simp add: Let_def) |
199 with h'_def show "h t = h' t" by (simp add: Let_def) |
199 next |
200 next |
200 from HH' show "H \<subseteq> H'" .. |
201 from HH' show "H \<subseteq> H'" .. |
201 qed |
202 qed |
202 with g_rep show ?thesis by (simp only:) |
203 with g_rep show ?thesis by (simp only:) |
214 from x'E show "x' = 0 + x'" by simp |
215 from x'E show "x' = 0 + x'" by simp |
215 qed |
216 qed |
216 hence "(x', h' x') \<in> graph H' h'" .. |
217 hence "(x', h' x') \<in> graph H' h'" .. |
217 with eq have "(x', h' x') \<in> graph H h" by (simp only:) |
218 with eq have "(x', h' x') \<in> graph H h" by (simp only:) |
218 hence "x' \<in> H" .. |
219 hence "x' \<in> H" .. |
219 thus False by contradiction |
220 with `x' \<notin> H` show False by contradiction |
220 qed |
221 qed |
221 with g_rep show ?thesis by simp |
222 with g_rep show ?thesis by simp |
222 qed |
223 qed |
223 qed |
224 qed |
224 moreover have "graph H' h' \<in> M" |
225 moreover have "graph H' h' \<in> M" |
225 -- {* and @{text h'} is norm-preserving. \skp *} |
226 -- {* and @{text h'} is norm-preserving. \skp *} |
226 proof (unfold M_def) |
227 proof (unfold M_def) |
227 show "graph H' h' \<in> norm_pres_extensions E p F f" |
228 show "graph H' h' \<in> norm_pres_extensions E p F f" |
228 proof (rule norm_pres_extensionI2) |
229 proof (rule norm_pres_extensionI2) |
229 show "linearform H' h'" by (rule h'_lf) |
230 show "linearform H' h'" |
|
231 using h'_def H'_def HE linearform `x' \<notin> H` `x' \<in> E` `x' \<noteq> 0` E |
|
232 by (rule h'_lf) |
230 show "H' \<unlhd> E" |
233 show "H' \<unlhd> E" |
231 proof (unfold H'_def, rule) |
234 unfolding H'_def |
232 show "H \<unlhd> E" . |
235 proof |
233 show "vectorspace E" . |
236 show "H \<unlhd> E" by fact |
|
237 show "vectorspace E" by fact |
234 from x'E show "lin x' \<unlhd> E" .. |
238 from x'E show "lin x' \<unlhd> E" .. |
235 qed |
239 qed |
236 have "F \<unlhd> H" . |
240 from H `F \<unlhd> H` HH' show FH': "F \<unlhd> H'" |
237 from H this HH' show FH': "F \<unlhd> H'" |
|
238 by (rule vectorspace.subspace_trans) |
241 by (rule vectorspace.subspace_trans) |
239 show "graph F f \<subseteq> graph H' h'" |
242 show "graph F f \<subseteq> graph H' h'" |
240 proof (rule graph_extI) |
243 proof (rule graph_extI) |
241 fix x assume x: "x \<in> F" |
244 fix x assume x: "x \<in> F" |
242 with graphs have "f x = h x" .. |
245 with graphs have "f x = h x" .. |
243 also have "\<dots> = h x + 0 * xi" by simp |
246 also have "\<dots> = h x + 0 * xi" by simp |
244 also have "\<dots> = (let (y, a) = (x, 0) in h y + a * xi)" |
247 also have "\<dots> = (let (y, a) = (x, 0) in h y + a * xi)" |
245 by (simp add: Let_def) |
248 by (simp add: Let_def) |
246 also have "(x, 0) = |
249 also have "(x, 0) = |
247 (SOME (y, a). x = y + a \<cdot> x' \<and> y \<in> H)" |
250 (SOME (y, a). x = y + a \<cdot> x' \<and> y \<in> H)" |
|
251 using E HE |
248 proof (rule decomp_H'_H [symmetric]) |
252 proof (rule decomp_H'_H [symmetric]) |
249 from FH x show "x \<in> H" .. |
253 from FH x show "x \<in> H" .. |
250 from x' show "x' \<noteq> 0" . |
254 from x' show "x' \<noteq> 0" . |
|
255 show "x' \<notin> H" by fact |
|
256 show "x' \<in> E" by fact |
251 qed |
257 qed |
252 also have |
258 also have |
253 "(let (y, a) = (SOME (y, a). x = y + a \<cdot> x' \<and> y \<in> H) |
259 "(let (y, a) = (SOME (y, a). x = y + a \<cdot> x' \<and> y \<in> H) |
254 in h y + a * xi) = h' x" by (simp only: h'_def) |
260 in h y + a * xi) = h' x" by (simp only: h'_def) |
255 finally show "f x = h' x" . |
261 finally show "f x = h' x" . |
256 next |
262 next |
257 from FH' show "F \<subseteq> H'" .. |
263 from FH' show "F \<subseteq> H'" .. |
258 qed |
264 qed |
259 show "\<forall>x \<in> H'. h' x \<le> p x" by (rule h'_norm_pres) |
265 show "\<forall>x \<in> H'. h' x \<le> p x" |
|
266 using h'_def H'_def `x' \<notin> H` `x' \<in> E` `x' \<noteq> 0` E HE |
|
267 `seminorm E p` linearform and hp xi |
|
268 by (rule h'_norm_pres) |
260 qed |
269 qed |
261 qed |
270 qed |
262 ultimately show ?thesis .. |
271 ultimately show ?thesis .. |
263 qed |
272 qed |
264 hence "\<not> (\<forall>x \<in> M. g \<subseteq> x \<longrightarrow> g = x)" by simp |
273 hence "\<not> (\<forall>x \<in> M. g \<subseteq> x \<longrightarrow> g = x)" by simp |
265 -- {* So the graph @{text g} of @{text h} cannot be maximal. Contradiction! \skp *} |
274 -- {* So the graph @{text g} of @{text h} cannot be maximal. Contradiction! \skp *} |
266 then show "H = E" by contradiction |
275 with gx show "H = E" by contradiction |
267 qed |
276 qed |
268 |
277 |
269 from HE_eq and linearform have "linearform E h" |
278 from HE_eq and linearform have "linearform E h" |
270 by (simp only:) |
279 by (simp only:) |
271 moreover have "\<forall>x \<in> F. h x = f x" |
280 moreover have "\<forall>x \<in> F. h x = f x" |
301 assumes fp: "\<forall>x \<in> F. \<bar>f x\<bar> \<le> p x" |
310 assumes fp: "\<forall>x \<in> F. \<bar>f x\<bar> \<le> p x" |
302 shows "\<exists>g. linearform E g |
311 shows "\<exists>g. linearform E g |
303 \<and> (\<forall>x \<in> F. g x = f x) |
312 \<and> (\<forall>x \<in> F. g x = f x) |
304 \<and> (\<forall>x \<in> E. \<bar>g x\<bar> \<le> p x)" |
313 \<and> (\<forall>x \<in> E. \<bar>g x\<bar> \<le> p x)" |
305 proof - |
314 proof - |
306 have "\<exists>g. linearform E g \<and> (\<forall>x \<in> F. g x = f x) |
315 note E = `vectorspace E` |
307 \<and> (\<forall>x \<in> E. g x \<le> p x)" |
316 note FE = `subspace F E` |
|
317 note sn = `seminorm E p` |
|
318 note lf = `linearform F f` |
|
319 have "\<exists>g. linearform E g \<and> (\<forall>x \<in> F. g x = f x) \<and> (\<forall>x \<in> E. g x \<le> p x)" |
|
320 using E FE sn lf |
308 proof (rule HahnBanach) |
321 proof (rule HahnBanach) |
309 show "\<forall>x \<in> F. f x \<le> p x" |
322 show "\<forall>x \<in> F. f x \<le> p x" |
310 by (rule abs_ineq_iff [THEN iffD1]) |
323 using FE E sn lf and fp by (rule abs_ineq_iff [THEN iffD1]) |
311 qed |
324 qed |
312 then obtain g where * : "linearform E g" "\<forall>x \<in> F. g x = f x" |
325 then obtain g where lg: "linearform E g" and *: "\<forall>x \<in> F. g x = f x" |
313 and "\<forall>x \<in> E. g x \<le> p x" by blast |
326 and **: "\<forall>x \<in> E. g x \<le> p x" by blast |
314 have "\<forall>x \<in> E. \<bar>g x\<bar> \<le> p x" |
327 have "\<forall>x \<in> E. \<bar>g x\<bar> \<le> p x" |
|
328 using _ E sn lg ** |
315 proof (rule abs_ineq_iff [THEN iffD2]) |
329 proof (rule abs_ineq_iff [THEN iffD2]) |
316 show "E \<unlhd> E" .. |
330 show "E \<unlhd> E" .. |
317 qed |
331 qed |
318 with * show ?thesis by blast |
332 with lg * show ?thesis by blast |
319 qed |
333 qed |
320 |
334 |
321 |
335 |
322 subsection {* The Hahn-Banach Theorem for normed spaces *} |
336 subsection {* The Hahn-Banach Theorem for normed spaces *} |
323 |
337 |
334 \<and> (\<forall>x \<in> F. g x = f x) |
348 \<and> (\<forall>x \<in> F. g x = f x) |
335 \<and> \<parallel>g\<parallel>\<hyphen>E = \<parallel>f\<parallel>\<hyphen>F" |
349 \<and> \<parallel>g\<parallel>\<hyphen>E = \<parallel>f\<parallel>\<hyphen>F" |
336 proof - |
350 proof - |
337 have E: "vectorspace E" by unfold_locales |
351 have E: "vectorspace E" by unfold_locales |
338 have E_norm: "normed_vectorspace E norm" by rule unfold_locales |
352 have E_norm: "normed_vectorspace E norm" by rule unfold_locales |
339 have FE: "F \<unlhd> E" . |
353 note FE = `F \<unlhd> E` |
340 have F: "vectorspace F" by rule unfold_locales |
354 have F: "vectorspace F" by rule unfold_locales |
341 have linearform: "linearform F f" . |
355 note linearform = `linearform F f` |
342 have F_norm: "normed_vectorspace F norm" |
356 have F_norm: "normed_vectorspace F norm" |
343 by (rule subspace_normed_vs) |
357 using FE E_norm by (rule subspace_normed_vs) |
344 have ge_zero: "0 \<le> \<parallel>f\<parallel>\<hyphen>F" |
358 have ge_zero: "0 \<le> \<parallel>f\<parallel>\<hyphen>F" |
345 by (rule normed_vectorspace.fn_norm_ge_zero |
359 by (rule normed_vectorspace.fn_norm_ge_zero |
346 [OF F_norm (* continuous.intro*), folded B_def fn_norm_def]) |
360 [OF F_norm `continuous F norm f`, folded B_def fn_norm_def]) |
347 txt {* We define a function @{text p} on @{text E} as follows: |
361 txt {* We define a function @{text p} on @{text E} as follows: |
348 @{text "p x = \<parallel>f\<parallel> \<cdot> \<parallel>x\<parallel>"} *} |
362 @{text "p x = \<parallel>f\<parallel> \<cdot> \<parallel>x\<parallel>"} *} |
349 def p \<equiv> "\<lambda>x. \<parallel>f\<parallel>\<hyphen>F * \<parallel>x\<parallel>" |
363 def p \<equiv> "\<lambda>x. \<parallel>f\<parallel>\<hyphen>F * \<parallel>x\<parallel>" |
350 |
364 |
351 txt {* @{text p} is a seminorm on @{text E}: *} |
365 txt {* @{text p} is a seminorm on @{text E}: *} |
450 show "\<parallel>f\<parallel>\<hyphen>F \<le> \<parallel>g\<parallel>\<hyphen>E" |
465 show "\<parallel>f\<parallel>\<hyphen>F \<le> \<parallel>g\<parallel>\<hyphen>E" |
451 proof (rule normed_vectorspace.fn_norm_least [OF F_norm, folded B_def fn_norm_def]) |
466 proof (rule normed_vectorspace.fn_norm_least [OF F_norm, folded B_def fn_norm_def]) |
452 show "\<forall>x \<in> F. \<bar>f x\<bar> \<le> \<parallel>g\<parallel>\<hyphen>E * \<parallel>x\<parallel>" |
467 show "\<forall>x \<in> F. \<bar>f x\<bar> \<le> \<parallel>g\<parallel>\<hyphen>E * \<parallel>x\<parallel>" |
453 proof |
468 proof |
454 fix x assume x: "x \<in> F" |
469 fix x assume x: "x \<in> F" |
455 from a have "g x = f x" .. |
470 from a x have "g x = f x" .. |
456 hence "\<bar>f x\<bar> = \<bar>g x\<bar>" by (simp only:) |
471 hence "\<bar>f x\<bar> = \<bar>g x\<bar>" by (simp only:) |
457 also from g_cont |
472 also from g_cont |
458 have "\<dots> \<le> \<parallel>g\<parallel>\<hyphen>E * \<parallel>x\<parallel>" |
473 have "\<dots> \<le> \<parallel>g\<parallel>\<hyphen>E * \<parallel>x\<parallel>" |
459 proof (rule fn_norm_le_cong [of g, folded B_def fn_norm_def]) |
474 proof (rule fn_norm_le_cong [of g, folded B_def fn_norm_def]) |
460 from FE x show "x \<in> E" .. |
475 from FE x show "x \<in> E" .. |