src/HOL/ex/Group.ML
changeset 11701 3d51fbf81c17
parent 8936 a1c426541757
equal deleted inserted replaced
11700:a0e6bda62b7b 11701:3d51fbf81c17
     8 
     8 
     9 (* Derives the well-known convergent set of equations for groups
     9 (* Derives the well-known convergent set of equations for groups
    10    based on the unary inverse 0-x.
    10    based on the unary inverse 0-x.
    11 *)
    11 *)
    12 
    12 
    13 Goal "!!x::'a::add_group. (0-x)+(x+y) = y";
    13 Goal "!!x::'a::add_group. (0 - x) + (x + y) = y";
    14 by (rtac trans 1);
    14 by (rtac trans 1);
    15 by (rtac (plus_assoc RS sym) 1);
    15 by (rtac (plus_assoc RS sym) 1);
    16 by (stac left_inv 1);
    16 by (stac left_inv 1);
    17 by (rtac zeroL 1);
    17 by (rtac zeroL 1);
    18 qed "left_inv2";
    18 qed "left_inv2";
    19 
    19 
    20 Goal "!!x::'a::add_group. (0-(0-x)) = x";
    20 Goal "!!x::'a::add_group. (0 - (0 - x)) = x";
    21 by (rtac trans 1);
    21 by (rtac trans 1);
    22 by (res_inst_tac [("x","0-x")] left_inv2 2);
    22 by (res_inst_tac [("x","0 - x")] left_inv2 2);
    23 by (stac left_inv 1);
    23 by (stac left_inv 1);
    24 by (rtac (zeroR RS sym) 1);
    24 by (rtac (zeroR RS sym) 1);
    25 qed "inv_inv";
    25 qed "inv_inv";
    26 
    26 
    27 Goal "0-0 = (0::'a::add_group)";
    27 Goal "0 - 0 = (0::'a::add_group)";
    28 by (rtac trans 1);
    28 by (rtac trans 1);
    29 by (rtac (zeroR RS sym) 1);
    29 by (rtac (zeroR RS sym) 1);
    30 by (rtac trans 1);
    30 by (rtac trans 1);
    31 by (res_inst_tac [("x","0")] left_inv2 2);
    31 by (res_inst_tac [("x","0")] left_inv2 2);
    32 by (simp_tac (simpset() addsimps [zeroR]) 1);
    32 by (simp_tac (simpset() addsimps [zeroR]) 1);
    33 qed "inv_zero";
    33 qed "inv_zero";
    34 
    34 
    35 Goal "!!x::'a::add_group. x+(0-x) = 0";
    35 Goal "!!x::'a::add_group. x + (0 - x) = 0";
    36 by (rtac trans 1);
    36 by (rtac trans 1);
    37 by (res_inst_tac [("x","0-x")] left_inv 2);
    37 by (res_inst_tac [("x","0-x")] left_inv 2);
    38 by (stac inv_inv 1);
    38 by (stac inv_inv 1);
    39 by (rtac refl 1);
    39 by (rtac refl 1);
    40 qed "right_inv";
    40 qed "right_inv";
    41 
    41 
    42 Goal "!!x::'a::add_group. x+((0-x)+y) = y";
    42 Goal "!!x::'a::add_group. x + ((0 - x) + y) = y";
    43 by (rtac trans 1);
    43 by (rtac trans 1);
    44 by (res_inst_tac [("x","0-x")] left_inv2 2);
    44 by (res_inst_tac [("x","0 - x")] left_inv2 2);
    45 by (stac inv_inv 1);
    45 by (stac inv_inv 1);
    46 by (rtac refl 1);
    46 by (rtac refl 1);
    47 qed "right_inv2";
    47 qed "right_inv2";
    48 
    48 
    49 val plus_cong = read_instantiate [("f1","op +")] (arg_cong RS cong);
    49 val plus_cong = read_instantiate [("f1","op +")] (arg_cong RS cong);
    50 
    50 
    51 Goal "!!x::'a::add_group. 0-(x+y) = (0-y)+(0-x)";
    51 Goal "!!x::'a::add_group. 0 - (x + y) = (0 - y) + (0 - x)";
    52 by (rtac trans 1);
    52 by (rtac trans 1);
    53  by (rtac zeroR 2);
    53  by (rtac zeroR 2);
    54 by (rtac trans 1);
    54 by (rtac trans 1);
    55  by (rtac plus_cong 2);
    55  by (rtac plus_cong 2);
    56   by (rtac refl 2);
    56   by (rtac refl 2);
    63         [plus_assoc,left_inv,left_inv2,right_inv,right_inv2]) 2);
    63         [plus_assoc,left_inv,left_inv2,right_inv,right_inv2]) 2);
    64  by (rtac refl 2);
    64  by (rtac refl 2);
    65 by (rtac (zeroL RS sym) 1);
    65 by (rtac (zeroL RS sym) 1);
    66 qed "inv_plus";
    66 qed "inv_plus";
    67 
    67 
    68 (*** convergent TRS for groups with unary inverse 0-x ***)
    68 (*** convergent TRS for groups with unary inverse 0 - x ***)
    69 val group1_simps =
    69 val group1_simps =
    70   [zeroL,zeroR,plus_assoc,left_inv,left_inv2,right_inv,right_inv2,inv_inv,
    70   [zeroL,zeroR,plus_assoc,left_inv,left_inv2,right_inv,right_inv2,inv_inv,
    71    inv_zero,inv_plus];
    71    inv_zero,inv_plus];
    72 
    72 
    73 val group1_tac =
    73 val group1_tac =
    74   let val ss = HOL_basic_ss addsimps group1_simps
    74   let val ss = HOL_basic_ss addsimps group1_simps
    75   in simp_tac ss end;
    75   in simp_tac ss end;
    76 
    76 
    77 (* I believe there is no convergent TRS for groups with binary `-',
    77 (* I believe there is no convergent TRS for groups with binary `-',
    78    unless you have an extra unary `-' and simply define x-y = x+(-y).
    78    unless you have an extra unary `-' and simply define x - y = x + (-y).
    79    This does not work with only a binary `-' because x-y = x+(0-y) does
    79    This does not work with only a binary `-' because x - y = x + (0 - y) does
    80    not terminate. Hence we have a special tactic for converting all
    80    not terminate. Hence we have a special tactic for converting all
    81    occurrences of x-y into x+(0-y):
    81    occurrences of x - y into x + (0 - y):
    82 *)
    82 *)
    83 
    83 
    84 local
    84 local
    85 fun find(Const("op -",Type("fun",[T,_]))$s$t) = [(T,s,t)] @ find s @ find t
    85 fun find(Const("op -",Type("fun",[T,_]))$s$t) = [(T,s,t)] @ find s @ find t
    86   | find(s$t) = find s @ find t
    86   | find(s$t) = find s @ find t
   100 end;
   100 end;
   101 
   101 
   102 (* The following two equations are not used in any of the decision procedures,
   102 (* The following two equations are not used in any of the decision procedures,
   103    but are still very useful. They also demonstrate mk_group1_tac.
   103    but are still very useful. They also demonstrate mk_group1_tac.
   104 *)
   104 *)
   105 Goal "x-x = (0::'a::add_group)";
   105 Goal "x - x = (0::'a::add_group)";
   106 by (mk_group1_tac 1);
   106 by (mk_group1_tac 1);
   107 by (group1_tac 1);
   107 by (group1_tac 1);
   108 qed "minus_self_zero";
   108 qed "minus_self_zero";
   109 
   109 
   110 Goal "x-0 = (x::'a::add_group)";
   110 Goal "x - 0 = (x::'a::add_group)";
   111 by (mk_group1_tac 1);
   111 by (mk_group1_tac 1);
   112 by (group1_tac 1);
   112 by (group1_tac 1);
   113 qed "minus_zero";
   113 qed "minus_zero";
   114 
   114 
   115 (*** Abelian Groups ***)
   115 (*** Abelian Groups ***)
   120 by (rtac trans 1);
   120 by (rtac trans 1);
   121 by (rtac plus_assoc 1);
   121 by (rtac plus_assoc 1);
   122 by (simp_tac (simpset() addsimps [plus_commute]) 1);
   122 by (simp_tac (simpset() addsimps [plus_commute]) 1);
   123 qed "plus_commuteL";
   123 qed "plus_commuteL";
   124 
   124 
   125 (* Convergent TRS for Abelian groups with unary inverse 0-x.
   125 (* Convergent TRS for Abelian groups with unary inverse 0 - x.
   126    Requires ordered rewriting
   126    Requires ordered rewriting
   127 *)
   127 *)
   128 
   128 
   129 val agroup1_simps = plus_commute::plus_commuteL::group1_simps;
   129 val agroup1_simps = plus_commute::plus_commuteL::group1_simps;
   130 
   130