src/CCL/Set.ML
changeset 3837 d7f033c74b38
parent 1459 d12da312eff4
child 5062 fbdb0b541314
equal deleted inserted replaced
3836:f1a1817659e6 3837:d7f033c74b38
    11 For set.thy.  Set theory for higher-order logic.  A set is simply a predicate.
    11 For set.thy.  Set theory for higher-order logic.  A set is simply a predicate.
    12 *)
    12 *)
    13 
    13 
    14 open Set;
    14 open Set;
    15 
    15 
    16 val [prem] = goal Set.thy "[| P(a) |] ==> a : {x.P(x)}";
    16 val [prem] = goal Set.thy "[| P(a) |] ==> a : {x. P(x)}";
    17 by (rtac (mem_Collect_iff RS iffD2) 1);
    17 by (rtac (mem_Collect_iff RS iffD2) 1);
    18 by (rtac prem 1);
    18 by (rtac prem 1);
    19 qed "CollectI";
    19 qed "CollectI";
    20 
    20 
    21 val prems = goal Set.thy "[| a : {x.P(x)} |] ==> P(a)";
    21 val prems = goal Set.thy "[| a : {x. P(x)} |] ==> P(a)";
    22 by (resolve_tac (prems RL [mem_Collect_iff  RS iffD1]) 1);
    22 by (resolve_tac (prems RL [mem_Collect_iff  RS iffD1]) 1);
    23 qed "CollectD";
    23 qed "CollectD";
    24 
    24 
    25 val CollectE = make_elim CollectD;
    25 val CollectE = make_elim CollectD;
    26 
    26 
    54     "[| P(x);  x:A |] ==> EX x:A. P(x)";
    54     "[| P(x);  x:A |] ==> EX x:A. P(x)";
    55 by (REPEAT (ares_tac (prems @ [exI,conjI]) 1));
    55 by (REPEAT (ares_tac (prems @ [exI,conjI]) 1));
    56 qed "bexI";
    56 qed "bexI";
    57 
    57 
    58 qed_goal "bexCI" Set.thy 
    58 qed_goal "bexCI" Set.thy 
    59    "[| EX x:A. ~P(x) ==> P(a);  a:A |] ==> EX x:A.P(x)"
    59    "[| EX x:A. ~P(x) ==> P(a);  a:A |] ==> EX x:A. P(x)"
    60  (fn prems=>
    60  (fn prems=>
    61   [ (rtac classical 1),
    61   [ (rtac classical 1),
    62     (REPEAT (ares_tac (prems@[bexI,ballI,notI,notE]) 1))  ]);
    62     (REPEAT (ares_tac (prems@[bexI,ballI,notI,notE]) 1))  ]);
    63 
    63 
    64 val major::prems = goalw Set.thy [Bex_def]
    64 val major::prems = goalw Set.thy [Bex_def]
    91      ORELSE ares_tac ([bexI,iffI] @ (prems RL [iffD1,iffD2])) 1));
    91      ORELSE ares_tac ([bexI,iffI] @ (prems RL [iffD1,iffD2])) 1));
    92 qed "bex_cong";
    92 qed "bex_cong";
    93 
    93 
    94 (*** Rules for subsets ***)
    94 (*** Rules for subsets ***)
    95 
    95 
    96 val prems = goalw Set.thy [subset_def] "(!!x.x:A ==> x:B) ==> A <= B";
    96 val prems = goalw Set.thy [subset_def] "(!!x. x:A ==> x:B) ==> A <= B";
    97 by (REPEAT (ares_tac (prems @ [ballI]) 1));
    97 by (REPEAT (ares_tac (prems @ [ballI]) 1));
    98 qed "subsetI";
    98 qed "subsetI";
    99 
    99 
   100 (*Rule in Modus Ponens style*)
   100 (*Rule in Modus Ponens style*)
   101 val major::prems = goalw Set.thy [subset_def] "[| A <= B;  c:A |] ==> c:B";
   101 val major::prems = goalw Set.thy [subset_def] "[| A <= B;  c:A |] ==> c:B";
   161     "[| p:A;  !!z. z:A ==> p=z --> R |] ==> R";
   161     "[| p:A;  !!z. z:A ==> p=z --> R |] ==> R";
   162 by (rtac mp 1);
   162 by (rtac mp 1);
   163 by (REPEAT (resolve_tac (refl::prems) 1));
   163 by (REPEAT (resolve_tac (refl::prems) 1));
   164 qed "setup_induction";
   164 qed "setup_induction";
   165 
   165 
   166 goal Set.thy "{x.x:A} = A";
   166 goal Set.thy "{x. x:A} = A";
   167 by (REPEAT (ares_tac [equalityI,subsetI,CollectI] 1  ORELSE etac CollectD 1));
   167 by (REPEAT (ares_tac [equalityI,subsetI,CollectI] 1  ORELSE etac CollectD 1));
   168 qed "trivial_set";
   168 qed "trivial_set";
   169 
   169 
   170 (*** Rules for binary union -- Un ***)
   170 (*** Rules for binary union -- Un ***)
   171 
   171 
   232 val ComplE = make_elim ComplD;
   232 val ComplE = make_elim ComplD;
   233 
   233 
   234 
   234 
   235 (*** Empty sets ***)
   235 (*** Empty sets ***)
   236 
   236 
   237 goalw Set.thy [empty_def] "{x.False} = {}";
   237 goalw Set.thy [empty_def] "{x. False} = {}";
   238 by (rtac refl 1);
   238 by (rtac refl 1);
   239 qed "empty_eq";
   239 qed "empty_eq";
   240 
   240 
   241 val [prem] = goalw Set.thy [empty_def] "a : {} ==> P";
   241 val [prem] = goalw Set.thy [empty_def] "a : {} ==> P";
   242 by (rtac (prem RS CollectD RS FalseE) 1);
   242 by (rtac (prem RS CollectD RS FalseE) 1);
   243 qed "emptyD";
   243 qed "emptyD";
   244 
   244 
   245 val emptyE = make_elim emptyD;
   245 val emptyE = make_elim emptyD;
   246 
   246 
   247 val [prem] = goal Set.thy "~ A={} ==> (EX x.x:A)";
   247 val [prem] = goal Set.thy "~ A={} ==> (EX x. x:A)";
   248 by (rtac (prem RS swap) 1);
   248 by (rtac (prem RS swap) 1);
   249 by (rtac equalityI 1);
   249 by (rtac equalityI 1);
   250 by (ALLGOALS (fast_tac (FOL_cs addSIs [subsetI] addSEs [emptyD])));
   250 by (ALLGOALS (fast_tac (FOL_cs addSIs [subsetI] addSEs [emptyD])));
   251 qed "not_emptyD";
   251 qed "not_emptyD";
   252 
   252