src/ZF/Induct/Multiset.ML
changeset 12152 46f128d8133c
parent 12089 34e7693271a9
child 12484 7ad150f5fc10
equal deleted inserted replaced
12151:fb0fb0209c87 12152:46f128d8133c
   553 by (rotate_simp_tac "M:?u" 1);
   553 by (rotate_simp_tac "M:?u" 1);
   554 by (rotate_simp_tac "M:?u" 2);
   554 by (rotate_simp_tac "M:?u" 2);
   555 by (rotate_simp_tac "ALL a:A. ?u(a)" 1);
   555 by (rotate_simp_tac "ALL a:A. ?u(a)" 1);
   556 by (subgoal_tac "setsum(%x. $# mcount(M, x), A)=$# succ(x)" 1);
   556 by (subgoal_tac "setsum(%x. $# mcount(M, x), A)=$# succ(x)" 1);
   557 by (dtac setsum_succD 1 THEN Auto_tac);
   557 by (dtac setsum_succD 1 THEN Auto_tac);
   558 by (case_tac "1 <M`xa" 1);
   558 by (case_tac "1 <M`a" 1);
   559 by (dtac not_lt_imp_le 2);
   559 by (dtac not_lt_imp_le 2);
   560 by (ALLGOALS(asm_full_simp_tac (simpset() addsimps [nat_le_1_cases])));
   560 by (ALLGOALS(asm_full_simp_tac (simpset() addsimps [nat_le_1_cases])));
   561 by (subgoal_tac "M=(M(xa:=M`xa #- 1))(xa:=(M(xa:=M`xa #- 1))`xa #+ 1)" 1);
   561 by (subgoal_tac "M=(M(a:=M`a #- 1))(a:=(M(a:=M`a #- 1))`a #+ 1)" 1);
   562 by (res_inst_tac [("A","A"),("B","%x. nat"),("D","%x. nat")] fun_extension 2);
   562 by (res_inst_tac [("A","A"),("B","%x. nat"),("D","%x. nat")] fun_extension 2);
   563 by (REPEAT(rtac update_type 3));
   563 by (REPEAT(rtac update_type 3));
   564 by (ALLGOALS(Asm_simp_tac));
   564 by (ALLGOALS(Asm_simp_tac));
   565 by (Clarify_tac 2);
   565 by (Clarify_tac 2);
   566 by (rtac (succ_pred_eq_self RS sym) 2);
   566 by (rtac (succ_pred_eq_self RS sym) 2);
   568 by (rtac subst 1 THEN rtac sym 1 THEN Blast_tac 1 THEN resolve_tac prems 1);
   568 by (rtac subst 1 THEN rtac sym 1 THEN Blast_tac 1 THEN resolve_tac prems 1);
   569 by (simp_tac (simpset() addsimps [multiset_def, multiset_fun_iff]) 1);
   569 by (simp_tac (simpset() addsimps [multiset_def, multiset_fun_iff]) 1);
   570 by (res_inst_tac [("x", "A")] exI 1);
   570 by (res_inst_tac [("x", "A")] exI 1);
   571 by (force_tac (claset() addIs [update_type], simpset()) 1);
   571 by (force_tac (claset() addIs [update_type], simpset()) 1);
   572 by (asm_simp_tac (simpset() addsimps [mset_of_def, mcount_def]) 1);
   572 by (asm_simp_tac (simpset() addsimps [mset_of_def, mcount_def]) 1);
   573 by (dres_inst_tac [("x", "M(xa := M ` xa #- 1)")] spec 1);
   573 by (dres_inst_tac [("x", "M(a := M ` a #- 1)")] spec 1);
   574 by (dtac mp 1 THEN dtac mp 2);
   574 by (dtac mp 1 THEN dtac mp 2);
   575 by (ALLGOALS(Asm_full_simp_tac));
   575 by (ALLGOALS(Asm_full_simp_tac));
   576 by (res_inst_tac [("x", "A")] exI 1);
   576 by (res_inst_tac [("x", "A")] exI 1);
   577 by (auto_tac (claset() addIs [update_type], simpset()));
   577 by (auto_tac (claset() addIs [update_type], simpset()));
   578 by (subgoal_tac "Finite({x:cons(xa, A). x~=xa-->0<M`x})" 1);
   578 by (subgoal_tac "Finite({x:cons(a, A). x~=a-->0<M`x})" 1);
   579 by (blast_tac(claset() addIs [Collect_subset RS subset_Finite,Finite_cons])2);
   579 by (blast_tac(claset() addIs [Collect_subset RS subset_Finite,Finite_cons])2);
   580 by (dres_inst_tac [("A", "{x:cons(xa, A). x~=xa-->0<M`x}")] setsum_decr 1);
   580 by (dres_inst_tac [("A", "{x:cons(a, A). x~=a-->0<M`x}")] setsum_decr 1);
   581 by (dres_inst_tac [("x", "M")] spec 1);
   581 by (dres_inst_tac [("x", "M")] spec 1);
   582 by (subgoal_tac "multiset(M)" 1);
   582 by (subgoal_tac "multiset(M)" 1);
   583 by (simp_tac (simpset() addsimps [multiset_def, multiset_fun_iff]) 2);
   583 by (simp_tac (simpset() addsimps [multiset_def, multiset_fun_iff]) 2);
   584 by (res_inst_tac [("x", "A")] exI 2);
   584 by (res_inst_tac [("x", "A")] exI 2);
   585 by (Force_tac 2);
   585 by (Force_tac 2);
   586 by (ALLGOALS(asm_full_simp_tac (simpset() addsimps [mset_of_def])));
   586 by (ALLGOALS(asm_full_simp_tac (simpset() addsimps [mset_of_def])));
   587 by (dres_inst_tac [("psi", "ALL x:A. ?u(x)")] asm_rl 1);
   587 by (dres_inst_tac [("psi", "ALL x:A. ?u(x)")] asm_rl 1);
   588 by (dres_inst_tac [("x", "xa")] bspec 1);
   588 by (dres_inst_tac [("x", "a")] bspec 1);
   589 by (Asm_simp_tac 1);
   589 by (Asm_simp_tac 1);
   590 by (subgoal_tac "cons(xa, A)= A" 1);
   590 by (subgoal_tac "cons(a, A)= A" 1);
   591 by (Blast_tac 2);
   591 by (Blast_tac 2);
   592 by (rotate_simp_tac "cons(xa, A) = A" 1);
   592 by (rotate_simp_tac "cons(a, A) = A" 1);
   593 by (rotate_simp_tac "ALL x:A. ?u(x)" 1);
   593 by (rotate_simp_tac "ALL x:A. ?u(x)" 1);
   594 by (rotate_simp_tac "ALL x:A. ?u(x)" 2);
   594 by (rotate_simp_tac "ALL x:A. ?u(x)" 2);
   595 by (subgoal_tac "M=cons(<xa, M`xa>, restrict(M, A-{xa}))" 1);
   595 by (subgoal_tac "M=cons(<a, M`a>, restrict(M, A-{a}))" 1);
   596 by (rtac  fun_cons_restrict_eq 2);
   596 by (rtac  fun_cons_restrict_eq 2);
   597 by (subgoal_tac "cons(xa, A-{xa}) = A" 2);
   597 by (subgoal_tac "cons(a, A-{a}) = A" 2);
   598 by (REPEAT(Force_tac 2));
   598 by (REPEAT(Force_tac 2));
   599 by (res_inst_tac [("a", "cons(<xa, 1>, restrict(M, A - {xa}))")] ssubst 1);
   599 by (res_inst_tac [("a", "cons(<a, 1>, restrict(M, A - {a}))")] ssubst 1);
   600 by (Asm_full_simp_tac 1);
   600 by (Asm_full_simp_tac 1);
   601 by (subgoal_tac "multiset(restrict(M, A - {xa}))" 1);
   601 by (subgoal_tac "multiset(restrict(M, A - {a}))" 1);
   602 by (simp_tac (simpset() addsimps [multiset_def, multiset_fun_iff]) 2);
   602 by (simp_tac (simpset() addsimps [multiset_def, multiset_fun_iff]) 2);
   603 by (res_inst_tac [("x", "A-{xa}")] exI 2);
   603 by (res_inst_tac [("x", "A-{a}")] exI 2);
   604 by Safe_tac;
   604 by Safe_tac;
   605 by (res_inst_tac [("A", "A-{xa}")] apply_type 3);
   605 by (res_inst_tac [("A", "A-{a}")] apply_type 3);
   606 by (asm_simp_tac (simpset() addsimps [restrict]) 5);
   606 by (asm_simp_tac (simpset() addsimps [restrict]) 5);
   607 by (REPEAT(blast_tac (claset() addIs [Finite_Diff, restrict_type]) 2));;
   607 by (REPEAT(blast_tac (claset() addIs [Finite_Diff, restrict_type]) 2));;
   608 by (resolve_tac prems 1);
   608 by (resolve_tac prems 1);
   609 by (assume_tac 1);
   609 by (assume_tac 1);
   610 by (asm_full_simp_tac (simpset() addsimps [mset_of_def]) 1);
   610 by (asm_full_simp_tac (simpset() addsimps [mset_of_def]) 1);
   611 by (dres_inst_tac [("x", "restrict(M, A-{xa})")] spec 1);
   611 by (dres_inst_tac [("x", "restrict(M, A-{a})")] spec 1);
   612 by (dtac mp 1);
   612 by (dtac mp 1);
   613 by (res_inst_tac [("x", "A-{xa}")] exI 1);
   613 by (res_inst_tac [("x", "A-{a}")] exI 1);
   614 by (auto_tac (claset() addIs [Finite_Diff, restrict_type], 
   614 by (auto_tac (claset() addIs [Finite_Diff, restrict_type], 
   615              simpset() addsimps [restrict]));
   615              simpset() addsimps [restrict]));
   616 by (forw_inst_tac [("A", "A"), ("M", "M"), ("a", "xa")] setsum_decr3 1);
   616 by (forw_inst_tac [("A", "A"), ("M", "M"), ("a", "a")] setsum_decr3 1);
   617 by (asm_simp_tac  (simpset() addsimps [multiset_def, multiset_fun_iff]) 1);
   617 by (asm_simp_tac  (simpset() addsimps [multiset_def, multiset_fun_iff]) 1);
   618 by (Blast_tac 1);
   618 by (Blast_tac 1);
   619 by (asm_simp_tac (simpset() addsimps [mset_of_def]) 1);
   619 by (asm_simp_tac (simpset() addsimps [mset_of_def]) 1);
   620 by (dres_inst_tac [("b", "if ?u then ?v else ?w")] sym 1);
   620 by (dres_inst_tac [("b", "if ?u then ?v else ?w")] sym 1);
   621 by (ALLGOALS(rotate_simp_tac "ALL x:A. ?u(x)"));
   621 by (ALLGOALS(rotate_simp_tac "ALL x:A. ?u(x)"));
   622 by (subgoal_tac "{x:A - {xa} . 0 < restrict(M, A - {x}) ` x} = A - {xa}" 1);
   622 by (subgoal_tac "{x:A - {a} . 0 < restrict(M, A - {x}) ` x} = A - {a}" 1);
   623 by (auto_tac (claset() addSIs [setsum_cong], 
   623 by (auto_tac (claset() addSIs [setsum_cong], 
   624               simpset() addsimps [zdiff_eq_iff, 
   624               simpset() addsimps [zdiff_eq_iff, 
   625                zadd_commute, multiset_def, multiset_fun_iff,mset_of_def]));
   625                zadd_commute, multiset_def, multiset_fun_iff,mset_of_def]));
   626 qed "multiset_induct_aux";
   626 qed "multiset_induct_aux";
   627 
   627 
   822 by (ALLGOALS(asm_full_simp_tac(simpset() 
   822 by (ALLGOALS(asm_full_simp_tac(simpset() 
   823     addsimps [Un_subset_iff, multiset_on_def])));
   823     addsimps [Un_subset_iff, multiset_on_def])));
   824 by (res_inst_tac [("x", "x")] bexI 3);
   824 by (res_inst_tac [("x", "x")] bexI 3);
   825 by (res_inst_tac [("x", "xb")] bexI 3);
   825 by (res_inst_tac [("x", "xb")] bexI 3);
   826 by (Asm_simp_tac 3);
   826 by (Asm_simp_tac 3);
   827 by (res_inst_tac [("x", "xc")] bexI 3);
   827 by (res_inst_tac [("x", "K")] bexI 3);
   828 by (ALLGOALS(asm_simp_tac (simpset() 
   828 by (ALLGOALS(asm_simp_tac (simpset() 
   829     addsimps [FiniteFun_iff_multiset_on, multiset_on_def])));
   829     addsimps [FiniteFun_iff_multiset_on, multiset_on_def])));
   830 by Auto_tac;
   830 by Auto_tac;
   831 qed "multirel1_mono1";
   831 qed "multirel1_mono1";
   832 
   832 
   834 by (auto_tac (claset(), simpset() addsimps [FiniteFun_iff_multiset_on]));
   834 by (auto_tac (claset(), simpset() addsimps [FiniteFun_iff_multiset_on]));
   835 by (res_inst_tac [("x", "x")] bexI 1);
   835 by (res_inst_tac [("x", "x")] bexI 1);
   836 by (res_inst_tac [("x", "xb")] bexI 1);
   836 by (res_inst_tac [("x", "xb")] bexI 1);
   837 by (ALLGOALS(asm_full_simp_tac (simpset() 
   837 by (ALLGOALS(asm_full_simp_tac (simpset() 
   838     addsimps [FiniteFun_iff_multiset_on, multiset_on_def])));
   838     addsimps [FiniteFun_iff_multiset_on, multiset_on_def])));
   839 by (res_inst_tac [("x", "xc")] bexI 1);
   839 by (res_inst_tac [("x", "K")] bexI 1);
   840 by (ALLGOALS(asm_full_simp_tac (simpset() 
   840 by (ALLGOALS(asm_full_simp_tac (simpset() 
   841     addsimps [FiniteFun_iff_multiset_on,multiset_on_def])));
   841     addsimps [FiniteFun_iff_multiset_on,multiset_on_def])));
   842 by Auto_tac;
   842 by Auto_tac;
   843 qed "multirel1_mono2";
   843 qed "multirel1_mono2";
   844 
   844