src/CCL/subset.ML

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/CCL/subset.ML	Thu Sep 16 12:20:38 1993 +0200
@@ -0,0 +1,129 @@
+(*  Title: 	CCL/subset
+    ID:         $Id$
+
+Modified version of
+    Title: 	HOL/subset
+    Author: 	Lawrence C Paulson, Cambridge University Computer Laboratory
+    Copyright   1991  University of Cambridge
+
+Derived rules involving subsets
+Union and Intersection as lattice operations
+*)
+
+(*** Big Union -- least upper bound of a set  ***)
+
+val prems = goal Set.thy
+    "B:A ==> B <= Union(A)";
+by (REPEAT (ares_tac (prems@[subsetI,UnionI]) 1));
+val Union_upper = result();
+
+val prems = goal Set.thy
+    "[| !!X. X:A ==> X<=C |] ==> Union(A) <= C";
+by (REPEAT (ares_tac [subsetI] 1
+     ORELSE eresolve_tac ([UnionE] @ (prems RL [subsetD])) 1));
+val Union_least = result();
+
+
+(*** Big Intersection -- greatest lower bound of a set ***)
+
+val prems = goal Set.thy
+    "B:A ==> Inter(A) <= B";
+by (REPEAT (resolve_tac (prems@[subsetI]) 1
+     ORELSE etac InterD 1));
+val Inter_lower = result();
+
+val prems = goal Set.thy
+    "[| !!X. X:A ==> C<=X |] ==> C <= Inter(A)";
+by (REPEAT (ares_tac [subsetI,InterI] 1
+     ORELSE eresolve_tac (prems RL [subsetD]) 1));
+val Inter_greatest = result();
+
+(*** Finite Union -- the least upper bound of 2 sets ***)
+
+goal Set.thy "A <= A Un B";
+by (REPEAT (ares_tac [subsetI,UnI1] 1));
+val Un_upper1 = result();
+
+goal Set.thy "B <= A Un B";
+by (REPEAT (ares_tac [subsetI,UnI2] 1));
+val Un_upper2 = result();
+
+val prems = goal Set.thy "[| A<=C;  B<=C |] ==> A Un B <= C";
+by (cut_facts_tac prems 1);
+by (DEPTH_SOLVE (ares_tac [subsetI] 1 
+          ORELSE eresolve_tac [UnE,subsetD] 1));
+val Un_least = result();
+
+(*** Finite Intersection -- the greatest lower bound of 2 sets *)
+
+goal Set.thy "A Int B <= A";
+by (REPEAT (ares_tac [subsetI] 1 ORELSE etac IntE 1));
+val Int_lower1 = result();
+
+goal Set.thy "A Int B <= B";
+by (REPEAT (ares_tac [subsetI] 1 ORELSE etac IntE 1));
+val Int_lower2 = result();
+
+val prems = goal Set.thy "[| C<=A;  C<=B |] ==> C <= A Int B";
+by (cut_facts_tac prems 1);
+by (REPEAT (ares_tac [subsetI,IntI] 1
+     ORELSE etac subsetD 1));
+val Int_greatest = result();
+
+(*** Monotonicity ***)
+
+val [prem] = goalw Set.thy [mono_def]
+    "[| !!A B. A <= B ==> f(A) <= f(B) |] ==> mono(f)";
+by (REPEAT (ares_tac [allI, impI, prem] 1));
+val monoI = result();
+
+val [major,minor] = goalw Set.thy [mono_def]
+    "[| mono(f);  A <= B |] ==> f(A) <= f(B)";
+by (rtac (major RS spec RS spec RS mp) 1);
+by (rtac minor 1);
+val monoD = result();
+
+val [prem] = goalw Set.thy [mono_def] "(!!x.f(x) = g(x)) ==> mono(f) <-> mono(g)";
+by (REPEAT (resolve_tac (iff_refl::FOL_congs @ [prem RS subst]) 1));
+val mono_cong = result();
+
+val [prem] = goal Set.thy "mono(f) ==> f(A) Un f(B) <= f(A Un B)";
+by (rtac Un_least 1);
+by (rtac (Un_upper1 RS (prem RS monoD)) 1);
+by (rtac (Un_upper2 RS (prem RS monoD)) 1);
+val mono_Un = result();
+
+val [prem] = goal Set.thy "mono(f) ==> f(A Int B) <= f(A) Int f(B)";
+by (rtac Int_greatest 1);
+by (rtac (Int_lower1 RS (prem RS monoD)) 1);
+by (rtac (Int_lower2 RS (prem RS monoD)) 1);
+val mono_Int = result();
+
+(****)
+
+val set_cs = FOL_cs 
+    addSIs [ballI, subsetI, InterI, INT_I, CollectI, 
+	    ComplI, IntI, UnCI, singletonI] 
+    addIs  [bexI, UnionI, UN_I] 
+    addSEs [bexE, UnionE, UN_E,
+	    CollectE, ComplE, IntE, UnE, emptyE, singletonE] 
+    addEs  [ballE, InterD, InterE, INT_D, INT_E, subsetD, subsetCE];
+
+fun cfast_tac prems = cut_facts_tac prems THEN' fast_tac set_cs;
+
+fun prover s = prove_goal Set.thy s (fn _=>[fast_tac set_cs 1]);
+
+val mem_rews = [trivial_set,empty_eq] @ (map prover
+ [ "(a : A Un B)   <->  (a:A | a:B)",
+   "(a : A Int B)  <->  (a:A & a:B)",
+   "(a : Compl(B)) <->  (~a:B)",
+   "(a : {b})      <->  (a=b)",
+   "(a : {})       <->   False",
+   "(a : {x.P(x)}) <->  P(a)" ]);
+
+val set_congs = 
+    [Collect_cong, ball_cong, bex_cong, INT_cong, UN_cong, mono_cong] @ 
+    mk_congs Set.thy ["Compl", "op Int", "op Un", "Union", "Inter", 
+		      "op :", "op <=", "singleton"];
+
+val set_ss = FOL_ss addcongs set_congs addrews mem_rews;