src/HOL/Relation.ML
 author paulson Thu Feb 05 10:48:43 1998 +0100 (1998-02-05) changeset 4601 87fc0d44b837 parent 4593 6fc8f224655f child 4644 ecf8f17f6fe0 permissions -rw-r--r--
New theorem Image_id
1 (*  Title:      Relation.ML
2     ID:         \$Id\$
3     Authors:    Lawrence C Paulson, Cambridge University Computer Laboratory
4     Copyright   1996  University of Cambridge
5 *)
7 open Relation;
9 (** Identity relation **)
11 goalw Relation.thy [id_def] "(a,a) : id";
12 by (Blast_tac 1);
13 qed "idI";
15 val major::prems = goalw Relation.thy [id_def]
16     "[| p: id;  !!x.[| p = (x,x) |] ==> P  \
17 \    |] ==>  P";
18 by (rtac (major RS CollectE) 1);
19 by (etac exE 1);
20 by (eresolve_tac prems 1);
21 qed "idE";
23 goalw Relation.thy [id_def] "(a,b):id = (a=b)";
24 by (Blast_tac 1);
25 qed "pair_in_id_conv";
29 (** Composition of two relations **)
31 goalw Relation.thy [comp_def]
32     "!!r s. [| (a,b):s; (b,c):r |] ==> (a,c) : r O s";
33 by (Blast_tac 1);
34 qed "compI";
36 (*proof requires higher-level assumptions or a delaying of hyp_subst_tac*)
37 val prems = goalw Relation.thy [comp_def]
38     "[| xz : r O s;  \
39 \       !!x y z. [| xz = (x,z);  (x,y):s;  (y,z):r |] ==> P \
40 \    |] ==> P";
41 by (cut_facts_tac prems 1);
42 by (REPEAT (eresolve_tac [CollectE, splitE, exE, conjE] 1
43      ORELSE ares_tac prems 1));
44 qed "compE";
46 val prems = goal Relation.thy
47     "[| (a,c) : r O s;  \
48 \       !!y. [| (a,y):s;  (y,c):r |] ==> P \
49 \    |] ==> P";
50 by (rtac compE 1);
51 by (REPEAT (ares_tac prems 1 ORELSE eresolve_tac [Pair_inject,ssubst] 1));
52 qed "compEpair";
57 goal Relation.thy "!!r s. [| r'<=r; s'<=s |] ==> (r' O s') <= (r O s)";
58 by (Blast_tac 1);
59 qed "comp_mono";
61 goal Relation.thy
62     "!!r s. [| s <= A Times B;  r <= B Times C |] ==> (r O s) <= A Times C";
63 by (Blast_tac 1);
64 qed "comp_subset_Sigma";
66 (** Natural deduction for trans(r) **)
68 val prems = goalw Relation.thy [trans_def]
69     "(!! x y z. [| (x,y):r;  (y,z):r |] ==> (x,z):r) ==> trans(r)";
70 by (REPEAT (ares_tac (prems@[allI,impI]) 1));
71 qed "transI";
73 goalw Relation.thy [trans_def]
74     "!!r. [| trans(r);  (a,b):r;  (b,c):r |] ==> (a,c):r";
75 by (Blast_tac 1);
76 qed "transD";
78 (** Natural deduction for r^-1 **)
80 goalw Relation.thy [inverse_def] "!!a b r. ((a,b): r^-1) = ((b,a):r)";
81 by (Simp_tac 1);
82 qed "inverse_iff";
86 goalw Relation.thy [inverse_def] "!!a b r. (a,b):r ==> (b,a): r^-1";
87 by (Simp_tac 1);
88 qed "inverseI";
90 goalw Relation.thy [inverse_def] "!!a b r. (a,b) : r^-1 ==> (b,a) : r";
91 by (Blast_tac 1);
92 qed "inverseD";
94 (*More general than inverseD, as it "splits" the member of the relation*)
95 qed_goalw "inverseE" Relation.thy [inverse_def]
96     "[| yx : r^-1;  \
97 \       !!x y. [| yx=(y,x);  (x,y):r |] ==> P \
98 \    |] ==> P"
99  (fn [major,minor]=>
100   [ (rtac (major RS CollectE) 1),
101     (REPEAT (eresolve_tac [splitE, bexE,exE, conjE, minor] 1)),
102     (assume_tac 1) ]);
106 goalw Relation.thy [inverse_def] "(r^-1)^-1 = r";
107 by (Blast_tac 1);
108 qed "inverse_inverse";
111 goal Relation.thy "(r O s)^-1 = s^-1 O r^-1";
112 by (Blast_tac 1);
113 qed "inverse_comp";
115 (** Domain **)
117 qed_goalw "Domain_iff" Relation.thy [Domain_def]
118     "a: Domain(r) = (EX y. (a,y): r)"
119  (fn _=> [ (Blast_tac 1) ]);
121 qed_goal "DomainI" Relation.thy "!!a b r. (a,b): r ==> a: Domain(r)"
122  (fn _ => [ (etac (exI RS (Domain_iff RS iffD2)) 1) ]);
124 qed_goal "DomainE" Relation.thy
125     "[| a : Domain(r);  !!y. (a,y): r ==> P |] ==> P"
126  (fn prems=>
127   [ (rtac (Domain_iff RS iffD1 RS exE) 1),
128     (REPEAT (ares_tac prems 1)) ]);
133 (** Range **)
135 qed_goalw "RangeI" Relation.thy [Range_def] "!!a b r.(a,b): r ==> b : Range(r)"
136  (fn _ => [ (etac (inverseI RS DomainI) 1) ]);
138 qed_goalw "RangeE" Relation.thy [Range_def]
139     "[| b : Range(r);  !!x. (x,b): r ==> P |] ==> P"
140  (fn major::prems=>
141   [ (rtac (major RS DomainE) 1),
142     (resolve_tac prems 1),
143     (etac inverseD 1) ]);
148 (*** Image of a set under a relation ***)
150 qed_goalw "Image_iff" Relation.thy [Image_def]
151     "b : r^^A = (? x:A. (x,b):r)"
152  (fn _ => [ Blast_tac 1 ]);
154 qed_goal "Image_singleton_iff" Relation.thy
155     "(b : r^^{a}) = ((a,b):r)"
156  (fn _ => [ rtac (Image_iff RS trans) 1,
157             Blast_tac 1 ]);
159 qed_goalw "ImageI" Relation.thy [Image_def]
160     "!!a b r. [| (a,b): r;  a:A |] ==> b : r^^A"
161  (fn _ => [ (Blast_tac 1)]);
163 qed_goalw "ImageE" Relation.thy [Image_def]
164     "[| b: r^^A;  !!x.[| (x,b): r;  x:A |] ==> P |] ==> P"
165  (fn major::prems=>
166   [ (rtac (major RS CollectE) 1),
167     (Clarify_tac 1),
168     (rtac (hd prems) 1),
169     (REPEAT (etac bexE 1 ORELSE ares_tac prems 1)) ]);
175 qed_goal "Image_empty" Relation.thy
176     "R^^{} = {}"
177  (fn _ => [ Blast_tac 1 ]);
181 goal thy "id ^^ A = A";
182 by (Blast_tac 1);
183 qed "Image_id";
187 qed_goal "Image_Int_subset" Relation.thy
188     "R ^^ (A Int B) <= R ^^ A Int R ^^ B"
189  (fn _ => [ Blast_tac 1 ]);
191 qed_goal "Image_Un" Relation.thy
192     "R ^^ (A Un B) = R ^^ A Un R ^^ B"
193  (fn _ => [ Blast_tac 1 ]);
196 qed_goal "Image_subset" Relation.thy
197     "!!A B r. r <= A Times B ==> r^^C <= B"
198  (fn _ =>
199   [ (rtac subsetI 1),
200     (REPEAT (eresolve_tac [asm_rl, ImageE, subsetD RS SigmaD2] 1)) ]);
202 goal Relation.thy "R O id = R";
203 by (fast_tac (claset() addbefore split_all_tac) 1);
204 qed "R_O_id";
206 goal Relation.thy "id O R = R";
207 by (fast_tac (claset() addbefore split_all_tac) 1);
208 qed "id_O_R";