src/HOL/Lambda/ListOrder.ML
changeset 5318 72bf8039b53f
parent 5261 ce3c25c8a694
child 5326 8f9056ce5dfb
equal deleted inserted replaced
5317:3a9214482762 5318:72bf8039b53f
     3     Author:     Tobias Nipkow
     3     Author:     Tobias Nipkow
     4     Copyright   1998 TU Muenchen
     4     Copyright   1998 TU Muenchen
     5 *)
     5 *)
     6 
     6 
     7 Goalw [step1_def] "step1(r^-1) = (step1 r)^-1";
     7 Goalw [step1_def] "step1(r^-1) = (step1 r)^-1";
     8 by(Blast_tac 1);
     8 by (Blast_tac 1);
     9 qed "step1_converse";
     9 qed "step1_converse";
    10 Addsimps [step1_converse];
    10 Addsimps [step1_converse];
    11 
    11 
    12 Goal "(p : step1(r^-1)) = (p : (step1 r)^-1)";
    12 Goal "(p : step1(r^-1)) = (p : (step1 r)^-1)";
    13 by(Auto_tac);
    13 by (Auto_tac);
    14 qed "in_step1_converse";
    14 qed "in_step1_converse";
    15 AddIffs [in_step1_converse];
    15 AddIffs [in_step1_converse];
    16 
    16 
    17 Goalw [step1_def] "([],xs) ~: step1 r";
    17 Goalw [step1_def] "([],xs) ~: step1 r";
    18 by(Blast_tac 1);
    18 by (Blast_tac 1);
    19 qed "not_Nil_step1";
    19 qed "not_Nil_step1";
    20 AddIffs [not_Nil_step1];
    20 AddIffs [not_Nil_step1];
    21 
    21 
    22 Goalw [step1_def] "(xs,[]) ~: step1 r";
    22 Goalw [step1_def] "(xs,[]) ~: step1 r";
    23 by(Blast_tac 1);
    23 by (Blast_tac 1);
    24 qed "not_step1_Nil";
    24 qed "not_step1_Nil";
    25 AddIffs [not_step1_Nil];
    25 AddIffs [not_step1_Nil];
    26 
    26 
    27 Goalw [step1_def]
    27 Goalw [step1_def]
    28   "((y#ys,x#xs) : step1 r) = ((y,x):r & xs=ys | x=y & (ys,xs) : step1 r)";
    28   "((y#ys,x#xs) : step1 r) = ((y,x):r & xs=ys | x=y & (ys,xs) : step1 r)";
    29 by(Asm_full_simp_tac 1);
    29 by (Asm_full_simp_tac 1);
    30 br iffI 1;
    30 by (rtac iffI 1);
    31  be exE 1;
    31  by (etac exE 1);
    32  by(rename_tac "ts" 1);
    32  by (rename_tac "ts" 1);
    33  by(exhaust_tac "ts" 1);
    33  by (exhaust_tac "ts" 1);
    34   by(Force_tac 1);
    34   by (Force_tac 1);
    35  by(Force_tac 1);
    35  by (Force_tac 1);
    36 be disjE 1;
    36 by (etac disjE 1);
    37  by(Blast_tac 1);
    37  by (Blast_tac 1);
    38 by(blast_tac (claset() addIs [Cons_eq_appendI]) 1);
    38 by (blast_tac (claset() addIs [Cons_eq_appendI]) 1);
    39 qed "Cons_step1_Cons";
    39 qed "Cons_step1_Cons";
    40 AddIffs [Cons_step1_Cons];
    40 AddIffs [Cons_step1_Cons];
    41 
    41 
    42 Goalw [step1_def]
    42 Goalw [step1_def]
    43  "(ys,xs) : step1 r & vs=us | ys=xs & (vs,us) : step1 r \
    43  "(ys,xs) : step1 r & vs=us | ys=xs & (vs,us) : step1 r \
    44 \ ==> (ys@vs,xs@us) : step1 r";
    44 \ ==> (ys@vs,xs@us) : step1 r";
    45 by(Auto_tac);
    45 by (Auto_tac);
    46 by(Force_tac 1);
    46 by (Force_tac 1);
    47 by(blast_tac (claset() addIs [append_eq_appendI]) 1);
    47 by (blast_tac (claset() addIs [append_eq_appendI]) 1);
    48 qed "append_step1I";
    48 qed "append_step1I";
    49 
    49 
    50 Goal "[| (ys,x#xs) : step1 r; \
    50 Goal "[| (ys,x#xs) : step1 r; \
    51 \        !y. ys = y#xs --> (y,x) : r --> R; \
    51 \        !y. ys = y#xs --> (y,x) : r --> R; \
    52 \        !zs. ys = x#zs --> (zs,xs) : step1 r --> R \
    52 \        !zs. ys = x#zs --> (zs,xs) : step1 r --> R \
    53 \     |] ==> R";
    53 \     |] ==> R";
    54 by(exhaust_tac "ys" 1);
    54 by (exhaust_tac "ys" 1);
    55  by(asm_full_simp_tac (simpset() addsimps [step1_def]) 1);
    55  by (asm_full_simp_tac (simpset() addsimps [step1_def]) 1);
    56 by(Blast_tac 1);
    56 by (Blast_tac 1);
    57 val lemma = result();
    57 val lemma = result();
    58 bind_thm("Cons_step1E",
    58 bind_thm("Cons_step1E",
    59           impI RSN (3,impI RSN (3,allI RSN (3,impI RSN (2,
    59           impI RSN (3,impI RSN (3,allI RSN (3,impI RSN (2,
    60           impI RSN (2,allI RSN (2,lemma)))))));
    60           impI RSN (2,allI RSN (2,lemma)))))));
    61 AddSEs [Cons_step1E];
    61 AddSEs [Cons_step1E];
    62 
    62 
    63 Goalw [step1_def]
    63 Goalw [step1_def]
    64  "(ys@[y],xs@[x]) : step1 r ==> ((ys,xs) : step1 r & y=x | ys=xs & (y,x) : r)";
    64  "(ys@[y],xs@[x]) : step1 r ==> ((ys,xs) : step1 r & y=x | ys=xs & (y,x) : r)";
    65 by(Asm_full_simp_tac 1);
    65 by (Asm_full_simp_tac 1);
    66 by(clarify_tac (claset() delrules [disjCI]) 1);
    66 by (clarify_tac (claset() delrules [disjCI]) 1);
    67 by(rename_tac "vs" 1);
    67 by (rename_tac "vs" 1);
    68 by(res_inst_tac [("xs","vs")]rev_exhaust 1);
    68 by (res_inst_tac [("xs","vs")]rev_exhaust 1);
    69  by(Force_tac 1);
    69  by (Force_tac 1);
    70 by(Asm_full_simp_tac 1);
    70 by (Asm_full_simp_tac 1);
    71 by(Blast_tac 1);
    71 by (Blast_tac 1);
    72 qed "Snoc_step1_SnocD";
    72 qed "Snoc_step1_SnocD";
    73 
    73 
    74 Goal "x : acc r ==> !xs. xs : acc(step1 r) --> x#xs : acc(step1 r)";
    74 Goal "x : acc r ==> !xs. xs : acc(step1 r) --> x#xs : acc(step1 r)";
    75 be acc_induct 1;
    75 by (etac acc_induct 1);
    76 be thin_rl 1;
    76 by (etac thin_rl 1);
    77 by(Clarify_tac 1);
    77 by (Clarify_tac 1);
    78 be acc_induct 1;
    78 by (etac acc_induct 1);
    79 br accI 1;
    79 by (rtac accI 1);
    80 by(Blast_tac 1);
    80 by (Blast_tac 1);
    81 val lemma = result();
    81 val lemma = result();
    82 qed_spec_mp "Cons_acc_step1I";
    82 qed_spec_mp "Cons_acc_step1I";
    83 AddSIs [Cons_acc_step1I];
    83 AddSIs [Cons_acc_step1I];
    84 
    84 
    85 Goal "xs : lists(acc r) ==> xs : acc(step1 r)";
    85 Goal "xs : lists(acc r) ==> xs : acc(step1 r)";
    86 be lists.induct 1;
    86 be lists.induct 1;
    87  br accI 1;
    87  by (rtac accI 1);
    88  by(asm_full_simp_tac (simpset() addsimps [step1_def]) 1);
    88  by (asm_full_simp_tac (simpset() addsimps [step1_def]) 1);
    89 br accI 1;
    89 by (rtac accI 1);
    90 by(fast_tac (claset() addDs [acc_downward]) 1);
    90 by (fast_tac (claset() addDs [acc_downward]) 1);
    91 qed "lists_accD";
    91 qed "lists_accD";
    92 
    92 
    93 Goalw [step1_def]
    93 Goalw [step1_def]
    94  "[| x : set xs; (y,x) : r |] ==> ? ys. (ys,xs) : step1 r & y : set ys";
    94  "[| x : set xs; (y,x) : r |] ==> ? ys. (ys,xs) : step1 r & y : set ys";
    95 bd (in_set_conv_decomp RS iffD1) 1;
    95 by (dtac (in_set_conv_decomp RS iffD1) 1);
    96 by(Force_tac 1);
    96 by (Force_tac 1);
    97 qed "ex_step1I";
    97 qed "ex_step1I";
    98 
    98 
    99 Goal "xs : acc(step1 r) ==> xs : lists(acc r)";
    99 Goal "xs : acc(step1 r) ==> xs : lists(acc r)";
   100 be acc_induct 1;
   100 by (etac acc_induct 1);
   101 by(Clarify_tac 1);
   101 by (Clarify_tac 1);
   102 br accI 1;
   102 by (rtac accI 1);
   103 by(EVERY1[dtac ex_step1I, atac]);
   103 by (EVERY1[dtac ex_step1I, atac]);
   104 by(Blast_tac 1);
   104 by (Blast_tac 1);
   105 qed "lists_accI";
   105 qed "lists_accI";