10 |
10 |
11 val RSLIST = curry (op MRS); |
11 val RSLIST = curry (op MRS); |
12 |
12 |
13 open Relation; |
13 open Relation; |
14 |
14 |
15 goalw Relation.thy [converse_def] "!!a b r. <a,b>:r ==> <b,a>:converse(r)"; |
15 goalw Relation.thy [converse_def] "!!a b r. (a,b):r ==> (b,a):converse(r)"; |
16 by (simp_tac prod_ss 1); |
16 by (simp_tac prod_ss 1); |
17 by (fast_tac set_cs 1); |
17 by (fast_tac set_cs 1); |
18 qed "converseI"; |
18 qed "converseI"; |
19 |
19 |
20 goalw Relation.thy [converse_def] "!!a b r. <a,b> : converse(r) ==> <b,a> : r"; |
20 goalw Relation.thy [converse_def] "!!a b r. (a,b) : converse(r) ==> (b,a) : r"; |
21 by (fast_tac comp_cs 1); |
21 by (fast_tac comp_cs 1); |
22 qed "converseD"; |
22 qed "converseD"; |
23 |
23 |
24 qed_goalw "converseE" Relation.thy [converse_def] |
24 qed_goalw "converseE" Relation.thy [converse_def] |
25 "[| yx : converse(r); \ |
25 "[| yx : converse(r); \ |
26 \ !!x y. [| yx=<y,x>; <x,y>:r |] ==> P \ |
26 \ !!x y. [| yx=(y,x); (x,y):r |] ==> P \ |
27 \ |] ==> P" |
27 \ |] ==> P" |
28 (fn [major,minor]=> |
28 (fn [major,minor]=> |
29 [ (rtac (major RS CollectE) 1), |
29 [ (rtac (major RS CollectE) 1), |
30 (REPEAT (eresolve_tac [bexE,exE, conjE, minor] 1)), |
30 (REPEAT (eresolve_tac [bexE,exE, conjE, minor] 1)), |
31 (hyp_subst_tac 1), |
31 (hyp_subst_tac 1), |
33 |
33 |
34 val converse_cs = comp_cs addSIs [converseI] |
34 val converse_cs = comp_cs addSIs [converseI] |
35 addSEs [converseD,converseE]; |
35 addSEs [converseD,converseE]; |
36 |
36 |
37 qed_goalw "Domain_iff" Relation.thy [Domain_def] |
37 qed_goalw "Domain_iff" Relation.thy [Domain_def] |
38 "a: Domain(r) = (EX y. <a,y>: r)" |
38 "a: Domain(r) = (EX y. (a,y): r)" |
39 (fn _=> [ (fast_tac comp_cs 1) ]); |
39 (fn _=> [ (fast_tac comp_cs 1) ]); |
40 |
40 |
41 qed_goal "DomainI" Relation.thy "!!a b r. <a,b>: r ==> a: Domain(r)" |
41 qed_goal "DomainI" Relation.thy "!!a b r. (a,b): r ==> a: Domain(r)" |
42 (fn _ => [ (etac (exI RS (Domain_iff RS iffD2)) 1) ]); |
42 (fn _ => [ (etac (exI RS (Domain_iff RS iffD2)) 1) ]); |
43 |
43 |
44 qed_goal "DomainE" Relation.thy |
44 qed_goal "DomainE" Relation.thy |
45 "[| a : Domain(r); !!y. <a,y>: r ==> P |] ==> P" |
45 "[| a : Domain(r); !!y. (a,y): r ==> P |] ==> P" |
46 (fn prems=> |
46 (fn prems=> |
47 [ (rtac (Domain_iff RS iffD1 RS exE) 1), |
47 [ (rtac (Domain_iff RS iffD1 RS exE) 1), |
48 (REPEAT (ares_tac prems 1)) ]); |
48 (REPEAT (ares_tac prems 1)) ]); |
49 |
49 |
50 qed_goalw "RangeI" Relation.thy [Range_def] "!!a b r.<a,b>: r ==> b : Range(r)" |
50 qed_goalw "RangeI" Relation.thy [Range_def] "!!a b r.(a,b): r ==> b : Range(r)" |
51 (fn _ => [ (etac (converseI RS DomainI) 1) ]); |
51 (fn _ => [ (etac (converseI RS DomainI) 1) ]); |
52 |
52 |
53 qed_goalw "RangeE" Relation.thy [Range_def] |
53 qed_goalw "RangeE" Relation.thy [Range_def] |
54 "[| b : Range(r); !!x. <x,b>: r ==> P |] ==> P" |
54 "[| b : Range(r); !!x. (x,b): r ==> P |] ==> P" |
55 (fn major::prems=> |
55 (fn major::prems=> |
56 [ (rtac (major RS DomainE) 1), |
56 [ (rtac (major RS DomainE) 1), |
57 (resolve_tac prems 1), |
57 (resolve_tac prems 1), |
58 (etac converseD 1) ]); |
58 (etac converseD 1) ]); |
59 |
59 |
60 (*** Image of a set under a function/relation ***) |
60 (*** Image of a set under a function/relation ***) |
61 |
61 |
62 qed_goalw "Image_iff" Relation.thy [Image_def] |
62 qed_goalw "Image_iff" Relation.thy [Image_def] |
63 "b : r^^A = (? x:A. <x,b>:r)" |
63 "b : r^^A = (? x:A. (x,b):r)" |
64 (fn _ => [ fast_tac (comp_cs addIs [RangeI]) 1 ]); |
64 (fn _ => [ fast_tac (comp_cs addIs [RangeI]) 1 ]); |
65 |
65 |
66 qed_goal "Image_singleton_iff" Relation.thy |
66 qed_goal "Image_singleton_iff" Relation.thy |
67 "(b : r^^{a}) = (<a,b>:r)" |
67 "(b : r^^{a}) = ((a,b):r)" |
68 (fn _ => [ rtac (Image_iff RS trans) 1, |
68 (fn _ => [ rtac (Image_iff RS trans) 1, |
69 fast_tac comp_cs 1 ]); |
69 fast_tac comp_cs 1 ]); |
70 |
70 |
71 qed_goalw "ImageI" Relation.thy [Image_def] |
71 qed_goalw "ImageI" Relation.thy [Image_def] |
72 "!!a b r. [| <a,b>: r; a:A |] ==> b : r^^A" |
72 "!!a b r. [| (a,b): r; a:A |] ==> b : r^^A" |
73 (fn _ => [ (REPEAT (ares_tac [CollectI,RangeI,bexI] 1)), |
73 (fn _ => [ (REPEAT (ares_tac [CollectI,RangeI,bexI] 1)), |
74 (resolve_tac [conjI ] 1), |
74 (resolve_tac [conjI ] 1), |
75 (resolve_tac [RangeI] 1), |
75 (resolve_tac [RangeI] 1), |
76 (REPEAT (fast_tac set_cs 1))]); |
76 (REPEAT (fast_tac set_cs 1))]); |
77 |
77 |
78 qed_goalw "ImageE" Relation.thy [Image_def] |
78 qed_goalw "ImageE" Relation.thy [Image_def] |
79 "[| b: r^^A; !!x.[| <x,b>: r; x:A |] ==> P |] ==> P" |
79 "[| b: r^^A; !!x.[| (x,b): r; x:A |] ==> P |] ==> P" |
80 (fn major::prems=> |
80 (fn major::prems=> |
81 [ (rtac (major RS CollectE) 1), |
81 [ (rtac (major RS CollectE) 1), |
82 (safe_tac set_cs), |
82 (safe_tac set_cs), |
83 (etac RangeE 1), |
83 (etac RangeE 1), |
84 (rtac (hd prems) 1), |
84 (rtac (hd prems) 1), |