--- a/src/HOL/Analysis/Analysis.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Analysis.thy Thu Jan 17 16:08:41 2019 +0000
@@ -1,5 +1,20 @@
theory Analysis
-imports
+ imports
+ (* Linear Algebra *)
+ Convex
+ Determinants
+ (* Topology *)
+ Connected
+ (* Functional Analysis *)
+ Elementary_Normed_Spaces
+ Norm_Arith
+ (* Vector Analysis *)
+ Convex_Euclidean_Space
+ (* Measure and Integration Theory *)
+ Ball_Volume
+ Integral_Test
+ Improper_Integral
+ (* Unsorted *)
Lebesgue_Integral_Substitution
Improper_Integral
Embed_Measure
--- a/src/HOL/Analysis/Cartesian_Space.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Cartesian_Space.thy Thu Jan 17 16:08:41 2019 +0000
@@ -930,4 +930,492 @@
lemma%unimportant const_vector_cart:"((\<chi> i. d)::real^'n) = (\<Sum>i\<in>Basis. d *\<^sub>R i)"
by (rule vector_cart)
+subsection%unimportant \<open>Explicit formulas for low dimensions\<close>
+
+lemma%unimportant prod_neutral_const: "prod f {(1::nat)..1} = f 1"
+ by simp
+
+lemma%unimportant prod_2: "prod f {(1::nat)..2} = f 1 * f 2"
+ by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute)
+
+lemma%unimportant prod_3: "prod f {(1::nat)..3} = f 1 * f 2 * f 3"
+ by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute)
+
+
+subsection%important \<open>Orthogonality of a matrix\<close>
+
+definition%important "orthogonal_matrix (Q::'a::semiring_1^'n^'n) \<longleftrightarrow>
+ transpose Q ** Q = mat 1 \<and> Q ** transpose Q = mat 1"
+
+lemma%unimportant orthogonal_matrix: "orthogonal_matrix (Q:: real ^'n^'n) \<longleftrightarrow> transpose Q ** Q = mat 1"
+ by (metis matrix_left_right_inverse orthogonal_matrix_def)
+
+lemma%unimportant orthogonal_matrix_id: "orthogonal_matrix (mat 1 :: _^'n^'n)"
+ by (simp add: orthogonal_matrix_def)
+
+lemma%unimportant orthogonal_matrix_mul:
+ fixes A :: "real ^'n^'n"
+ assumes "orthogonal_matrix A" "orthogonal_matrix B"
+ shows "orthogonal_matrix(A ** B)"
+ using assms
+ by (simp add: orthogonal_matrix matrix_transpose_mul matrix_left_right_inverse matrix_mul_assoc)
+
+lemma%important orthogonal_transformation_matrix:
+ fixes f:: "real^'n \<Rightarrow> real^'n"
+ shows "orthogonal_transformation f \<longleftrightarrow> linear f \<and> orthogonal_matrix(matrix f)"
+ (is "?lhs \<longleftrightarrow> ?rhs")
+proof%unimportant -
+ let ?mf = "matrix f"
+ let ?ot = "orthogonal_transformation f"
+ let ?U = "UNIV :: 'n set"
+ have fU: "finite ?U" by simp
+ let ?m1 = "mat 1 :: real ^'n^'n"
+ {
+ assume ot: ?ot
+ from ot have lf: "Vector_Spaces.linear (*s) (*s) f" and fd: "\<And>v w. f v \<bullet> f w = v \<bullet> w"
+ unfolding orthogonal_transformation_def orthogonal_matrix linear_def scalar_mult_eq_scaleR
+ by blast+
+ {
+ fix i j
+ let ?A = "transpose ?mf ** ?mf"
+ have th0: "\<And>b (x::'a::comm_ring_1). (if b then 1 else 0)*x = (if b then x else 0)"
+ "\<And>b (x::'a::comm_ring_1). x*(if b then 1 else 0) = (if b then x else 0)"
+ by simp_all
+ from fd[of "axis i 1" "axis j 1",
+ simplified matrix_works[OF lf, symmetric] dot_matrix_vector_mul]
+ have "?A$i$j = ?m1 $ i $ j"
+ by (simp add: inner_vec_def matrix_matrix_mult_def columnvector_def rowvector_def
+ th0 sum.delta[OF fU] mat_def axis_def)
+ }
+ then have "orthogonal_matrix ?mf"
+ unfolding orthogonal_matrix
+ by vector
+ with lf have ?rhs
+ unfolding linear_def scalar_mult_eq_scaleR
+ by blast
+ }
+ moreover
+ {
+ assume lf: "Vector_Spaces.linear (*s) (*s) f" and om: "orthogonal_matrix ?mf"
+ from lf om have ?lhs
+ unfolding orthogonal_matrix_def norm_eq orthogonal_transformation
+ apply (simp only: matrix_works[OF lf, symmetric] dot_matrix_vector_mul)
+ apply (simp add: dot_matrix_product linear_def scalar_mult_eq_scaleR)
+ done
+ }
+ ultimately show ?thesis
+ by (auto simp: linear_def scalar_mult_eq_scaleR)
+qed
+
+
+subsection%important \<open> We can find an orthogonal matrix taking any unit vector to any other\<close>
+
+lemma%unimportant orthogonal_matrix_transpose [simp]:
+ "orthogonal_matrix(transpose A) \<longleftrightarrow> orthogonal_matrix A"
+ by (auto simp: orthogonal_matrix_def)
+
+lemma%unimportant orthogonal_matrix_orthonormal_columns:
+ fixes A :: "real^'n^'n"
+ shows "orthogonal_matrix A \<longleftrightarrow>
+ (\<forall>i. norm(column i A) = 1) \<and>
+ (\<forall>i j. i \<noteq> j \<longrightarrow> orthogonal (column i A) (column j A))"
+ by (auto simp: orthogonal_matrix matrix_mult_transpose_dot_column vec_eq_iff mat_def norm_eq_1 orthogonal_def)
+
+lemma%unimportant orthogonal_matrix_orthonormal_rows:
+ fixes A :: "real^'n^'n"
+ shows "orthogonal_matrix A \<longleftrightarrow>
+ (\<forall>i. norm(row i A) = 1) \<and>
+ (\<forall>i j. i \<noteq> j \<longrightarrow> orthogonal (row i A) (row j A))"
+ using orthogonal_matrix_orthonormal_columns [of "transpose A"] by simp
+
+lemma%important orthogonal_matrix_exists_basis:
+ fixes a :: "real^'n"
+ assumes "norm a = 1"
+ obtains A where "orthogonal_matrix A" "A *v (axis k 1) = a"
+proof%unimportant -
+ obtain S where "a \<in> S" "pairwise orthogonal S" and noS: "\<And>x. x \<in> S \<Longrightarrow> norm x = 1"
+ and "independent S" "card S = CARD('n)" "span S = UNIV"
+ using vector_in_orthonormal_basis assms by force
+ then obtain f0 where "bij_betw f0 (UNIV::'n set) S"
+ by (metis finite_class.finite_UNIV finite_same_card_bij finiteI_independent)
+ then obtain f where f: "bij_betw f (UNIV::'n set) S" and a: "a = f k"
+ using bij_swap_iff [of k "inv f0 a" f0]
+ by (metis UNIV_I \<open>a \<in> S\<close> bij_betw_inv_into_right bij_betw_swap_iff swap_apply(1))
+ show thesis
+ proof
+ have [simp]: "\<And>i. norm (f i) = 1"
+ using bij_betwE [OF \<open>bij_betw f UNIV S\<close>] by (blast intro: noS)
+ have [simp]: "\<And>i j. i \<noteq> j \<Longrightarrow> orthogonal (f i) (f j)"
+ using \<open>pairwise orthogonal S\<close> \<open>bij_betw f UNIV S\<close>
+ by (auto simp: pairwise_def bij_betw_def inj_on_def)
+ show "orthogonal_matrix (\<chi> i j. f j $ i)"
+ by (simp add: orthogonal_matrix_orthonormal_columns column_def)
+ show "(\<chi> i j. f j $ i) *v axis k 1 = a"
+ by (simp add: matrix_vector_mult_def axis_def a if_distrib cong: if_cong)
+ qed
+qed
+
+lemma%unimportant orthogonal_transformation_exists_1:
+ fixes a b :: "real^'n"
+ assumes "norm a = 1" "norm b = 1"
+ obtains f where "orthogonal_transformation f" "f a = b"
+proof%unimportant -
+ obtain k::'n where True
+ by simp
+ obtain A B where AB: "orthogonal_matrix A" "orthogonal_matrix B" and eq: "A *v (axis k 1) = a" "B *v (axis k 1) = b"
+ using orthogonal_matrix_exists_basis assms by metis
+ let ?f = "\<lambda>x. (B ** transpose A) *v x"
+ show thesis
+ proof
+ show "orthogonal_transformation ?f"
+ by (subst orthogonal_transformation_matrix)
+ (auto simp: AB orthogonal_matrix_mul)
+ next
+ show "?f a = b"
+ using \<open>orthogonal_matrix A\<close> unfolding orthogonal_matrix_def
+ by (metis eq matrix_mul_rid matrix_vector_mul_assoc)
+ qed
+qed
+
+lemma%important orthogonal_transformation_exists:
+ fixes a b :: "real^'n"
+ assumes "norm a = norm b"
+ obtains f where "orthogonal_transformation f" "f a = b"
+proof%unimportant (cases "a = 0 \<or> b = 0")
+ case True
+ with assms show ?thesis
+ using that by force
+next
+ case False
+ then obtain f where f: "orthogonal_transformation f" and eq: "f (a /\<^sub>R norm a) = (b /\<^sub>R norm b)"
+ by (auto intro: orthogonal_transformation_exists_1 [of "a /\<^sub>R norm a" "b /\<^sub>R norm b"])
+ show ?thesis
+ proof
+ interpret linear f
+ using f by (simp add: orthogonal_transformation_linear)
+ have "f a /\<^sub>R norm a = f (a /\<^sub>R norm a)"
+ by (simp add: scale)
+ also have "\<dots> = b /\<^sub>R norm a"
+ by (simp add: eq assms [symmetric])
+ finally show "f a = b"
+ using False by auto
+ qed (use f in auto)
+qed
+
+
+subsection%important \<open>Linearity of scaling, and hence isometry, that preserves origin\<close>
+
+lemma%important scaling_linear:
+ fixes f :: "'a::real_inner \<Rightarrow> 'a::real_inner"
+ assumes f0: "f 0 = 0"
+ and fd: "\<forall>x y. dist (f x) (f y) = c * dist x y"
+ shows "linear f"
+proof%unimportant -
+ {
+ fix v w
+ have "norm (f x) = c * norm x" for x
+ by (metis dist_0_norm f0 fd)
+ then have "f v \<bullet> f w = c\<^sup>2 * (v \<bullet> w)"
+ unfolding dot_norm_neg dist_norm[symmetric]
+ by (simp add: fd power2_eq_square field_simps)
+ }
+ then show ?thesis
+ unfolding linear_iff vector_eq[where 'a="'a"] scalar_mult_eq_scaleR
+ by (simp add: inner_add field_simps)
+qed
+
+lemma%unimportant isometry_linear:
+ "f (0::'a::real_inner) = (0::'a) \<Longrightarrow> \<forall>x y. dist(f x) (f y) = dist x y \<Longrightarrow> linear f"
+ by (rule scaling_linear[where c=1]) simp_all
+
+text \<open>Hence another formulation of orthogonal transformation\<close>
+
+lemma%important orthogonal_transformation_isometry:
+ "orthogonal_transformation f \<longleftrightarrow> f(0::'a::real_inner) = (0::'a) \<and> (\<forall>x y. dist(f x) (f y) = dist x y)"
+ unfolding orthogonal_transformation
+ apply (auto simp: linear_0 isometry_linear)
+ apply (metis (no_types, hide_lams) dist_norm linear_diff)
+ by (metis dist_0_norm)
+
+
+subsection%important \<open>Can extend an isometry from unit sphere\<close>
+
+lemma%important isometry_sphere_extend:
+ fixes f:: "'a::real_inner \<Rightarrow> 'a"
+ assumes f1: "\<And>x. norm x = 1 \<Longrightarrow> norm (f x) = 1"
+ and fd1: "\<And>x y. \<lbrakk>norm x = 1; norm y = 1\<rbrakk> \<Longrightarrow> dist (f x) (f y) = dist x y"
+ shows "\<exists>g. orthogonal_transformation g \<and> (\<forall>x. norm x = 1 \<longrightarrow> g x = f x)"
+proof%unimportant -
+ {
+ fix x y x' y' u v u' v' :: "'a"
+ assume H: "x = norm x *\<^sub>R u" "y = norm y *\<^sub>R v"
+ "x' = norm x *\<^sub>R u'" "y' = norm y *\<^sub>R v'"
+ and J: "norm u = 1" "norm u' = 1" "norm v = 1" "norm v' = 1" "norm(u' - v') = norm(u - v)"
+ then have *: "u \<bullet> v = u' \<bullet> v' + v' \<bullet> u' - v \<bullet> u "
+ by (simp add: norm_eq norm_eq_1 inner_add inner_diff)
+ have "norm (norm x *\<^sub>R u' - norm y *\<^sub>R v') = norm (norm x *\<^sub>R u - norm y *\<^sub>R v)"
+ using J by (simp add: norm_eq norm_eq_1 inner_diff * field_simps)
+ then have "norm(x' - y') = norm(x - y)"
+ using H by metis
+ }
+ note norm_eq = this
+ let ?g = "\<lambda>x. if x = 0 then 0 else norm x *\<^sub>R f (x /\<^sub>R norm x)"
+ have thfg: "?g x = f x" if "norm x = 1" for x
+ using that by auto
+ have thd: "dist (?g x) (?g y) = dist x y" for x y
+ proof (cases "x=0 \<or> y=0")
+ case False
+ show "dist (?g x) (?g y) = dist x y"
+ unfolding dist_norm
+ proof (rule norm_eq)
+ show "x = norm x *\<^sub>R (x /\<^sub>R norm x)" "y = norm y *\<^sub>R (y /\<^sub>R norm y)"
+ "norm (f (x /\<^sub>R norm x)) = 1" "norm (f (y /\<^sub>R norm y)) = 1"
+ using False f1 by auto
+ qed (use False in \<open>auto simp: field_simps intro: f1 fd1[unfolded dist_norm]\<close>)
+ qed (auto simp: f1)
+ show ?thesis
+ unfolding orthogonal_transformation_isometry
+ by (rule exI[where x= ?g]) (metis thfg thd)
+qed
+
+subsection%important\<open>Induction on matrix row operations\<close>
+
+lemma%unimportant induct_matrix_row_operations:
+ fixes P :: "real^'n^'n \<Rightarrow> bool"
+ assumes zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
+ and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
+ and swap_cols: "\<And>A m n. \<lbrakk>P A; m \<noteq> n\<rbrakk> \<Longrightarrow> P(\<chi> i j. A $ i $ Fun.swap m n id j)"
+ and row_op: "\<And>A m n c. \<lbrakk>P A; m \<noteq> n\<rbrakk>
+ \<Longrightarrow> P(\<chi> i. if i = m then row m A + c *\<^sub>R row n A else row i A)"
+ shows "P A"
+proof -
+ have "P A" if "(\<And>i j. \<lbrakk>j \<in> -K; i \<noteq> j\<rbrakk> \<Longrightarrow> A$i$j = 0)" for A K
+ proof -
+ have "finite K"
+ by simp
+ then show ?thesis using that
+ proof (induction arbitrary: A rule: finite_induct)
+ case empty
+ with diagonal show ?case
+ by simp
+ next
+ case (insert k K)
+ note insertK = insert
+ have "P A" if kk: "A$k$k \<noteq> 0"
+ and 0: "\<And>i j. \<lbrakk>j \<in> - insert k K; i \<noteq> j\<rbrakk> \<Longrightarrow> A$i$j = 0"
+ "\<And>i. \<lbrakk>i \<in> -L; i \<noteq> k\<rbrakk> \<Longrightarrow> A$i$k = 0" for A L
+ proof -
+ have "finite L"
+ by simp
+ then show ?thesis using 0 kk
+ proof (induction arbitrary: A rule: finite_induct)
+ case (empty B)
+ show ?case
+ proof (rule insertK)
+ fix i j
+ assume "i \<in> - K" "j \<noteq> i"
+ show "B $ j $ i = 0"
+ using \<open>j \<noteq> i\<close> \<open>i \<in> - K\<close> empty
+ by (metis ComplD ComplI Compl_eq_Diff_UNIV Diff_empty UNIV_I insert_iff)
+ qed
+ next
+ case (insert l L B)
+ show ?case
+ proof (cases "k = l")
+ case True
+ with insert show ?thesis
+ by auto
+ next
+ case False
+ let ?C = "\<chi> i. if i = l then row l B - (B $ l $ k / B $ k $ k) *\<^sub>R row k B else row i B"
+ have 1: "\<lbrakk>j \<in> - insert k K; i \<noteq> j\<rbrakk> \<Longrightarrow> ?C $ i $ j = 0" for j i
+ by (auto simp: insert.prems(1) row_def)
+ have 2: "?C $ i $ k = 0"
+ if "i \<in> - L" "i \<noteq> k" for i
+ proof (cases "i=l")
+ case True
+ with that insert.prems show ?thesis
+ by (simp add: row_def)
+ next
+ case False
+ with that show ?thesis
+ by (simp add: insert.prems(2) row_def)
+ qed
+ have 3: "?C $ k $ k \<noteq> 0"
+ by (auto simp: insert.prems row_def \<open>k \<noteq> l\<close>)
+ have PC: "P ?C"
+ using insert.IH [OF 1 2 3] by auto
+ have eqB: "(\<chi> i. if i = l then row l ?C + (B $ l $ k / B $ k $ k) *\<^sub>R row k ?C else row i ?C) = B"
+ using \<open>k \<noteq> l\<close> by (simp add: vec_eq_iff row_def)
+ show ?thesis
+ using row_op [OF PC, of l k, where c = "B$l$k / B$k$k"] eqB \<open>k \<noteq> l\<close>
+ by (simp add: cong: if_cong)
+ qed
+ qed
+ qed
+ then have nonzero_hyp: "P A"
+ if kk: "A$k$k \<noteq> 0" and zeroes: "\<And>i j. j \<in> - insert k K \<and> i\<noteq>j \<Longrightarrow> A$i$j = 0" for A
+ by (auto simp: intro!: kk zeroes)
+ show ?case
+ proof (cases "row k A = 0")
+ case True
+ with zero_row show ?thesis by auto
+ next
+ case False
+ then obtain l where l: "A$k$l \<noteq> 0"
+ by (auto simp: row_def zero_vec_def vec_eq_iff)
+ show ?thesis
+ proof (cases "k = l")
+ case True
+ with l nonzero_hyp insert.prems show ?thesis
+ by blast
+ next
+ case False
+ have *: "A $ i $ Fun.swap k l id j = 0" if "j \<noteq> k" "j \<notin> K" "i \<noteq> j" for i j
+ using False l insert.prems that
+ by (auto simp: swap_def insert split: if_split_asm)
+ have "P (\<chi> i j. (\<chi> i j. A $ i $ Fun.swap k l id j) $ i $ Fun.swap k l id j)"
+ by (rule swap_cols [OF nonzero_hyp False]) (auto simp: l *)
+ moreover
+ have "(\<chi> i j. (\<chi> i j. A $ i $ Fun.swap k l id j) $ i $ Fun.swap k l id j) = A"
+ by (vector Fun.swap_def)
+ ultimately show ?thesis
+ by simp
+ qed
+ qed
+ qed
+ qed
+ then show ?thesis
+ by blast
+qed
+
+lemma%unimportant induct_matrix_elementary:
+ fixes P :: "real^'n^'n \<Rightarrow> bool"
+ assumes mult: "\<And>A B. \<lbrakk>P A; P B\<rbrakk> \<Longrightarrow> P(A ** B)"
+ and zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
+ and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
+ and swap1: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. mat 1 $ i $ Fun.swap m n id j)"
+ and idplus: "\<And>m n c. m \<noteq> n \<Longrightarrow> P(\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j))"
+ shows "P A"
+proof -
+ have swap: "P (\<chi> i j. A $ i $ Fun.swap m n id j)" (is "P ?C")
+ if "P A" "m \<noteq> n" for A m n
+ proof -
+ have "A ** (\<chi> i j. mat 1 $ i $ Fun.swap m n id j) = ?C"
+ by (simp add: matrix_matrix_mult_def mat_def vec_eq_iff if_distrib sum.delta_remove)
+ then show ?thesis
+ using mult swap1 that by metis
+ qed
+ have row: "P (\<chi> i. if i = m then row m A + c *\<^sub>R row n A else row i A)" (is "P ?C")
+ if "P A" "m \<noteq> n" for A m n c
+ proof -
+ let ?B = "\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j)"
+ have "?B ** A = ?C"
+ using \<open>m \<noteq> n\<close> unfolding matrix_matrix_mult_def row_def of_bool_def
+ by (auto simp: vec_eq_iff if_distrib [of "\<lambda>x. x * y" for y] sum.remove cong: if_cong)
+ then show ?thesis
+ by (rule subst) (auto simp: that mult idplus)
+ qed
+ show ?thesis
+ by (rule induct_matrix_row_operations [OF zero_row diagonal swap row])
+qed
+
+lemma%unimportant induct_matrix_elementary_alt:
+ fixes P :: "real^'n^'n \<Rightarrow> bool"
+ assumes mult: "\<And>A B. \<lbrakk>P A; P B\<rbrakk> \<Longrightarrow> P(A ** B)"
+ and zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
+ and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
+ and swap1: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. mat 1 $ i $ Fun.swap m n id j)"
+ and idplus: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j))"
+ shows "P A"
+proof -
+ have *: "P (\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j))"
+ if "m \<noteq> n" for m n c
+ proof (cases "c = 0")
+ case True
+ with diagonal show ?thesis by auto
+ next
+ case False
+ then have eq: "(\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j)) =
+ (\<chi> i j. if i = j then (if j = n then inverse c else 1) else 0) **
+ (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)) **
+ (\<chi> i j. if i = j then if j = n then c else 1 else 0)"
+ using \<open>m \<noteq> n\<close>
+ apply (simp add: matrix_matrix_mult_def vec_eq_iff of_bool_def if_distrib [of "\<lambda>x. y * x" for y] cong: if_cong)
+ apply (simp add: if_if_eq_conj sum.neutral conj_commute cong: conj_cong)
+ done
+ show ?thesis
+ apply (subst eq)
+ apply (intro mult idplus that)
+ apply (auto intro: diagonal)
+ done
+ qed
+ show ?thesis
+ by (rule induct_matrix_elementary) (auto intro: assms *)
+qed
+
+lemma%unimportant matrix_vector_mult_matrix_matrix_mult_compose:
+ "(*v) (A ** B) = (*v) A \<circ> (*v) B"
+ by (auto simp: matrix_vector_mul_assoc)
+
+lemma%unimportant induct_linear_elementary:
+ fixes f :: "real^'n \<Rightarrow> real^'n"
+ assumes "linear f"
+ and comp: "\<And>f g. \<lbrakk>linear f; linear g; P f; P g\<rbrakk> \<Longrightarrow> P(f \<circ> g)"
+ and zeroes: "\<And>f i. \<lbrakk>linear f; \<And>x. (f x) $ i = 0\<rbrakk> \<Longrightarrow> P f"
+ and const: "\<And>c. P(\<lambda>x. \<chi> i. c i * x$i)"
+ and swap: "\<And>m n::'n. m \<noteq> n \<Longrightarrow> P(\<lambda>x. \<chi> i. x $ Fun.swap m n id i)"
+ and idplus: "\<And>m n::'n. m \<noteq> n \<Longrightarrow> P(\<lambda>x. \<chi> i. if i = m then x$m + x$n else x$i)"
+ shows "P f"
+proof -
+ have "P ((*v) A)" for A
+ proof (rule induct_matrix_elementary_alt)
+ fix A B
+ assume "P ((*v) A)" and "P ((*v) B)"
+ then show "P ((*v) (A ** B))"
+ by (auto simp add: matrix_vector_mult_matrix_matrix_mult_compose matrix_vector_mul_linear
+ intro!: comp)
+ next
+ fix A :: "real^'n^'n" and i
+ assume "row i A = 0"
+ show "P ((*v) A)"
+ using matrix_vector_mul_linear
+ by (rule zeroes[where i=i])
+ (metis \<open>row i A = 0\<close> inner_zero_left matrix_vector_mul_component row_def vec_lambda_eta)
+ next
+ fix A :: "real^'n^'n"
+ assume 0: "\<And>i j. i \<noteq> j \<Longrightarrow> A $ i $ j = 0"
+ have "A $ i $ i * x $ i = (\<Sum>j\<in>UNIV. A $ i $ j * x $ j)" for x and i :: "'n"
+ by (simp add: 0 comm_monoid_add_class.sum.remove [where x=i])
+ then have "(\<lambda>x. \<chi> i. A $ i $ i * x $ i) = ((*v) A)"
+ by (auto simp: 0 matrix_vector_mult_def)
+ then show "P ((*v) A)"
+ using const [of "\<lambda>i. A $ i $ i"] by simp
+ next
+ fix m n :: "'n"
+ assume "m \<noteq> n"
+ have eq: "(\<Sum>j\<in>UNIV. if i = Fun.swap m n id j then x $ j else 0) =
+ (\<Sum>j\<in>UNIV. if j = Fun.swap m n id i then x $ j else 0)"
+ for i and x :: "real^'n"
+ unfolding swap_def by (rule sum.cong) auto
+ have "(\<lambda>x::real^'n. \<chi> i. x $ Fun.swap m n id i) = ((*v) (\<chi> i j. if i = Fun.swap m n id j then 1 else 0))"
+ by (auto simp: mat_def matrix_vector_mult_def eq if_distrib [of "\<lambda>x. x * y" for y] cong: if_cong)
+ with swap [OF \<open>m \<noteq> n\<close>] show "P ((*v) (\<chi> i j. mat 1 $ i $ Fun.swap m n id j))"
+ by (simp add: mat_def matrix_vector_mult_def)
+ next
+ fix m n :: "'n"
+ assume "m \<noteq> n"
+ then have "x $ m + x $ n = (\<Sum>j\<in>UNIV. of_bool (j = n \<or> m = j) * x $ j)" for x :: "real^'n"
+ by (auto simp: of_bool_def if_distrib [of "\<lambda>x. x * y" for y] sum.remove cong: if_cong)
+ then have "(\<lambda>x::real^'n. \<chi> i. if i = m then x $ m + x $ n else x $ i) =
+ ((*v) (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)))"
+ unfolding matrix_vector_mult_def of_bool_def
+ by (auto simp: vec_eq_iff if_distrib [of "\<lambda>x. x * y" for y] cong: if_cong)
+ then show "P ((*v) (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)))"
+ using idplus [OF \<open>m \<noteq> n\<close>] by simp
+ qed
+ then show ?thesis
+ by (metis \<open>linear f\<close> matrix_vector_mul)
+qed
+
end
\ No newline at end of file
--- a/src/HOL/Analysis/Change_Of_Vars.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Change_Of_Vars.thy Thu Jan 17 16:08:41 2019 +0000
@@ -9,258 +9,51 @@
begin
-subsection%important\<open>Induction on matrix row operations\<close>
-(*FIX move first 3 lemmas of subsection to linear algebra, contain technical tools on matrix operations.
-Keep the rest of the subsection contents in this theory but rename the subsection, they refer
-to lebesgue measure
-*)
-lemma induct_matrix_row_operations:
- fixes P :: "real^'n^'n \<Rightarrow> bool"
- assumes zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
- and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
- and swap_cols: "\<And>A m n. \<lbrakk>P A; m \<noteq> n\<rbrakk> \<Longrightarrow> P(\<chi> i j. A $ i $ Fun.swap m n id j)"
- and row_op: "\<And>A m n c. \<lbrakk>P A; m \<noteq> n\<rbrakk>
- \<Longrightarrow> P(\<chi> i. if i = m then row m A + c *\<^sub>R row n A else row i A)"
- shows "P A"
-proof -
- have "P A" if "(\<And>i j. \<lbrakk>j \<in> -K; i \<noteq> j\<rbrakk> \<Longrightarrow> A$i$j = 0)" for A K
- proof -
- have "finite K"
- by simp
- then show ?thesis using that
- proof (induction arbitrary: A rule: finite_induct)
- case empty
- with diagonal show ?case
- by simp
- next
- case (insert k K)
- note insertK = insert
- have "P A" if kk: "A$k$k \<noteq> 0"
- and 0: "\<And>i j. \<lbrakk>j \<in> - insert k K; i \<noteq> j\<rbrakk> \<Longrightarrow> A$i$j = 0"
- "\<And>i. \<lbrakk>i \<in> -L; i \<noteq> k\<rbrakk> \<Longrightarrow> A$i$k = 0" for A L
- proof -
- have "finite L"
- by simp
- then show ?thesis using 0 kk
- proof (induction arbitrary: A rule: finite_induct)
- case (empty B)
- show ?case
- proof (rule insertK)
- fix i j
- assume "i \<in> - K" "j \<noteq> i"
- show "B $ j $ i = 0"
- using \<open>j \<noteq> i\<close> \<open>i \<in> - K\<close> empty
- by (metis ComplD ComplI Compl_eq_Diff_UNIV Diff_empty UNIV_I insert_iff)
- qed
- next
- case (insert l L B)
- show ?case
- proof (cases "k = l")
- case True
- with insert show ?thesis
- by auto
- next
- case False
- let ?C = "\<chi> i. if i = l then row l B - (B $ l $ k / B $ k $ k) *\<^sub>R row k B else row i B"
- have 1: "\<lbrakk>j \<in> - insert k K; i \<noteq> j\<rbrakk> \<Longrightarrow> ?C $ i $ j = 0" for j i
- by (auto simp: insert.prems(1) row_def)
- have 2: "?C $ i $ k = 0"
- if "i \<in> - L" "i \<noteq> k" for i
- proof (cases "i=l")
- case True
- with that insert.prems show ?thesis
- by (simp add: row_def)
- next
- case False
- with that show ?thesis
- by (simp add: insert.prems(2) row_def)
- qed
- have 3: "?C $ k $ k \<noteq> 0"
- by (auto simp: insert.prems row_def \<open>k \<noteq> l\<close>)
- have PC: "P ?C"
- using insert.IH [OF 1 2 3] by auto
- have eqB: "(\<chi> i. if i = l then row l ?C + (B $ l $ k / B $ k $ k) *\<^sub>R row k ?C else row i ?C) = B"
- using \<open>k \<noteq> l\<close> by (simp add: vec_eq_iff row_def)
- show ?thesis
- using row_op [OF PC, of l k, where c = "B$l$k / B$k$k"] eqB \<open>k \<noteq> l\<close>
- by (simp add: cong: if_cong)
- qed
- qed
- qed
- then have nonzero_hyp: "P A"
- if kk: "A$k$k \<noteq> 0" and zeroes: "\<And>i j. j \<in> - insert k K \<and> i\<noteq>j \<Longrightarrow> A$i$j = 0" for A
- by (auto simp: intro!: kk zeroes)
- show ?case
- proof (cases "row k A = 0")
- case True
- with zero_row show ?thesis by auto
- next
- case False
- then obtain l where l: "A$k$l \<noteq> 0"
- by (auto simp: row_def zero_vec_def vec_eq_iff)
- show ?thesis
- proof (cases "k = l")
- case True
- with l nonzero_hyp insert.prems show ?thesis
- by blast
- next
- case False
- have *: "A $ i $ Fun.swap k l id j = 0" if "j \<noteq> k" "j \<notin> K" "i \<noteq> j" for i j
- using False l insert.prems that
- by (auto simp: swap_def insert split: if_split_asm)
- have "P (\<chi> i j. (\<chi> i j. A $ i $ Fun.swap k l id j) $ i $ Fun.swap k l id j)"
- by (rule swap_cols [OF nonzero_hyp False]) (auto simp: l *)
- moreover
- have "(\<chi> i j. (\<chi> i j. A $ i $ Fun.swap k l id j) $ i $ Fun.swap k l id j) = A"
- by (metis (no_types, lifting) id_apply o_apply swap_id_idempotent vec_lambda_unique vec_lambda_unique)
- ultimately show ?thesis
- by simp
- qed
- qed
- qed
- qed
- then show ?thesis
- by blast
+subsection%unimportant \<open>Orthogonal Transformation of Balls\<close>
+
+lemma%unimportant image_orthogonal_transformation_ball:
+ fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
+ assumes "orthogonal_transformation f"
+ shows "f ` ball x r = ball (f x) r"
+proof (intro equalityI subsetI)
+ fix y assume "y \<in> f ` ball x r"
+ with assms show "y \<in> ball (f x) r"
+ by (auto simp: orthogonal_transformation_isometry)
+next
+ fix y assume y: "y \<in> ball (f x) r"
+ then obtain z where z: "y = f z"
+ using assms orthogonal_transformation_surj by blast
+ with y assms show "y \<in> f ` ball x r"
+ by (auto simp: orthogonal_transformation_isometry)
qed
-lemma induct_matrix_elementary:
- fixes P :: "real^'n^'n \<Rightarrow> bool"
- assumes mult: "\<And>A B. \<lbrakk>P A; P B\<rbrakk> \<Longrightarrow> P(A ** B)"
- and zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
- and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
- and swap1: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. mat 1 $ i $ Fun.swap m n id j)"
- and idplus: "\<And>m n c. m \<noteq> n \<Longrightarrow> P(\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j))"
- shows "P A"
-proof -
- have swap: "P (\<chi> i j. A $ i $ Fun.swap m n id j)" (is "P ?C")
- if "P A" "m \<noteq> n" for A m n
- proof -
- have "A ** (\<chi> i j. mat 1 $ i $ Fun.swap m n id j) = ?C"
- by (simp add: matrix_matrix_mult_def mat_def vec_eq_iff if_distrib sum.delta_remove)
- then show ?thesis
- using mult swap1 that by metis
- qed
- have row: "P (\<chi> i. if i = m then row m A + c *\<^sub>R row n A else row i A)" (is "P ?C")
- if "P A" "m \<noteq> n" for A m n c
- proof -
- let ?B = "\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j)"
- have "?B ** A = ?C"
- using \<open>m \<noteq> n\<close> unfolding matrix_matrix_mult_def row_def of_bool_def
- by (auto simp: vec_eq_iff if_distrib [of "\<lambda>x. x * y" for y] sum.remove cong: if_cong)
- then show ?thesis
- by (rule subst) (auto simp: that mult idplus)
- qed
- show ?thesis
- by (rule induct_matrix_row_operations [OF zero_row diagonal swap row])
-qed
-
-lemma induct_matrix_elementary_alt:
- fixes P :: "real^'n^'n \<Rightarrow> bool"
- assumes mult: "\<And>A B. \<lbrakk>P A; P B\<rbrakk> \<Longrightarrow> P(A ** B)"
- and zero_row: "\<And>A i. row i A = 0 \<Longrightarrow> P A"
- and diagonal: "\<And>A. (\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0) \<Longrightarrow> P A"
- and swap1: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. mat 1 $ i $ Fun.swap m n id j)"
- and idplus: "\<And>m n. m \<noteq> n \<Longrightarrow> P(\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j))"
- shows "P A"
-proof -
- have *: "P (\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j))"
- if "m \<noteq> n" for m n c
- proof (cases "c = 0")
- case True
- with diagonal show ?thesis by auto
- next
- case False
- then have eq: "(\<chi> i j. if i = m \<and> j = n then c else of_bool (i = j)) =
- (\<chi> i j. if i = j then (if j = n then inverse c else 1) else 0) **
- (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)) **
- (\<chi> i j. if i = j then if j = n then c else 1 else 0)"
- using \<open>m \<noteq> n\<close>
- apply (simp add: matrix_matrix_mult_def vec_eq_iff of_bool_def if_distrib [of "\<lambda>x. y * x" for y] cong: if_cong)
- apply (simp add: if_if_eq_conj sum.neutral conj_commute cong: conj_cong)
- done
- show ?thesis
- apply (subst eq)
- apply (intro mult idplus that)
- apply (auto intro: diagonal)
- done
- qed
- show ?thesis
- by (rule induct_matrix_elementary) (auto intro: assms *)
-qed
-
-lemma matrix_vector_mult_matrix_matrix_mult_compose:
- "(*v) (A ** B) = (*v) A \<circ> (*v) B"
- by (auto simp: matrix_vector_mul_assoc)
-
-lemma induct_linear_elementary:
- fixes f :: "real^'n \<Rightarrow> real^'n"
- assumes "linear f"
- and comp: "\<And>f g. \<lbrakk>linear f; linear g; P f; P g\<rbrakk> \<Longrightarrow> P(f \<circ> g)"
- and zeroes: "\<And>f i. \<lbrakk>linear f; \<And>x. (f x) $ i = 0\<rbrakk> \<Longrightarrow> P f"
- and const: "\<And>c. P(\<lambda>x. \<chi> i. c i * x$i)"
- and swap: "\<And>m n::'n. m \<noteq> n \<Longrightarrow> P(\<lambda>x. \<chi> i. x $ Fun.swap m n id i)"
- and idplus: "\<And>m n::'n. m \<noteq> n \<Longrightarrow> P(\<lambda>x. \<chi> i. if i = m then x$m + x$n else x$i)"
- shows "P f"
-proof -
- have "P ((*v) A)" for A
- proof (rule induct_matrix_elementary_alt)
- fix A B
- assume "P ((*v) A)" and "P ((*v) B)"
- then show "P ((*v) (A ** B))"
- by (auto simp add: matrix_vector_mult_matrix_matrix_mult_compose matrix_vector_mul_linear
- intro!: comp)
- next
- fix A :: "real^'n^'n" and i
- assume "row i A = 0"
- show "P ((*v) A)"
- using matrix_vector_mul_linear
- by (rule zeroes[where i=i])
- (metis \<open>row i A = 0\<close> inner_zero_left matrix_vector_mul_component row_def vec_lambda_eta)
- next
- fix A :: "real^'n^'n"
- assume 0: "\<And>i j. i \<noteq> j \<Longrightarrow> A $ i $ j = 0"
- have "A $ i $ i * x $ i = (\<Sum>j\<in>UNIV. A $ i $ j * x $ j)" for x and i :: "'n"
- by (simp add: 0 comm_monoid_add_class.sum.remove [where x=i])
- then have "(\<lambda>x. \<chi> i. A $ i $ i * x $ i) = ((*v) A)"
- by (auto simp: 0 matrix_vector_mult_def)
- then show "P ((*v) A)"
- using const [of "\<lambda>i. A $ i $ i"] by simp
- next
- fix m n :: "'n"
- assume "m \<noteq> n"
- have eq: "(\<Sum>j\<in>UNIV. if i = Fun.swap m n id j then x $ j else 0) =
- (\<Sum>j\<in>UNIV. if j = Fun.swap m n id i then x $ j else 0)"
- for i and x :: "real^'n"
- unfolding swap_def by (rule sum.cong) auto
- have "(\<lambda>x::real^'n. \<chi> i. x $ Fun.swap m n id i) = ((*v) (\<chi> i j. if i = Fun.swap m n id j then 1 else 0))"
- by (auto simp: mat_def matrix_vector_mult_def eq if_distrib [of "\<lambda>x. x * y" for y] cong: if_cong)
- with swap [OF \<open>m \<noteq> n\<close>] show "P ((*v) (\<chi> i j. mat 1 $ i $ Fun.swap m n id j))"
- by (simp add: mat_def matrix_vector_mult_def)
- next
- fix m n :: "'n"
- assume "m \<noteq> n"
- then have "x $ m + x $ n = (\<Sum>j\<in>UNIV. of_bool (j = n \<or> m = j) * x $ j)" for x :: "real^'n"
- by (auto simp: of_bool_def if_distrib [of "\<lambda>x. x * y" for y] sum.remove cong: if_cong)
- then have "(\<lambda>x::real^'n. \<chi> i. if i = m then x $ m + x $ n else x $ i) =
- ((*v) (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)))"
- unfolding matrix_vector_mult_def of_bool_def
- by (auto simp: vec_eq_iff if_distrib [of "\<lambda>x. x * y" for y] cong: if_cong)
- then show "P ((*v) (\<chi> i j. of_bool (i = m \<and> j = n \<or> i = j)))"
- using idplus [OF \<open>m \<noteq> n\<close>] by simp
- qed
- then show ?thesis
- by (metis \<open>linear f\<close> matrix_vector_mul)
+lemma%unimportant image_orthogonal_transformation_cball:
+ fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
+ assumes "orthogonal_transformation f"
+ shows "f ` cball x r = cball (f x) r"
+proof (intro equalityI subsetI)
+ fix y assume "y \<in> f ` cball x r"
+ with assms show "y \<in> cball (f x) r"
+ by (auto simp: orthogonal_transformation_isometry)
+next
+ fix y assume y: "y \<in> cball (f x) r"
+ then obtain z where z: "y = f z"
+ using assms orthogonal_transformation_surj by blast
+ with y assms show "y \<in> f ` cball x r"
+ by (auto simp: orthogonal_transformation_isometry)
qed
-proposition (*FIX needs name *)
+subsection \<open>Measurable Shear and Stretch\<close>
+
+proposition%important
fixes a :: "real^'n"
assumes "m \<noteq> n" and ab_ne: "cbox a b \<noteq> {}" and an: "0 \<le> a$n"
shows measurable_shear_interval: "(\<lambda>x. \<chi> i. if i = m then x$m + x$n else x$i) ` (cbox a b) \<in> lmeasurable"
(is "?f ` _ \<in> _")
and measure_shear_interval: "measure lebesgue ((\<lambda>x. \<chi> i. if i = m then x$m + x$n else x$i) ` cbox a b)
= measure lebesgue (cbox a b)" (is "?Q")
-proof -
+proof%unimportant -
have lin: "linear ?f"
by (rule linearI) (auto simp: plus_vec_def scaleR_vec_def algebra_simps)
show fab: "?f ` cbox a b \<in> lmeasurable"
@@ -362,13 +155,13 @@
qed
-proposition (*FIX needs name *)
+proposition%important
fixes S :: "(real^'n) set"
assumes "S \<in> lmeasurable"
shows measurable_stretch: "((\<lambda>x. \<chi> k. m k * x$k) ` S) \<in> lmeasurable" (is "?f ` S \<in> _")
and measure_stretch: "measure lebesgue ((\<lambda>x. \<chi> k. m k * x$k) ` S) = \<bar>prod m UNIV\<bar> * measure lebesgue S"
(is "?MEQ")
-proof -
+proof%unimportant -
have "(?f ` S) \<in> lmeasurable \<and> ?MEQ"
proof (cases "\<forall>k. m k \<noteq> 0")
case True
@@ -466,12 +259,12 @@
qed
-proposition (*FIX needs name *)
+proposition%important
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real^'n::_"
assumes "linear f" "S \<in> lmeasurable"
shows measurable_linear_image: "(f ` S) \<in> lmeasurable"
and measure_linear_image: "measure lebesgue (f ` S) = \<bar>det (matrix f)\<bar> * measure lebesgue S" (is "?Q f S")
-proof -
+proof%unimportant -
have "\<forall>S \<in> lmeasurable. (f ` S) \<in> lmeasurable \<and> ?Q f S"
proof (rule induct_linear_elementary [OF \<open>linear f\<close>]; intro ballI)
fix f g and S :: "(real,'n) vec set"
@@ -614,7 +407,7 @@
qed
-lemma (* needs name *)
+lemma%unimportant
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real^'n::_"
assumes f: "orthogonal_transformation f" and S: "S \<in> lmeasurable"
shows measurable_orthogonal_image: "f ` S \<in> lmeasurable"
@@ -637,10 +430,10 @@
inductive%important gdelta :: "'a::topological_space set \<Rightarrow> bool" where
"(\<And>n::nat. open (F n)) \<Longrightarrow> gdelta (\<Inter>(F ` UNIV))"
-proposition fsigma_Union_compact:
+lemma%important fsigma_Union_compact:
fixes S :: "'a::{real_normed_vector,heine_borel} set"
shows "fsigma S \<longleftrightarrow> (\<exists>F::nat \<Rightarrow> 'a set. range F \<subseteq> Collect compact \<and> S = \<Union>(F ` UNIV))"
-proof safe
+proof%unimportant safe
assume "fsigma S"
then obtain F :: "nat \<Rightarrow> 'a set" where F: "range F \<subseteq> Collect closed" "S = \<Union>(F ` UNIV)"
by (meson fsigma.cases image_subsetI mem_Collect_eq)
@@ -671,7 +464,7 @@
by (simp add: compact_imp_closed fsigma.intros image_subset_iff)
qed
-lemma gdelta_imp_fsigma: "gdelta S \<Longrightarrow> fsigma (- S)"
+lemma%unimportant gdelta_imp_fsigma: "gdelta S \<Longrightarrow> fsigma (- S)"
proof (induction rule: gdelta.induct)
case (1 F)
have "- \<Inter>(F ` UNIV) = (\<Union>i. -(F i))"
@@ -680,7 +473,7 @@
by (simp add: fsigma.intros closed_Compl 1)
qed
-lemma fsigma_imp_gdelta: "fsigma S \<Longrightarrow> gdelta (- S)"
+lemma%unimportant fsigma_imp_gdelta: "fsigma S \<Longrightarrow> gdelta (- S)"
proof (induction rule: fsigma.induct)
case (1 F)
have "- \<Union>(F ` UNIV) = (\<Inter>i. -(F i))"
@@ -689,11 +482,11 @@
by (simp add: 1 gdelta.intros open_closed)
qed
-lemma gdelta_complement: "gdelta(- S) \<longleftrightarrow> fsigma S"
+lemma%unimportant gdelta_complement: "gdelta(- S) \<longleftrightarrow> fsigma S"
using fsigma_imp_gdelta gdelta_imp_fsigma by force
text\<open>A Lebesgue set is almost an \<open>F_sigma\<close> or \<open>G_delta\<close>.\<close>
-lemma lebesgue_set_almost_fsigma:
+lemma%unimportant lebesgue_set_almost_fsigma:
assumes "S \<in> sets lebesgue"
obtains C T where "fsigma C" "negligible T" "C \<union> T = S" "disjnt C T"
proof -
@@ -728,7 +521,7 @@
qed
qed
-lemma lebesgue_set_almost_gdelta:
+lemma%unimportant lebesgue_set_almost_gdelta:
assumes "S \<in> sets lebesgue"
obtains C T where "gdelta C" "negligible T" "S \<union> T = C" "disjnt S T"
proof -
@@ -746,12 +539,12 @@
qed
-proposition measure_semicontinuous_with_hausdist_explicit:
+proposition%important measure_semicontinuous_with_hausdist_explicit:
assumes "bounded S" and neg: "negligible(frontier S)" and "e > 0"
obtains d where "d > 0"
"\<And>T. \<lbrakk>T \<in> lmeasurable; \<And>y. y \<in> T \<Longrightarrow> \<exists>x. x \<in> S \<and> dist x y < d\<rbrakk>
\<Longrightarrow> measure lebesgue T < measure lebesgue S + e"
-proof (cases "S = {}")
+proof%unimportant (cases "S = {}")
case True
with that \<open>e > 0\<close> show ?thesis by force
next
@@ -815,10 +608,10 @@
qed
qed
-proposition lebesgue_regular_inner:
+proposition%important lebesgue_regular_inner:
assumes "S \<in> sets lebesgue"
obtains K C where "negligible K" "\<And>n::nat. compact(C n)" "S = (\<Union>n. C n) \<union> K"
-proof -
+proof%unimportant -
have "\<exists>T. closed T \<and> T \<subseteq> S \<and> (S - T) \<in> lmeasurable \<and> measure lebesgue (S - T) < (1/2)^n" for n
using sets_lebesgue_inner_closed assms
by (metis sets_lebesgue_inner_closed zero_less_divide_1_iff zero_less_numeral zero_less_power)
@@ -868,7 +661,7 @@
qed
-lemma sets_lebesgue_continuous_image:
+lemma%unimportant sets_lebesgue_continuous_image:
assumes T: "T \<in> sets lebesgue" and contf: "continuous_on S f"
and negim: "\<And>T. \<lbrakk>negligible T; T \<subseteq> S\<rbrakk> \<Longrightarrow> negligible(f ` T)" and "T \<subseteq> S"
shows "f ` T \<in> sets lebesgue"
@@ -893,7 +686,7 @@
by (simp add: Teq image_Un image_Union)
qed
-lemma differentiable_image_in_sets_lebesgue:
+lemma%unimportant differentiable_image_in_sets_lebesgue:
fixes f :: "'m::euclidean_space \<Rightarrow> 'n::euclidean_space"
assumes S: "S \<in> sets lebesgue" and dim: "DIM('m) \<le> DIM('n)" and f: "f differentiable_on S"
shows "f`S \<in> sets lebesgue"
@@ -905,7 +698,7 @@
by (auto simp: intro!: negligible_differentiable_image_negligible [OF dim])
qed auto
-lemma sets_lebesgue_on_continuous_image:
+lemma%unimportant sets_lebesgue_on_continuous_image:
assumes S: "S \<in> sets lebesgue" and X: "X \<in> sets (lebesgue_on S)" and contf: "continuous_on S f"
and negim: "\<And>T. \<lbrakk>negligible T; T \<subseteq> S\<rbrakk> \<Longrightarrow> negligible(f ` T)"
shows "f ` X \<in> sets (lebesgue_on (f ` S))"
@@ -920,7 +713,7 @@
by (auto simp: sets_restrict_space_iff)
qed
-lemma differentiable_image_in_sets_lebesgue_on:
+lemma%unimportant differentiable_image_in_sets_lebesgue_on:
fixes f :: "'m::euclidean_space \<Rightarrow> 'n::euclidean_space"
assumes S: "S \<in> sets lebesgue" and X: "X \<in> sets (lebesgue_on S)" and dim: "DIM('m) \<le> DIM('n)"
and f: "f differentiable_on S"
@@ -934,7 +727,7 @@
qed
-proposition (*FIX needs name *)
+proposition%important
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real^'n::_"
assumes S: "S \<in> lmeasurable"
and deriv: "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
@@ -944,7 +737,7 @@
"f ` S \<in> lmeasurable"
and measure_bounded_differentiable_image:
"measure lebesgue (f ` S) \<le> B * measure lebesgue S" (is "?M")
-proof -
+proof%unimportant -
have "f ` S \<in> lmeasurable \<and> measure lebesgue (f ` S) \<le> B * measure lebesgue S"
proof (cases "B < 0")
case True
@@ -1170,13 +963,13 @@
then show "f ` S \<in> lmeasurable" ?M by blast+
qed
-proposition (*FIX needs name *)
+lemma%important
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real^'n::_"
assumes S: "S \<in> lmeasurable"
and deriv: "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
and int: "(\<lambda>x. \<bar>det (matrix (f' x))\<bar>) integrable_on S"
shows m_diff_image_weak: "f ` S \<in> lmeasurable \<and> measure lebesgue (f ` S) \<le> integral S (\<lambda>x. \<bar>det (matrix (f' x))\<bar>)"
-proof -
+proof%unimportant -
let ?\<mu> = "measure lebesgue"
have aint_S: "(\<lambda>x. \<bar>det (matrix (f' x))\<bar>) absolutely_integrable_on S"
using int unfolding absolutely_integrable_on_def by auto
@@ -1368,7 +1161,7 @@
qed
-theorem (*FIX needs name *)
+theorem%important
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real^'n::_"
assumes S: "S \<in> sets lebesgue"
and deriv: "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
@@ -1376,7 +1169,7 @@
shows measurable_differentiable_image: "f ` S \<in> lmeasurable"
and measure_differentiable_image:
"measure lebesgue (f ` S) \<le> integral S (\<lambda>x. \<bar>det (matrix (f' x))\<bar>)" (is "?M")
-proof -
+proof%unimportant -
let ?I = "\<lambda>n::nat. cbox (vec (-n)) (vec n) \<inter> S"
let ?\<mu> = "measure lebesgue"
have "x \<in> cbox (vec (- real (nat \<lceil>norm x\<rceil>))) (vec (real (nat \<lceil>norm x\<rceil>)))" for x :: "real^'n::_"
@@ -1421,7 +1214,7 @@
qed
-lemma borel_measurable_simple_function_limit_increasing:
+lemma%unimportant borel_measurable_simple_function_limit_increasing:
fixes f :: "'a::euclidean_space \<Rightarrow> real"
shows "(f \<in> borel_measurable lebesgue \<and> (\<forall>x. 0 \<le> f x)) \<longleftrightarrow>
(\<exists>g. (\<forall>n x. 0 \<le> g n x \<and> g n x \<le> f x) \<and> (\<forall>n x. g n x \<le> (g(Suc n) x)) \<and>
@@ -1620,7 +1413,7 @@
subsection%important\<open>Borel measurable Jacobian determinant\<close>
-lemma lemma_partial_derivatives0:
+lemma%unimportant lemma_partial_derivatives0:
fixes f :: "'a::euclidean_space \<Rightarrow> 'b::euclidean_space"
assumes "linear f" and lim0: "((\<lambda>x. f x /\<^sub>R norm x) \<longlongrightarrow> 0) (at 0 within S)"
and lb: "\<And>v. v \<noteq> 0 \<Longrightarrow> (\<exists>k>0. \<forall>e>0. \<exists>x. x \<in> S - {0} \<and> norm x < e \<and> k * norm x \<le> \<bar>v \<bullet> x\<bar>)"
@@ -1693,7 +1486,7 @@
mem_Collect_eq module_hom_zero span_base span_raw_def)
qed
-lemma lemma_partial_derivatives:
+lemma%unimportant lemma_partial_derivatives:
fixes f :: "'a::euclidean_space \<Rightarrow> 'b::euclidean_space"
assumes "linear f" and lim: "((\<lambda>x. f (x - a) /\<^sub>R norm (x - a)) \<longlongrightarrow> 0) (at a within S)"
and lb: "\<And>v. v \<noteq> 0 \<Longrightarrow> (\<exists>k>0. \<forall>e>0. \<exists>x \<in> S - {a}. norm(a - x) < e \<and> k * norm(a - x) \<le> \<bar>v \<bullet> (x - a)\<bar>)"
@@ -1711,12 +1504,12 @@
qed
-proposition borel_measurable_partial_derivatives:
+proposition%important borel_measurable_partial_derivatives:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n"
assumes S: "S \<in> sets lebesgue"
and f: "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
shows "(\<lambda>x. (matrix(f' x)$m$n)) \<in> borel_measurable (lebesgue_on S)"
-proof -
+proof%unimportant -
have contf: "continuous_on S f"
using continuous_on_eq_continuous_within f has_derivative_continuous by blast
have "{x \<in> S. (matrix (f' x)$m$n) \<le> b} \<in> sets lebesgue" for b
@@ -2302,7 +2095,7 @@
qed
-theorem borel_measurable_det_Jacobian:
+theorem%important borel_measurable_det_Jacobian:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real^'n::_"
assumes S: "S \<in> sets lebesgue" and f: "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
shows "(\<lambda>x. det(matrix(f' x))) \<in> borel_measurable (lebesgue_on S)"
@@ -2316,7 +2109,7 @@
assumes "S \<in> sets lebesgue"
shows "f \<in> borel_measurable (lebesgue_on S) \<longleftrightarrow>
(\<forall>T. T \<in> sets borel \<longrightarrow> {x \<in> S. f x \<in> T} \<in> sets lebesgue)"
-proof -
+proof%unimportant -
have "{x. (if x \<in> S then f x else 0) \<in> T} \<in> sets lebesgue \<longleftrightarrow> {x \<in> S. f x \<in> T} \<in> sets lebesgue"
if "T \<in> sets borel" for T
proof (cases "0 \<in> T")
@@ -2338,7 +2131,7 @@
by blast
qed
-lemma sets_lebesgue_almost_borel:
+lemma%unimportant sets_lebesgue_almost_borel:
assumes "S \<in> sets lebesgue"
obtains B N where "B \<in> sets borel" "negligible N" "B \<union> N = S"
proof -
@@ -2348,7 +2141,7 @@
by (metis negligible_iff_null_sets negligible_subset null_sets_completionI that)
qed
-lemma double_lebesgue_sets:
+lemma%unimportant double_lebesgue_sets:
assumes S: "S \<in> sets lebesgue" and T: "T \<in> sets lebesgue" and fim: "f ` S \<subseteq> T"
shows "(\<forall>U. U \<in> sets lebesgue \<and> U \<subseteq> T \<longrightarrow> {x \<in> S. f x \<in> U} \<in> sets lebesgue) \<longleftrightarrow>
f \<in> borel_measurable (lebesgue_on S) \<and>
@@ -2393,7 +2186,7 @@
subsection%important\<open>Simplest case of Sard's theorem (we don't need continuity of derivative)\<close>
-lemma Sard_lemma00:
+lemma%important Sard_lemma00:
fixes P :: "'b::euclidean_space set"
assumes "a \<ge> 0" and a: "a *\<^sub>R i \<noteq> 0" and i: "i \<in> Basis"
and P: "P \<subseteq> {x. a *\<^sub>R i \<bullet> x = 0}"
@@ -2401,7 +2194,7 @@
obtains S where "S \<in> lmeasurable"
and "{z. norm z \<le> m \<and> (\<exists>t \<in> P. norm(z - t) \<le> e)} \<subseteq> S"
and "measure lebesgue S \<le> (2 * e) * (2 * m) ^ (DIM('b) - 1)"
-proof -
+proof%unimportant -
have "a > 0"
using assms by simp
let ?v = "(\<Sum>j\<in>Basis. (if j = i then e else m) *\<^sub>R j)"
@@ -2429,7 +2222,7 @@
qed
text\<open>As above, but reorienting the vector (HOL Light's @text{GEOM\_BASIS\_MULTIPLE\_TAC})\<close>
-lemma Sard_lemma0:
+lemma%unimportant Sard_lemma0:
fixes P :: "(real^'n::{finite,wellorder}) set"
assumes "a \<noteq> 0"
and P: "P \<subseteq> {x. a \<bullet> x = 0}" and "0 \<le> m" "0 \<le> e"
@@ -2489,13 +2282,13 @@
qed
text\<open>As above, but translating the sets (HOL Light's @text{GEN\_GEOM\_ORIGIN\_TAC})\<close>
-lemma Sard_lemma1:
+lemma%important Sard_lemma1:
fixes P :: "(real^'n::{finite,wellorder}) set"
assumes P: "dim P < CARD('n)" and "0 \<le> m" "0 \<le> e"
obtains S where "S \<in> lmeasurable"
and "{z. norm(z - w) \<le> m \<and> (\<exists>t \<in> P. norm(z - w - t) \<le> e)} \<subseteq> S"
and "measure lebesgue S \<le> (2 * e) * (2 * m) ^ (CARD('n) - 1)"
-proof -
+proof%unimportant -
obtain a where "a \<noteq> 0" "P \<subseteq> {x. a \<bullet> x = 0}"
using lowdim_subset_hyperplane [of P] P span_base by auto
then obtain S where S: "S \<in> lmeasurable"
@@ -2513,7 +2306,7 @@
qed
qed
-lemma Sard_lemma2:
+lemma%important Sard_lemma2:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n::{finite,wellorder}"
assumes mlen: "CARD('m) \<le> CARD('n)" (is "?m \<le> ?n")
and "B > 0" "bounded S"
@@ -2521,7 +2314,7 @@
and rank: "\<And>x. x \<in> S \<Longrightarrow> rank(matrix(f' x)) < CARD('n)"
and B: "\<And>x. x \<in> S \<Longrightarrow> onorm(f' x) \<le> B"
shows "negligible(f ` S)"
-proof -
+proof%unimportant -
have lin_f': "\<And>x. x \<in> S \<Longrightarrow> linear(f' x)"
using derS has_derivative_linear by blast
show ?thesis
@@ -2728,13 +2521,13 @@
qed
-theorem baby_Sard:
+theorem%important baby_Sard:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n::{finite,wellorder}"
assumes mlen: "CARD('m) \<le> CARD('n)"
and der: "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
and rank: "\<And>x. x \<in> S \<Longrightarrow> rank(matrix(f' x)) < CARD('n)"
shows "negligible(f ` S)"
-proof -
+proof%unimportant -
let ?U = "\<lambda>n. {x \<in> S. norm(x) \<le> n \<and> onorm(f' x) \<le> real n}"
have "\<And>x. x \<in> S \<Longrightarrow> \<exists>n. norm x \<le> real n \<and> onorm (f' x) \<le> real n"
by (meson linear order_trans real_arch_simple)
@@ -2756,7 +2549,7 @@
subsection%important\<open>A one-way version of change-of-variables not assuming injectivity. \<close>
-lemma integral_on_image_ubound_weak:
+lemma%important integral_on_image_ubound_weak:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real"
assumes S: "S \<in> sets lebesgue"
and f: "f \<in> borel_measurable (lebesgue_on (g ` S))"
@@ -2767,7 +2560,7 @@
shows "f integrable_on (g ` S) \<and>
integral (g ` S) f \<le> integral S (\<lambda>x. \<bar>det (matrix (g' x))\<bar> * f(g x))"
(is "_ \<and> _ \<le> ?b")
-proof -
+proof%unimportant -
let ?D = "\<lambda>x. \<bar>det (matrix (g' x))\<bar>"
have cont_g: "continuous_on S g"
using der_g has_derivative_continuous_on by blast
@@ -2945,14 +2738,14 @@
qed
-lemma integral_on_image_ubound_nonneg:
+lemma%important integral_on_image_ubound_nonneg:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real"
assumes nonneg_fg: "\<And>x. x \<in> S \<Longrightarrow> 0 \<le> f(g x)"
and der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
and intS: "(\<lambda>x. \<bar>det (matrix (g' x))\<bar> * f(g x)) integrable_on S"
shows "f integrable_on (g ` S) \<and> integral (g ` S) f \<le> integral S (\<lambda>x. \<bar>det (matrix (g' x))\<bar> * f(g x))"
(is "_ \<and> _ \<le> ?b")
-proof -
+proof%unimportant -
let ?D = "\<lambda>x. det (matrix (g' x))"
define S' where "S' \<equiv> {x \<in> S. ?D x * f(g x) \<noteq> 0}"
then have der_gS': "\<And>x. x \<in> S' \<Longrightarrow> (g has_derivative g' x) (at x within S')"
@@ -3075,7 +2868,7 @@
qed
-proposition absolutely_integrable_on_image_real:
+lemma%unimportant absolutely_integrable_on_image_real:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real" and g :: "real^'n::_ \<Rightarrow> real^'n::_"
assumes der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
and intS: "(\<lambda>x. \<bar>det (matrix (g' x))\<bar> * f(g x)) absolutely_integrable_on S"
@@ -3150,7 +2943,7 @@
qed
-proposition absolutely_integrable_on_image:
+proposition%important absolutely_integrable_on_image:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
and intS: "(\<lambda>x. \<bar>det (matrix (g' x))\<bar> *\<^sub>R f(g x)) absolutely_integrable_on S"
@@ -3158,7 +2951,7 @@
apply (rule absolutely_integrable_componentwise [OF absolutely_integrable_on_image_real [OF der_g]])
using%unimportant absolutely_integrable_component [OF intS] by%unimportant auto
-proposition integral_on_image_ubound:
+proposition%important integral_on_image_ubound:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real" and g :: "real^'n::_ \<Rightarrow> real^'n::_"
assumes"\<And>x. x \<in> S \<Longrightarrow> 0 \<le> f(g x)"
and "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
@@ -3172,7 +2965,7 @@
text\<open>The classic change-of-variables theorem. We have two versions with quite general hypotheses,
the first that the transforming function has a continuous inverse, the second that the base set is
Lebesgue measurable.\<close>
-lemma cov_invertible_nonneg_le:
+lemma%unimportant cov_invertible_nonneg_le:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real" and g :: "real^'n::_ \<Rightarrow> real^'n::_"
assumes der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
and der_h: "\<And>y. y \<in> T \<Longrightarrow> (h has_derivative h' y) (at y within T)"
@@ -3243,7 +3036,7 @@
qed
-lemma cov_invertible_nonneg_eq:
+lemma%unimportant cov_invertible_nonneg_eq:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real" and g :: "real^'n::_ \<Rightarrow> real^'n::_"
assumes "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
and "\<And>y. y \<in> T \<Longrightarrow> (h has_derivative h' y) (at y within T)"
@@ -3256,7 +3049,7 @@
by (simp add: has_integral_iff) (meson eq_iff)
-lemma cov_invertible_real:
+lemma%unimportant cov_invertible_real:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real" and g :: "real^'n::_ \<Rightarrow> real^'n::_"
assumes der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
and der_h: "\<And>y. y \<in> T \<Longrightarrow> (h has_derivative h' y) (at y within T)"
@@ -3422,7 +3215,7 @@
qed
-lemma cv_inv_version3:
+lemma%unimportant cv_inv_version3:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
and der_h: "\<And>y. y \<in> T \<Longrightarrow> (h has_derivative h' y) (at y within T)"
@@ -3448,7 +3241,7 @@
qed
-lemma cv_inv_version4:
+lemma%unimportant cv_inv_version4:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S) \<and> invertible(matrix(g' x))"
and hg: "\<And>x. x \<in> S \<Longrightarrow> continuous_on (g ` S) h \<and> h(g x) = x"
@@ -3473,7 +3266,7 @@
qed
-proposition has_absolute_integral_change_of_variables_invertible:
+proposition%important has_absolute_integral_change_of_variables_invertible:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
and hg: "\<And>x. x \<in> S \<Longrightarrow> h(g x) = x"
@@ -3481,7 +3274,7 @@
shows "(\<lambda>x. \<bar>det (matrix (g' x))\<bar> *\<^sub>R f(g x)) absolutely_integrable_on S \<and> integral S (\<lambda>x. \<bar>det (matrix (g' x))\<bar> *\<^sub>R f(g x)) = b \<longleftrightarrow>
f absolutely_integrable_on (g ` S) \<and> integral (g ` S) f = b"
(is "?lhs = ?rhs")
-proof -
+proof%unimportant -
let ?S = "{x \<in> S. invertible (matrix (g' x))}" and ?D = "\<lambda>x. \<bar>det (matrix (g' x))\<bar> *\<^sub>R f(g x)"
have *: "?D absolutely_integrable_on ?S \<and> integral ?S ?D = b
\<longleftrightarrow> f absolutely_integrable_on (g ` ?S) \<and> integral (g ` ?S) f = b"
@@ -3517,7 +3310,7 @@
-proposition has_absolute_integral_change_of_variables_compact:
+lemma%unimportant has_absolute_integral_change_of_variables_compact:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes "compact S"
and der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
@@ -3535,7 +3328,7 @@
qed
-lemma has_absolute_integral_change_of_variables_compact_family:
+lemma%unimportant has_absolute_integral_change_of_variables_compact_family:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes compact: "\<And>n::nat. compact (F n)"
and der_g: "\<And>x. x \<in> (\<Union>n. F n) \<Longrightarrow> (g has_derivative g' x) (at x within (\<Union>n. F n))"
@@ -3714,7 +3507,7 @@
qed
-proposition has_absolute_integral_change_of_variables:
+proposition%important has_absolute_integral_change_of_variables:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes S: "S \<in> sets lebesgue"
and der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
@@ -3722,7 +3515,7 @@
shows "(\<lambda>x. \<bar>det (matrix (g' x))\<bar> *\<^sub>R f(g x)) absolutely_integrable_on S \<and>
integral S (\<lambda>x. \<bar>det (matrix (g' x))\<bar> *\<^sub>R f(g x)) = b
\<longleftrightarrow> f absolutely_integrable_on (g ` S) \<and> integral (g ` S) f = b"
-proof -
+proof%unimportant -
obtain C N where "fsigma C" "negligible N" and CNS: "C \<union> N = S" and "disjnt C N"
using lebesgue_set_almost_fsigma [OF S] .
then obtain F :: "nat \<Rightarrow> (real^'m::_) set"
@@ -3776,16 +3569,16 @@
qed
-corollary absolutely_integrable_change_of_variables:
+corollary%important absolutely_integrable_change_of_variables:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes "S \<in> sets lebesgue"
and "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
and "inj_on g S"
shows "f absolutely_integrable_on (g ` S)
\<longleftrightarrow> (\<lambda>x. \<bar>det (matrix (g' x))\<bar> *\<^sub>R f(g x)) absolutely_integrable_on S"
- using assms has_absolute_integral_change_of_variables by blast
+ using%unimportant assms has_absolute_integral_change_of_variables by%unimportant blast
-corollary integral_change_of_variables:
+corollary%important integral_change_of_variables:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes S: "S \<in> sets lebesgue"
and der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_derivative g' x) (at x within S)"
@@ -3793,10 +3586,10 @@
and disj: "(f absolutely_integrable_on (g ` S) \<or>
(\<lambda>x. \<bar>det (matrix (g' x))\<bar> *\<^sub>R f(g x)) absolutely_integrable_on S)"
shows "integral (g ` S) f = integral S (\<lambda>x. \<bar>det (matrix (g' x))\<bar> *\<^sub>R f(g x))"
- using has_absolute_integral_change_of_variables [OF S der_g inj] disj
- by blast
+ using%unimportant has_absolute_integral_change_of_variables [OF S der_g inj] disj
+ by%unimportant blast
-lemma has_absolute_integral_change_of_variables_1:
+lemma%unimportant has_absolute_integral_change_of_variables_1:
fixes f :: "real \<Rightarrow> real^'n::{finite,wellorder}" and g :: "real \<Rightarrow> real"
assumes S: "S \<in> sets lebesgue"
and der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_vector_derivative g' x) (at x within S)"
@@ -3835,19 +3628,19 @@
qed
-corollary absolutely_integrable_change_of_variables_1:
+corollary%important absolutely_integrable_change_of_variables_1:
fixes f :: "real \<Rightarrow> real^'n::{finite,wellorder}" and g :: "real \<Rightarrow> real"
assumes S: "S \<in> sets lebesgue"
and der_g: "\<And>x. x \<in> S \<Longrightarrow> (g has_vector_derivative g' x) (at x within S)"
and inj: "inj_on g S"
shows "(f absolutely_integrable_on g ` S \<longleftrightarrow>
(\<lambda>x. \<bar>g' x\<bar> *\<^sub>R f(g x)) absolutely_integrable_on S)"
- using has_absolute_integral_change_of_variables_1 [OF assms] by auto
+ using%unimportant has_absolute_integral_change_of_variables_1 [OF assms] by%unimportant auto
subsection%important\<open>Change of variables for integrals: special case of linear function\<close>
-lemma has_absolute_integral_change_of_variables_linear:
+lemma%unimportant has_absolute_integral_change_of_variables_linear:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes "linear g"
shows "(\<lambda>x. \<bar>det (matrix g)\<bar> *\<^sub>R f(g x)) absolutely_integrable_on S \<and>
@@ -3872,14 +3665,14 @@
qed (use h in auto)
qed
-lemma absolutely_integrable_change_of_variables_linear:
+lemma%unimportant absolutely_integrable_change_of_variables_linear:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes "linear g"
shows "(\<lambda>x. \<bar>det (matrix g)\<bar> *\<^sub>R f(g x)) absolutely_integrable_on S
\<longleftrightarrow> f absolutely_integrable_on (g ` S)"
using assms has_absolute_integral_change_of_variables_linear by blast
-lemma absolutely_integrable_on_linear_image:
+lemma%unimportant absolutely_integrable_on_linear_image:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes "linear g"
shows "f absolutely_integrable_on (g ` S)
@@ -3887,12 +3680,12 @@
unfolding assms absolutely_integrable_change_of_variables_linear [OF assms, symmetric] absolutely_integrable_on_scaleR_iff
by (auto simp: set_integrable_def)
-lemma integral_change_of_variables_linear:
+lemma%important integral_change_of_variables_linear:
fixes f :: "real^'m::{finite,wellorder} \<Rightarrow> real^'n" and g :: "real^'m::_ \<Rightarrow> real^'m::_"
assumes "linear g"
and "f absolutely_integrable_on (g ` S) \<or> (f \<circ> g) absolutely_integrable_on S"
shows "integral (g ` S) f = \<bar>det (matrix g)\<bar> *\<^sub>R integral S (f \<circ> g)"
-proof -
+proof%unimportant -
have "((\<lambda>x. \<bar>det (matrix g)\<bar> *\<^sub>R f (g x)) absolutely_integrable_on S) \<or> (f absolutely_integrable_on g ` S)"
using absolutely_integrable_on_linear_image assms by blast
moreover
@@ -3906,18 +3699,18 @@
subsection%important\<open>Change of variable for measure\<close>
-lemma has_measure_differentiable_image:
+lemma%unimportant has_measure_differentiable_image:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real^'n::_"
assumes "S \<in> sets lebesgue"
and "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
and "inj_on f S"
shows "f ` S \<in> lmeasurable \<and> measure lebesgue (f ` S) = m
\<longleftrightarrow> ((\<lambda>x. \<bar>det (matrix (f' x))\<bar>) has_integral m) S"
- using has_absolute_integral_change_of_variables [OF assms, of "\<lambda>x. (1::real^1)" "vec m"]
- unfolding absolutely_integrable_on_1_iff integral_on_1_eq integrable_on_1_iff absolutely_integrable_on_def
- by (auto simp: has_integral_iff lmeasurable_iff_integrable_on lmeasure_integral)
+ using%unimportant has_absolute_integral_change_of_variables [OF assms, of "\<lambda>x. (1::real^1)" "vec m"]
+ unfolding%unimportant absolutely_integrable_on_1_iff integral_on_1_eq integrable_on_1_iff absolutely_integrable_on_def
+ by%unimportant (auto simp: has_integral_iff lmeasurable_iff_integrable_on lmeasure_integral)
-lemma measurable_differentiable_image_eq:
+lemma%unimportant measurable_differentiable_image_eq:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real^'n::_"
assumes "S \<in> sets lebesgue"
and "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
@@ -3926,23 +3719,23 @@
using has_measure_differentiable_image [OF assms]
by blast
-lemma measurable_differentiable_image_alt:
+lemma%important measurable_differentiable_image_alt:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real^'n::_"
assumes "S \<in> sets lebesgue"
and "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
and "inj_on f S"
shows "f ` S \<in> lmeasurable \<longleftrightarrow> (\<lambda>x. \<bar>det (matrix (f' x))\<bar>) absolutely_integrable_on S"
- using measurable_differentiable_image_eq [OF assms]
- by (simp only: absolutely_integrable_on_iff_nonneg)
+ using%unimportant measurable_differentiable_image_eq [OF assms]
+ by%unimportant (simp only: absolutely_integrable_on_iff_nonneg)
-lemma measure_differentiable_image_eq:
+lemma%important measure_differentiable_image_eq:
fixes f :: "real^'n::{finite,wellorder} \<Rightarrow> real^'n::_"
assumes S: "S \<in> sets lebesgue"
and der_f: "\<And>x. x \<in> S \<Longrightarrow> (f has_derivative f' x) (at x within S)"
and inj: "inj_on f S"
and intS: "(\<lambda>x. \<bar>det (matrix (f' x))\<bar>) integrable_on S"
shows "measure lebesgue (f ` S) = integral S (\<lambda>x. \<bar>det (matrix (f' x))\<bar>)"
- using measurable_differentiable_image_eq [OF S der_f inj]
+ using%unimportant measurable_differentiable_image_eq [OF S der_f inj]
assms has_measure_differentiable_image by%unimportant blast
end
--- a/src/HOL/Analysis/Convex.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Convex.thy Thu Jan 17 16:08:41 2019 +0000
@@ -14,79 +14,6 @@
"HOL-Library.Set_Algebras"
begin
-lemma substdbasis_expansion_unique:
- assumes d: "d \<subseteq> Basis"
- shows "(\<Sum>i\<in>d. f i *\<^sub>R i) = (x::'a::euclidean_space) \<longleftrightarrow>
- (\<forall>i\<in>Basis. (i \<in> d \<longrightarrow> f i = x \<bullet> i) \<and> (i \<notin> d \<longrightarrow> x \<bullet> i = 0))"
-proof -
- have *: "\<And>x a b P. x * (if P then a else b) = (if P then x * a else x * b)"
- by auto
- have **: "finite d"
- by (auto intro: finite_subset[OF assms])
- have ***: "\<And>i. i \<in> Basis \<Longrightarrow> (\<Sum>i\<in>d. f i *\<^sub>R i) \<bullet> i = (\<Sum>x\<in>d. if x = i then f x else 0)"
- using d
- by (auto intro!: sum.cong simp: inner_Basis inner_sum_left)
- show ?thesis
- unfolding euclidean_eq_iff[where 'a='a] by (auto simp: sum.delta[OF **] ***)
-qed
-
-lemma independent_substdbasis: "d \<subseteq> Basis \<Longrightarrow> independent d"
- by (rule independent_mono[OF independent_Basis])
-
-lemma sum_not_0: "sum f A \<noteq> 0 \<Longrightarrow> \<exists>a \<in> A. f a \<noteq> 0"
- by (rule ccontr) auto
-
-lemma subset_translation_eq [simp]:
- fixes a :: "'a::real_vector" shows "(+) a ` s \<subseteq> (+) a ` t \<longleftrightarrow> s \<subseteq> t"
- by auto
-
-lemma translate_inj_on:
- fixes A :: "'a::ab_group_add set"
- shows "inj_on (\<lambda>x. a + x) A"
- unfolding inj_on_def by auto
-
-lemma translation_assoc:
- fixes a b :: "'a::ab_group_add"
- shows "(\<lambda>x. b + x) ` ((\<lambda>x. a + x) ` S) = (\<lambda>x. (a + b) + x) ` S"
- by auto
-
-lemma translation_invert:
- fixes a :: "'a::ab_group_add"
- assumes "(\<lambda>x. a + x) ` A = (\<lambda>x. a + x) ` B"
- shows "A = B"
-proof -
- have "(\<lambda>x. -a + x) ` ((\<lambda>x. a + x) ` A) = (\<lambda>x. - a + x) ` ((\<lambda>x. a + x) ` B)"
- using assms by auto
- then show ?thesis
- using translation_assoc[of "-a" a A] translation_assoc[of "-a" a B] by auto
-qed
-
-lemma translation_galois:
- fixes a :: "'a::ab_group_add"
- shows "T = ((\<lambda>x. a + x) ` S) \<longleftrightarrow> S = ((\<lambda>x. (- a) + x) ` T)"
- using translation_assoc[of "-a" a S]
- apply auto
- using translation_assoc[of a "-a" T]
- apply auto
- done
-
-lemma translation_inverse_subset:
- assumes "((\<lambda>x. - a + x) ` V) \<le> (S :: 'n::ab_group_add set)"
- shows "V \<le> ((\<lambda>x. a + x) ` S)"
-proof -
- {
- fix x
- assume "x \<in> V"
- then have "x-a \<in> S" using assms by auto
- then have "x \<in> {a + v |v. v \<in> S}"
- apply auto
- apply (rule exI[of _ "x-a"], simp)
- done
- then have "x \<in> ((\<lambda>x. a+x) ` S)" by auto
- }
- then show ?thesis by auto
-qed
-
subsection \<open>Convexity\<close>
definition%important convex :: "'a::real_vector set \<Rightarrow> bool"
--- a/src/HOL/Analysis/Cross3.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Cross3.thy Thu Jan 17 16:08:41 2019 +0000
@@ -7,7 +7,7 @@
section\<open>Vector Cross Products in 3 Dimensions\<close>
theory "Cross3"
- imports Determinants
+ imports Determinants Cartesian_Euclidean_Space
begin
context includes no_Set_Product_syntax
--- a/src/HOL/Analysis/Determinants.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Determinants.thy Thu Jan 17 16:08:41 2019 +0000
@@ -15,19 +15,19 @@
definition%important trace :: "'a::semiring_1^'n^'n \<Rightarrow> 'a"
where "trace A = sum (\<lambda>i. ((A$i)$i)) (UNIV::'n set)"
-lemma trace_0: "trace (mat 0) = 0"
+lemma%unimportant trace_0: "trace (mat 0) = 0"
by (simp add: trace_def mat_def)
-lemma trace_I: "trace (mat 1 :: 'a::semiring_1^'n^'n) = of_nat(CARD('n))"
+lemma%unimportant trace_I: "trace (mat 1 :: 'a::semiring_1^'n^'n) = of_nat(CARD('n))"
by (simp add: trace_def mat_def)
-lemma trace_add: "trace ((A::'a::comm_semiring_1^'n^'n) + B) = trace A + trace B"
+lemma%unimportant trace_add: "trace ((A::'a::comm_semiring_1^'n^'n) + B) = trace A + trace B"
by (simp add: trace_def sum.distrib)
-lemma trace_sub: "trace ((A::'a::comm_ring_1^'n^'n) - B) = trace A - trace B"
+lemma%unimportant trace_sub: "trace ((A::'a::comm_ring_1^'n^'n) - B) = trace A - trace B"
by (simp add: trace_def sum_subtractf)
-lemma trace_mul_sym: "trace ((A::'a::comm_semiring_1^'n^'m) ** B) = trace (B**A)"
+lemma%important trace_mul_sym: "trace ((A::'a::comm_semiring_1^'n^'m) ** B) = trace (B**A)"
apply (simp add: trace_def matrix_matrix_mult_def)
apply (subst sum.swap)
apply (simp add: mult.commute)
@@ -42,8 +42,8 @@
text \<open>Basic determinant properties\<close>
-proposition det_transpose [simp]: "det (transpose A) = det (A::'a::comm_ring_1 ^'n^'n)"
-proof -
+lemma%important det_transpose [simp]: "det (transpose A) = det (A::'a::comm_ring_1 ^'n^'n)"
+proof%unimportant -
let ?di = "\<lambda>A i j. A$i$j"
let ?U = "(UNIV :: 'n set)"
have fU: "finite ?U" by simp
@@ -80,7 +80,7 @@
by (subst sum_permutations_inverse) (blast intro: sum.cong)
qed
-lemma det_lowerdiagonal:
+lemma%unimportant det_lowerdiagonal:
fixes A :: "'a::comm_ring_1^('n::{finite,wellorder})^('n::{finite,wellorder})"
assumes ld: "\<And>i j. i < j \<Longrightarrow> A$i$j = 0"
shows "det A = prod (\<lambda>i. A$i$i) (UNIV:: 'n set)"
@@ -107,11 +107,11 @@
unfolding det_def by (simp add: sign_id)
qed
-lemma det_upperdiagonal:
+lemma%important det_upperdiagonal:
fixes A :: "'a::comm_ring_1^'n::{finite,wellorder}^'n::{finite,wellorder}"
assumes ld: "\<And>i j. i > j \<Longrightarrow> A$i$j = 0"
shows "det A = prod (\<lambda>i. A$i$i) (UNIV:: 'n set)"
-proof -
+proof%unimportant -
let ?U = "UNIV:: 'n set"
let ?PU = "{p. p permutes ?U}"
let ?pp = "(\<lambda>p. of_int (sign p) * prod (\<lambda>i. A$i$p i) (UNIV :: 'n set))"
@@ -134,11 +134,11 @@
unfolding det_def by (simp add: sign_id)
qed
-proposition det_diagonal:
+lemma%important det_diagonal:
fixes A :: "'a::comm_ring_1^'n^'n"
assumes ld: "\<And>i j. i \<noteq> j \<Longrightarrow> A$i$j = 0"
shows "det A = prod (\<lambda>i. A$i$i) (UNIV::'n set)"
-proof -
+proof%unimportant -
let ?U = "UNIV:: 'n set"
let ?PU = "{p. p permutes ?U}"
let ?pp = "\<lambda>p. of_int (sign p) * prod (\<lambda>i. A$i$p i) (UNIV :: 'n set)"
@@ -161,13 +161,13 @@
unfolding det_def by (simp add: sign_id)
qed
-lemma det_I [simp]: "det (mat 1 :: 'a::comm_ring_1^'n^'n) = 1"
+lemma%unimportant det_I [simp]: "det (mat 1 :: 'a::comm_ring_1^'n^'n) = 1"
by (simp add: det_diagonal mat_def)
-lemma det_0 [simp]: "det (mat 0 :: 'a::comm_ring_1^'n^'n) = 0"
+lemma%unimportant det_0 [simp]: "det (mat 0 :: 'a::comm_ring_1^'n^'n) = 0"
by (simp add: det_def prod_zero power_0_left)
-lemma det_permute_rows:
+lemma%unimportant det_permute_rows:
fixes A :: "'a::comm_ring_1^'n^'n"
assumes p: "p permutes (UNIV :: 'n::finite set)"
shows "det (\<chi> i. A$p i :: 'a^'n^'n) = of_int (sign p) * det A"
@@ -204,11 +204,11 @@
done
qed
-lemma det_permute_columns:
+lemma%important det_permute_columns:
fixes A :: "'a::comm_ring_1^'n^'n"
assumes p: "p permutes (UNIV :: 'n set)"
shows "det(\<chi> i j. A$i$ p j :: 'a^'n^'n) = of_int (sign p) * det A"
-proof -
+proof%unimportant -
let ?Ap = "\<chi> i j. A$i$ p j :: 'a^'n^'n"
let ?At = "transpose A"
have "of_int (sign p) * det A = det (transpose (\<chi> i. transpose A $ p i))"
@@ -220,7 +220,7 @@
by simp
qed
-lemma det_identical_columns:
+lemma%unimportant det_identical_columns:
fixes A :: "'a::comm_ring_1^'n^'n"
assumes jk: "j \<noteq> k"
and r: "column j A = column k A"
@@ -300,24 +300,24 @@
finally show "det A = 0" by simp
qed
-lemma det_identical_rows:
+lemma%unimportant det_identical_rows:
fixes A :: "'a::comm_ring_1^'n^'n"
assumes ij: "i \<noteq> j" and r: "row i A = row j A"
shows "det A = 0"
by (metis column_transpose det_identical_columns det_transpose ij r)
-lemma det_zero_row:
+lemma%unimportant det_zero_row:
fixes A :: "'a::{idom, ring_char_0}^'n^'n" and F :: "'b::{field}^'m^'m"
shows "row i A = 0 \<Longrightarrow> det A = 0" and "row j F = 0 \<Longrightarrow> det F = 0"
by (force simp: row_def det_def vec_eq_iff sign_nz intro!: sum.neutral)+
-lemma det_zero_column:
+lemma%unimportant det_zero_column:
fixes A :: "'a::{idom, ring_char_0}^'n^'n" and F :: "'b::{field}^'m^'m"
shows "column i A = 0 \<Longrightarrow> det A = 0" and "column j F = 0 \<Longrightarrow> det F = 0"
unfolding atomize_conj atomize_imp
by (metis det_transpose det_zero_row row_transpose)
-lemma det_row_add:
+lemma%unimportant det_row_add:
fixes a b c :: "'n::finite \<Rightarrow> _ ^ 'n"
shows "det((\<chi> i. if i = k then a i + b i else c i)::'a::comm_ring_1^'n^'n) =
det((\<chi> i. if i = k then a i else c i)::'a::comm_ring_1^'n^'n) +
@@ -358,7 +358,7 @@
by (simp add: field_simps)
qed auto
-lemma det_row_mul:
+lemma%unimportant det_row_mul:
fixes a b :: "'n::finite \<Rightarrow> _ ^ 'n"
shows "det((\<chi> i. if i = k then c *s a i else b i)::'a::comm_ring_1^'n^'n) =
c * det((\<chi> i. if i = k then a i else b i)::'a::comm_ring_1^'n^'n)"
@@ -395,7 +395,7 @@
by (simp add: field_simps)
qed auto
-lemma det_row_0:
+lemma%unimportant det_row_0:
fixes b :: "'n::finite \<Rightarrow> _ ^ 'n"
shows "det((\<chi> i. if i = k then 0 else b i)::'a::comm_ring_1^'n^'n) = 0"
using det_row_mul[of k 0 "\<lambda>i. 1" b]
@@ -403,11 +403,11 @@
apply (simp only: vector_smult_lzero)
done
-lemma det_row_operation:
+lemma%important det_row_operation:
fixes A :: "'a::{comm_ring_1}^'n^'n"
assumes ij: "i \<noteq> j"
shows "det (\<chi> k. if k = i then row i A + c *s row j A else row k A) = det A"
-proof -
+proof%unimportant -
let ?Z = "(\<chi> k. if k = i then row j A else row k A) :: 'a ^'n^'n"
have th: "row i ?Z = row j ?Z" by (vector row_def)
have th2: "((\<chi> k. if k = i then row i A else row k A) :: 'a^'n^'n) = A"
@@ -417,7 +417,7 @@
by simp
qed
-lemma det_row_span:
+lemma%unimportant det_row_span:
fixes A :: "'a::{field}^'n^'n"
assumes x: "x \<in> vec.span {row j A |j. j \<noteq> i}"
shows "det (\<chi> k. if k = i then row i A + x else row k A) = det A"
@@ -449,10 +449,10 @@
unfolding scalar_mult_eq_scaleR .
qed
-lemma matrix_id [simp]: "det (matrix id) = 1"
+lemma%unimportant matrix_id [simp]: "det (matrix id) = 1"
by (simp add: matrix_id_mat_1)
-lemma det_matrix_scaleR [simp]: "det (matrix (((*\<^sub>R) r)) :: real^'n^'n) = r ^ CARD('n::finite)"
+lemma%important det_matrix_scaleR [simp]: "det (matrix (((*\<^sub>R) r)) :: real^'n^'n) = r ^ CARD('n::finite)"
apply (subst det_diagonal)
apply (auto simp: matrix_def mat_def)
apply (simp add: cart_eq_inner_axis inner_axis_axis)
@@ -463,7 +463,7 @@
exact duplicates by considering the rows/columns as a set.
\<close>
-lemma det_dependent_rows:
+lemma%unimportant det_dependent_rows:
fixes A:: "'a::{field}^'n^'n"
assumes d: "vec.dependent (rows A)"
shows "det A = 0"
@@ -491,23 +491,23 @@
qed
qed
-lemma det_dependent_columns:
+lemma%unimportant det_dependent_columns:
assumes d: "vec.dependent (columns (A::real^'n^'n))"
shows "det A = 0"
by (metis d det_dependent_rows rows_transpose det_transpose)
text \<open>Multilinearity and the multiplication formula\<close>
-lemma Cart_lambda_cong: "(\<And>x. f x = g x) \<Longrightarrow> (vec_lambda f::'a^'n) = (vec_lambda g :: 'a^'n)"
+lemma%unimportant Cart_lambda_cong: "(\<And>x. f x = g x) \<Longrightarrow> (vec_lambda f::'a^'n) = (vec_lambda g :: 'a^'n)"
by auto
-lemma det_linear_row_sum:
+lemma%unimportant det_linear_row_sum:
assumes fS: "finite S"
shows "det ((\<chi> i. if i = k then sum (a i) S else c i)::'a::comm_ring_1^'n^'n) =
sum (\<lambda>j. det ((\<chi> i. if i = k then a i j else c i)::'a^'n^'n)) S"
using fS by (induct rule: finite_induct; simp add: det_row_0 det_row_add cong: if_cong)
-lemma finite_bounded_functions:
+lemma%unimportant finite_bounded_functions:
assumes fS: "finite S"
shows "finite {f. (\<forall>i \<in> {1.. (k::nat)}. f i \<in> S) \<and> (\<forall>i. i \<notin> {1 .. k} \<longrightarrow> f i = i)}"
proof (induct k)
@@ -532,14 +532,14 @@
qed
-lemma det_linear_rows_sum_lemma:
+lemma%important det_linear_rows_sum_lemma:
assumes fS: "finite S"
and fT: "finite T"
shows "det ((\<chi> i. if i \<in> T then sum (a i) S else c i):: 'a::comm_ring_1^'n^'n) =
sum (\<lambda>f. det((\<chi> i. if i \<in> T then a i (f i) else c i)::'a^'n^'n))
{f. (\<forall>i \<in> T. f i \<in> S) \<and> (\<forall>i. i \<notin> T \<longrightarrow> f i = i)}"
using fT
-proof (induct T arbitrary: a c set: finite)
+proof%unimportant (induct T arbitrary: a c set: finite)
case empty
have th0: "\<And>x y. (\<chi> i. if i \<in> {} then x i else y i) = (\<chi> i. y i)"
by vector
@@ -577,7 +577,7 @@
(auto intro!: cong[OF refl[of det]] simp: vec_eq_iff)
qed
-lemma det_linear_rows_sum:
+lemma%unimportant det_linear_rows_sum:
fixes S :: "'n::finite set"
assumes fS: "finite S"
shows "det (\<chi> i. sum (a i) S) =
@@ -589,12 +589,12 @@
show ?thesis by simp
qed
-lemma matrix_mul_sum_alt:
+lemma%unimportant matrix_mul_sum_alt:
fixes A B :: "'a::comm_ring_1^'n^'n"
shows "A ** B = (\<chi> i. sum (\<lambda>k. A$i$k *s B $ k) (UNIV :: 'n set))"
by (vector matrix_matrix_mult_def sum_component)
-lemma det_rows_mul:
+lemma%unimportant det_rows_mul:
"det((\<chi> i. c i *s a i)::'a::comm_ring_1^'n^'n) =
prod (\<lambda>i. c i) (UNIV:: 'n set) * det((\<chi> i. a i)::'a^'n^'n)"
proof (simp add: det_def sum_distrib_left cong add: prod.cong, rule sum.cong)
@@ -612,10 +612,10 @@
by (simp add: field_simps)
qed rule
-proposition det_mul:
+lemma%important det_mul:
fixes A B :: "'a::comm_ring_1^'n^'n"
shows "det (A ** B) = det A * det B"
-proof -
+proof%unimportant -
let ?U = "UNIV :: 'n set"
let ?F = "{f. (\<forall>i \<in> ?U. f i \<in> ?U) \<and> (\<forall>i. i \<notin> ?U \<longrightarrow> f i = i)}"
let ?PU = "{p. p permutes ?U}"
@@ -714,10 +714,10 @@
subsection%important \<open>Relation to invertibility\<close>
-proposition invertible_det_nz:
+lemma%important invertible_det_nz:
fixes A::"'a::{field}^'n^'n"
shows "invertible A \<longleftrightarrow> det A \<noteq> 0"
-proof (cases "invertible A")
+proof%unimportant (cases "invertible A")
case True
then obtain B :: "'a^'n^'n" where B: "A ** B = mat 1"
unfolding invertible_right_inverse by blast
@@ -748,7 +748,7 @@
qed
-lemma det_nz_iff_inj_gen:
+lemma%unimportant det_nz_iff_inj_gen:
fixes f :: "'a::field^'n \<Rightarrow> 'a::field^'n"
assumes "Vector_Spaces.linear (*s) (*s) f"
shows "det (matrix f) \<noteq> 0 \<longleftrightarrow> inj f"
@@ -763,14 +763,14 @@
by (metis assms invertible_det_nz invertible_left_inverse matrix_compose_gen matrix_id_mat_1)
qed
-lemma det_nz_iff_inj:
+lemma%unimportant det_nz_iff_inj:
fixes f :: "real^'n \<Rightarrow> real^'n"
assumes "linear f"
shows "det (matrix f) \<noteq> 0 \<longleftrightarrow> inj f"
using det_nz_iff_inj_gen[of f] assms
unfolding linear_matrix_vector_mul_eq .
-lemma det_eq_0_rank:
+lemma%unimportant det_eq_0_rank:
fixes A :: "real^'n^'n"
shows "det A = 0 \<longleftrightarrow> rank A < CARD('n)"
using invertible_det_nz [of A]
@@ -778,11 +778,11 @@
subsubsection%important \<open>Invertibility of matrices and corresponding linear functions\<close>
-proposition matrix_left_invertible_gen:
+lemma%important matrix_left_invertible_gen:
fixes f :: "'a::field^'m \<Rightarrow> 'a::field^'n"
assumes "Vector_Spaces.linear (*s) (*s) f"
shows "((\<exists>B. B ** matrix f = mat 1) \<longleftrightarrow> (\<exists>g. Vector_Spaces.linear (*s) (*s) g \<and> g \<circ> f = id))"
-proof safe
+proof%unimportant safe
fix B
assume 1: "B ** matrix f = mat 1"
show "\<exists>g. Vector_Spaces.linear (*s) (*s) g \<and> g \<circ> f = id"
@@ -801,12 +801,12 @@
then show "\<exists>B. B ** matrix f = mat 1" ..
qed
-lemma matrix_left_invertible:
+lemma%unimportant matrix_left_invertible:
"linear f \<Longrightarrow> ((\<exists>B. B ** matrix f = mat 1) \<longleftrightarrow> (\<exists>g. linear g \<and> g \<circ> f = id))" for f::"real^'m \<Rightarrow> real^'n"
using matrix_left_invertible_gen[of f]
by (auto simp: linear_matrix_vector_mul_eq)
-lemma matrix_right_invertible_gen:
+lemma%unimportant matrix_right_invertible_gen:
fixes f :: "'a::field^'m \<Rightarrow> 'a^'n"
assumes "Vector_Spaces.linear (*s) (*s) f"
shows "((\<exists>B. matrix f ** B = mat 1) \<longleftrightarrow> (\<exists>g. Vector_Spaces.linear (*s) (*s) g \<and> f \<circ> g = id))"
@@ -829,12 +829,12 @@
then show "\<exists>B. matrix f ** B = mat 1" ..
qed
-lemma matrix_right_invertible:
+lemma%unimportant matrix_right_invertible:
"linear f \<Longrightarrow> ((\<exists>B. matrix f ** B = mat 1) \<longleftrightarrow> (\<exists>g. linear g \<and> f \<circ> g = id))" for f::"real^'m \<Rightarrow> real^'n"
using matrix_right_invertible_gen[of f]
by (auto simp: linear_matrix_vector_mul_eq)
-lemma matrix_invertible_gen:
+lemma%unimportant matrix_invertible_gen:
fixes f :: "'a::field^'m \<Rightarrow> 'a::field^'n"
assumes "Vector_Spaces.linear (*s) (*s) f"
shows "invertible (matrix f) \<longleftrightarrow> (\<exists>g. Vector_Spaces.linear (*s) (*s) g \<and> f \<circ> g = id \<and> g \<circ> f = id)"
@@ -847,13 +847,13 @@
by (metis assms invertible_def matrix_compose_gen matrix_id_mat_1)
qed
-lemma matrix_invertible:
+lemma%unimportant matrix_invertible:
"linear f \<Longrightarrow> invertible (matrix f) \<longleftrightarrow> (\<exists>g. linear g \<and> f \<circ> g = id \<and> g \<circ> f = id)"
for f::"real^'m \<Rightarrow> real^'n"
using matrix_invertible_gen[of f]
by (auto simp: linear_matrix_vector_mul_eq)
-lemma invertible_eq_bij:
+lemma%unimportant invertible_eq_bij:
fixes m :: "'a::field^'m^'n"
shows "invertible m \<longleftrightarrow> bij ((*v) m)"
using matrix_invertible_gen[OF matrix_vector_mul_linear_gen, of m, simplified matrix_of_matrix_vector_mul]
@@ -863,13 +863,13 @@
subsection%important \<open>Cramer's rule\<close>
-proposition cramer_lemma_transpose:
+lemma%important cramer_lemma_transpose:
fixes A:: "'a::{field}^'n^'n"
and x :: "'a::{field}^'n"
shows "det ((\<chi> i. if i = k then sum (\<lambda>i. x$i *s row i A) (UNIV::'n set)
else row i A)::'a::{field}^'n^'n) = x$k * det A"
(is "?lhs = ?rhs")
-proof -
+proof%unimportant -
let ?U = "UNIV :: 'n set"
let ?Uk = "?U - {k}"
have U: "?U = insert k ?Uk"
@@ -899,10 +899,10 @@
done
qed
-proposition cramer_lemma:
+lemma%important cramer_lemma:
fixes A :: "'a::{field}^'n^'n"
shows "det((\<chi> i j. if j = k then (A *v x)$i else A$i$j):: 'a::{field}^'n^'n) = x$k * det A"
-proof -
+proof%unimportant -
let ?U = "UNIV :: 'n set"
have *: "\<And>c. sum (\<lambda>i. c i *s row i (transpose A)) ?U = sum (\<lambda>i. c i *s column i A) ?U"
by (auto intro: sum.cong)
@@ -916,11 +916,11 @@
done
qed
-theorem cramer:
+lemma%important cramer:
fixes A ::"'a::{field}^'n^'n"
assumes d0: "det A \<noteq> 0"
shows "A *v x = b \<longleftrightarrow> x = (\<chi> k. det(\<chi> i j. if j=k then b$i else A$i$j) / det A)"
-proof -
+proof%unimportant -
from d0 obtain B where B: "A ** B = mat 1" "B ** A = mat 1"
unfolding invertible_det_nz[symmetric] invertible_def
by blast
@@ -941,376 +941,10 @@
by auto
qed
-subsection%important \<open>Orthogonality of a transformation and matrix\<close>
-
-definition%important "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)"
-
-definition%important "orthogonal_matrix (Q::'a::semiring_1^'n^'n) \<longleftrightarrow>
- transpose Q ** Q = mat 1 \<and> Q ** transpose Q = mat 1"
-
-lemma orthogonal_transformation:
- "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v. norm (f v) = norm v)"
- unfolding orthogonal_transformation_def
- apply auto
- apply (erule_tac x=v in allE)+
- apply (simp add: norm_eq_sqrt_inner)
- apply (simp add: dot_norm linear_add[symmetric])
- done
-
-lemma orthogonal_transformation_id [simp]: "orthogonal_transformation (\<lambda>x. x)"
- by (simp add: linear_iff orthogonal_transformation_def)
-
-lemma orthogonal_orthogonal_transformation:
- "orthogonal_transformation f \<Longrightarrow> orthogonal (f x) (f y) \<longleftrightarrow> orthogonal x y"
- by (simp add: orthogonal_def orthogonal_transformation_def)
-
-lemma orthogonal_transformation_compose:
- "\<lbrakk>orthogonal_transformation f; orthogonal_transformation g\<rbrakk> \<Longrightarrow> orthogonal_transformation(f \<circ> g)"
- by (auto simp: orthogonal_transformation_def linear_compose)
-
-lemma orthogonal_transformation_neg:
- "orthogonal_transformation(\<lambda>x. -(f x)) \<longleftrightarrow> orthogonal_transformation f"
- by (auto simp: orthogonal_transformation_def dest: linear_compose_neg)
-
-lemma orthogonal_transformation_scaleR: "orthogonal_transformation f \<Longrightarrow> f (c *\<^sub>R v) = c *\<^sub>R f v"
- by (simp add: linear_iff orthogonal_transformation_def)
-
-lemma orthogonal_transformation_linear:
- "orthogonal_transformation f \<Longrightarrow> linear f"
- by (simp add: orthogonal_transformation_def)
-
-lemma orthogonal_transformation_inj:
- "orthogonal_transformation f \<Longrightarrow> inj f"
- unfolding orthogonal_transformation_def inj_on_def
- by (metis vector_eq)
-
-lemma orthogonal_transformation_surj:
- "orthogonal_transformation f \<Longrightarrow> surj f"
- for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
- by (simp add: linear_injective_imp_surjective orthogonal_transformation_inj orthogonal_transformation_linear)
-
-lemma orthogonal_transformation_bij:
- "orthogonal_transformation f \<Longrightarrow> bij f"
- for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
- by (simp add: bij_def orthogonal_transformation_inj orthogonal_transformation_surj)
-
-lemma orthogonal_transformation_inv:
- "orthogonal_transformation f \<Longrightarrow> orthogonal_transformation (inv f)"
- for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
- by (metis (no_types, hide_lams) bijection.inv_right bijection_def inj_linear_imp_inv_linear orthogonal_transformation orthogonal_transformation_bij orthogonal_transformation_inj)
-
-lemma orthogonal_transformation_norm:
- "orthogonal_transformation f \<Longrightarrow> norm (f x) = norm x"
- by (metis orthogonal_transformation)
-
-lemma orthogonal_matrix: "orthogonal_matrix (Q:: real ^'n^'n) \<longleftrightarrow> transpose Q ** Q = mat 1"
- by (metis matrix_left_right_inverse orthogonal_matrix_def)
-
-lemma orthogonal_matrix_id: "orthogonal_matrix (mat 1 :: _^'n^'n)"
- by (simp add: orthogonal_matrix_def)
-
-lemma orthogonal_matrix_mul:
- fixes A :: "real ^'n^'n"
- assumes "orthogonal_matrix A" "orthogonal_matrix B"
- shows "orthogonal_matrix(A ** B)"
- using assms
- by (simp add: orthogonal_matrix matrix_transpose_mul matrix_left_right_inverse matrix_mul_assoc)
-
-proposition orthogonal_transformation_matrix:
- fixes f:: "real^'n \<Rightarrow> real^'n"
- shows "orthogonal_transformation f \<longleftrightarrow> linear f \<and> orthogonal_matrix(matrix f)"
- (is "?lhs \<longleftrightarrow> ?rhs")
-proof -
- let ?mf = "matrix f"
- let ?ot = "orthogonal_transformation f"
- let ?U = "UNIV :: 'n set"
- have fU: "finite ?U" by simp
- let ?m1 = "mat 1 :: real ^'n^'n"
- {
- assume ot: ?ot
- from ot have lf: "Vector_Spaces.linear (*s) (*s) f" and fd: "\<And>v w. f v \<bullet> f w = v \<bullet> w"
- unfolding orthogonal_transformation_def orthogonal_matrix linear_def scalar_mult_eq_scaleR
- by blast+
- {
- fix i j
- let ?A = "transpose ?mf ** ?mf"
- have th0: "\<And>b (x::'a::comm_ring_1). (if b then 1 else 0)*x = (if b then x else 0)"
- "\<And>b (x::'a::comm_ring_1). x*(if b then 1 else 0) = (if b then x else 0)"
- by simp_all
- from fd[of "axis i 1" "axis j 1",
- simplified matrix_works[OF lf, symmetric] dot_matrix_vector_mul]
- have "?A$i$j = ?m1 $ i $ j"
- by (simp add: inner_vec_def matrix_matrix_mult_def columnvector_def rowvector_def
- th0 sum.delta[OF fU] mat_def axis_def)
- }
- then have "orthogonal_matrix ?mf"
- unfolding orthogonal_matrix
- by vector
- with lf have ?rhs
- unfolding linear_def scalar_mult_eq_scaleR
- by blast
- }
- moreover
- {
- assume lf: "Vector_Spaces.linear (*s) (*s) f" and om: "orthogonal_matrix ?mf"
- from lf om have ?lhs
- unfolding orthogonal_matrix_def norm_eq orthogonal_transformation
- apply (simp only: matrix_works[OF lf, symmetric] dot_matrix_vector_mul)
- apply (simp add: dot_matrix_product linear_def scalar_mult_eq_scaleR)
- done
- }
- ultimately show ?thesis
- by (auto simp: linear_def scalar_mult_eq_scaleR)
-qed
-
-theorem det_orthogonal_matrix:
- fixes Q:: "'a::linordered_idom^'n^'n"
- assumes oQ: "orthogonal_matrix Q"
- shows "det Q = 1 \<or> det Q = - 1"
-proof -
- have "Q ** transpose Q = mat 1"
- by (metis oQ orthogonal_matrix_def)
- then have "det (Q ** transpose Q) = det (mat 1:: 'a^'n^'n)"
- by simp
- then have "det Q * det Q = 1"
- by (simp add: det_mul)
- then show ?thesis
- by (simp add: square_eq_1_iff)
-qed
-
-lemma orthogonal_transformation_det [simp]:
- fixes f :: "real^'n \<Rightarrow> real^'n"
- shows "orthogonal_transformation f \<Longrightarrow> \<bar>det (matrix f)\<bar> = 1"
- using det_orthogonal_matrix orthogonal_transformation_matrix by fastforce
-
-
-subsection%important \<open>Linearity of scaling, and hence isometry, that preserves origin\<close>
-
-lemma scaling_linear:
- fixes f :: "'a::real_inner \<Rightarrow> 'a::real_inner"
- assumes f0: "f 0 = 0"
- and fd: "\<forall>x y. dist (f x) (f y) = c * dist x y"
- shows "linear f"
-proof -
- {
- fix v w
- have "norm (f x) = c * norm x" for x
- by (metis dist_0_norm f0 fd)
- then have "f v \<bullet> f w = c\<^sup>2 * (v \<bullet> w)"
- unfolding dot_norm_neg dist_norm[symmetric]
- by (simp add: fd power2_eq_square field_simps)
- }
- then show ?thesis
- unfolding linear_iff vector_eq[where 'a="'a"] scalar_mult_eq_scaleR
- by (simp add: inner_add field_simps)
-qed
-
-lemma isometry_linear:
- "f (0::'a::real_inner) = (0::'a) \<Longrightarrow> \<forall>x y. dist(f x) (f y) = dist x y \<Longrightarrow> linear f"
- by (rule scaling_linear[where c=1]) simp_all
-
-text \<open>Hence another formulation of orthogonal transformation\<close>
-
-lemma orthogonal_transformation_isometry:
- "orthogonal_transformation f \<longleftrightarrow> f(0::'a::real_inner) = (0::'a) \<and> (\<forall>x y. dist(f x) (f y) = dist x y)"
- unfolding orthogonal_transformation
- apply (auto simp: linear_0 isometry_linear)
- apply (metis (no_types, hide_lams) dist_norm linear_diff)
- by (metis dist_0_norm)
-
-
-lemma image_orthogonal_transformation_ball:
- fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
- assumes "orthogonal_transformation f"
- shows "f ` ball x r = ball (f x) r"
-proof (intro equalityI subsetI)
- fix y assume "y \<in> f ` ball x r"
- with assms show "y \<in> ball (f x) r"
- by (auto simp: orthogonal_transformation_isometry)
-next
- fix y assume y: "y \<in> ball (f x) r"
- then obtain z where z: "y = f z"
- using assms orthogonal_transformation_surj by blast
- with y assms show "y \<in> f ` ball x r"
- by (auto simp: orthogonal_transformation_isometry)
-qed
-
-lemma image_orthogonal_transformation_cball:
- fixes f :: "'a::euclidean_space \<Rightarrow> 'a"
- assumes "orthogonal_transformation f"
- shows "f ` cball x r = cball (f x) r"
-proof (intro equalityI subsetI)
- fix y assume "y \<in> f ` cball x r"
- with assms show "y \<in> cball (f x) r"
- by (auto simp: orthogonal_transformation_isometry)
-next
- fix y assume y: "y \<in> cball (f x) r"
- then obtain z where z: "y = f z"
- using assms orthogonal_transformation_surj by blast
- with y assms show "y \<in> f ` cball x r"
- by (auto simp: orthogonal_transformation_isometry)
-qed
-
-subsection%important \<open> We can find an orthogonal matrix taking any unit vector to any other\<close>
-
-lemma orthogonal_matrix_transpose [simp]:
- "orthogonal_matrix(transpose A) \<longleftrightarrow> orthogonal_matrix A"
- by (auto simp: orthogonal_matrix_def)
-
-lemma orthogonal_matrix_orthonormal_columns:
- fixes A :: "real^'n^'n"
- shows "orthogonal_matrix A \<longleftrightarrow>
- (\<forall>i. norm(column i A) = 1) \<and>
- (\<forall>i j. i \<noteq> j \<longrightarrow> orthogonal (column i A) (column j A))"
- by (auto simp: orthogonal_matrix matrix_mult_transpose_dot_column vec_eq_iff mat_def norm_eq_1 orthogonal_def)
-
-lemma orthogonal_matrix_orthonormal_rows:
- fixes A :: "real^'n^'n"
- shows "orthogonal_matrix A \<longleftrightarrow>
- (\<forall>i. norm(row i A) = 1) \<and>
- (\<forall>i j. i \<noteq> j \<longrightarrow> orthogonal (row i A) (row j A))"
- using orthogonal_matrix_orthonormal_columns [of "transpose A"] by simp
-
-theorem orthogonal_matrix_exists_basis:
- fixes a :: "real^'n"
- assumes "norm a = 1"
- obtains A where "orthogonal_matrix A" "A *v (axis k 1) = a"
-proof -
- obtain S where "a \<in> S" "pairwise orthogonal S" and noS: "\<And>x. x \<in> S \<Longrightarrow> norm x = 1"
- and "independent S" "card S = CARD('n)" "span S = UNIV"
- using vector_in_orthonormal_basis assms by force
- then obtain f0 where "bij_betw f0 (UNIV::'n set) S"
- by (metis finite_class.finite_UNIV finite_same_card_bij finiteI_independent)
- then obtain f where f: "bij_betw f (UNIV::'n set) S" and a: "a = f k"
- using bij_swap_iff [of k "inv f0 a" f0]
- by (metis UNIV_I \<open>a \<in> S\<close> bij_betw_inv_into_right bij_betw_swap_iff swap_apply1)
- show thesis
- proof
- have [simp]: "\<And>i. norm (f i) = 1"
- using bij_betwE [OF \<open>bij_betw f UNIV S\<close>] by (blast intro: noS)
- have [simp]: "\<And>i j. i \<noteq> j \<Longrightarrow> orthogonal (f i) (f j)"
- using \<open>pairwise orthogonal S\<close> \<open>bij_betw f UNIV S\<close>
- by (auto simp: pairwise_def bij_betw_def inj_on_def)
- show "orthogonal_matrix (\<chi> i j. f j $ i)"
- by (simp add: orthogonal_matrix_orthonormal_columns column_def)
- show "(\<chi> i j. f j $ i) *v axis k 1 = a"
- by (simp add: matrix_vector_mult_def axis_def a if_distrib cong: if_cong)
- qed
-qed
-
-lemma orthogonal_transformation_exists_1:
- fixes a b :: "real^'n"
- assumes "norm a = 1" "norm b = 1"
- obtains f where "orthogonal_transformation f" "f a = b"
-proof -
- obtain k::'n where True
- by simp
- obtain A B where AB: "orthogonal_matrix A" "orthogonal_matrix B" and eq: "A *v (axis k 1) = a" "B *v (axis k 1) = b"
- using orthogonal_matrix_exists_basis assms by metis
- let ?f = "\<lambda>x. (B ** transpose A) *v x"
- show thesis
- proof
- show "orthogonal_transformation ?f"
- by (subst orthogonal_transformation_matrix)
- (auto simp: AB orthogonal_matrix_mul)
- next
- show "?f a = b"
- using \<open>orthogonal_matrix A\<close> unfolding orthogonal_matrix_def
- by (metis eq matrix_mul_rid matrix_vector_mul_assoc)
- qed
-qed
-
-theorem orthogonal_transformation_exists:
- fixes a b :: "real^'n"
- assumes "norm a = norm b"
- obtains f where "orthogonal_transformation f" "f a = b"
-proof (cases "a = 0 \<or> b = 0")
- case True
- with assms show ?thesis
- using that by force
-next
- case False
- then obtain f where f: "orthogonal_transformation f" and eq: "f (a /\<^sub>R norm a) = (b /\<^sub>R norm b)"
- by (auto intro: orthogonal_transformation_exists_1 [of "a /\<^sub>R norm a" "b /\<^sub>R norm b"])
- show ?thesis
- proof
- interpret linear f
- using f by (simp add: orthogonal_transformation_linear)
- have "f a /\<^sub>R norm a = f (a /\<^sub>R norm a)"
- by (simp add: scale)
- also have "\<dots> = b /\<^sub>R norm a"
- by (simp add: eq assms [symmetric])
- finally show "f a = b"
- using False by auto
- qed (use f in auto)
-qed
-
-
-subsection%important \<open>Can extend an isometry from unit sphere\<close>
-
-lemma isometry_sphere_extend:
- fixes f:: "'a::real_inner \<Rightarrow> 'a"
- assumes f1: "\<And>x. norm x = 1 \<Longrightarrow> norm (f x) = 1"
- and fd1: "\<And>x y. \<lbrakk>norm x = 1; norm y = 1\<rbrakk> \<Longrightarrow> dist (f x) (f y) = dist x y"
- shows "\<exists>g. orthogonal_transformation g \<and> (\<forall>x. norm x = 1 \<longrightarrow> g x = f x)"
-proof -
- {
- fix x y x' y' u v u' v' :: "'a"
- assume H: "x = norm x *\<^sub>R u" "y = norm y *\<^sub>R v"
- "x' = norm x *\<^sub>R u'" "y' = norm y *\<^sub>R v'"
- and J: "norm u = 1" "norm u' = 1" "norm v = 1" "norm v' = 1" "norm(u' - v') = norm(u - v)"
- then have *: "u \<bullet> v = u' \<bullet> v' + v' \<bullet> u' - v \<bullet> u "
- by (simp add: norm_eq norm_eq_1 inner_add inner_diff)
- have "norm (norm x *\<^sub>R u' - norm y *\<^sub>R v') = norm (norm x *\<^sub>R u - norm y *\<^sub>R v)"
- using J by (simp add: norm_eq norm_eq_1 inner_diff * field_simps)
- then have "norm(x' - y') = norm(x - y)"
- using H by metis
- }
- note norm_eq = this
- let ?g = "\<lambda>x. if x = 0 then 0 else norm x *\<^sub>R f (x /\<^sub>R norm x)"
- have thfg: "?g x = f x" if "norm x = 1" for x
- using that by auto
- have thd: "dist (?g x) (?g y) = dist x y" for x y
- proof (cases "x=0 \<or> y=0")
- case False
- show "dist (?g x) (?g y) = dist x y"
- unfolding dist_norm
- proof (rule norm_eq)
- show "x = norm x *\<^sub>R (x /\<^sub>R norm x)" "y = norm y *\<^sub>R (y /\<^sub>R norm y)"
- "norm (f (x /\<^sub>R norm x)) = 1" "norm (f (y /\<^sub>R norm y)) = 1"
- using False f1 by auto
- qed (use False in \<open>auto simp: field_simps intro: f1 fd1[unfolded dist_norm]\<close>)
- qed (auto simp: f1)
- show ?thesis
- unfolding orthogonal_transformation_isometry
- by (rule exI[where x= ?g]) (metis thfg thd)
-qed
-
-subsection%important \<open>Rotation, reflection, rotoinversion\<close>
-
-definition%important "rotation_matrix Q \<longleftrightarrow> orthogonal_matrix Q \<and> det Q = 1"
-definition%important "rotoinversion_matrix Q \<longleftrightarrow> orthogonal_matrix Q \<and> det Q = - 1"
-
-lemma orthogonal_rotation_or_rotoinversion:
- fixes Q :: "'a::linordered_idom^'n^'n"
- shows " orthogonal_matrix Q \<longleftrightarrow> rotation_matrix Q \<or> rotoinversion_matrix Q"
- by (metis rotoinversion_matrix_def rotation_matrix_def det_orthogonal_matrix)
-
-text \<open>Explicit formulas for low dimensions\<close>
-
-lemma prod_neutral_const: "prod f {(1::nat)..1} = f 1"
- by simp
-
-lemma prod_2: "prod f {(1::nat)..2} = f 1 * f 2"
- by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute)
-
-lemma prod_3: "prod f {(1::nat)..3} = f 1 * f 2 * f 3"
- by (simp add: eval_nat_numeral atLeastAtMostSuc_conv mult.commute)
-
-lemma det_1: "det (A::'a::comm_ring_1^1^1) = A$1$1"
+lemma%unimportant det_1: "det (A::'a::comm_ring_1^1^1) = A$1$1"
by (simp add: det_def sign_id)
-lemma det_2: "det (A::'a::comm_ring_1^2^2) = A$1$1 * A$2$2 - A$1$2 * A$2$1"
+lemma%unimportant det_2: "det (A::'a::comm_ring_1^2^2) = A$1$1 * A$2$2 - A$1$2 * A$2$1"
proof -
have f12: "finite {2::2}" "1 \<notin> {2::2}" by auto
show ?thesis
@@ -1320,7 +954,7 @@
by (simp add: sign_swap_id sign_id swap_id_eq)
qed
-lemma det_3:
+lemma%unimportant det_3:
"det (A::'a::comm_ring_1^3^3) =
A$1$1 * A$2$2 * A$3$3 +
A$1$2 * A$2$3 * A$3$1 +
@@ -1344,7 +978,7 @@
text\<open> Slightly stronger results giving rotation, but only in two or more dimensions\<close>
-lemma rotation_matrix_exists_basis:
+lemma%unimportant rotation_matrix_exists_basis:
fixes a :: "real^'n"
assumes 2: "2 \<le> CARD('n)" and "norm a = 1"
obtains A where "rotation_matrix A" "A *v (axis k 1) = a"
@@ -1383,7 +1017,7 @@
qed
qed
-lemma rotation_exists_1:
+lemma%unimportant rotation_exists_1:
fixes a :: "real^'n"
assumes "2 \<le> CARD('n)" "norm a = 1" "norm b = 1"
obtains f where "orthogonal_transformation f" "det(matrix f) = 1" "f a = b"
@@ -1406,7 +1040,7 @@
qed
qed
-lemma rotation_exists:
+lemma%unimportant rotation_exists:
fixes a :: "real^'n"
assumes 2: "2 \<le> CARD('n)" and eq: "norm a = norm b"
obtains f where "orthogonal_transformation f" "det(matrix f) = 1" "f a = b"
@@ -1428,7 +1062,7 @@
with f show thesis ..
qed
-lemma rotation_rightward_line:
+lemma%unimportant rotation_rightward_line:
fixes a :: "real^'n"
obtains f where "orthogonal_transformation f" "2 \<le> CARD('n) \<Longrightarrow> det(matrix f) = 1"
"f(norm a *\<^sub>R axis k 1) = a"
--- a/src/HOL/Analysis/Elementary_Metric_Spaces.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Elementary_Metric_Spaces.thy Thu Jan 17 16:08:41 2019 +0000
@@ -4,13 +4,15 @@
Author: Brian Huffman, Portland State University
*)
-section \<open>Elementary Metric Spaces\<close>
+chapter \<open>Functional Analysis\<close>
theory Elementary_Metric_Spaces
imports
Abstract_Topology_2
begin
+section \<open>Elementary Metric Spaces\<close>
+
subsection \<open>Open and closed balls\<close>
definition%important ball :: "'a::metric_space \<Rightarrow> real \<Rightarrow> 'a set"
--- a/src/HOL/Analysis/Elementary_Topology.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Elementary_Topology.thy Thu Jan 17 16:08:41 2019 +0000
@@ -4,7 +4,7 @@
Author: Brian Huffman, Portland State University
*)
-section \<open>Elementary Topology\<close>
+chapter \<open>Topology\<close>
theory Elementary_Topology
imports
@@ -14,6 +14,8 @@
begin
+section \<open>Elementary Topology\<close>
+
subsection \<open>TODO: move?\<close>
lemma open_subopen: "open S \<longleftrightarrow> (\<forall>x\<in>S. \<exists>T. open T \<and> x \<in> T \<and> T \<subseteq> S)"
--- a/src/HOL/Analysis/Inner_Product.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Inner_Product.thy Thu Jan 17 16:08:41 2019 +0000
@@ -462,4 +462,12 @@
lemmas has_derivative_norm = GDERIV_norm [unfolded gderiv_def]
+bundle inner_syntax begin
+notation inner (infix "\<bullet>" 70)
end
+
+bundle no_inner_syntax begin
+no_notation inner (infix "\<bullet>" 70)
+end
+
+end
--- a/src/HOL/Analysis/L2_Norm.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/L2_Norm.thy Thu Jan 17 16:08:41 2019 +0000
@@ -2,12 +2,14 @@
Author: Brian Huffman, Portland State University
*)
-section \<open>L2 Norm\<close>
+chapter \<open>Linear Algebra\<close>
theory L2_Norm
imports Complex_Main
begin
+section \<open>L2 Norm\<close>
+
definition%important L2_set :: "('a \<Rightarrow> real) \<Rightarrow> 'a set \<Rightarrow> real" where
"L2_set f A = sqrt (\<Sum>i\<in>A. (f i)\<^sup>2)"
--- a/src/HOL/Analysis/Linear_Algebra.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Linear_Algebra.thy Thu Jan 17 16:08:41 2019 +0000
@@ -30,10 +30,83 @@
lemma finite_Atleast_Atmost_nat[simp]: "finite {f x |x. x \<in> (UNIV::'a::finite set)}"
using finite finite_image_set by blast
+lemma substdbasis_expansion_unique:
+ includes inner_syntax
+ assumes d: "d \<subseteq> Basis"
+ shows "(\<Sum>i\<in>d. f i *\<^sub>R i) = (x::'a::euclidean_space) \<longleftrightarrow>
+ (\<forall>i\<in>Basis. (i \<in> d \<longrightarrow> f i = x \<bullet> i) \<and> (i \<notin> d \<longrightarrow> x \<bullet> i = 0))"
+proof -
+ have *: "\<And>x a b P. x * (if P then a else b) = (if P then x * a else x * b)"
+ by auto
+ have **: "finite d"
+ by (auto intro: finite_subset[OF assms])
+ have ***: "\<And>i. i \<in> Basis \<Longrightarrow> (\<Sum>i\<in>d. f i *\<^sub>R i) \<bullet> i = (\<Sum>x\<in>d. if x = i then f x else 0)"
+ using d
+ by (auto intro!: sum.cong simp: inner_Basis inner_sum_left)
+ show ?thesis
+ unfolding euclidean_eq_iff[where 'a='a] by (auto simp: sum.delta[OF **] ***)
+qed
+
+lemma independent_substdbasis: "d \<subseteq> Basis \<Longrightarrow> independent d"
+ by (rule independent_mono[OF independent_Basis])
+
+lemma sum_not_0: "sum f A \<noteq> 0 \<Longrightarrow> \<exists>a \<in> A. f a \<noteq> 0"
+ by (rule ccontr) auto
+
+lemma subset_translation_eq [simp]:
+ fixes a :: "'a::real_vector" shows "(+) a ` s \<subseteq> (+) a ` t \<longleftrightarrow> s \<subseteq> t"
+ by auto
+
+lemma translate_inj_on:
+ fixes A :: "'a::ab_group_add set"
+ shows "inj_on (\<lambda>x. a + x) A"
+ unfolding inj_on_def by auto
+
+lemma translation_assoc:
+ fixes a b :: "'a::ab_group_add"
+ shows "(\<lambda>x. b + x) ` ((\<lambda>x. a + x) ` S) = (\<lambda>x. (a + b) + x) ` S"
+ by auto
+
+lemma translation_invert:
+ fixes a :: "'a::ab_group_add"
+ assumes "(\<lambda>x. a + x) ` A = (\<lambda>x. a + x) ` B"
+ shows "A = B"
+proof -
+ have "(\<lambda>x. -a + x) ` ((\<lambda>x. a + x) ` A) = (\<lambda>x. - a + x) ` ((\<lambda>x. a + x) ` B)"
+ using assms by auto
+ then show ?thesis
+ using translation_assoc[of "-a" a A] translation_assoc[of "-a" a B] by auto
+qed
+
+lemma translation_galois:
+ fixes a :: "'a::ab_group_add"
+ shows "T = ((\<lambda>x. a + x) ` S) \<longleftrightarrow> S = ((\<lambda>x. (- a) + x) ` T)"
+ using translation_assoc[of "-a" a S]
+ apply auto
+ using translation_assoc[of a "-a" T]
+ apply auto
+ done
+
+lemma translation_inverse_subset:
+ assumes "((\<lambda>x. - a + x) ` V) \<le> (S :: 'n::ab_group_add set)"
+ shows "V \<le> ((\<lambda>x. a + x) ` S)"
+proof -
+ {
+ fix x
+ assume "x \<in> V"
+ then have "x-a \<in> S" using assms by auto
+ then have "x \<in> {a + v |v. v \<in> S}"
+ apply auto
+ apply (rule exI[of _ "x-a"], simp)
+ done
+ then have "x \<in> ((\<lambda>x. a+x) ` S)" by auto
+ }
+ then show ?thesis by auto
+qed
subsection%unimportant \<open>More interesting properties of the norm\<close>
-notation inner (infix "\<bullet>" 70)
+unbundle inner_syntax
text\<open>Equality of vectors in terms of \<^term>\<open>(\<bullet>)\<close> products.\<close>
@@ -224,6 +297,66 @@
qed
+subsection%important \<open>Orthogonality of a transformation\<close>
+
+definition%important "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v w. f v \<bullet> f w = v \<bullet> w)"
+
+lemma%unimportant orthogonal_transformation:
+ "orthogonal_transformation f \<longleftrightarrow> linear f \<and> (\<forall>v. norm (f v) = norm v)"
+ unfolding orthogonal_transformation_def
+ apply auto
+ apply (erule_tac x=v in allE)+
+ apply (simp add: norm_eq_sqrt_inner)
+ apply (simp add: dot_norm linear_add[symmetric])
+ done
+
+lemma%unimportant orthogonal_transformation_id [simp]: "orthogonal_transformation (\<lambda>x. x)"
+ by (simp add: linear_iff orthogonal_transformation_def)
+
+lemma%unimportant orthogonal_orthogonal_transformation:
+ "orthogonal_transformation f \<Longrightarrow> orthogonal (f x) (f y) \<longleftrightarrow> orthogonal x y"
+ by (simp add: orthogonal_def orthogonal_transformation_def)
+
+lemma%unimportant orthogonal_transformation_compose:
+ "\<lbrakk>orthogonal_transformation f; orthogonal_transformation g\<rbrakk> \<Longrightarrow> orthogonal_transformation(f \<circ> g)"
+ by (auto simp: orthogonal_transformation_def linear_compose)
+
+lemma%unimportant orthogonal_transformation_neg:
+ "orthogonal_transformation(\<lambda>x. -(f x)) \<longleftrightarrow> orthogonal_transformation f"
+ by (auto simp: orthogonal_transformation_def dest: linear_compose_neg)
+
+lemma%unimportant orthogonal_transformation_scaleR: "orthogonal_transformation f \<Longrightarrow> f (c *\<^sub>R v) = c *\<^sub>R f v"
+ by (simp add: linear_iff orthogonal_transformation_def)
+
+lemma%unimportant orthogonal_transformation_linear:
+ "orthogonal_transformation f \<Longrightarrow> linear f"
+ by (simp add: orthogonal_transformation_def)
+
+lemma%unimportant orthogonal_transformation_inj:
+ "orthogonal_transformation f \<Longrightarrow> inj f"
+ unfolding orthogonal_transformation_def inj_on_def
+ by (metis vector_eq)
+
+lemma%unimportant orthogonal_transformation_surj:
+ "orthogonal_transformation f \<Longrightarrow> surj f"
+ for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
+ by (simp add: linear_injective_imp_surjective orthogonal_transformation_inj orthogonal_transformation_linear)
+
+lemma%unimportant orthogonal_transformation_bij:
+ "orthogonal_transformation f \<Longrightarrow> bij f"
+ for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
+ by (simp add: bij_def orthogonal_transformation_inj orthogonal_transformation_surj)
+
+lemma%unimportant orthogonal_transformation_inv:
+ "orthogonal_transformation f \<Longrightarrow> orthogonal_transformation (inv f)"
+ for f :: "'a::euclidean_space \<Rightarrow> 'a::euclidean_space"
+ by (metis (no_types, hide_lams) bijection.inv_right bijection_def inj_linear_imp_inv_linear orthogonal_transformation orthogonal_transformation_bij orthogonal_transformation_inj)
+
+lemma%unimportant orthogonal_transformation_norm:
+ "orthogonal_transformation f \<Longrightarrow> norm (f x) = norm x"
+ by (metis orthogonal_transformation)
+
+
subsection \<open>Bilinear functions\<close>
definition%important
@@ -1210,4 +1343,540 @@
qed
qed
+
+subsection\<open>Properties of special hyperplanes\<close>
+
+lemma subspace_hyperplane: "subspace {x. a \<bullet> x = 0}"
+ by (simp add: subspace_def inner_right_distrib)
+
+lemma subspace_hyperplane2: "subspace {x. x \<bullet> a = 0}"
+ by (simp add: inner_commute inner_right_distrib subspace_def)
+
+lemma special_hyperplane_span:
+ fixes S :: "'n::euclidean_space set"
+ assumes "k \<in> Basis"
+ shows "{x. k \<bullet> x = 0} = span (Basis - {k})"
+proof -
+ have *: "x \<in> span (Basis - {k})" if "k \<bullet> x = 0" for x
+ proof -
+ have "x = (\<Sum>b\<in>Basis. (x \<bullet> b) *\<^sub>R b)"
+ by (simp add: euclidean_representation)
+ also have "... = (\<Sum>b \<in> Basis - {k}. (x \<bullet> b) *\<^sub>R b)"
+ by (auto simp: sum.remove [of _ k] inner_commute assms that)
+ finally have "x = (\<Sum>b\<in>Basis - {k}. (x \<bullet> b) *\<^sub>R b)" .
+ then show ?thesis
+ by (simp add: span_finite)
+ qed
+ show ?thesis
+ apply (rule span_subspace [symmetric])
+ using assms
+ apply (auto simp: inner_not_same_Basis intro: * subspace_hyperplane)
+ done
+qed
+
+lemma dim_special_hyperplane:
+ fixes k :: "'n::euclidean_space"
+ shows "k \<in> Basis \<Longrightarrow> dim {x. k \<bullet> x = 0} = DIM('n) - 1"
+apply (simp add: special_hyperplane_span)
+apply (rule dim_unique [OF subset_refl])
+apply (auto simp: independent_substdbasis)
+apply (metis member_remove remove_def span_base)
+done
+
+proposition dim_hyperplane:
+ fixes a :: "'a::euclidean_space"
+ assumes "a \<noteq> 0"
+ shows "dim {x. a \<bullet> x = 0} = DIM('a) - 1"
+proof -
+ have span0: "span {x. a \<bullet> x = 0} = {x. a \<bullet> x = 0}"
+ by (rule span_unique) (auto simp: subspace_hyperplane)
+ then obtain B where "independent B"
+ and Bsub: "B \<subseteq> {x. a \<bullet> x = 0}"
+ and subspB: "{x. a \<bullet> x = 0} \<subseteq> span B"
+ and card0: "(card B = dim {x. a \<bullet> x = 0})"
+ and ortho: "pairwise orthogonal B"
+ using orthogonal_basis_exists by metis
+ with assms have "a \<notin> span B"
+ by (metis (mono_tags, lifting) span_eq inner_eq_zero_iff mem_Collect_eq span0)
+ then have ind: "independent (insert a B)"
+ by (simp add: \<open>independent B\<close> independent_insert)
+ have "finite B"
+ using \<open>independent B\<close> independent_bound by blast
+ have "UNIV \<subseteq> span (insert a B)"
+ proof fix y::'a
+ obtain r z where z: "y = r *\<^sub>R a + z" "a \<bullet> z = 0"
+ apply (rule_tac r="(a \<bullet> y) / (a \<bullet> a)" and z = "y - ((a \<bullet> y) / (a \<bullet> a)) *\<^sub>R a" in that)
+ using assms
+ by (auto simp: algebra_simps)
+ show "y \<in> span (insert a B)"
+ by (metis (mono_tags, lifting) z Bsub span_eq_iff
+ add_diff_cancel_left' mem_Collect_eq span0 span_breakdown_eq span_subspace subspB)
+ qed
+ then have dima: "DIM('a) = dim(insert a B)"
+ by (metis independent_Basis span_Basis dim_eq_card top.extremum_uniqueI)
+ then show ?thesis
+ by (metis (mono_tags, lifting) Bsub Diff_insert_absorb \<open>a \<notin> span B\<close> ind card0
+ card_Diff_singleton dim_span indep_card_eq_dim_span insertI1 subsetCE
+ subspB)
+qed
+
+lemma lowdim_eq_hyperplane:
+ fixes S :: "'a::euclidean_space set"
+ assumes "dim S = DIM('a) - 1"
+ obtains a where "a \<noteq> 0" and "span S = {x. a \<bullet> x = 0}"
+proof -
+ have dimS: "dim S < DIM('a)"
+ by (simp add: assms)
+ then obtain b where b: "b \<noteq> 0" "span S \<subseteq> {a. b \<bullet> a = 0}"
+ using lowdim_subset_hyperplane [of S] by fastforce
+ show ?thesis
+ apply (rule that[OF b(1)])
+ apply (rule subspace_dim_equal)
+ by (auto simp: assms b dim_hyperplane dim_span subspace_hyperplane
+ subspace_span)
+qed
+
+lemma dim_eq_hyperplane:
+ fixes S :: "'n::euclidean_space set"
+ shows "dim S = DIM('n) - 1 \<longleftrightarrow> (\<exists>a. a \<noteq> 0 \<and> span S = {x. a \<bullet> x = 0})"
+by (metis One_nat_def dim_hyperplane dim_span lowdim_eq_hyperplane)
+
+
+subsection\<open> Orthogonal bases, Gram-Schmidt process, and related theorems\<close>
+
+lemma pairwise_orthogonal_independent:
+ assumes "pairwise orthogonal S" and "0 \<notin> S"
+ shows "independent S"
+proof -
+ have 0: "\<And>x y. \<lbrakk>x \<noteq> y; x \<in> S; y \<in> S\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ using assms by (simp add: pairwise_def orthogonal_def)
+ have "False" if "a \<in> S" and a: "a \<in> span (S - {a})" for a
+ proof -
+ obtain T U where "T \<subseteq> S - {a}" "a = (\<Sum>v\<in>T. U v *\<^sub>R v)"
+ using a by (force simp: span_explicit)
+ then have "a \<bullet> a = a \<bullet> (\<Sum>v\<in>T. U v *\<^sub>R v)"
+ by simp
+ also have "... = 0"
+ apply (simp add: inner_sum_right)
+ apply (rule comm_monoid_add_class.sum.neutral)
+ by (metis "0" DiffE \<open>T \<subseteq> S - {a}\<close> mult_not_zero singletonI subsetCE \<open>a \<in> S\<close>)
+ finally show ?thesis
+ using \<open>0 \<notin> S\<close> \<open>a \<in> S\<close> by auto
+ qed
+ then show ?thesis
+ by (force simp: dependent_def)
+qed
+
+lemma pairwise_orthogonal_imp_finite:
+ fixes S :: "'a::euclidean_space set"
+ assumes "pairwise orthogonal S"
+ shows "finite S"
+proof -
+ have "independent (S - {0})"
+ apply (rule pairwise_orthogonal_independent)
+ apply (metis Diff_iff assms pairwise_def)
+ by blast
+ then show ?thesis
+ by (meson independent_imp_finite infinite_remove)
+qed
+
+lemma subspace_orthogonal_to_vector: "subspace {y. orthogonal x y}"
+ by (simp add: subspace_def orthogonal_clauses)
+
+lemma subspace_orthogonal_to_vectors: "subspace {y. \<forall>x \<in> S. orthogonal x y}"
+ by (simp add: subspace_def orthogonal_clauses)
+
+lemma orthogonal_to_span:
+ assumes a: "a \<in> span S" and x: "\<And>y. y \<in> S \<Longrightarrow> orthogonal x y"
+ shows "orthogonal x a"
+ by (metis a orthogonal_clauses(1,2,4)
+ span_induct_alt x)
+
+proposition Gram_Schmidt_step:
+ fixes S :: "'a::euclidean_space set"
+ assumes S: "pairwise orthogonal S" and x: "x \<in> span S"
+ shows "orthogonal x (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b))"
+proof -
+ have "finite S"
+ by (simp add: S pairwise_orthogonal_imp_finite)
+ have "orthogonal (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)) x"
+ if "x \<in> S" for x
+ proof -
+ have "a \<bullet> x = (\<Sum>y\<in>S. if y = x then y \<bullet> a else 0)"
+ by (simp add: \<open>finite S\<close> inner_commute sum.delta that)
+ also have "... = (\<Sum>b\<in>S. b \<bullet> a * (b \<bullet> x) / (b \<bullet> b))"
+ apply (rule sum.cong [OF refl], simp)
+ by (meson S orthogonal_def pairwise_def that)
+ finally show ?thesis
+ by (simp add: orthogonal_def algebra_simps inner_sum_left)
+ qed
+ then show ?thesis
+ using orthogonal_to_span orthogonal_commute x by blast
+qed
+
+
+lemma orthogonal_extension_aux:
+ fixes S :: "'a::euclidean_space set"
+ assumes "finite T" "finite S" "pairwise orthogonal S"
+ shows "\<exists>U. pairwise orthogonal (S \<union> U) \<and> span (S \<union> U) = span (S \<union> T)"
+using assms
+proof (induction arbitrary: S)
+ case empty then show ?case
+ by simp (metis sup_bot_right)
+next
+ case (insert a T)
+ have 0: "\<And>x y. \<lbrakk>x \<noteq> y; x \<in> S; y \<in> S\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ using insert by (simp add: pairwise_def orthogonal_def)
+ define a' where "a' = a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)"
+ obtain U where orthU: "pairwise orthogonal (S \<union> insert a' U)"
+ and spanU: "span (insert a' S \<union> U) = span (insert a' S \<union> T)"
+ by (rule exE [OF insert.IH [of "insert a' S"]])
+ (auto simp: Gram_Schmidt_step a'_def insert.prems orthogonal_commute
+ pairwise_orthogonal_insert span_clauses)
+ have orthS: "\<And>x. x \<in> S \<Longrightarrow> a' \<bullet> x = 0"
+ apply (simp add: a'_def)
+ using Gram_Schmidt_step [OF \<open>pairwise orthogonal S\<close>]
+ apply (force simp: orthogonal_def inner_commute span_superset [THEN subsetD])
+ done
+ have "span (S \<union> insert a' U) = span (insert a' (S \<union> T))"
+ using spanU by simp
+ also have "... = span (insert a (S \<union> T))"
+ apply (rule eq_span_insert_eq)
+ apply (simp add: a'_def span_neg span_sum span_base span_mul)
+ done
+ also have "... = span (S \<union> insert a T)"
+ by simp
+ finally show ?case
+ by (rule_tac x="insert a' U" in exI) (use orthU in auto)
+qed
+
+
+proposition orthogonal_extension:
+ fixes S :: "'a::euclidean_space set"
+ assumes S: "pairwise orthogonal S"
+ obtains U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> T)"
+proof -
+ obtain B where "finite B" "span B = span T"
+ using basis_subspace_exists [of "span T"] subspace_span by metis
+ with orthogonal_extension_aux [of B S]
+ obtain U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> B)"
+ using assms pairwise_orthogonal_imp_finite by auto
+ with \<open>span B = span T\<close> show ?thesis
+ by (rule_tac U=U in that) (auto simp: span_Un)
+qed
+
+corollary%unimportant orthogonal_extension_strong:
+ fixes S :: "'a::euclidean_space set"
+ assumes S: "pairwise orthogonal S"
+ obtains U where "U \<inter> (insert 0 S) = {}" "pairwise orthogonal (S \<union> U)"
+ "span (S \<union> U) = span (S \<union> T)"
+proof -
+ obtain U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> T)"
+ using orthogonal_extension assms by blast
+ then show ?thesis
+ apply (rule_tac U = "U - (insert 0 S)" in that)
+ apply blast
+ apply (force simp: pairwise_def)
+ apply (metis Un_Diff_cancel Un_insert_left span_redundant span_zero)
+ done
+qed
+
+subsection\<open>Decomposing a vector into parts in orthogonal subspaces\<close>
+
+text\<open>existence of orthonormal basis for a subspace.\<close>
+
+lemma orthogonal_spanningset_subspace:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "subspace S"
+ obtains B where "B \<subseteq> S" "pairwise orthogonal B" "span B = S"
+proof -
+ obtain B where "B \<subseteq> S" "independent B" "S \<subseteq> span B" "card B = dim S"
+ using basis_exists by blast
+ with orthogonal_extension [of "{}" B]
+ show ?thesis
+ by (metis Un_empty_left assms pairwise_empty span_superset span_subspace that)
+qed
+
+lemma orthogonal_basis_subspace:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "subspace S"
+ obtains B where "0 \<notin> B" "B \<subseteq> S" "pairwise orthogonal B" "independent B"
+ "card B = dim S" "span B = S"
+proof -
+ obtain B where "B \<subseteq> S" "pairwise orthogonal B" "span B = S"
+ using assms orthogonal_spanningset_subspace by blast
+ then show ?thesis
+ apply (rule_tac B = "B - {0}" in that)
+ apply (auto simp: indep_card_eq_dim_span pairwise_subset pairwise_orthogonal_independent elim: pairwise_subset)
+ done
+qed
+
+proposition orthonormal_basis_subspace:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "subspace S"
+ obtains B where "B \<subseteq> S" "pairwise orthogonal B"
+ and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1"
+ and "independent B" "card B = dim S" "span B = S"
+proof -
+ obtain B where "0 \<notin> B" "B \<subseteq> S"
+ and orth: "pairwise orthogonal B"
+ and "independent B" "card B = dim S" "span B = S"
+ by (blast intro: orthogonal_basis_subspace [OF assms])
+ have 1: "(\<lambda>x. x /\<^sub>R norm x) ` B \<subseteq> S"
+ using \<open>span B = S\<close> span_superset span_mul by fastforce
+ have 2: "pairwise orthogonal ((\<lambda>x. x /\<^sub>R norm x) ` B)"
+ using orth by (force simp: pairwise_def orthogonal_clauses)
+ have 3: "\<And>x. x \<in> (\<lambda>x. x /\<^sub>R norm x) ` B \<Longrightarrow> norm x = 1"
+ by (metis (no_types, lifting) \<open>0 \<notin> B\<close> image_iff norm_sgn sgn_div_norm)
+ have 4: "independent ((\<lambda>x. x /\<^sub>R norm x) ` B)"
+ by (metis "2" "3" norm_zero pairwise_orthogonal_independent zero_neq_one)
+ have "inj_on (\<lambda>x. x /\<^sub>R norm x) B"
+ proof
+ fix x y
+ assume "x \<in> B" "y \<in> B" "x /\<^sub>R norm x = y /\<^sub>R norm y"
+ moreover have "\<And>i. i \<in> B \<Longrightarrow> norm (i /\<^sub>R norm i) = 1"
+ using 3 by blast
+ ultimately show "x = y"
+ by (metis norm_eq_1 orth orthogonal_clauses(7) orthogonal_commute orthogonal_def pairwise_def zero_neq_one)
+ qed
+ then have 5: "card ((\<lambda>x. x /\<^sub>R norm x) ` B) = dim S"
+ by (metis \<open>card B = dim S\<close> card_image)
+ have 6: "span ((\<lambda>x. x /\<^sub>R norm x) ` B) = S"
+ by (metis "1" "4" "5" assms card_eq_dim independent_imp_finite span_subspace)
+ show ?thesis
+ by (rule that [OF 1 2 3 4 5 6])
+qed
+
+
+proposition%unimportant orthogonal_to_subspace_exists_gen:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "span S \<subset> span T"
+ obtains x where "x \<noteq> 0" "x \<in> span T" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
+proof -
+ obtain B where "B \<subseteq> span S" and orthB: "pairwise orthogonal B"
+ and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1"
+ and "independent B" "card B = dim S" "span B = span S"
+ by (rule orthonormal_basis_subspace [of "span S", OF subspace_span])
+ (auto simp: dim_span)
+ with assms obtain u where spanBT: "span B \<subseteq> span T" and "u \<notin> span B" "u \<in> span T"
+ by auto
+ obtain C where orthBC: "pairwise orthogonal (B \<union> C)" and spanBC: "span (B \<union> C) = span (B \<union> {u})"
+ by (blast intro: orthogonal_extension [OF orthB])
+ show thesis
+ proof (cases "C \<subseteq> insert 0 B")
+ case True
+ then have "C \<subseteq> span B"
+ using span_eq
+ by (metis span_insert_0 subset_trans)
+ moreover have "u \<in> span (B \<union> C)"
+ using \<open>span (B \<union> C) = span (B \<union> {u})\<close> span_superset by force
+ ultimately show ?thesis
+ using True \<open>u \<notin> span B\<close>
+ by (metis Un_insert_left span_insert_0 sup.orderE)
+ next
+ case False
+ then obtain x where "x \<in> C" "x \<noteq> 0" "x \<notin> B"
+ by blast
+ then have "x \<in> span T"
+ by (metis (no_types, lifting) Un_insert_right Un_upper2 \<open>u \<in> span T\<close> spanBT spanBC
+ \<open>u \<in> span T\<close> insert_subset span_superset span_mono
+ span_span subsetCE subset_trans sup_bot.comm_neutral)
+ moreover have "orthogonal x y" if "y \<in> span B" for y
+ using that
+ proof (rule span_induct)
+ show "subspace {a. orthogonal x a}"
+ by (simp add: subspace_orthogonal_to_vector)
+ show "\<And>b. b \<in> B \<Longrightarrow> orthogonal x b"
+ by (metis Un_iff \<open>x \<in> C\<close> \<open>x \<notin> B\<close> orthBC pairwise_def)
+ qed
+ ultimately show ?thesis
+ using \<open>x \<noteq> 0\<close> that \<open>span B = span S\<close> by auto
+ qed
+qed
+
+corollary%unimportant orthogonal_to_subspace_exists:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "dim S < DIM('a)"
+ obtains x where "x \<noteq> 0" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
+proof -
+have "span S \<subset> UNIV"
+ by (metis (mono_tags) UNIV_I assms inner_eq_zero_iff less_le lowdim_subset_hyperplane
+ mem_Collect_eq top.extremum_strict top.not_eq_extremum)
+ with orthogonal_to_subspace_exists_gen [of S UNIV] that show ?thesis
+ by (auto simp: span_UNIV)
+qed
+
+corollary%unimportant orthogonal_to_vector_exists:
+ fixes x :: "'a :: euclidean_space"
+ assumes "2 \<le> DIM('a)"
+ obtains y where "y \<noteq> 0" "orthogonal x y"
+proof -
+ have "dim {x} < DIM('a)"
+ using assms by auto
+ then show thesis
+ by (rule orthogonal_to_subspace_exists) (simp add: orthogonal_commute span_base that)
+qed
+
+proposition%unimportant orthogonal_subspace_decomp_exists:
+ fixes S :: "'a :: euclidean_space set"
+ obtains y z
+ where "y \<in> span S"
+ and "\<And>w. w \<in> span S \<Longrightarrow> orthogonal z w"
+ and "x = y + z"
+proof -
+ obtain T where "0 \<notin> T" "T \<subseteq> span S" "pairwise orthogonal T" "independent T"
+ "card T = dim (span S)" "span T = span S"
+ using orthogonal_basis_subspace subspace_span by blast
+ let ?a = "\<Sum>b\<in>T. (b \<bullet> x / (b \<bullet> b)) *\<^sub>R b"
+ have orth: "orthogonal (x - ?a) w" if "w \<in> span S" for w
+ by (simp add: Gram_Schmidt_step \<open>pairwise orthogonal T\<close> \<open>span T = span S\<close>
+ orthogonal_commute that)
+ show ?thesis
+ apply (rule_tac y = "?a" and z = "x - ?a" in that)
+ apply (meson \<open>T \<subseteq> span S\<close> span_scale span_sum subsetCE)
+ apply (fact orth, simp)
+ done
+qed
+
+lemma orthogonal_subspace_decomp_unique:
+ fixes S :: "'a :: euclidean_space set"
+ assumes "x + y = x' + y'"
+ and ST: "x \<in> span S" "x' \<in> span S" "y \<in> span T" "y' \<in> span T"
+ and orth: "\<And>a b. \<lbrakk>a \<in> S; b \<in> T\<rbrakk> \<Longrightarrow> orthogonal a b"
+ shows "x = x' \<and> y = y'"
+proof -
+ have "x + y - y' = x'"
+ by (simp add: assms)
+ moreover have "\<And>a b. \<lbrakk>a \<in> span S; b \<in> span T\<rbrakk> \<Longrightarrow> orthogonal a b"
+ by (meson orth orthogonal_commute orthogonal_to_span)
+ ultimately have "0 = x' - x"
+ by (metis (full_types) add_diff_cancel_left' ST diff_right_commute orthogonal_clauses(10) orthogonal_clauses(5) orthogonal_self)
+ with assms show ?thesis by auto
+qed
+
+lemma vector_in_orthogonal_spanningset:
+ fixes a :: "'a::euclidean_space"
+ obtains S where "a \<in> S" "pairwise orthogonal S" "span S = UNIV"
+ by (metis UNIV_I Un_iff empty_iff insert_subset orthogonal_extension pairwise_def
+ pairwise_orthogonal_insert span_UNIV subsetI subset_antisym)
+
+lemma vector_in_orthogonal_basis:
+ fixes a :: "'a::euclidean_space"
+ assumes "a \<noteq> 0"
+ obtains S where "a \<in> S" "0 \<notin> S" "pairwise orthogonal S" "independent S" "finite S"
+ "span S = UNIV" "card S = DIM('a)"
+proof -
+ obtain S where S: "a \<in> S" "pairwise orthogonal S" "span S = UNIV"
+ using vector_in_orthogonal_spanningset .
+ show thesis
+ proof
+ show "pairwise orthogonal (S - {0})"
+ using pairwise_mono S(2) by blast
+ show "independent (S - {0})"
+ by (simp add: \<open>pairwise orthogonal (S - {0})\<close> pairwise_orthogonal_independent)
+ show "finite (S - {0})"
+ using \<open>independent (S - {0})\<close> independent_imp_finite by blast
+ show "card (S - {0}) = DIM('a)"
+ using span_delete_0 [of S] S
+ by (simp add: \<open>independent (S - {0})\<close> indep_card_eq_dim_span dim_UNIV)
+ qed (use S \<open>a \<noteq> 0\<close> in auto)
+qed
+
+lemma vector_in_orthonormal_basis:
+ fixes a :: "'a::euclidean_space"
+ assumes "norm a = 1"
+ obtains S where "a \<in> S" "pairwise orthogonal S" "\<And>x. x \<in> S \<Longrightarrow> norm x = 1"
+ "independent S" "card S = DIM('a)" "span S = UNIV"
+proof -
+ have "a \<noteq> 0"
+ using assms by auto
+ then obtain S where "a \<in> S" "0 \<notin> S" "finite S"
+ and S: "pairwise orthogonal S" "independent S" "span S = UNIV" "card S = DIM('a)"
+ by (metis vector_in_orthogonal_basis)
+ let ?S = "(\<lambda>x. x /\<^sub>R norm x) ` S"
+ show thesis
+ proof
+ show "a \<in> ?S"
+ using \<open>a \<in> S\<close> assms image_iff by fastforce
+ next
+ show "pairwise orthogonal ?S"
+ using \<open>pairwise orthogonal S\<close> by (auto simp: pairwise_def orthogonal_def)
+ show "\<And>x. x \<in> (\<lambda>x. x /\<^sub>R norm x) ` S \<Longrightarrow> norm x = 1"
+ using \<open>0 \<notin> S\<close> by (auto simp: divide_simps)
+ then show "independent ?S"
+ by (metis \<open>pairwise orthogonal ((\<lambda>x. x /\<^sub>R norm x) ` S)\<close> norm_zero pairwise_orthogonal_independent zero_neq_one)
+ have "inj_on (\<lambda>x. x /\<^sub>R norm x) S"
+ unfolding inj_on_def
+ by (metis (full_types) S(1) \<open>0 \<notin> S\<close> inverse_nonzero_iff_nonzero norm_eq_zero orthogonal_scaleR orthogonal_self pairwise_def)
+ then show "card ?S = DIM('a)"
+ by (simp add: card_image S)
+ show "span ?S = UNIV"
+ by (metis (no_types) \<open>0 \<notin> S\<close> \<open>finite S\<close> \<open>span S = UNIV\<close>
+ field_class.field_inverse_zero inverse_inverse_eq less_irrefl span_image_scale
+ zero_less_norm_iff)
+ qed
+qed
+
+proposition dim_orthogonal_sum:
+ fixes A :: "'a::euclidean_space set"
+ assumes "\<And>x y. \<lbrakk>x \<in> A; y \<in> B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ shows "dim(A \<union> B) = dim A + dim B"
+proof -
+ have 1: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ by (erule span_induct [OF _ subspace_hyperplane2]; simp add: assms)
+ have "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ using 1 by (simp add: span_induct [OF _ subspace_hyperplane])
+ then have 0: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
+ by simp
+ have "dim(A \<union> B) = dim (span (A \<union> B))"
+ by (simp add: dim_span)
+ also have "span (A \<union> B) = ((\<lambda>(a, b). a + b) ` (span A \<times> span B))"
+ by (auto simp add: span_Un image_def)
+ also have "dim \<dots> = dim {x + y |x y. x \<in> span A \<and> y \<in> span B}"
+ by (auto intro!: arg_cong [where f=dim])
+ also have "... = dim {x + y |x y. x \<in> span A \<and> y \<in> span B} + dim(span A \<inter> span B)"
+ by (auto simp: dest: 0)
+ also have "... = dim (span A) + dim (span B)"
+ by (rule dim_sums_Int) (auto simp: subspace_span)
+ also have "... = dim A + dim B"
+ by (simp add: dim_span)
+ finally show ?thesis .
+qed
+
+lemma dim_subspace_orthogonal_to_vectors:
+ fixes A :: "'a::euclidean_space set"
+ assumes "subspace A" "subspace B" "A \<subseteq> B"
+ shows "dim {y \<in> B. \<forall>x \<in> A. orthogonal x y} + dim A = dim B"
+proof -
+ have "dim (span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)) = dim (span B)"
+ proof (rule arg_cong [where f=dim, OF subset_antisym])
+ show "span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A) \<subseteq> span B"
+ by (simp add: \<open>A \<subseteq> B\<close> Collect_restrict span_mono)
+ next
+ have *: "x \<in> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)"
+ if "x \<in> B" for x
+ proof -
+ obtain y z where "x = y + z" "y \<in> span A" and orth: "\<And>w. w \<in> span A \<Longrightarrow> orthogonal z w"
+ using orthogonal_subspace_decomp_exists [of A x] that by auto
+ have "y \<in> span B"
+ using \<open>y \<in> span A\<close> assms(3) span_mono by blast
+ then have "z \<in> {a \<in> B. \<forall>x. x \<in> A \<longrightarrow> orthogonal x a}"
+ apply simp
+ using \<open>x = y + z\<close> assms(1) assms(2) orth orthogonal_commute span_add_eq
+ span_eq_iff that by blast
+ then have z: "z \<in> span {y \<in> B. \<forall>x\<in>A. orthogonal x y}"
+ by (meson span_superset subset_iff)
+ then show ?thesis
+ apply (auto simp: span_Un image_def \<open>x = y + z\<close> \<open>y \<in> span A\<close>)
+ using \<open>y \<in> span A\<close> add.commute by blast
+ qed
+ show "span B \<subseteq> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)"
+ by (rule span_minimal)
+ (auto intro: * span_minimal simp: subspace_span)
+ qed
+ then show ?thesis
+ by (metis (no_types, lifting) dim_orthogonal_sum dim_span mem_Collect_eq
+ orthogonal_commute orthogonal_def)
+qed
+
end
--- a/src/HOL/Analysis/Sigma_Algebra.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Sigma_Algebra.thy Thu Jan 17 16:08:41 2019 +0000
@@ -5,7 +5,7 @@
translated by Lawrence Paulson.
*)
-section \<open>Sigma Algebra\<close>
+chapter \<open>Measure and Integration Theory\<close>
theory Sigma_Algebra
imports
@@ -17,6 +17,9 @@
"HOL-Library.Disjoint_Sets"
begin
+
+section \<open>Sigma Algebra\<close>
+
text \<open>Sigma algebras are an elementary concept in measure
theory. To measure --- that is to integrate --- functions, we first have
to measure sets. Unfortunately, when dealing with a large universe,
--- a/src/HOL/Analysis/Starlike.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Starlike.thy Thu Jan 17 16:08:41 2019 +0000
@@ -5,13 +5,14 @@
Author: Armin Heller, TU Muenchen
Author: Johannes Hoelzl, TU Muenchen
*)
-
-section \<open>Line Segments\<close>
+chapter \<open>Unsorted\<close>
theory Starlike
imports Convex_Euclidean_Space
begin
+section \<open>Line Segments\<close>
+
subsection \<open>Midpoint\<close>
definition%important midpoint :: "'a::real_vector \<Rightarrow> 'a \<Rightarrow> 'a"
@@ -5469,103 +5470,6 @@
(if a = 0 \<and> r > 0 then -1 else DIM('a))"
using aff_dim_halfspace_le [of "-a" "-r"] by simp
-subsection\<open>Properties of special hyperplanes\<close>
-
-lemma subspace_hyperplane: "subspace {x. a \<bullet> x = 0}"
- by (simp add: subspace_def inner_right_distrib)
-
-lemma subspace_hyperplane2: "subspace {x. x \<bullet> a = 0}"
- by (simp add: inner_commute inner_right_distrib subspace_def)
-
-lemma special_hyperplane_span:
- fixes S :: "'n::euclidean_space set"
- assumes "k \<in> Basis"
- shows "{x. k \<bullet> x = 0} = span (Basis - {k})"
-proof -
- have *: "x \<in> span (Basis - {k})" if "k \<bullet> x = 0" for x
- proof -
- have "x = (\<Sum>b\<in>Basis. (x \<bullet> b) *\<^sub>R b)"
- by (simp add: euclidean_representation)
- also have "... = (\<Sum>b \<in> Basis - {k}. (x \<bullet> b) *\<^sub>R b)"
- by (auto simp: sum.remove [of _ k] inner_commute assms that)
- finally have "x = (\<Sum>b\<in>Basis - {k}. (x \<bullet> b) *\<^sub>R b)" .
- then show ?thesis
- by (simp add: span_finite)
- qed
- show ?thesis
- apply (rule span_subspace [symmetric])
- using assms
- apply (auto simp: inner_not_same_Basis intro: * subspace_hyperplane)
- done
-qed
-
-lemma dim_special_hyperplane:
- fixes k :: "'n::euclidean_space"
- shows "k \<in> Basis \<Longrightarrow> dim {x. k \<bullet> x = 0} = DIM('n) - 1"
-apply (simp add: special_hyperplane_span)
-apply (rule dim_unique [OF subset_refl])
-apply (auto simp: independent_substdbasis)
-apply (metis member_remove remove_def span_base)
-done
-
-proposition dim_hyperplane:
- fixes a :: "'a::euclidean_space"
- assumes "a \<noteq> 0"
- shows "dim {x. a \<bullet> x = 0} = DIM('a) - 1"
-proof -
- have span0: "span {x. a \<bullet> x = 0} = {x. a \<bullet> x = 0}"
- by (rule span_unique) (auto simp: subspace_hyperplane)
- then obtain B where "independent B"
- and Bsub: "B \<subseteq> {x. a \<bullet> x = 0}"
- and subspB: "{x. a \<bullet> x = 0} \<subseteq> span B"
- and card0: "(card B = dim {x. a \<bullet> x = 0})"
- and ortho: "pairwise orthogonal B"
- using orthogonal_basis_exists by metis
- with assms have "a \<notin> span B"
- by (metis (mono_tags, lifting) span_eq inner_eq_zero_iff mem_Collect_eq span0)
- then have ind: "independent (insert a B)"
- by (simp add: \<open>independent B\<close> independent_insert)
- have "finite B"
- using \<open>independent B\<close> independent_bound by blast
- have "UNIV \<subseteq> span (insert a B)"
- proof fix y::'a
- obtain r z where z: "y = r *\<^sub>R a + z" "a \<bullet> z = 0"
- apply (rule_tac r="(a \<bullet> y) / (a \<bullet> a)" and z = "y - ((a \<bullet> y) / (a \<bullet> a)) *\<^sub>R a" in that)
- using assms
- by (auto simp: algebra_simps)
- show "y \<in> span (insert a B)"
- by (metis (mono_tags, lifting) z Bsub span_eq_iff
- add_diff_cancel_left' mem_Collect_eq span0 span_breakdown_eq span_subspace subspB)
- qed
- then have dima: "DIM('a) = dim(insert a B)"
- by (metis independent_Basis span_Basis dim_eq_card top.extremum_uniqueI)
- then show ?thesis
- by (metis (mono_tags, lifting) Bsub Diff_insert_absorb \<open>a \<notin> span B\<close> ind card0
- card_Diff_singleton dim_span indep_card_eq_dim_span insertI1 subsetCE
- subspB)
-qed
-
-lemma lowdim_eq_hyperplane:
- fixes S :: "'a::euclidean_space set"
- assumes "dim S = DIM('a) - 1"
- obtains a where "a \<noteq> 0" and "span S = {x. a \<bullet> x = 0}"
-proof -
- have dimS: "dim S < DIM('a)"
- by (simp add: assms)
- then obtain b where b: "b \<noteq> 0" "span S \<subseteq> {a. b \<bullet> a = 0}"
- using lowdim_subset_hyperplane [of S] by fastforce
- show ?thesis
- apply (rule that[OF b(1)])
- apply (rule subspace_dim_equal)
- by (auto simp: assms b dim_hyperplane dim_span subspace_hyperplane
- subspace_span)
-qed
-
-lemma dim_eq_hyperplane:
- fixes S :: "'n::euclidean_space set"
- shows "dim S = DIM('n) - 1 \<longleftrightarrow> (\<exists>a. a \<noteq> 0 \<and> span S = {x. a \<bullet> x = 0})"
-by (metis One_nat_def dim_hyperplane dim_span lowdim_eq_hyperplane)
-
proposition aff_dim_eq_hyperplane:
fixes S :: "'a::euclidean_space set"
shows "aff_dim S = DIM('a) - 1 \<longleftrightarrow> (\<exists>a b. a \<noteq> 0 \<and> affine hull S = {x. a \<bullet> x = b})"
@@ -6436,444 +6340,6 @@
shows "aff_dim S < DIM('a) \<longleftrightarrow> (affine hull S \<noteq> UNIV)"
by (metis (no_types) aff_dim_affine_hull aff_dim_le_DIM aff_dim_UNIV affine_hull_UNIV less_le)
-
-subsection\<open> Orthogonal bases, Gram-Schmidt process, and related theorems\<close>
-
-lemma pairwise_orthogonal_independent:
- assumes "pairwise orthogonal S" and "0 \<notin> S"
- shows "independent S"
-proof -
- have 0: "\<And>x y. \<lbrakk>x \<noteq> y; x \<in> S; y \<in> S\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- using assms by (simp add: pairwise_def orthogonal_def)
- have "False" if "a \<in> S" and a: "a \<in> span (S - {a})" for a
- proof -
- obtain T U where "T \<subseteq> S - {a}" "a = (\<Sum>v\<in>T. U v *\<^sub>R v)"
- using a by (force simp: span_explicit)
- then have "a \<bullet> a = a \<bullet> (\<Sum>v\<in>T. U v *\<^sub>R v)"
- by simp
- also have "... = 0"
- apply (simp add: inner_sum_right)
- apply (rule comm_monoid_add_class.sum.neutral)
- by (metis "0" DiffE \<open>T \<subseteq> S - {a}\<close> mult_not_zero singletonI subsetCE \<open>a \<in> S\<close>)
- finally show ?thesis
- using \<open>0 \<notin> S\<close> \<open>a \<in> S\<close> by auto
- qed
- then show ?thesis
- by (force simp: dependent_def)
-qed
-
-lemma pairwise_orthogonal_imp_finite:
- fixes S :: "'a::euclidean_space set"
- assumes "pairwise orthogonal S"
- shows "finite S"
-proof -
- have "independent (S - {0})"
- apply (rule pairwise_orthogonal_independent)
- apply (metis Diff_iff assms pairwise_def)
- by blast
- then show ?thesis
- by (meson independent_imp_finite infinite_remove)
-qed
-
-lemma subspace_orthogonal_to_vector: "subspace {y. orthogonal x y}"
- by (simp add: subspace_def orthogonal_clauses)
-
-lemma subspace_orthogonal_to_vectors: "subspace {y. \<forall>x \<in> S. orthogonal x y}"
- by (simp add: subspace_def orthogonal_clauses)
-
-lemma orthogonal_to_span:
- assumes a: "a \<in> span S" and x: "\<And>y. y \<in> S \<Longrightarrow> orthogonal x y"
- shows "orthogonal x a"
- by (metis a orthogonal_clauses(1,2,4)
- span_induct_alt x)
-
-proposition Gram_Schmidt_step:
- fixes S :: "'a::euclidean_space set"
- assumes S: "pairwise orthogonal S" and x: "x \<in> span S"
- shows "orthogonal x (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b))"
-proof -
- have "finite S"
- by (simp add: S pairwise_orthogonal_imp_finite)
- have "orthogonal (a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)) x"
- if "x \<in> S" for x
- proof -
- have "a \<bullet> x = (\<Sum>y\<in>S. if y = x then y \<bullet> a else 0)"
- by (simp add: \<open>finite S\<close> inner_commute sum.delta that)
- also have "... = (\<Sum>b\<in>S. b \<bullet> a * (b \<bullet> x) / (b \<bullet> b))"
- apply (rule sum.cong [OF refl], simp)
- by (meson S orthogonal_def pairwise_def that)
- finally show ?thesis
- by (simp add: orthogonal_def algebra_simps inner_sum_left)
- qed
- then show ?thesis
- using orthogonal_to_span orthogonal_commute x by blast
-qed
-
-
-lemma orthogonal_extension_aux:
- fixes S :: "'a::euclidean_space set"
- assumes "finite T" "finite S" "pairwise orthogonal S"
- shows "\<exists>U. pairwise orthogonal (S \<union> U) \<and> span (S \<union> U) = span (S \<union> T)"
-using assms
-proof (induction arbitrary: S)
- case empty then show ?case
- by simp (metis sup_bot_right)
-next
- case (insert a T)
- have 0: "\<And>x y. \<lbrakk>x \<noteq> y; x \<in> S; y \<in> S\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- using insert by (simp add: pairwise_def orthogonal_def)
- define a' where "a' = a - (\<Sum>b\<in>S. (b \<bullet> a / (b \<bullet> b)) *\<^sub>R b)"
- obtain U where orthU: "pairwise orthogonal (S \<union> insert a' U)"
- and spanU: "span (insert a' S \<union> U) = span (insert a' S \<union> T)"
- by (rule exE [OF insert.IH [of "insert a' S"]])
- (auto simp: Gram_Schmidt_step a'_def insert.prems orthogonal_commute
- pairwise_orthogonal_insert span_clauses)
- have orthS: "\<And>x. x \<in> S \<Longrightarrow> a' \<bullet> x = 0"
- apply (simp add: a'_def)
- using Gram_Schmidt_step [OF \<open>pairwise orthogonal S\<close>]
- apply (force simp: orthogonal_def inner_commute span_superset [THEN subsetD])
- done
- have "span (S \<union> insert a' U) = span (insert a' (S \<union> T))"
- using spanU by simp
- also have "... = span (insert a (S \<union> T))"
- apply (rule eq_span_insert_eq)
- apply (simp add: a'_def span_neg span_sum span_base span_mul)
- done
- also have "... = span (S \<union> insert a T)"
- by simp
- finally show ?case
- by (rule_tac x="insert a' U" in exI) (use orthU in auto)
-qed
-
-
-proposition orthogonal_extension:
- fixes S :: "'a::euclidean_space set"
- assumes S: "pairwise orthogonal S"
- obtains U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> T)"
-proof -
- obtain B where "finite B" "span B = span T"
- using basis_subspace_exists [of "span T"] subspace_span by metis
- with orthogonal_extension_aux [of B S]
- obtain U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> B)"
- using assms pairwise_orthogonal_imp_finite by auto
- with \<open>span B = span T\<close> show ?thesis
- by (rule_tac U=U in that) (auto simp: span_Un)
-qed
-
-corollary%unimportant orthogonal_extension_strong:
- fixes S :: "'a::euclidean_space set"
- assumes S: "pairwise orthogonal S"
- obtains U where "U \<inter> (insert 0 S) = {}" "pairwise orthogonal (S \<union> U)"
- "span (S \<union> U) = span (S \<union> T)"
-proof -
- obtain U where "pairwise orthogonal (S \<union> U)" "span (S \<union> U) = span (S \<union> T)"
- using orthogonal_extension assms by blast
- then show ?thesis
- apply (rule_tac U = "U - (insert 0 S)" in that)
- apply blast
- apply (force simp: pairwise_def)
- apply (metis Un_Diff_cancel Un_insert_left span_redundant span_zero)
- done
-qed
-
-subsection\<open>Decomposing a vector into parts in orthogonal subspaces\<close>
-
-text\<open>existence of orthonormal basis for a subspace.\<close>
-
-lemma orthogonal_spanningset_subspace:
- fixes S :: "'a :: euclidean_space set"
- assumes "subspace S"
- obtains B where "B \<subseteq> S" "pairwise orthogonal B" "span B = S"
-proof -
- obtain B where "B \<subseteq> S" "independent B" "S \<subseteq> span B" "card B = dim S"
- using basis_exists by blast
- with orthogonal_extension [of "{}" B]
- show ?thesis
- by (metis Un_empty_left assms pairwise_empty span_superset span_subspace that)
-qed
-
-lemma orthogonal_basis_subspace:
- fixes S :: "'a :: euclidean_space set"
- assumes "subspace S"
- obtains B where "0 \<notin> B" "B \<subseteq> S" "pairwise orthogonal B" "independent B"
- "card B = dim S" "span B = S"
-proof -
- obtain B where "B \<subseteq> S" "pairwise orthogonal B" "span B = S"
- using assms orthogonal_spanningset_subspace by blast
- then show ?thesis
- apply (rule_tac B = "B - {0}" in that)
- apply (auto simp: indep_card_eq_dim_span pairwise_subset pairwise_orthogonal_independent elim: pairwise_subset)
- done
-qed
-
-proposition orthonormal_basis_subspace:
- fixes S :: "'a :: euclidean_space set"
- assumes "subspace S"
- obtains B where "B \<subseteq> S" "pairwise orthogonal B"
- and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1"
- and "independent B" "card B = dim S" "span B = S"
-proof -
- obtain B where "0 \<notin> B" "B \<subseteq> S"
- and orth: "pairwise orthogonal B"
- and "independent B" "card B = dim S" "span B = S"
- by (blast intro: orthogonal_basis_subspace [OF assms])
- have 1: "(\<lambda>x. x /\<^sub>R norm x) ` B \<subseteq> S"
- using \<open>span B = S\<close> span_superset span_mul by fastforce
- have 2: "pairwise orthogonal ((\<lambda>x. x /\<^sub>R norm x) ` B)"
- using orth by (force simp: pairwise_def orthogonal_clauses)
- have 3: "\<And>x. x \<in> (\<lambda>x. x /\<^sub>R norm x) ` B \<Longrightarrow> norm x = 1"
- by (metis (no_types, lifting) \<open>0 \<notin> B\<close> image_iff norm_sgn sgn_div_norm)
- have 4: "independent ((\<lambda>x. x /\<^sub>R norm x) ` B)"
- by (metis "2" "3" norm_zero pairwise_orthogonal_independent zero_neq_one)
- have "inj_on (\<lambda>x. x /\<^sub>R norm x) B"
- proof
- fix x y
- assume "x \<in> B" "y \<in> B" "x /\<^sub>R norm x = y /\<^sub>R norm y"
- moreover have "\<And>i. i \<in> B \<Longrightarrow> norm (i /\<^sub>R norm i) = 1"
- using 3 by blast
- ultimately show "x = y"
- by (metis norm_eq_1 orth orthogonal_clauses(7) orthogonal_commute orthogonal_def pairwise_def zero_neq_one)
- qed
- then have 5: "card ((\<lambda>x. x /\<^sub>R norm x) ` B) = dim S"
- by (metis \<open>card B = dim S\<close> card_image)
- have 6: "span ((\<lambda>x. x /\<^sub>R norm x) ` B) = S"
- by (metis "1" "4" "5" assms card_eq_dim independent_finite span_subspace)
- show ?thesis
- by (rule that [OF 1 2 3 4 5 6])
-qed
-
-
-proposition%unimportant orthogonal_to_subspace_exists_gen:
- fixes S :: "'a :: euclidean_space set"
- assumes "span S \<subset> span T"
- obtains x where "x \<noteq> 0" "x \<in> span T" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
-proof -
- obtain B where "B \<subseteq> span S" and orthB: "pairwise orthogonal B"
- and "\<And>x. x \<in> B \<Longrightarrow> norm x = 1"
- and "independent B" "card B = dim S" "span B = span S"
- by (rule orthonormal_basis_subspace [of "span S", OF subspace_span])
- (auto simp: dim_span)
- with assms obtain u where spanBT: "span B \<subseteq> span T" and "u \<notin> span B" "u \<in> span T"
- by auto
- obtain C where orthBC: "pairwise orthogonal (B \<union> C)" and spanBC: "span (B \<union> C) = span (B \<union> {u})"
- by (blast intro: orthogonal_extension [OF orthB])
- show thesis
- proof (cases "C \<subseteq> insert 0 B")
- case True
- then have "C \<subseteq> span B"
- using span_eq
- by (metis span_insert_0 subset_trans)
- moreover have "u \<in> span (B \<union> C)"
- using \<open>span (B \<union> C) = span (B \<union> {u})\<close> span_superset by force
- ultimately show ?thesis
- using True \<open>u \<notin> span B\<close>
- by (metis Un_insert_left span_insert_0 sup.orderE)
- next
- case False
- then obtain x where "x \<in> C" "x \<noteq> 0" "x \<notin> B"
- by blast
- then have "x \<in> span T"
- by (metis (no_types, lifting) Un_insert_right Un_upper2 \<open>u \<in> span T\<close> spanBT spanBC
- \<open>u \<in> span T\<close> insert_subset span_superset span_mono
- span_span subsetCE subset_trans sup_bot.comm_neutral)
- moreover have "orthogonal x y" if "y \<in> span B" for y
- using that
- proof (rule span_induct)
- show "subspace {a. orthogonal x a}"
- by (simp add: subspace_orthogonal_to_vector)
- show "\<And>b. b \<in> B \<Longrightarrow> orthogonal x b"
- by (metis Un_iff \<open>x \<in> C\<close> \<open>x \<notin> B\<close> orthBC pairwise_def)
- qed
- ultimately show ?thesis
- using \<open>x \<noteq> 0\<close> that \<open>span B = span S\<close> by auto
- qed
-qed
-
-corollary%unimportant orthogonal_to_subspace_exists:
- fixes S :: "'a :: euclidean_space set"
- assumes "dim S < DIM('a)"
- obtains x where "x \<noteq> 0" "\<And>y. y \<in> span S \<Longrightarrow> orthogonal x y"
-proof -
-have "span S \<subset> UNIV"
- by (metis (mono_tags) UNIV_I assms inner_eq_zero_iff less_le lowdim_subset_hyperplane
- mem_Collect_eq top.extremum_strict top.not_eq_extremum)
- with orthogonal_to_subspace_exists_gen [of S UNIV] that show ?thesis
- by (auto simp: span_UNIV)
-qed
-
-corollary%unimportant orthogonal_to_vector_exists:
- fixes x :: "'a :: euclidean_space"
- assumes "2 \<le> DIM('a)"
- obtains y where "y \<noteq> 0" "orthogonal x y"
-proof -
- have "dim {x} < DIM('a)"
- using assms by auto
- then show thesis
- by (rule orthogonal_to_subspace_exists) (simp add: orthogonal_commute span_base that)
-qed
-
-proposition%unimportant orthogonal_subspace_decomp_exists:
- fixes S :: "'a :: euclidean_space set"
- obtains y z
- where "y \<in> span S"
- and "\<And>w. w \<in> span S \<Longrightarrow> orthogonal z w"
- and "x = y + z"
-proof -
- obtain T where "0 \<notin> T" "T \<subseteq> span S" "pairwise orthogonal T" "independent T"
- "card T = dim (span S)" "span T = span S"
- using orthogonal_basis_subspace subspace_span by blast
- let ?a = "\<Sum>b\<in>T. (b \<bullet> x / (b \<bullet> b)) *\<^sub>R b"
- have orth: "orthogonal (x - ?a) w" if "w \<in> span S" for w
- by (simp add: Gram_Schmidt_step \<open>pairwise orthogonal T\<close> \<open>span T = span S\<close>
- orthogonal_commute that)
- show ?thesis
- apply (rule_tac y = "?a" and z = "x - ?a" in that)
- apply (meson \<open>T \<subseteq> span S\<close> span_scale span_sum subsetCE)
- apply (fact orth, simp)
- done
-qed
-
-lemma orthogonal_subspace_decomp_unique:
- fixes S :: "'a :: euclidean_space set"
- assumes "x + y = x' + y'"
- and ST: "x \<in> span S" "x' \<in> span S" "y \<in> span T" "y' \<in> span T"
- and orth: "\<And>a b. \<lbrakk>a \<in> S; b \<in> T\<rbrakk> \<Longrightarrow> orthogonal a b"
- shows "x = x' \<and> y = y'"
-proof -
- have "x + y - y' = x'"
- by (simp add: assms)
- moreover have "\<And>a b. \<lbrakk>a \<in> span S; b \<in> span T\<rbrakk> \<Longrightarrow> orthogonal a b"
- by (meson orth orthogonal_commute orthogonal_to_span)
- ultimately have "0 = x' - x"
- by (metis (full_types) add_diff_cancel_left' ST diff_right_commute orthogonal_clauses(10) orthogonal_clauses(5) orthogonal_self)
- with assms show ?thesis by auto
-qed
-
-lemma vector_in_orthogonal_spanningset:
- fixes a :: "'a::euclidean_space"
- obtains S where "a \<in> S" "pairwise orthogonal S" "span S = UNIV"
- by (metis UNIV_I Un_iff empty_iff insert_subset orthogonal_extension pairwise_def
- pairwise_orthogonal_insert span_UNIV subsetI subset_antisym)
-
-lemma vector_in_orthogonal_basis:
- fixes a :: "'a::euclidean_space"
- assumes "a \<noteq> 0"
- obtains S where "a \<in> S" "0 \<notin> S" "pairwise orthogonal S" "independent S" "finite S"
- "span S = UNIV" "card S = DIM('a)"
-proof -
- obtain S where S: "a \<in> S" "pairwise orthogonal S" "span S = UNIV"
- using vector_in_orthogonal_spanningset .
- show thesis
- proof
- show "pairwise orthogonal (S - {0})"
- using pairwise_mono S(2) by blast
- show "independent (S - {0})"
- by (simp add: \<open>pairwise orthogonal (S - {0})\<close> pairwise_orthogonal_independent)
- show "finite (S - {0})"
- using \<open>independent (S - {0})\<close> independent_finite by blast
- show "card (S - {0}) = DIM('a)"
- using span_delete_0 [of S] S
- by (simp add: \<open>independent (S - {0})\<close> indep_card_eq_dim_span dim_UNIV)
- qed (use S \<open>a \<noteq> 0\<close> in auto)
-qed
-
-lemma vector_in_orthonormal_basis:
- fixes a :: "'a::euclidean_space"
- assumes "norm a = 1"
- obtains S where "a \<in> S" "pairwise orthogonal S" "\<And>x. x \<in> S \<Longrightarrow> norm x = 1"
- "independent S" "card S = DIM('a)" "span S = UNIV"
-proof -
- have "a \<noteq> 0"
- using assms by auto
- then obtain S where "a \<in> S" "0 \<notin> S" "finite S"
- and S: "pairwise orthogonal S" "independent S" "span S = UNIV" "card S = DIM('a)"
- by (metis vector_in_orthogonal_basis)
- let ?S = "(\<lambda>x. x /\<^sub>R norm x) ` S"
- show thesis
- proof
- show "a \<in> ?S"
- using \<open>a \<in> S\<close> assms image_iff by fastforce
- next
- show "pairwise orthogonal ?S"
- using \<open>pairwise orthogonal S\<close> by (auto simp: pairwise_def orthogonal_def)
- show "\<And>x. x \<in> (\<lambda>x. x /\<^sub>R norm x) ` S \<Longrightarrow> norm x = 1"
- using \<open>0 \<notin> S\<close> by (auto simp: divide_simps)
- then show "independent ?S"
- by (metis \<open>pairwise orthogonal ((\<lambda>x. x /\<^sub>R norm x) ` S)\<close> norm_zero pairwise_orthogonal_independent zero_neq_one)
- have "inj_on (\<lambda>x. x /\<^sub>R norm x) S"
- unfolding inj_on_def
- by (metis (full_types) S(1) \<open>0 \<notin> S\<close> inverse_nonzero_iff_nonzero norm_eq_zero orthogonal_scaleR orthogonal_self pairwise_def)
- then show "card ?S = DIM('a)"
- by (simp add: card_image S)
- show "span ?S = UNIV"
- by (metis (no_types) \<open>0 \<notin> S\<close> \<open>finite S\<close> \<open>span S = UNIV\<close>
- field_class.field_inverse_zero inverse_inverse_eq less_irrefl span_image_scale
- zero_less_norm_iff)
- qed
-qed
-
-proposition dim_orthogonal_sum:
- fixes A :: "'a::euclidean_space set"
- assumes "\<And>x y. \<lbrakk>x \<in> A; y \<in> B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- shows "dim(A \<union> B) = dim A + dim B"
-proof -
- have 1: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- by (erule span_induct [OF _ subspace_hyperplane2]; simp add: assms)
- have "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- using 1 by (simp add: span_induct [OF _ subspace_hyperplane])
- then have 0: "\<And>x y. \<lbrakk>x \<in> span A; y \<in> span B\<rbrakk> \<Longrightarrow> x \<bullet> y = 0"
- by simp
- have "dim(A \<union> B) = dim (span (A \<union> B))"
- by (simp add: dim_span)
- also have "span (A \<union> B) = ((\<lambda>(a, b). a + b) ` (span A \<times> span B))"
- by (auto simp add: span_Un image_def)
- also have "dim \<dots> = dim {x + y |x y. x \<in> span A \<and> y \<in> span B}"
- by (auto intro!: arg_cong [where f=dim])
- also have "... = dim {x + y |x y. x \<in> span A \<and> y \<in> span B} + dim(span A \<inter> span B)"
- by (auto simp: dest: 0)
- also have "... = dim (span A) + dim (span B)"
- by (rule dim_sums_Int) (auto simp: subspace_span)
- also have "... = dim A + dim B"
- by (simp add: dim_span)
- finally show ?thesis .
-qed
-
-lemma dim_subspace_orthogonal_to_vectors:
- fixes A :: "'a::euclidean_space set"
- assumes "subspace A" "subspace B" "A \<subseteq> B"
- shows "dim {y \<in> B. \<forall>x \<in> A. orthogonal x y} + dim A = dim B"
-proof -
- have "dim (span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)) = dim (span B)"
- proof (rule arg_cong [where f=dim, OF subset_antisym])
- show "span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A) \<subseteq> span B"
- by (simp add: \<open>A \<subseteq> B\<close> Collect_restrict span_mono)
- next
- have *: "x \<in> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)"
- if "x \<in> B" for x
- proof -
- obtain y z where "x = y + z" "y \<in> span A" and orth: "\<And>w. w \<in> span A \<Longrightarrow> orthogonal z w"
- using orthogonal_subspace_decomp_exists [of A x] that by auto
- have "y \<in> span B"
- using \<open>y \<in> span A\<close> assms(3) span_mono by blast
- then have "z \<in> {a \<in> B. \<forall>x. x \<in> A \<longrightarrow> orthogonal x a}"
- apply simp
- using \<open>x = y + z\<close> assms(1) assms(2) orth orthogonal_commute span_add_eq
- span_eq_iff that by blast
- then have z: "z \<in> span {y \<in> B. \<forall>x\<in>A. orthogonal x y}"
- by (meson span_superset subset_iff)
- then show ?thesis
- apply (auto simp: span_Un image_def \<open>x = y + z\<close> \<open>y \<in> span A\<close>)
- using \<open>y \<in> span A\<close> add.commute by blast
- qed
- show "span B \<subseteq> span ({y \<in> B. \<forall>x\<in>A. orthogonal x y} \<union> A)"
- by (rule span_minimal)
- (auto intro: * span_minimal simp: subspace_span)
- qed
- then show ?thesis
- by (metis (no_types, lifting) dim_orthogonal_sum dim_span mem_Collect_eq
- orthogonal_commute orthogonal_def)
-qed
-
lemma aff_dim_openin:
fixes S :: "'a::euclidean_space set"
assumes ope: "openin (subtopology euclidean T) S" and "affine T" "S \<noteq> {}"
--- a/src/HOL/Analysis/Topology_Euclidean_Space.thy Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/Topology_Euclidean_Space.thy Thu Jan 17 16:08:41 2019 +0000
@@ -4,7 +4,7 @@
Author: Brian Huffman, Portland State University
*)
-section \<open>Elementary Topology in Euclidean Space\<close>
+chapter \<open>Vector Analysis\<close>
theory Topology_Euclidean_Space
imports
@@ -13,6 +13,8 @@
Norm_Arith
begin
+section \<open>Elementary Topology in Euclidean Space\<close>
+
lemma euclidean_dist_l2:
fixes x y :: "'a :: euclidean_space"
shows "dist x y = L2_set (\<lambda>i. dist (x \<bullet> i) (y \<bullet> i)) Basis"
--- a/src/HOL/Analysis/document/root.tex Thu Jan 17 15:50:28 2019 +0000
+++ b/src/HOL/Analysis/document/root.tex Thu Jan 17 16:08:41 2019 +0000
@@ -1,4 +1,4 @@
-\documentclass[11pt,a4paper]{article}
+\documentclass[11pt,a4paper]{book}
\usepackage{graphicx}
\usepackage{isabelle}
\usepackage{isabellesym}