329 by (vector ring_simps) |
329 by (vector ring_simps) |
330 |
330 |
331 lemma vec_eq[simp]: "(vec m = vec n) \<longleftrightarrow> (m = n)" |
331 lemma vec_eq[simp]: "(vec m = vec n) \<longleftrightarrow> (m = n)" |
332 by (simp add: Cart_eq) |
332 by (simp add: Cart_eq) |
333 |
333 |
|
334 subsection {* Topological space *} |
|
335 |
|
336 instantiation "^" :: (topological_space, finite) topological_space |
|
337 begin |
|
338 |
|
339 definition open_vector_def: |
|
340 "open (S :: ('a ^ 'b) set) \<longleftrightarrow> |
|
341 (\<forall>x\<in>S. \<exists>A. (\<forall>i. open (A i) \<and> x$i \<in> A i) \<and> |
|
342 (\<forall>y. (\<forall>i. y$i \<in> A i) \<longrightarrow> y \<in> S))" |
|
343 |
|
344 instance proof |
|
345 show "open (UNIV :: ('a ^ 'b) set)" |
|
346 unfolding open_vector_def by auto |
|
347 next |
|
348 fix S T :: "('a ^ 'b) set" |
|
349 assume "open S" "open T" thus "open (S \<inter> T)" |
|
350 unfolding open_vector_def |
|
351 apply clarify |
|
352 apply (drule (1) bspec)+ |
|
353 apply (clarify, rename_tac Sa Ta) |
|
354 apply (rule_tac x="\<lambda>i. Sa i \<inter> Ta i" in exI) |
|
355 apply (simp add: open_Int) |
|
356 done |
|
357 next |
|
358 fix K :: "('a ^ 'b) set set" |
|
359 assume "\<forall>S\<in>K. open S" thus "open (\<Union>K)" |
|
360 unfolding open_vector_def |
|
361 apply clarify |
|
362 apply (drule (1) bspec) |
|
363 apply (drule (1) bspec) |
|
364 apply clarify |
|
365 apply (rule_tac x=A in exI) |
|
366 apply fast |
|
367 done |
|
368 qed |
|
369 |
|
370 end |
|
371 |
|
372 lemma tendsto_Cart_nth: |
|
373 fixes f :: "'a \<Rightarrow> 'b::topological_space ^ 'n::finite" |
|
374 assumes "((\<lambda>x. f x) ---> a) net" |
|
375 shows "((\<lambda>x. f x $ i) ---> a $ i) net" |
|
376 proof (rule topological_tendstoI) |
|
377 fix S :: "'b set" assume "open S" "a $ i \<in> S" |
|
378 then have "open ((\<lambda>y. y $ i) -` S)" "a \<in> ((\<lambda>y. y $ i) -` S)" |
|
379 unfolding open_vector_def |
|
380 apply simp_all |
|
381 apply clarify |
|
382 apply (rule_tac x="\<lambda>k. if k = i then S else UNIV" in exI) |
|
383 apply simp |
|
384 done |
|
385 with assms have "eventually (\<lambda>x. f x \<in> (\<lambda>y. y $ i) -` S) net" |
|
386 by (rule topological_tendstoD) |
|
387 then show "eventually (\<lambda>x. f x $ i \<in> S) net" |
|
388 by simp |
|
389 qed |
|
390 |
334 subsection {* Square root of sum of squares *} |
391 subsection {* Square root of sum of squares *} |
335 |
392 |
336 definition |
393 definition |
337 "setL2 f A = sqrt (\<Sum>i\<in>A. (f i)\<twosuperior>)" |
394 "setL2 f A = sqrt (\<Sum>i\<in>A. (f i)\<twosuperior>)" |
338 |
395 |
358 lemma setL2_nonneg [simp]: "0 \<le> setL2 f A" |
415 lemma setL2_nonneg [simp]: "0 \<le> setL2 f A" |
359 unfolding setL2_def by (simp add: setsum_nonneg) |
416 unfolding setL2_def by (simp add: setsum_nonneg) |
360 |
417 |
361 lemma setL2_0': "\<forall>a\<in>A. f a = 0 \<Longrightarrow> setL2 f A = 0" |
418 lemma setL2_0': "\<forall>a\<in>A. f a = 0 \<Longrightarrow> setL2 f A = 0" |
362 unfolding setL2_def by simp |
419 unfolding setL2_def by simp |
|
420 |
|
421 lemma setL2_constant: "setL2 (\<lambda>x. y) A = sqrt (of_nat (card A)) * \<bar>y\<bar>" |
|
422 unfolding setL2_def by (simp add: real_sqrt_mult) |
363 |
423 |
364 lemma setL2_mono: |
424 lemma setL2_mono: |
365 assumes "\<And>i. i \<in> K \<Longrightarrow> f i \<le> g i" |
425 assumes "\<And>i. i \<in> K \<Longrightarrow> f i \<le> g i" |
366 assumes "\<And>i. i \<in> K \<Longrightarrow> 0 \<le> f i" |
426 assumes "\<And>i. i \<in> K \<Longrightarrow> 0 \<le> f i" |
367 shows "setL2 f K \<le> setL2 g K" |
427 shows "setL2 f K \<le> setL2 g K" |
368 unfolding setL2_def |
428 unfolding setL2_def |
369 by (simp add: setsum_nonneg setsum_mono power_mono prems) |
429 by (simp add: setsum_nonneg setsum_mono power_mono prems) |
|
430 |
|
431 lemma setL2_strict_mono: |
|
432 assumes "finite K" and "K \<noteq> {}" |
|
433 assumes "\<And>i. i \<in> K \<Longrightarrow> f i < g i" |
|
434 assumes "\<And>i. i \<in> K \<Longrightarrow> 0 \<le> f i" |
|
435 shows "setL2 f K < setL2 g K" |
|
436 unfolding setL2_def |
|
437 by (simp add: setsum_strict_mono power_strict_mono assms) |
370 |
438 |
371 lemma setL2_right_distrib: |
439 lemma setL2_right_distrib: |
372 "0 \<le> r \<Longrightarrow> r * setL2 f A = setL2 (\<lambda>x. r * f x) A" |
440 "0 \<le> r \<Longrightarrow> r * setL2 f A = setL2 (\<lambda>x. r * f x) A" |
373 unfolding setL2_def |
441 unfolding setL2_def |
374 apply (simp add: power_mult_distrib) |
442 apply (simp add: power_mult_distrib) |
498 apply simp |
566 apply simp |
499 done |
567 done |
500 |
568 |
501 subsection {* Metric *} |
569 subsection {* Metric *} |
502 |
570 |
|
571 (* TODO: move somewhere else *) |
|
572 lemma finite_choice: "finite A \<Longrightarrow> \<forall>x\<in>A. \<exists>y. P x y \<Longrightarrow> \<exists>f. \<forall>x\<in>A. P x (f x)" |
|
573 apply (induct set: finite, simp_all) |
|
574 apply (clarify, rename_tac y) |
|
575 apply (rule_tac x="f(x:=y)" in exI, simp) |
|
576 done |
|
577 |
503 instantiation "^" :: (metric_space, finite) metric_space |
578 instantiation "^" :: (metric_space, finite) metric_space |
504 begin |
579 begin |
505 |
580 |
506 definition dist_vector_def: |
581 definition dist_vector_def: |
507 "dist (x::'a^'b) (y::'a^'b) = setL2 (\<lambda>i. dist (x$i) (y$i)) UNIV" |
582 "dist (x::'a^'b) (y::'a^'b) = setL2 (\<lambda>i. dist (x$i) (y$i)) UNIV" |
508 |
583 |
509 definition open_vector_def: |
584 lemma dist_nth_le: "dist (x $ i) (y $ i) \<le> dist x y" |
510 "open (S :: ('a ^ 'b) set) \<longleftrightarrow> |
585 unfolding dist_vector_def |
511 (\<forall>x\<in>S. \<exists>e>0. \<forall>y. dist y x < e \<longrightarrow> y \<in> S)" |
586 by (rule member_le_setL2) simp_all |
512 |
587 |
513 instance proof |
588 instance proof |
514 fix x y :: "'a ^ 'b" |
589 fix x y :: "'a ^ 'b" |
515 show "dist x y = 0 \<longleftrightarrow> x = y" |
590 show "dist x y = 0 \<longleftrightarrow> x = y" |
516 unfolding dist_vector_def |
591 unfolding dist_vector_def |
521 unfolding dist_vector_def |
596 unfolding dist_vector_def |
522 apply (rule order_trans [OF _ setL2_triangle_ineq]) |
597 apply (rule order_trans [OF _ setL2_triangle_ineq]) |
523 apply (simp add: setL2_mono dist_triangle2) |
598 apply (simp add: setL2_mono dist_triangle2) |
524 done |
599 done |
525 next |
600 next |
|
601 (* FIXME: long proof! *) |
526 fix S :: "('a ^ 'b) set" |
602 fix S :: "('a ^ 'b) set" |
527 show "open S \<longleftrightarrow> (\<forall>x\<in>S. \<exists>e>0. \<forall>y. dist y x < e \<longrightarrow> y \<in> S)" |
603 show "open S \<longleftrightarrow> (\<forall>x\<in>S. \<exists>e>0. \<forall>y. dist y x < e \<longrightarrow> y \<in> S)" |
528 by (rule open_vector_def) |
604 unfolding open_vector_def open_dist |
|
605 apply safe |
|
606 apply (drule (1) bspec) |
|
607 apply clarify |
|
608 apply (subgoal_tac "\<exists>e>0. \<forall>i y. dist y (x$i) < e \<longrightarrow> y \<in> A i") |
|
609 apply clarify |
|
610 apply (rule_tac x=e in exI, clarify) |
|
611 apply (drule spec, erule mp, clarify) |
|
612 apply (drule spec, drule spec, erule mp) |
|
613 apply (erule le_less_trans [OF dist_nth_le]) |
|
614 apply (subgoal_tac "\<forall>i\<in>UNIV. \<exists>e>0. \<forall>y. dist y (x$i) < e \<longrightarrow> y \<in> A i") |
|
615 apply (drule finite_choice [OF finite], clarify) |
|
616 apply (rule_tac x="Min (range f)" in exI, simp) |
|
617 apply clarify |
|
618 apply (drule_tac x=i in spec, clarify) |
|
619 apply (erule (1) bspec) |
|
620 apply (drule (1) bspec, clarify) |
|
621 apply (subgoal_tac "\<exists>r. (\<forall>i::'b. 0 < r i) \<and> e = setL2 r UNIV") |
|
622 apply clarify |
|
623 apply (rule_tac x="\<lambda>i. {y. dist y (x$i) < r i}" in exI) |
|
624 apply (rule conjI) |
|
625 apply clarify |
|
626 apply (rule conjI) |
|
627 apply (clarify, rename_tac y) |
|
628 apply (rule_tac x="r i - dist y (x$i)" in exI, rule conjI, simp) |
|
629 apply clarify |
|
630 apply (simp only: less_diff_eq) |
|
631 apply (erule le_less_trans [OF dist_triangle]) |
|
632 apply simp |
|
633 apply clarify |
|
634 apply (drule spec, erule mp) |
|
635 apply (simp add: dist_vector_def setL2_strict_mono) |
|
636 apply (rule_tac x="\<lambda>i. e / sqrt (of_nat CARD('b))" in exI) |
|
637 apply (simp add: divide_pos_pos setL2_constant) |
|
638 done |
529 qed |
639 qed |
530 |
640 |
531 end |
641 end |
532 |
|
533 lemma dist_nth_le: "dist (x $ i) (y $ i) \<le> dist x y" |
|
534 unfolding dist_vector_def |
|
535 by (rule member_le_setL2) simp_all |
|
536 |
|
537 lemma tendsto_Cart_nth: |
|
538 fixes X :: "'a \<Rightarrow> 'b::metric_space ^ 'n::finite" |
|
539 assumes "tendsto (\<lambda>n. X n) a net" |
|
540 shows "tendsto (\<lambda>n. X n $ i) (a $ i) net" |
|
541 proof (rule tendstoI) |
|
542 fix e :: real assume "0 < e" |
|
543 with assms have "eventually (\<lambda>n. dist (X n) a < e) net" |
|
544 by (rule tendstoD) |
|
545 thus "eventually (\<lambda>n. dist (X n $ i) (a $ i) < e) net" |
|
546 proof (rule eventually_elim1) |
|
547 fix n :: 'a |
|
548 have "dist (X n $ i) (a $ i) \<le> dist (X n) a" |
|
549 by (rule dist_nth_le) |
|
550 also assume "dist (X n) a < e" |
|
551 finally show "dist (X n $ i) (a $ i) < e" . |
|
552 qed |
|
553 qed |
|
554 |
642 |
555 lemma LIMSEQ_Cart_nth: |
643 lemma LIMSEQ_Cart_nth: |
556 "(X ----> a) \<Longrightarrow> (\<lambda>n. X n $ i) ----> a $ i" |
644 "(X ----> a) \<Longrightarrow> (\<lambda>n. X n $ i) ----> a $ i" |
557 unfolding LIMSEQ_conv_tendsto by (rule tendsto_Cart_nth) |
645 unfolding LIMSEQ_conv_tendsto by (rule tendsto_Cart_nth) |
558 |
646 |