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*) |