14 text {* A non-empty subset $U$ of a vector space $V$ is a |
14 text {* A non-empty subset $U$ of a vector space $V$ is a |
15 \emph{subspace} of $V$, iff $U$ is closed under addition and |
15 \emph{subspace} of $V$, iff $U$ is closed under addition and |
16 scalar multiplication. *} |
16 scalar multiplication. *} |
17 |
17 |
18 constdefs |
18 constdefs |
19 is_subspace :: "['a::{minus, plus} set, 'a set] => bool" |
19 is_subspace :: "['a::{plus, minus, zero} set, 'a set] => bool" |
20 "is_subspace U V == U ~= {} & U <= V |
20 "is_subspace U V == U \<noteq> {} \<and> U <= V |
21 & (ALL x:U. ALL y:U. ALL a. x + y : U & a (*) x : U)" |
21 \<and> (\<forall>x \<in> U. \<forall>y \<in> U. \<forall>a. x + y \<in> U \<and> a \<cdot> x\<in> U)" |
22 |
22 |
23 lemma subspaceI [intro]: |
23 lemma subspaceI [intro]: |
24 "[| 00 : U; U <= V; ALL x:U. ALL y:U. (x + y : U); |
24 "[| 0 \<in> U; U <= V; \<forall>x \<in> U. \<forall>y \<in> U. (x + y \<in> U); |
25 ALL x:U. ALL a. a (*) x : U |] |
25 \<forall>x \<in> U. \<forall>a. a \<cdot> x \<in> U |] |
26 ==> is_subspace U V" |
26 ==> is_subspace U V" |
27 proof (unfold is_subspace_def, intro conjI) |
27 proof (unfold is_subspace_def, intro conjI) |
28 assume "00 : U" thus "U ~= {}" by fast |
28 assume "0 \<in> U" thus "U \<noteq> {}" by fast |
29 qed (simp+) |
29 qed (simp+) |
30 |
30 |
31 lemma subspace_not_empty [intro??]: "is_subspace U V ==> U ~= {}" |
31 lemma subspace_not_empty [intro??]: "is_subspace U V ==> U \<noteq> {}" |
32 by (unfold is_subspace_def) simp |
32 by (unfold is_subspace_def) simp |
33 |
33 |
34 lemma subspace_subset [intro??]: "is_subspace U V ==> U <= V" |
34 lemma subspace_subset [intro??]: "is_subspace U V ==> U <= V" |
35 by (unfold is_subspace_def) simp |
35 by (unfold is_subspace_def) simp |
36 |
36 |
37 lemma subspace_subsetD [simp, intro??]: |
37 lemma subspace_subsetD [simp, intro??]: |
38 "[| is_subspace U V; x:U |] ==> x:V" |
38 "[| is_subspace U V; x \<in> U |] ==> x \<in> V" |
39 by (unfold is_subspace_def) force |
39 by (unfold is_subspace_def) force |
40 |
40 |
41 lemma subspace_add_closed [simp, intro??]: |
41 lemma subspace_add_closed [simp, intro??]: |
42 "[| is_subspace U V; x:U; y:U |] ==> x + y : U" |
42 "[| is_subspace U V; x \<in> U; y \<in> U |] ==> x + y \<in> U" |
43 by (unfold is_subspace_def) simp |
43 by (unfold is_subspace_def) simp |
44 |
44 |
45 lemma subspace_mult_closed [simp, intro??]: |
45 lemma subspace_mult_closed [simp, intro??]: |
46 "[| is_subspace U V; x:U |] ==> a (*) x : U" |
46 "[| is_subspace U V; x \<in> U |] ==> a \<cdot> x \<in> U" |
47 by (unfold is_subspace_def) simp |
47 by (unfold is_subspace_def) simp |
48 |
48 |
49 lemma subspace_diff_closed [simp, intro??]: |
49 lemma subspace_diff_closed [simp, intro??]: |
50 "[| is_subspace U V; is_vectorspace V; x:U; y:U |] |
50 "[| is_subspace U V; is_vectorspace V; x \<in> U; y \<in> U |] |
51 ==> x - y : U" |
51 ==> x - y \<in> U" |
52 by (simp! add: diff_eq1 negate_eq1) |
52 by (simp! add: diff_eq1 negate_eq1) |
53 |
53 |
54 text {* Similar as for linear spaces, the existence of the |
54 text {* Similar as for linear spaces, the existence of the |
55 zero element in every subspace follows from the non-emptiness |
55 zero element in every subspace follows from the non-emptiness |
56 of the carrier set and by vector space laws.*} |
56 of the carrier set and by vector space laws.*} |
57 |
57 |
58 lemma zero_in_subspace [intro??]: |
58 lemma zero_in_subspace [intro??]: |
59 "[| is_subspace U V; is_vectorspace V |] ==> 00 : U" |
59 "[| is_subspace U V; is_vectorspace V |] ==> 0 \<in> U" |
60 proof - |
60 proof - |
61 assume "is_subspace U V" and v: "is_vectorspace V" |
61 assume "is_subspace U V" and v: "is_vectorspace V" |
62 have "U ~= {}" .. |
62 have "U \<noteq> {}" .. |
63 hence "EX x. x:U" by force |
63 hence "\<exists>x. x \<in> U" by force |
64 thus ?thesis |
64 thus ?thesis |
65 proof |
65 proof |
66 fix x assume u: "x:U" |
66 fix x assume u: "x \<in> U" |
67 hence "x:V" by (simp!) |
67 hence "x \<in> V" by (simp!) |
68 with v have "00 = x - x" by (simp!) |
68 with v have "0 = x - x" by (simp!) |
69 also have "... : U" by (rule subspace_diff_closed) |
69 also have "... \<in> U" by (rule subspace_diff_closed) |
70 finally show ?thesis . |
70 finally show ?thesis . |
71 qed |
71 qed |
72 qed |
72 qed |
73 |
73 |
74 lemma subspace_neg_closed [simp, intro??]: |
74 lemma subspace_neg_closed [simp, intro??]: |
75 "[| is_subspace U V; is_vectorspace V; x:U |] ==> - x : U" |
75 "[| is_subspace U V; is_vectorspace V; x \<in> U |] ==> - x \<in> U" |
76 by (simp add: negate_eq1) |
76 by (simp add: negate_eq1) |
77 |
77 |
78 text_raw {* \medskip *} |
78 text_raw {* \medskip *} |
79 text {* Further derived laws: every subspace is a vector space. *} |
79 text {* Further derived laws: every subspace is a vector space. *} |
80 |
80 |
82 "[| is_subspace U V; is_vectorspace V |] ==> is_vectorspace U" |
82 "[| is_subspace U V; is_vectorspace V |] ==> is_vectorspace U" |
83 proof - |
83 proof - |
84 assume "is_subspace U V" "is_vectorspace V" |
84 assume "is_subspace U V" "is_vectorspace V" |
85 show ?thesis |
85 show ?thesis |
86 proof |
86 proof |
87 show "00 : U" .. |
87 show "0 \<in> U" .. |
88 show "ALL x:U. ALL a. a (*) x : U" by (simp!) |
88 show "\<forall>x \<in> U. \<forall>a. a \<cdot> x \<in> U" by (simp!) |
89 show "ALL x:U. ALL y:U. x + y : U" by (simp!) |
89 show "\<forall>x \<in> U. \<forall>y \<in> U. x + y \<in> U" by (simp!) |
90 show "ALL x:U. - x = -#1 (*) x" by (simp! add: negate_eq1) |
90 show "\<forall>x \<in> U. - x = -#1 \<cdot> x" by (simp! add: negate_eq1) |
91 show "ALL x:U. ALL y:U. x - y = x + - y" |
91 show "\<forall>x \<in> U. \<forall>y \<in> U. x - y = x + - y" |
92 by (simp! add: diff_eq1) |
92 by (simp! add: diff_eq1) |
93 qed (simp! add: vs_add_mult_distrib1 vs_add_mult_distrib2)+ |
93 qed (simp! add: vs_add_mult_distrib1 vs_add_mult_distrib2)+ |
94 qed |
94 qed |
95 |
95 |
96 text {* The subspace relation is reflexive. *} |
96 text {* The subspace relation is reflexive. *} |
97 |
97 |
98 lemma subspace_refl [intro]: "is_vectorspace V ==> is_subspace V V" |
98 lemma subspace_refl [intro]: "is_vectorspace V ==> is_subspace V V" |
99 proof |
99 proof |
100 assume "is_vectorspace V" |
100 assume "is_vectorspace V" |
101 show "00 : V" .. |
101 show "0 \<in> V" .. |
102 show "V <= V" .. |
102 show "V <= V" .. |
103 show "ALL x:V. ALL y:V. x + y : V" by (simp!) |
103 show "\<forall>x \<in> V. \<forall>y \<in> V. x + y \<in> V" by (simp!) |
104 show "ALL x:V. ALL a. a (*) x : V" by (simp!) |
104 show "\<forall>x \<in> V. \<forall>a. a \<cdot> x \<in> V" by (simp!) |
105 qed |
105 qed |
106 |
106 |
107 text {* The subspace relation is transitive. *} |
107 text {* The subspace relation is transitive. *} |
108 |
108 |
109 lemma subspace_trans: |
109 lemma subspace_trans: |
110 "[| is_subspace U V; is_vectorspace V; is_subspace V W |] |
110 "[| is_subspace U V; is_vectorspace V; is_subspace V W |] |
111 ==> is_subspace U W" |
111 ==> is_subspace U W" |
112 proof |
112 proof |
113 assume "is_subspace U V" "is_subspace V W" "is_vectorspace V" |
113 assume "is_subspace U V" "is_subspace V W" "is_vectorspace V" |
114 show "00 : U" .. |
114 show "0 \<in> U" .. |
115 |
115 |
116 have "U <= V" .. |
116 have "U <= V" .. |
117 also have "V <= W" .. |
117 also have "V <= W" .. |
118 finally show "U <= W" . |
118 finally show "U <= W" . |
119 |
119 |
120 show "ALL x:U. ALL y:U. x + y : U" |
120 show "\<forall>x \<in> U. \<forall>y \<in> U. x + y \<in> U" |
121 proof (intro ballI) |
121 proof (intro ballI) |
122 fix x y assume "x:U" "y:U" |
122 fix x y assume "x \<in> U" "y \<in> U" |
123 show "x + y : U" by (simp!) |
123 show "x + y \<in> U" by (simp!) |
124 qed |
124 qed |
125 |
125 |
126 show "ALL x:U. ALL a. a (*) x : U" |
126 show "\<forall>x \<in> U. \<forall>a. a \<cdot> x \<in> U" |
127 proof (intro ballI allI) |
127 proof (intro ballI allI) |
128 fix x a assume "x:U" |
128 fix x a assume "x \<in> U" |
129 show "a (*) x : U" by (simp!) |
129 show "a \<cdot> x \<in> U" by (simp!) |
130 qed |
130 qed |
131 qed |
131 qed |
132 |
132 |
133 |
133 |
134 |
134 |
136 |
136 |
137 text {* The \emph{linear closure} of a vector $x$ is the set of all |
137 text {* The \emph{linear closure} of a vector $x$ is the set of all |
138 scalar multiples of $x$. *} |
138 scalar multiples of $x$. *} |
139 |
139 |
140 constdefs |
140 constdefs |
141 lin :: "'a => 'a set" |
141 lin :: "('a::{minus,plus,zero}) => 'a set" |
142 "lin x == {a (*) x | a. True}" |
142 "lin x == {a \<cdot> x | a. True}" |
143 |
143 |
144 lemma linD: "x : lin v = (EX a::real. x = a (*) v)" |
144 lemma linD: "x \<in> lin v = (\<exists>a::real. x = a \<cdot> v)" |
145 by (unfold lin_def) fast |
145 by (unfold lin_def) fast |
146 |
146 |
147 lemma linI [intro??]: "a (*) x0 : lin x0" |
147 lemma linI [intro??]: "a \<cdot> x0 \<in> lin x0" |
148 by (unfold lin_def) fast |
148 by (unfold lin_def) fast |
149 |
149 |
150 text {* Every vector is contained in its linear closure. *} |
150 text {* Every vector is contained in its linear closure. *} |
151 |
151 |
152 lemma x_lin_x: "[| is_vectorspace V; x:V |] ==> x : lin x" |
152 lemma x_lin_x: "[| is_vectorspace V; x \<in> V |] ==> x \<in> lin x" |
153 proof (unfold lin_def, intro CollectI exI conjI) |
153 proof (unfold lin_def, intro CollectI exI conjI) |
154 assume "is_vectorspace V" "x:V" |
154 assume "is_vectorspace V" "x \<in> V" |
155 show "x = #1 (*) x" by (simp!) |
155 show "x = #1 \<cdot> x" by (simp!) |
156 qed simp |
156 qed simp |
157 |
157 |
158 text {* Any linear closure is a subspace. *} |
158 text {* Any linear closure is a subspace. *} |
159 |
159 |
160 lemma lin_subspace [intro??]: |
160 lemma lin_subspace [intro??]: |
161 "[| is_vectorspace V; x:V |] ==> is_subspace (lin x) V" |
161 "[| is_vectorspace V; x \<in> V |] ==> is_subspace (lin x) V" |
162 proof |
162 proof |
163 assume "is_vectorspace V" "x:V" |
163 assume "is_vectorspace V" "x \<in> V" |
164 show "00 : lin x" |
164 show "0 \<in> lin x" |
165 proof (unfold lin_def, intro CollectI exI conjI) |
165 proof (unfold lin_def, intro CollectI exI conjI) |
166 show "00 = (#0::real) (*) x" by (simp!) |
166 show "0 = (#0::real) \<cdot> x" by (simp!) |
167 qed simp |
167 qed simp |
168 |
168 |
169 show "lin x <= V" |
169 show "lin x <= V" |
170 proof (unfold lin_def, intro subsetI, elim CollectE exE conjE) |
170 proof (unfold lin_def, intro subsetI, elim CollectE exE conjE) |
171 fix xa a assume "xa = a (*) x" |
171 fix xa a assume "xa = a \<cdot> x" |
172 show "xa:V" by (simp!) |
172 show "xa \<in> V" by (simp!) |
173 qed |
173 qed |
174 |
174 |
175 show "ALL x1 : lin x. ALL x2 : lin x. x1 + x2 : lin x" |
175 show "\<forall>x1 \<in> lin x. \<forall>x2 \<in> lin x. x1 + x2 \<in> lin x" |
176 proof (intro ballI) |
176 proof (intro ballI) |
177 fix x1 x2 assume "x1 : lin x" "x2 : lin x" |
177 fix x1 x2 assume "x1 \<in> lin x" "x2 \<in> lin x" |
178 thus "x1 + x2 : lin x" |
178 thus "x1 + x2 \<in> lin x" |
179 proof (unfold lin_def, elim CollectE exE conjE, |
179 proof (unfold lin_def, elim CollectE exE conjE, |
180 intro CollectI exI conjI) |
180 intro CollectI exI conjI) |
181 fix a1 a2 assume "x1 = a1 (*) x" "x2 = a2 (*) x" |
181 fix a1 a2 assume "x1 = a1 \<cdot> x" "x2 = a2 \<cdot> x" |
182 show "x1 + x2 = (a1 + a2) (*) x" |
182 show "x1 + x2 = (a1 + a2) \<cdot> x" |
183 by (simp! add: vs_add_mult_distrib2) |
183 by (simp! add: vs_add_mult_distrib2) |
184 qed simp |
184 qed simp |
185 qed |
185 qed |
186 |
186 |
187 show "ALL xa:lin x. ALL a. a (*) xa : lin x" |
187 show "\<forall>xa \<in> lin x. \<forall>a. a \<cdot> xa \<in> lin x" |
188 proof (intro ballI allI) |
188 proof (intro ballI allI) |
189 fix x1 a assume "x1 : lin x" |
189 fix x1 a assume "x1 \<in> lin x" |
190 thus "a (*) x1 : lin x" |
190 thus "a \<cdot> x1 \<in> lin x" |
191 proof (unfold lin_def, elim CollectE exE conjE, |
191 proof (unfold lin_def, elim CollectE exE conjE, |
192 intro CollectI exI conjI) |
192 intro CollectI exI conjI) |
193 fix a1 assume "x1 = a1 (*) x" |
193 fix a1 assume "x1 = a1 \<cdot> x" |
194 show "a (*) x1 = (a * a1) (*) x" by (simp!) |
194 show "a \<cdot> x1 = (a * a1) \<cdot> x" by (simp!) |
195 qed simp |
195 qed simp |
196 qed |
196 qed |
197 qed |
197 qed |
198 |
198 |
199 text {* Any linear closure is a vector space. *} |
199 text {* Any linear closure is a vector space. *} |
200 |
200 |
201 lemma lin_vs [intro??]: |
201 lemma lin_vs [intro??]: |
202 "[| is_vectorspace V; x:V |] ==> is_vectorspace (lin x)" |
202 "[| is_vectorspace V; x \<in> V |] ==> is_vectorspace (lin x)" |
203 proof (rule subspace_vs) |
203 proof (rule subspace_vs) |
204 assume "is_vectorspace V" "x:V" |
204 assume "is_vectorspace V" "x \<in> V" |
205 show "is_subspace (lin x) V" .. |
205 show "is_subspace (lin x) V" .. |
206 qed |
206 qed |
207 |
207 |
208 |
208 |
209 |
209 |
213 all sums of elements from $U$ and $V$. *} |
213 all sums of elements from $U$ and $V$. *} |
214 |
214 |
215 instance set :: (plus) plus by intro_classes |
215 instance set :: (plus) plus by intro_classes |
216 |
216 |
217 defs vs_sum_def: |
217 defs vs_sum_def: |
218 "U + V == {u + v | u v. u:U & v:V}" (*** |
218 "U + V == {u + v | u v. u \<in> U \<and> v \<in> V}" (*** |
219 |
219 |
220 constdefs |
220 constdefs |
221 vs_sum :: |
221 vs_sum :: |
222 "['a::{minus, plus} set, 'a set] => 'a set" (infixl "+" 65) |
222 "['a::{plus, minus, zero} set, 'a set] => 'a set" (infixl "+" 65) |
223 "vs_sum U V == {x. EX u:U. EX v:V. x = u + v}"; |
223 "vs_sum U V == {x. \<exists>u \<in> U. \<exists>v \<in> V. x = u + v}"; |
224 ***) |
224 ***) |
225 |
225 |
226 lemma vs_sumD: |
226 lemma vs_sumD: |
227 "x: U + V = (EX u:U. EX v:V. x = u + v)" |
227 "x \<in> U + V = (\<exists>u \<in> U. \<exists>v \<in> V. x = u + v)" |
228 by (unfold vs_sum_def) fast |
228 by (unfold vs_sum_def) fast |
229 |
229 |
230 lemmas vs_sumE = vs_sumD [RS iffD1, elimify] |
230 lemmas vs_sumE = vs_sumD [RS iffD1, elimify] |
231 |
231 |
232 lemma vs_sumI [intro??]: |
232 lemma vs_sumI [intro??]: |
233 "[| x:U; y:V; t= x + y |] ==> t : U + V" |
233 "[| x \<in> U; y \<in> V; t= x + y |] ==> t \<in> U + V" |
234 by (unfold vs_sum_def) fast |
234 by (unfold vs_sum_def) fast |
235 |
235 |
236 text{* $U$ is a subspace of $U + V$. *} |
236 text{* $U$ is a subspace of $U + V$. *} |
237 |
237 |
238 lemma subspace_vs_sum1 [intro??]: |
238 lemma subspace_vs_sum1 [intro??]: |
239 "[| is_vectorspace U; is_vectorspace V |] |
239 "[| is_vectorspace U; is_vectorspace V |] |
240 ==> is_subspace U (U + V)" |
240 ==> is_subspace U (U + V)" |
241 proof |
241 proof |
242 assume "is_vectorspace U" "is_vectorspace V" |
242 assume "is_vectorspace U" "is_vectorspace V" |
243 show "00 : U" .. |
243 show "0 \<in> U" .. |
244 show "U <= U + V" |
244 show "U <= U + V" |
245 proof (intro subsetI vs_sumI) |
245 proof (intro subsetI vs_sumI) |
246 fix x assume "x:U" |
246 fix x assume "x \<in> U" |
247 show "x = x + 00" by (simp!) |
247 show "x = x + 0" by (simp!) |
248 show "00 : V" by (simp!) |
248 show "0 \<in> V" by (simp!) |
249 qed |
249 qed |
250 show "ALL x:U. ALL y:U. x + y : U" |
250 show "\<forall>x \<in> U. \<forall>y \<in> U. x + y \<in> U" |
251 proof (intro ballI) |
251 proof (intro ballI) |
252 fix x y assume "x:U" "y:U" show "x + y : U" by (simp!) |
252 fix x y assume "x \<in> U" "y \<in> U" show "x + y \<in> U" by (simp!) |
253 qed |
253 qed |
254 show "ALL x:U. ALL a. a (*) x : U" |
254 show "\<forall>x \<in> U. \<forall>a. a \<cdot> x \<in> U" |
255 proof (intro ballI allI) |
255 proof (intro ballI allI) |
256 fix x a assume "x:U" show "a (*) x : U" by (simp!) |
256 fix x a assume "x \<in> U" show "a \<cdot> x \<in> U" by (simp!) |
257 qed |
257 qed |
258 qed |
258 qed |
259 |
259 |
260 text{* The sum of two subspaces is again a subspace.*} |
260 text{* The sum of two subspaces is again a subspace.*} |
261 |
261 |
262 lemma vs_sum_subspace [intro??]: |
262 lemma vs_sum_subspace [intro??]: |
263 "[| is_subspace U E; is_subspace V E; is_vectorspace E |] |
263 "[| is_subspace U E; is_subspace V E; is_vectorspace E |] |
264 ==> is_subspace (U + V) E" |
264 ==> is_subspace (U + V) E" |
265 proof |
265 proof |
266 assume "is_subspace U E" "is_subspace V E" "is_vectorspace E" |
266 assume "is_subspace U E" "is_subspace V E" "is_vectorspace E" |
267 show "00 : U + V" |
267 show "0 \<in> U + V" |
268 proof (intro vs_sumI) |
268 proof (intro vs_sumI) |
269 show "00 : U" .. |
269 show "0 \<in> U" .. |
270 show "00 : V" .. |
270 show "0 \<in> V" .. |
271 show "(00::'a) = 00 + 00" by (simp!) |
271 show "(0::'a) = 0 + 0" by (simp!) |
272 qed |
272 qed |
273 |
273 |
274 show "U + V <= E" |
274 show "U + V <= E" |
275 proof (intro subsetI, elim vs_sumE bexE) |
275 proof (intro subsetI, elim vs_sumE bexE) |
276 fix x u v assume "u : U" "v : V" "x = u + v" |
276 fix x u v assume "u \<in> U" "v \<in> V" "x = u + v" |
277 show "x:E" by (simp!) |
277 show "x \<in> E" by (simp!) |
278 qed |
278 qed |
279 |
279 |
280 show "ALL x: U + V. ALL y: U + V. x + y : U + V" |
280 show "\<forall>x \<in> U + V. \<forall>y \<in> U + V. x + y \<in> U + V" |
281 proof (intro ballI) |
281 proof (intro ballI) |
282 fix x y assume "x : U + V" "y : U + V" |
282 fix x y assume "x \<in> U + V" "y \<in> U + V" |
283 thus "x + y : U + V" |
283 thus "x + y \<in> U + V" |
284 proof (elim vs_sumE bexE, intro vs_sumI) |
284 proof (elim vs_sumE bexE, intro vs_sumI) |
285 fix ux vx uy vy |
285 fix ux vx uy vy |
286 assume "ux : U" "vx : V" "x = ux + vx" |
286 assume "ux \<in> U" "vx \<in> V" "x = ux + vx" |
287 and "uy : U" "vy : V" "y = uy + vy" |
287 and "uy \<in> U" "vy \<in> V" "y = uy + vy" |
288 show "x + y = (ux + uy) + (vx + vy)" by (simp!) |
288 show "x + y = (ux + uy) + (vx + vy)" by (simp!) |
289 qed (simp!)+ |
289 qed (simp!)+ |
290 qed |
290 qed |
291 |
291 |
292 show "ALL x : U + V. ALL a. a (*) x : U + V" |
292 show "\<forall>x \<in> U + V. \<forall>a. a \<cdot> x \<in> U + V" |
293 proof (intro ballI allI) |
293 proof (intro ballI allI) |
294 fix x a assume "x : U + V" |
294 fix x a assume "x \<in> U + V" |
295 thus "a (*) x : U + V" |
295 thus "a \<cdot> x \<in> U + V" |
296 proof (elim vs_sumE bexE, intro vs_sumI) |
296 proof (elim vs_sumE bexE, intro vs_sumI) |
297 fix a x u v assume "u : U" "v : V" "x = u + v" |
297 fix a x u v assume "u \<in> U" "v \<in> V" "x = u + v" |
298 show "a (*) x = (a (*) u) + (a (*) v)" |
298 show "a \<cdot> x = (a \<cdot> u) + (a \<cdot> v)" |
299 by (simp! add: vs_add_mult_distrib1) |
299 by (simp! add: vs_add_mult_distrib1) |
300 qed (simp!)+ |
300 qed (simp!)+ |
301 qed |
301 qed |
302 qed |
302 qed |
303 |
303 |
321 $x$ of the direct sum of $U$ and $V$ the decomposition in |
321 $x$ of the direct sum of $U$ and $V$ the decomposition in |
322 $x = u + v$ with $u \in U$ and $v \in V$ is unique.*} |
322 $x = u + v$ with $u \in U$ and $v \in V$ is unique.*} |
323 |
323 |
324 lemma decomp: |
324 lemma decomp: |
325 "[| is_vectorspace E; is_subspace U E; is_subspace V E; |
325 "[| is_vectorspace E; is_subspace U E; is_subspace V E; |
326 U Int V = {00}; u1:U; u2:U; v1:V; v2:V; u1 + v1 = u2 + v2 |] |
326 U \<inter> V = {0}; u1 \<in> U; u2 \<in> U; v1 \<in> V; v2 \<in> V; u1 + v1 = u2 + v2 |] |
327 ==> u1 = u2 & v1 = v2" |
327 ==> u1 = u2 \<and> v1 = v2" |
328 proof |
328 proof |
329 assume "is_vectorspace E" "is_subspace U E" "is_subspace V E" |
329 assume "is_vectorspace E" "is_subspace U E" "is_subspace V E" |
330 "U Int V = {00}" "u1:U" "u2:U" "v1:V" "v2:V" |
330 "U \<inter> V = {0}" "u1 \<in> U" "u2 \<in> U" "v1 \<in> V" "v2 \<in> V" |
331 "u1 + v1 = u2 + v2" |
331 "u1 + v1 = u2 + v2" |
332 have eq: "u1 - u2 = v2 - v1" by (simp! add: vs_add_diff_swap) |
332 have eq: "u1 - u2 = v2 - v1" by (simp! add: vs_add_diff_swap) |
333 have u: "u1 - u2 : U" by (simp!) |
333 have u: "u1 - u2 \<in> U" by (simp!) |
334 with eq have v': "v2 - v1 : U" by simp |
334 with eq have v': "v2 - v1 \<in> U" by simp |
335 have v: "v2 - v1 : V" by (simp!) |
335 have v: "v2 - v1 \<in> V" by (simp!) |
336 with eq have u': "u1 - u2 : V" by simp |
336 with eq have u': "u1 - u2 \<in> V" by simp |
337 |
337 |
338 show "u1 = u2" |
338 show "u1 = u2" |
339 proof (rule vs_add_minus_eq) |
339 proof (rule vs_add_minus_eq) |
340 show "u1 - u2 = 00" by (rule Int_singletonD [OF _ u u']) |
340 show "u1 - u2 = 0" by (rule Int_singletonD [OF _ u u']) |
341 show "u1 : E" .. |
341 show "u1 \<in> E" .. |
342 show "u2 : E" .. |
342 show "u2 \<in> E" .. |
343 qed |
343 qed |
344 |
344 |
345 show "v1 = v2" |
345 show "v1 = v2" |
346 proof (rule vs_add_minus_eq [RS sym]) |
346 proof (rule vs_add_minus_eq [RS sym]) |
347 show "v2 - v1 = 00" by (rule Int_singletonD [OF _ v' v]) |
347 show "v2 - v1 = 0" by (rule Int_singletonD [OF _ v' v]) |
348 show "v1 : E" .. |
348 show "v1 \<in> E" .. |
349 show "v2 : E" .. |
349 show "v2 \<in> E" .. |
350 qed |
350 qed |
351 qed |
351 qed |
352 |
352 |
353 text {* An application of the previous lemma will be used in the proof |
353 text {* An application of the previous lemma will be used in the proof |
354 of the Hahn-Banach Theorem (see page \pageref{decomp-H0-use}): for any |
354 of the Hahn-Banach Theorem (see page \pageref{decomp-H-use}): for any |
355 element $y + a \mult x_0$ of the direct sum of a vectorspace $H$ and |
355 element $y + a \mult x_0$ of the direct sum of a vectorspace $H$ and |
356 the linear closure of $x_0$ the components $y \in H$ and $a$ are |
356 the linear closure of $x_0$ the components $y \in H$ and $a$ are |
357 uniquely determined. *} |
357 uniquely determined. *} |
358 |
358 |
359 lemma decomp_H0: |
359 lemma decomp_H': |
360 "[| is_vectorspace E; is_subspace H E; y1 : H; y2 : H; |
360 "[| is_vectorspace E; is_subspace H E; y1 \<in> H; y2 \<in> H; |
361 x0 ~: H; x0 : E; x0 ~= 00; y1 + a1 (*) x0 = y2 + a2 (*) x0 |] |
361 x' \<notin> H; x' \<in> E; x' \<noteq> 0; y1 + a1 \<cdot> x' = y2 + a2 \<cdot> x' |] |
362 ==> y1 = y2 & a1 = a2" |
362 ==> y1 = y2 \<and> a1 = a2" |
363 proof |
363 proof |
364 assume "is_vectorspace E" and h: "is_subspace H E" |
364 assume "is_vectorspace E" and h: "is_subspace H E" |
365 and "y1 : H" "y2 : H" "x0 ~: H" "x0 : E" "x0 ~= 00" |
365 and "y1 \<in> H" "y2 \<in> H" "x' \<notin> H" "x' \<in> E" "x' \<noteq> 0" |
366 "y1 + a1 (*) x0 = y2 + a2 (*) x0" |
366 "y1 + a1 \<cdot> x' = y2 + a2 \<cdot> x'" |
367 |
367 |
368 have c: "y1 = y2 & a1 (*) x0 = a2 (*) x0" |
368 have c: "y1 = y2 \<and> a1 \<cdot> x' = a2 \<cdot> x'" |
369 proof (rule decomp) |
369 proof (rule decomp) |
370 show "a1 (*) x0 : lin x0" .. |
370 show "a1 \<cdot> x' \<in> lin x'" .. |
371 show "a2 (*) x0 : lin x0" .. |
371 show "a2 \<cdot> x' \<in> lin x'" .. |
372 show "H Int (lin x0) = {00}" |
372 show "H \<inter> (lin x') = {0}" |
373 proof |
373 proof |
374 show "H Int lin x0 <= {00}" |
374 show "H \<inter> lin x' <= {0}" |
375 proof (intro subsetI, elim IntE, rule singleton_iff[RS iffD2]) |
375 proof (intro subsetI, elim IntE, rule singleton_iff[RS iffD2]) |
376 fix x assume "x:H" "x : lin x0" |
376 fix x assume "x \<in> H" "x \<in> lin x'" |
377 thus "x = 00" |
377 thus "x = 0" |
378 proof (unfold lin_def, elim CollectE exE conjE) |
378 proof (unfold lin_def, elim CollectE exE conjE) |
379 fix a assume "x = a (*) x0" |
379 fix a assume "x = a \<cdot> x'" |
380 show ?thesis |
380 show ?thesis |
381 proof cases |
381 proof cases |
382 assume "a = (#0::real)" show ?thesis by (simp!) |
382 assume "a = (#0::real)" show ?thesis by (simp!) |
383 next |
383 next |
384 assume "a ~= (#0::real)" |
384 assume "a \<noteq> (#0::real)" |
385 from h have "rinv a (*) a (*) x0 : H" |
385 from h have "rinv a \<cdot> a \<cdot> x' \<in> H" |
386 by (rule subspace_mult_closed) (simp!) |
386 by (rule subspace_mult_closed) (simp!) |
387 also have "rinv a (*) a (*) x0 = x0" by (simp!) |
387 also have "rinv a \<cdot> a \<cdot> x' = x'" by (simp!) |
388 finally have "x0 : H" . |
388 finally have "x' \<in> H" . |
389 thus ?thesis by contradiction |
389 thus ?thesis by contradiction |
390 qed |
390 qed |
391 qed |
391 qed |
392 qed |
392 qed |
393 show "{00} <= H Int lin x0" |
393 show "{0} <= H \<inter> lin x'" |
394 proof - |
394 proof - |
395 have "00: H Int lin x0" |
395 have "0 \<in> H \<inter> lin x'" |
396 proof (rule IntI) |
396 proof (rule IntI) |
397 show "00:H" .. |
397 show "0 \<in> H" .. |
398 from lin_vs show "00 : lin x0" .. |
398 from lin_vs show "0 \<in> lin x'" .. |
399 qed |
399 qed |
400 thus ?thesis by simp |
400 thus ?thesis by simp |
401 qed |
401 qed |
402 qed |
402 qed |
403 show "is_subspace (lin x0) E" .. |
403 show "is_subspace (lin x') E" .. |
404 qed |
404 qed |
405 |
405 |
406 from c show "y1 = y2" by simp |
406 from c show "y1 = y2" by simp |
407 |
407 |
408 show "a1 = a2" |
408 show "a1 = a2" |
409 proof (rule vs_mult_right_cancel [RS iffD1]) |
409 proof (rule vs_mult_right_cancel [RS iffD1]) |
410 from c show "a1 (*) x0 = a2 (*) x0" by simp |
410 from c show "a1 \<cdot> x' = a2 \<cdot> x'" by simp |
411 qed |
411 qed |
412 qed |
412 qed |
413 |
413 |
414 text {* Since for any element $y + a \mult x_0$ of the direct sum |
414 text {* Since for any element $y + a \mult x'$ of the direct sum |
415 of a vectorspace $H$ and the linear closure of $x_0$ the components |
415 of a vectorspace $H$ and the linear closure of $x'$ the components |
416 $y\in H$ and $a$ are unique, it follows from $y\in H$ that |
416 $y\in H$ and $a$ are unique, it follows from $y\in H$ that |
417 $a = 0$.*} |
417 $a = 0$.*} |
418 |
418 |
419 lemma decomp_H0_H: |
419 lemma decomp_H'_H: |
420 "[| is_vectorspace E; is_subspace H E; t:H; x0 ~: H; x0:E; |
420 "[| is_vectorspace E; is_subspace H E; t \<in> H; x' \<notin> H; x' \<in> E; |
421 x0 ~= 00 |] |
421 x' \<noteq> 0 |] |
422 ==> (SOME (y, a). t = y + a (*) x0 & y : H) = (t, (#0::real))" |
422 ==> (SOME (y, a). t = y + a \<cdot> x' \<and> y \<in> H) = (t, (#0::real))" |
423 proof (rule, unfold split_tupled_all) |
423 proof (rule, unfold split_tupled_all) |
424 assume "is_vectorspace E" "is_subspace H E" "t:H" "x0 ~: H" "x0:E" |
424 assume "is_vectorspace E" "is_subspace H E" "t \<in> H" "x' \<notin> H" "x' \<in> E" |
425 "x0 ~= 00" |
425 "x' \<noteq> 0" |
426 have h: "is_vectorspace H" .. |
426 have h: "is_vectorspace H" .. |
427 fix y a presume t1: "t = y + a (*) x0" and "y:H" |
427 fix y a presume t1: "t = y + a \<cdot> x'" and "y \<in> H" |
428 have "y = t & a = (#0::real)" |
428 have "y = t \<and> a = (#0::real)" |
429 by (rule decomp_H0) (assumption | (simp!))+ |
429 by (rule decomp_H') (assumption | (simp!))+ |
430 thus "(y, a) = (t, (#0::real))" by (simp!) |
430 thus "(y, a) = (t, (#0::real))" by (simp!) |
431 qed (simp!)+ |
431 qed (simp!)+ |
432 |
432 |
433 text {* The components $y\in H$ and $a$ in $y \plus a \mult x_0$ |
433 text {* The components $y\in H$ and $a$ in $y \plus a \mult x'$ |
434 are unique, so the function $h_0$ defined by |
434 are unique, so the function $h'$ defined by |
435 $h_0 (y \plus a \mult x_0) = h y + a \cdot \xi$ is definite. *} |
435 $h' (y \plus a \mult x') = h y + a \cdot \xi$ is definite. *} |
436 |
436 |
437 lemma h0_definite: |
437 lemma h'_definite: |
438 "[| h0 == (\\<lambda>x. let (y, a) = SOME (y, a). (x = y + a (*) x0 & y:H) |
438 "[| h' == (\<lambda>x. let (y, a) = SOME (y, a). (x = y + a \<cdot> x' \<and> y \<in> H) |
439 in (h y) + a * xi); |
439 in (h y) + a * xi); |
440 x = y + a (*) x0; is_vectorspace E; is_subspace H E; |
440 x = y + a \<cdot> x'; is_vectorspace E; is_subspace H E; |
441 y:H; x0 ~: H; x0:E; x0 ~= 00 |] |
441 y \<in> H; x' \<notin> H; x' \<in> E; x' \<noteq> 0 |] |
442 ==> h0 x = h y + a * xi" |
442 ==> h' x = h y + a * xi" |
443 proof - |
443 proof - |
444 assume |
444 assume |
445 "h0 == (\\<lambda>x. let (y, a) = SOME (y, a). (x = y + a (*) x0 & y:H) |
445 "h' == (\<lambda>x. let (y, a) = SOME (y, a). (x = y + a \<cdot> x' \<and> y \<in> H) |
446 in (h y) + a * xi)" |
446 in (h y) + a * xi)" |
447 "x = y + a (*) x0" "is_vectorspace E" "is_subspace H E" |
447 "x = y + a \<cdot> x'" "is_vectorspace E" "is_subspace H E" |
448 "y:H" "x0 ~: H" "x0:E" "x0 ~= 00" |
448 "y \<in> H" "x' \<notin> H" "x' \<in> E" "x' \<noteq> 0" |
449 have "x : H + (lin x0)" |
449 have "x \<in> H + (lin x')" |
450 by (simp! add: vs_sum_def lin_def) force+ |
450 by (simp! add: vs_sum_def lin_def) force+ |
451 have "EX! xa. ((\\<lambda>(y, a). x = y + a (*) x0 & y:H) xa)" |
451 have "\<exists>! xa. ((\<lambda>(y, a). x = y + a \<cdot> x' \<and> y \<in> H) xa)" |
452 proof |
452 proof |
453 show "EX xa. ((\\<lambda>(y, a). x = y + a (*) x0 & y:H) xa)" |
453 show "\<exists>xa. ((\<lambda>(y, a). x = y + a \<cdot> x' \<and> y \<in> H) xa)" |
454 by (force!) |
454 by (force!) |
455 next |
455 next |
456 fix xa ya |
456 fix xa ya |
457 assume "(\\<lambda>(y,a). x = y + a (*) x0 & y : H) xa" |
457 assume "(\<lambda>(y,a). x = y + a \<cdot> x' \<and> y \<in> H) xa" |
458 "(\\<lambda>(y,a). x = y + a (*) x0 & y : H) ya" |
458 "(\<lambda>(y,a). x = y + a \<cdot> x' \<and> y \<in> H) ya" |
459 show "xa = ya" |
459 show "xa = ya" |
460 proof - |
460 proof - |
461 show "fst xa = fst ya & snd xa = snd ya ==> xa = ya" |
461 show "fst xa = fst ya \<and> snd xa = snd ya ==> xa = ya" |
462 by (simp add: Pair_fst_snd_eq) |
462 by (simp add: Pair_fst_snd_eq) |
463 have x: "x = fst xa + snd xa (*) x0 & fst xa : H" |
463 have x: "x = fst xa + snd xa \<cdot> x' \<and> fst xa \<in> H" |
464 by (force!) |
464 by (force!) |
465 have y: "x = fst ya + snd ya (*) x0 & fst ya : H" |
465 have y: "x = fst ya + snd ya \<cdot> x' \<and> fst ya \<in> H" |
466 by (force!) |
466 by (force!) |
467 from x y show "fst xa = fst ya & snd xa = snd ya" |
467 from x y show "fst xa = fst ya \<and> snd xa = snd ya" |
468 by (elim conjE) (rule decomp_H0, (simp!)+) |
468 by (elim conjE) (rule decomp_H', (simp!)+) |
469 qed |
469 qed |
470 qed |
470 qed |
471 hence eq: "(SOME (y, a). x = y + a (*) x0 & y:H) = (y, a)" |
471 hence eq: "(SOME (y, a). x = y + a \<cdot> x' \<and> y \<in> H) = (y, a)" |
472 by (rule select1_equality) (force!) |
472 by (rule select1_equality) (force!) |
473 thus "h0 x = h y + a * xi" by (simp! add: Let_def) |
473 thus "h' x = h y + a * xi" by (simp! add: Let_def) |
474 qed |
474 qed |
475 |
475 |
476 end |
476 end |