src/HOL/Set.thy
changeset 67398 5eb932e604a2
parent 67307 54e2111d6f0e
child 67401 a82df75b7f85
equal deleted inserted replaced
67397:12b0c11e3d20 67398:5eb932e604a2
    18   and member :: "'a \<Rightarrow> 'a set \<Rightarrow> bool" \<comment> "membership"
    18   and member :: "'a \<Rightarrow> 'a set \<Rightarrow> bool" \<comment> "membership"
    19   where mem_Collect_eq [iff, code_unfold]: "member a (Collect P) = P a"
    19   where mem_Collect_eq [iff, code_unfold]: "member a (Collect P) = P a"
    20     and Collect_mem_eq [simp]: "Collect (\<lambda>x. member x A) = A"
    20     and Collect_mem_eq [simp]: "Collect (\<lambda>x. member x A) = A"
    21 
    21 
    22 notation
    22 notation
    23   member  ("op \<in>") and
    23   member  ("'(\<in>')") and
    24   member  ("(_/ \<in> _)" [51, 51] 50)
    24   member  ("(_/ \<in> _)" [51, 51] 50)
    25 
    25 
    26 abbreviation not_member
    26 abbreviation not_member
    27   where "not_member x A \<equiv> \<not> (x \<in> A)" \<comment> "non-membership"
    27   where "not_member x A \<equiv> \<not> (x \<in> A)" \<comment> "non-membership"
    28 notation
    28 notation
    29   not_member  ("op \<notin>") and
    29   not_member  ("'(\<notin>')") and
    30   not_member  ("(_/ \<notin> _)" [51, 51] 50)
    30   not_member  ("(_/ \<notin> _)" [51, 51] 50)
    31 
    31 
    32 notation (ASCII)
    32 notation (ASCII)
    33   member  ("op :") and
    33   member  ("'(:')") and
    34   member  ("(_/ : _)" [51, 51] 50) and
    34   member  ("(_/ : _)" [51, 51] 50) and
    35   not_member  ("op ~:") and
    35   not_member  ("'(~:')") and
    36   not_member  ("(_/ ~: _)" [51, 51] 50)
    36   not_member  ("(_/ ~: _)" [51, 51] 50)
    37 
    37 
    38 
    38 
    39 text \<open>Set comprehensions\<close>
    39 text \<open>Set comprehensions\<close>
    40 
    40 
   153 
   153 
   154 abbreviation subset_eq :: "'a set \<Rightarrow> 'a set \<Rightarrow> bool"
   154 abbreviation subset_eq :: "'a set \<Rightarrow> 'a set \<Rightarrow> bool"
   155   where "subset_eq \<equiv> less_eq"
   155   where "subset_eq \<equiv> less_eq"
   156 
   156 
   157 notation
   157 notation
   158   subset  ("op \<subset>") and
   158   subset  ("'(\<subset>')") and
   159   subset  ("(_/ \<subset> _)" [51, 51] 50) and
   159   subset  ("(_/ \<subset> _)" [51, 51] 50) and
   160   subset_eq  ("op \<subseteq>") and
   160   subset_eq  ("'(\<subseteq>')") and
   161   subset_eq  ("(_/ \<subseteq> _)" [51, 51] 50)
   161   subset_eq  ("(_/ \<subseteq> _)" [51, 51] 50)
   162 
   162 
   163 abbreviation (input)
   163 abbreviation (input)
   164   supset :: "'a set \<Rightarrow> 'a set \<Rightarrow> bool" where
   164   supset :: "'a set \<Rightarrow> 'a set \<Rightarrow> bool" where
   165   "supset \<equiv> greater"
   165   "supset \<equiv> greater"
   167 abbreviation (input)
   167 abbreviation (input)
   168   supset_eq :: "'a set \<Rightarrow> 'a set \<Rightarrow> bool" where
   168   supset_eq :: "'a set \<Rightarrow> 'a set \<Rightarrow> bool" where
   169   "supset_eq \<equiv> greater_eq"
   169   "supset_eq \<equiv> greater_eq"
   170 
   170 
   171 notation
   171 notation
   172   supset  ("op \<supset>") and
   172   supset  ("'(\<supset>')") and
   173   supset  ("(_/ \<supset> _)" [51, 51] 50) and
   173   supset  ("(_/ \<supset> _)" [51, 51] 50) and
   174   supset_eq  ("op \<supseteq>") and
   174   supset_eq  ("'(\<supseteq>')") and
   175   supset_eq  ("(_/ \<supseteq> _)" [51, 51] 50)
   175   supset_eq  ("(_/ \<supseteq> _)" [51, 51] 50)
   176 
   176 
   177 notation (ASCII output)
   177 notation (ASCII output)
   178   subset  ("op <") and
   178   subset  ("'(<')") and
   179   subset  ("(_/ < _)" [51, 51] 50) and
   179   subset  ("(_/ < _)" [51, 51] 50) and
   180   subset_eq  ("op <=") and
   180   subset_eq  ("'(<=')") and
   181   subset_eq  ("(_/ <= _)" [51, 51] 50)
   181   subset_eq  ("(_/ <= _)" [51, 51] 50)
   182 
   182 
   183 definition Ball :: "'a set \<Rightarrow> ('a \<Rightarrow> bool) \<Rightarrow> bool"
   183 definition Ball :: "'a set \<Rightarrow> ('a \<Rightarrow> bool) \<Rightarrow> bool"
   184   where "Ball A P \<longleftrightarrow> (\<forall>x. x \<in> A \<longrightarrow> P x)"   \<comment> "bounded universal quantifiers"
   184   where "Ball A P \<longleftrightarrow> (\<forall>x. x \<in> A \<longrightarrow> P x)"   \<comment> "bounded universal quantifiers"
   185 
   185 
   252 
   252 
   253     fun tr' q = (q, fn _ =>
   253     fun tr' q = (q, fn _ =>
   254       (fn [Const (@{syntax_const "_bound"}, _) $ Free (v, Type (@{type_name set}, _)),
   254       (fn [Const (@{syntax_const "_bound"}, _) $ Free (v, Type (@{type_name set}, _)),
   255           Const (c, _) $
   255           Const (c, _) $
   256             (Const (d, _) $ (Const (@{syntax_const "_bound"}, _) $ Free (v', T)) $ n) $ P] =>
   256             (Const (d, _) $ (Const (@{syntax_const "_bound"}, _) $ Free (v', T)) $ n) $ P] =>
   257           (case AList.lookup (op =) trans (q, c, d) of
   257           (case AList.lookup (=) trans (q, c, d) of
   258             NONE => raise Match
   258             NONE => raise Match
   259           | SOME l => mk v (v', T) l n P)
   259           | SOME l => mk v (v', T) l n P)
   260         | _ => raise Match));
   260         | _ => raise Match));
   261   in
   261   in
   262     [tr' All_binder, tr' Ex_binder]
   262     [tr' All_binder, tr' Ex_binder]
   303     let
   303     let
   304       fun check (Const (@{const_syntax Ex}, _) $ Abs (_, _, P), n) = check (P, n + 1)
   304       fun check (Const (@{const_syntax Ex}, _) $ Abs (_, _, P), n) = check (P, n + 1)
   305         | check (Const (@{const_syntax HOL.conj}, _) $
   305         | check (Const (@{const_syntax HOL.conj}, _) $
   306               (Const (@{const_syntax HOL.eq}, _) $ Bound m $ e) $ P, n) =
   306               (Const (@{const_syntax HOL.eq}, _) $ Bound m $ e) $ P, n) =
   307             n > 0 andalso m = n andalso not (loose_bvar1 (P, n)) andalso
   307             n > 0 andalso m = n andalso not (loose_bvar1 (P, n)) andalso
   308             subset (op =) (0 upto (n - 1), add_loose_bnos (e, 0, []))
   308             subset (=) (0 upto (n - 1), add_loose_bnos (e, 0, []))
   309         | check _ = false;
   309         | check _ = false;
   310 
   310 
   311         fun tr' (_ $ abs) =
   311         fun tr' (_ $ abs) =
   312           let val _ $ idts $ (_ $ (_ $ _ $ e) $ Q) = ex_tr' ctxt [abs]
   312           let val _ $ idts $ (_ $ (_ $ _ $ e) $ Q) = ex_tr' ctxt [abs]
   313           in Syntax.const @{syntax_const "_Setcompr"} $ e $ idts $ Q end;
   313           in Syntax.const @{syntax_const "_Setcompr"} $ e $ idts $ Q end;
   651 
   651 
   652 
   652 
   653 subsubsection \<open>Binary intersection\<close>
   653 subsubsection \<open>Binary intersection\<close>
   654 
   654 
   655 abbreviation inter :: "'a set \<Rightarrow> 'a set \<Rightarrow> 'a set"  (infixl "\<inter>" 70)
   655 abbreviation inter :: "'a set \<Rightarrow> 'a set \<Rightarrow> 'a set"  (infixl "\<inter>" 70)
   656   where "op \<inter> \<equiv> inf"
   656   where "(\<inter>) \<equiv> inf"
   657 
   657 
   658 notation (ASCII)
   658 notation (ASCII)
   659   inter  (infixl "Int" 70)
   659   inter  (infixl "Int" 70)
   660 
   660 
   661 lemma Int_def: "A \<inter> B = {x. x \<in> A \<and> x \<in> B}"
   661 lemma Int_def: "A \<inter> B = {x. x \<in> A \<and> x \<in> B}"
   955   by simp
   955   by simp
   956 
   956 
   957 lemma bex_imageD: "\<exists>x\<in>f ` A. P x \<Longrightarrow> \<exists>x\<in>A. P (f x)"
   957 lemma bex_imageD: "\<exists>x\<in>f ` A. P x \<Longrightarrow> \<exists>x\<in>A. P (f x)"
   958   by auto
   958   by auto
   959 
   959 
   960 lemma image_add_0 [simp]: "op + (0::'a::comm_monoid_add) ` S = S"
   960 lemma image_add_0 [simp]: "(+) (0::'a::comm_monoid_add) ` S = S"
   961   by auto
   961   by auto
   962 
   962 
   963 
   963 
   964 text \<open>\<^medskip> Range of a function -- just an abbreviation for image!\<close>
   964 text \<open>\<^medskip> Range of a function -- just an abbreviation for image!\<close>
   965 
   965