src/HOL/Isar_examples/MultisetOrder.thy
changeset 8281 188e2924433e
parent 7982 d534b897ce39
child 8304 e132d147374b
equal deleted inserted replaced
8280:259073d16f84 8281:188e2924433e
    20 lemma less_add: "(N, M0 + {#a#}) : mult1 r ==>
    20 lemma less_add: "(N, M0 + {#a#}) : mult1 r ==>
    21     (EX M. (M, M0) : mult1 r & N = M + {#a#}) |
    21     (EX M. (M, M0) : mult1 r & N = M + {#a#}) |
    22     (EX K. (ALL b. elem K b --> (b, a) : r) & N = M0 + K)"
    22     (EX K. (ALL b. elem K b --> (b, a) : r) & N = M0 + K)"
    23   (concl is "?case1 (mult1 r) | ?case2");
    23   (concl is "?case1 (mult1 r) | ?case2");
    24 proof (unfold mult1_def);
    24 proof (unfold mult1_def);
    25   let ?r = "\<lambda>K a. ALL b. elem K b --> (b, a) : r";
    25   let ?r = "\\<lambda>K a. ALL b. elem K b --> (b, a) : r";
    26   let ?R = "\<lambda>N M. EX a M0 K. M = M0 + {#a#} & N = M0 + K & ?r K a";
    26   let ?R = "\\<lambda>N M. EX a M0 K. M = M0 + {#a#} & N = M0 + K & ?r K a";
    27   let ?case1 = "?case1 {(N, M). ?R N M}";
    27   let ?case1 = "?case1 {(N, M). ?R N M}";
    28 
    28 
    29   assume "(N, M0 + {#a#}) : {(N, M). ?R N M}";
    29   assume "(N, M0 + {#a#}) : {(N, M). ?R N M}";
    30   hence "EX a' M0' K.
    30   hence "EX a' M0' K.
    31       M0 + {#a#} = M0' + {#a'#} & N = M0' + K & ?r K a'"; by simp;
    31       M0 + {#a#} = M0' + {#a'#} & N = M0' + K & ?r K a'"; by simp;
    82       next;
    82       next;
    83 	fix K;
    83 	fix K;
    84 	assume N: "N = M0 + K";
    84 	assume N: "N = M0 + K";
    85 	assume "ALL b. elem K b --> (b, a) : r";
    85 	assume "ALL b. elem K b --> (b, a) : r";
    86 	have "?this --> M0 + K : ?W" (is "?P K");
    86 	have "?this --> M0 + K : ?W" (is "?P K");
    87 	proof (induct K rule: multiset_induct);
    87 	proof (induct K in rule: multiset_induct);
    88 	  from M0; have "M0 + {#} : ?W"; by simp;
    88 	  from M0; have "M0 + {#} : ?W"; by simp;
    89 	  thus "?P {#}"; ..;
    89 	  thus "?P {#}"; ..;
    90 
    90 
    91 	  fix K x; assume hyp: "?P K";
    91 	  fix K x; assume hyp: "?P K";
    92 	  show "?P (K + {#x#})";
    92 	  show "?P (K + {#x#})";
   107   }}; note tedious_reasoning = this;
   107   }}; note tedious_reasoning = this;
   108 
   108 
   109   assume wf: "wf r";
   109   assume wf: "wf r";
   110   fix M;
   110   fix M;
   111   show "M : ?W";
   111   show "M : ?W";
   112   proof (induct M rule: multiset_induct);
   112   proof (induct M in rule: multiset_induct);
   113     show "{#} : ?W";
   113     show "{#} : ?W";
   114     proof (rule accI);
   114     proof (rule accI);
   115       fix b; assume "(b, {#}) : ?R";
   115       fix b; assume "(b, {#}) : ?R";
   116       with not_less_empty; show "b : ?W"; by contradiction;
   116       with not_less_empty; show "b : ?W"; by contradiction;
   117     qed;
   117     qed;