Integ/Equiv.ML
changeset 242 8cd051d5cf74
parent 216 12943ab62cc5
equal deleted inserted replaced
241:b67c8e01ae04 242:8cd051d5cf74
    17 goalw Equiv.thy [trans_def,sym_def,converse_def]
    17 goalw Equiv.thy [trans_def,sym_def,converse_def]
    18     "!!r. [| sym(r); trans(r) |] ==> converse(r) O r <= r";
    18     "!!r. [| sym(r); trans(r) |] ==> converse(r) O r <= r";
    19 by (fast_tac (comp_cs addSEs [converseD]) 1);
    19 by (fast_tac (comp_cs addSEs [converseD]) 1);
    20 qed "sym_trans_comp_subset";
    20 qed "sym_trans_comp_subset";
    21 
    21 
    22 val [major,minor]=goal Equiv.thy "[|<x,y>:r; z=<x,y>|] ==>  z:r";
    22 goalw Equiv.thy [refl_def]
    23 by (simp_tac (prod_ss addsimps [minor]) 1);
       
    24 by (rtac major 1);
       
    25 qed "BreakPair";
       
    26 
       
    27 val [major]=goal Equiv.thy "[|? x y. <x,y>:r & z=<x,y>|] ==>  z:r";
       
    28 by (resolve_tac [major RS exE] 1);
       
    29 by (etac exE 1);
       
    30 by (etac conjE 1);
       
    31 by (asm_simp_tac (prod_ss addsimps [minor]) 1);
       
    32 qed "BreakPair1";
       
    33 
       
    34 val [major,minor]=goal Equiv.thy "[|z:r; z=<x,y>|] ==> <x,y>:r";
       
    35 by (simp_tac (prod_ss addsimps [minor RS sym]) 1);
       
    36 by (rtac major 1);
       
    37 qed "BuildPair";
       
    38 
       
    39 val [major]=goal Equiv.thy "[|? z:r. <x,y>=z|] ==> <x,y>:r";
       
    40 by (resolve_tac [major RS bexE] 1);
       
    41 by (asm_simp_tac (prod_ss addsimps []) 1);
       
    42 qed "BuildPair1";
       
    43 
       
    44 val rel_pair_cs = rel_cs addIs [BuildPair1] 
       
    45                          addEs [BreakPair1];
       
    46 
       
    47 goalw Equiv.thy [refl_def,converse_def]
       
    48     "!!A r. refl(A,r) ==> r <= converse(r) O r";
    23     "!!A r. refl(A,r) ==> r <= converse(r) O r";
    49 by (step_tac comp_cs 1);
    24 by (fast_tac (rel_cs addIs [compI]) 1);
    50 by (dtac subsetD 1);
       
    51 by (assume_tac 1);
       
    52 by (etac SigmaE 1);
       
    53 by (rtac BreakPair1 1);
       
    54 by (fast_tac comp_cs 1);
       
    55 qed "refl_comp_subset";
    25 qed "refl_comp_subset";
    56 
    26 
    57 goalw Equiv.thy [equiv_def]
    27 goalw Equiv.thy [equiv_def]
    58     "!!A r. equiv(A,r) ==> converse(r) O r = r";
    28     "!!A r. equiv(A,r) ==> converse(r) O r = r";
    59 by (rtac equalityI 1);
    29 by (rtac equalityI 1);
    66     "!!A r. [| converse(r) O r = r;  Domain(r) = A |] ==> equiv(A,r)";
    36     "!!A r. [| converse(r) O r = r;  Domain(r) = A |] ==> equiv(A,r)";
    67 by (etac equalityE 1);
    37 by (etac equalityE 1);
    68 by (subgoal_tac "ALL x y. <x,y> : r --> <y,x> : r" 1);
    38 by (subgoal_tac "ALL x y. <x,y> : r --> <y,x> : r" 1);
    69 by (safe_tac set_cs);
    39 by (safe_tac set_cs);
    70 by (fast_tac (set_cs addSIs [converseI] addIs [compI]) 3);
    40 by (fast_tac (set_cs addSIs [converseI] addIs [compI]) 3);
    71 by (fast_tac (set_cs addSIs [converseI] addIs [compI] addSEs [DomainE]) 2);
    41 by (ALLGOALS (fast_tac (rel_cs addIs [compI] addSEs [compE])));
    72 by (fast_tac (rel_pair_cs addSEs [SigmaE] addSIs [SigmaI]) 1);
       
    73 by (dtac subsetD 1);
       
    74 by (dtac subsetD 1);
       
    75 by (fast_tac rel_cs 1);
       
    76 by (fast_tac rel_cs 1);
       
    77 by flexflex_tac;
       
    78 by (dtac subsetD 1);
       
    79 by (fast_tac converse_cs 2);
       
    80 by (fast_tac converse_cs 1);
       
    81 qed "comp_equivI";
    42 qed "comp_equivI";
    82 
    43 
    83 (** Equivalence classes **)
    44 (** Equivalence classes **)
    84 
    45 
    85 (*Lemma for the next result*)
    46 (*Lemma for the next result*)