src/ZF/Induct/Multiset.thy
changeset 46953 2b6e55924af3
parent 46822 95f1e700b712
child 57492 74bf65a1910a
equal deleted inserted replaced
46952:5e1bcfdcb175 46953:2b6e55924af3
    91       \<exists>a \<in> A. \<exists>M0 \<in> Mult(A). \<exists>K \<in> Mult(A).
    91       \<exists>a \<in> A. \<exists>M0 \<in> Mult(A). \<exists>K \<in> Mult(A).
    92       N=M0 +# {#a#} & M=M0 +# K & (\<forall>b \<in> mset_of(K). <b,a> \<in> r)}"
    92       N=M0 +# {#a#} & M=M0 +# K & (\<forall>b \<in> mset_of(K). <b,a> \<in> r)}"
    93 
    93 
    94 definition
    94 definition
    95   multirel :: "[i, i] => i"  where
    95   multirel :: "[i, i] => i"  where
    96   "multirel(A, r) == multirel1(A, r)^+"                 
    96   "multirel(A, r) == multirel1(A, r)^+"
    97 
    97 
    98   (* ordinal multiset orderings *)
    98   (* ordinal multiset orderings *)
    99 
    99 
   100 definition
   100 definition
   101   omultiset :: "i => o"  where
   101   omultiset :: "i => o"  where
   444 
   444 
   445 lemma nat_add_eq_1_cases: "[| m \<in> nat; n \<in> nat |] ==> (m #+ n = 1) \<longleftrightarrow> (m=1 & n=0) | (m=0 & n=1)"
   445 lemma nat_add_eq_1_cases: "[| m \<in> nat; n \<in> nat |] ==> (m #+ n = 1) \<longleftrightarrow> (m=1 & n=0) | (m=0 & n=1)"
   446 by (induct_tac n) auto
   446 by (induct_tac n) auto
   447 
   447 
   448 lemma munion_is_single:
   448 lemma munion_is_single:
   449      "[|multiset(M); multiset(N)|] 
   449      "[|multiset(M); multiset(N)|]
   450       ==> (M +# N = {#a#}) \<longleftrightarrow>  (M={#a#} & N=0) | (M = 0 & N = {#a#})"
   450       ==> (M +# N = {#a#}) \<longleftrightarrow>  (M={#a#} & N=0) | (M = 0 & N = {#a#})"
   451 apply (simp (no_asm_simp) add: multiset_equality)
   451 apply (simp (no_asm_simp) add: multiset_equality)
   452 apply safe
   452 apply safe
   453 apply simp_all
   453 apply simp_all
   454 apply (case_tac "aa=a")
   454 apply (case_tac "aa=a")
   745 apply (rule_tac x = K in bexI)
   745 apply (rule_tac x = K in bexI)
   746 apply (auto simp add: Mult_iff_multiset)
   746 apply (auto simp add: Mult_iff_multiset)
   747 done
   747 done
   748 
   748 
   749 lemma multirel1_mono2: "r\<subseteq>s ==> multirel1(A,r)\<subseteq>multirel1(A, s)"
   749 lemma multirel1_mono2: "r\<subseteq>s ==> multirel1(A,r)\<subseteq>multirel1(A, s)"
   750 apply (simp add: multirel1_def, auto) 
   750 apply (simp add: multirel1_def, auto)
   751 apply (rule_tac x = a in bexI)
   751 apply (rule_tac x = a in bexI)
   752 apply (rule_tac x = M0 in bexI)
   752 apply (rule_tac x = M0 in bexI)
   753 apply (simp_all add: Mult_iff_multiset)
   753 apply (simp_all add: Mult_iff_multiset)
   754 apply (rule_tac x = K in bexI)
   754 apply (rule_tac x = K in bexI)
   755 apply (simp_all add: Mult_iff_multiset, auto)
   755 apply (simp_all add: Mult_iff_multiset, auto)
   805 apply (auto simp add: Mult_iff_multiset)
   805 apply (auto simp add: Mult_iff_multiset)
   806 apply (erule_tac P = "\<forall>x \<in> mset_of (K) . <x, a> \<in> r" in rev_mp)
   806 apply (erule_tac P = "\<forall>x \<in> mset_of (K) . <x, a> \<in> r" in rev_mp)
   807 apply (erule_tac P = "mset_of (K) \<subseteq>A" in rev_mp)
   807 apply (erule_tac P = "mset_of (K) \<subseteq>A" in rev_mp)
   808 apply (erule_tac M = K in multiset_induct)
   808 apply (erule_tac M = K in multiset_induct)
   809 (* three subgoals *)
   809 (* three subgoals *)
   810 (* subgoal 1: the induction base case *)
   810 (* subgoal 1 \<in> the induction base case *)
   811 apply (simp (no_asm_simp))
   811 apply (simp (no_asm_simp))
   812 (* subgoal 2: the induction general case *)
   812 (* subgoal 2 \<in> the induction general case *)
   813 apply (simp add: Ball_def Un_subset_iff, clarify)
   813 apply (simp add: Ball_def Un_subset_iff, clarify)
   814 apply (drule_tac x = aa in spec, simp)
   814 apply (drule_tac x = aa in spec, simp)
   815 apply (subgoal_tac "aa \<in> A")
   815 apply (subgoal_tac "aa \<in> A")
   816 prefer 2 apply blast
   816 prefer 2 apply blast
   817 apply (drule_tac x = "M0 +# M" and P =
   817 apply (drule_tac x = "M0 +# M" and P =
   818        "%x. x \<in> acc(multirel1(A, r)) \<longrightarrow> ?Q(x)" in spec)
   818        "%x. x \<in> acc(multirel1(A, r)) \<longrightarrow> ?Q(x)" in spec)
   819 apply (simp add: munion_assoc [symmetric])
   819 apply (simp add: munion_assoc [symmetric])
   820 (* subgoal 3: additional conditions *)
   820 (* subgoal 3 \<in> additional conditions *)
   821 apply (auto intro!: multirel1_base [THEN fieldI2] simp add: Mult_iff_multiset)
   821 apply (auto intro!: multirel1_base [THEN fieldI2] simp add: Mult_iff_multiset)
   822 done
   822 done
   823 
   823 
   824 lemma lemma2: "[| \<forall>b \<in> A. <b,a> \<in> r
   824 lemma lemma2: "[| \<forall>b \<in> A. <b,a> \<in> r
   825    \<longrightarrow> (\<forall>M \<in> acc(multirel1(A, r)). M +# {#b#} :acc(multirel1(A, r)));
   825    \<longrightarrow> (\<forall>M \<in> acc(multirel1(A, r)). M +# {#b#} :acc(multirel1(A, r)));