535 |
535 |
536 lemma Sigma_succ2: "A * succ(B) = A*{B} Un A*B" |
536 lemma Sigma_succ2: "A * succ(B) = A*{B} Un A*B" |
537 by blast |
537 by blast |
538 |
538 |
539 lemma SUM_UN_distrib1: |
539 lemma SUM_UN_distrib1: |
540 "(\<Sigma>x \<in> (\<Union>y\<in>A. C(y)). B(x)) = (\<Union>y\<in>A. \<Sigma>x\<in>C(y). B(x))" |
540 "(\<Sigma> x \<in> (\<Union>y\<in>A. C(y)). B(x)) = (\<Union>y\<in>A. \<Sigma> x\<in>C(y). B(x))" |
541 by blast |
541 by blast |
542 |
542 |
543 lemma SUM_UN_distrib2: |
543 lemma SUM_UN_distrib2: |
544 "(\<Sigma>i\<in>I. \<Union>j\<in>J. C(i,j)) = (\<Union>j\<in>J. \<Sigma>i\<in>I. C(i,j))" |
544 "(\<Sigma> i\<in>I. \<Union>j\<in>J. C(i,j)) = (\<Union>j\<in>J. \<Sigma> i\<in>I. C(i,j))" |
545 by blast |
545 by blast |
546 |
546 |
547 lemma SUM_Un_distrib1: |
547 lemma SUM_Un_distrib1: |
548 "(\<Sigma>i\<in>I Un J. C(i)) = (\<Sigma>i\<in>I. C(i)) Un (\<Sigma>j\<in>J. C(j))" |
548 "(\<Sigma> i\<in>I Un J. C(i)) = (\<Sigma> i\<in>I. C(i)) Un (\<Sigma> j\<in>J. C(j))" |
549 by blast |
549 by blast |
550 |
550 |
551 lemma SUM_Un_distrib2: |
551 lemma SUM_Un_distrib2: |
552 "(\<Sigma>i\<in>I. A(i) Un B(i)) = (\<Sigma>i\<in>I. A(i)) Un (\<Sigma>i\<in>I. B(i))" |
552 "(\<Sigma> i\<in>I. A(i) Un B(i)) = (\<Sigma> i\<in>I. A(i)) Un (\<Sigma> i\<in>I. B(i))" |
553 by blast |
553 by blast |
554 |
554 |
555 (*First-order version of the above, for rewriting*) |
555 (*First-order version of the above, for rewriting*) |
556 lemma prod_Un_distrib2: "I * (A Un B) = I*A Un I*B" |
556 lemma prod_Un_distrib2: "I * (A Un B) = I*A Un I*B" |
557 by (rule SUM_Un_distrib2) |
557 by (rule SUM_Un_distrib2) |
558 |
558 |
559 lemma SUM_Int_distrib1: |
559 lemma SUM_Int_distrib1: |
560 "(\<Sigma>i\<in>I Int J. C(i)) = (\<Sigma>i\<in>I. C(i)) Int (\<Sigma>j\<in>J. C(j))" |
560 "(\<Sigma> i\<in>I Int J. C(i)) = (\<Sigma> i\<in>I. C(i)) Int (\<Sigma> j\<in>J. C(j))" |
561 by blast |
561 by blast |
562 |
562 |
563 lemma SUM_Int_distrib2: |
563 lemma SUM_Int_distrib2: |
564 "(\<Sigma>i\<in>I. A(i) Int B(i)) = (\<Sigma>i\<in>I. A(i)) Int (\<Sigma>i\<in>I. B(i))" |
564 "(\<Sigma> i\<in>I. A(i) Int B(i)) = (\<Sigma> i\<in>I. A(i)) Int (\<Sigma> i\<in>I. B(i))" |
565 by blast |
565 by blast |
566 |
566 |
567 (*First-order version of the above, for rewriting*) |
567 (*First-order version of the above, for rewriting*) |
568 lemma prod_Int_distrib2: "I * (A Int B) = I*A Int I*B" |
568 lemma prod_Int_distrib2: "I * (A Int B) = I*A Int I*B" |
569 by (rule SUM_Int_distrib2) |
569 by (rule SUM_Int_distrib2) |
570 |
570 |
571 (*Cf Aczel, Non-Well-Founded Sets, page 115*) |
571 (*Cf Aczel, Non-Well-Founded Sets, page 115*) |
572 lemma SUM_eq_UN: "(\<Sigma>i\<in>I. A(i)) = (\<Union>i\<in>I. {i} * A(i))" |
572 lemma SUM_eq_UN: "(\<Sigma> i\<in>I. A(i)) = (\<Union>i\<in>I. {i} * A(i))" |
573 by blast |
573 by blast |
574 |
574 |
575 lemma times_subset_iff: |
575 lemma times_subset_iff: |
576 "(A'*B' \<subseteq> A*B) <-> (A' = 0 | B' = 0 | (A'\<subseteq>A) & (B'\<subseteq>B))" |
576 "(A'*B' \<subseteq> A*B) <-> (A' = 0 | B' = 0 | (A'\<subseteq>A) & (B'\<subseteq>B))" |
577 by blast |
577 by blast |
578 |
578 |
579 lemma Int_Sigma_eq: |
579 lemma Int_Sigma_eq: |
580 "(\<Sigma>x \<in> A'. B'(x)) Int (\<Sigma>x \<in> A. B(x)) = (\<Sigma>x \<in> A' Int A. B'(x) Int B(x))" |
580 "(\<Sigma> x \<in> A'. B'(x)) Int (\<Sigma> x \<in> A. B(x)) = (\<Sigma> x \<in> A' Int A. B'(x) Int B(x))" |
581 by blast |
581 by blast |
582 |
582 |
583 (** Domain **) |
583 (** Domain **) |
584 |
584 |
585 lemma domain_iff: "a: domain(r) <-> (EX y. <a,y>\<in> r)" |
585 lemma domain_iff: "a: domain(r) <-> (EX y. <a,y>\<in> r)" |