src/HOL/Library/Indicator_Function.thy
author haftmann
Mon Jun 05 15:59:41 2017 +0200 (2017-06-05)
changeset 66010 2f7d39285a1a
parent 64966 d53d7ca3303e
child 67683 817944aeac3f
permissions -rw-r--r--
executable domain membership checks
     1 (*  Title:      HOL/Library/Indicator_Function.thy
     2     Author:     Johannes Hoelzl (TU Muenchen)
     3 *)
     4 
     5 section \<open>Indicator Function\<close>
     6 
     7 theory Indicator_Function
     8 imports Complex_Main Disjoint_Sets
     9 begin
    10 
    11 definition "indicator S x = (if x \<in> S then 1 else 0)"
    12 
    13 lemma indicator_simps[simp]:
    14   "x \<in> S \<Longrightarrow> indicator S x = 1"
    15   "x \<notin> S \<Longrightarrow> indicator S x = 0"
    16   unfolding indicator_def by auto
    17 
    18 lemma indicator_pos_le[intro, simp]: "(0::'a::linordered_semidom) \<le> indicator S x"
    19   and indicator_le_1[intro, simp]: "indicator S x \<le> (1::'a::linordered_semidom)"
    20   unfolding indicator_def by auto
    21 
    22 lemma indicator_abs_le_1: "\<bar>indicator S x\<bar> \<le> (1::'a::linordered_idom)"
    23   unfolding indicator_def by auto
    24 
    25 lemma indicator_eq_0_iff: "indicator A x = (0::'a::zero_neq_one) \<longleftrightarrow> x \<notin> A"
    26   by (auto simp: indicator_def)
    27 
    28 lemma indicator_eq_1_iff: "indicator A x = (1::'a::zero_neq_one) \<longleftrightarrow> x \<in> A"
    29   by (auto simp: indicator_def)
    30 
    31 lemma indicator_UNIV [simp]: "indicator UNIV = (\<lambda>x. 1)"
    32   by auto
    33 
    34 lemma indicator_leI:
    35   "(x \<in> A \<Longrightarrow> y \<in> B) \<Longrightarrow> (indicator A x :: 'a::linordered_nonzero_semiring) \<le> indicator B y"
    36   by (auto simp: indicator_def)
    37 
    38 lemma split_indicator: "P (indicator S x) \<longleftrightarrow> ((x \<in> S \<longrightarrow> P 1) \<and> (x \<notin> S \<longrightarrow> P 0))"
    39   unfolding indicator_def by auto
    40 
    41 lemma split_indicator_asm: "P (indicator S x) \<longleftrightarrow> (\<not> (x \<in> S \<and> \<not> P 1 \<or> x \<notin> S \<and> \<not> P 0))"
    42   unfolding indicator_def by auto
    43 
    44 lemma indicator_inter_arith: "indicator (A \<inter> B) x = indicator A x * (indicator B x::'a::semiring_1)"
    45   unfolding indicator_def by (auto simp: min_def max_def)
    46 
    47 lemma indicator_union_arith:
    48   "indicator (A \<union> B) x = indicator A x + indicator B x - indicator A x * (indicator B x :: 'a::ring_1)"
    49   unfolding indicator_def by (auto simp: min_def max_def)
    50 
    51 lemma indicator_inter_min: "indicator (A \<inter> B) x = min (indicator A x) (indicator B x::'a::linordered_semidom)"
    52   and indicator_union_max: "indicator (A \<union> B) x = max (indicator A x) (indicator B x::'a::linordered_semidom)"
    53   unfolding indicator_def by (auto simp: min_def max_def)
    54 
    55 lemma indicator_disj_union:
    56   "A \<inter> B = {} \<Longrightarrow> indicator (A \<union> B) x = (indicator A x + indicator B x :: 'a::linordered_semidom)"
    57   by (auto split: split_indicator)
    58 
    59 lemma indicator_compl: "indicator (- A) x = 1 - (indicator A x :: 'a::ring_1)"
    60   and indicator_diff: "indicator (A - B) x = indicator A x * (1 - indicator B x ::'a::ring_1)"
    61   unfolding indicator_def by (auto simp: min_def max_def)
    62 
    63 lemma indicator_times:
    64   "indicator (A \<times> B) x = indicator A (fst x) * (indicator B (snd x) :: 'a::semiring_1)"
    65   unfolding indicator_def by (cases x) auto
    66 
    67 lemma indicator_sum:
    68   "indicator (A <+> B) x = (case x of Inl x \<Rightarrow> indicator A x | Inr x \<Rightarrow> indicator B x)"
    69   unfolding indicator_def by (cases x) auto
    70 
    71 lemma indicator_image: "inj f \<Longrightarrow> indicator (f ` X) (f x) = (indicator X x::_::zero_neq_one)"
    72   by (auto simp: indicator_def inj_def)
    73 
    74 lemma indicator_vimage: "indicator (f -` A) x = indicator A (f x)"
    75   by (auto split: split_indicator)
    76 
    77 lemma  (* FIXME unnamed!? *)
    78   fixes f :: "'a \<Rightarrow> 'b::semiring_1"
    79   assumes "finite A"
    80   shows sum_mult_indicator[simp]: "(\<Sum>x \<in> A. f x * indicator B x) = (\<Sum>x \<in> A \<inter> B. f x)"
    81     and sum_indicator_mult[simp]: "(\<Sum>x \<in> A. indicator B x * f x) = (\<Sum>x \<in> A \<inter> B. f x)"
    82   unfolding indicator_def
    83   using assms by (auto intro!: sum.mono_neutral_cong_right split: if_split_asm)
    84 
    85 lemma sum_indicator_eq_card:
    86   assumes "finite A"
    87   shows "(\<Sum>x \<in> A. indicator B x) = card (A Int B)"
    88   using sum_mult_indicator [OF assms, of "\<lambda>x. 1::nat"]
    89   unfolding card_eq_sum by simp
    90 
    91 lemma sum_indicator_scaleR[simp]:
    92   "finite A \<Longrightarrow>
    93     (\<Sum>x \<in> A. indicator (B x) (g x) *\<^sub>R f x) = (\<Sum>x \<in> {x\<in>A. g x \<in> B x}. f x :: 'a::real_vector)"
    94   by (auto intro!: sum.mono_neutral_cong_right split: if_split_asm simp: indicator_def)
    95 
    96 lemma LIMSEQ_indicator_incseq:
    97   assumes "incseq A"
    98   shows "(\<lambda>i. indicator (A i) x :: 'a::{topological_space,one,zero}) \<longlonglongrightarrow> indicator (\<Union>i. A i) x"
    99 proof (cases "\<exists>i. x \<in> A i")
   100   case True
   101   then obtain i where "x \<in> A i"
   102     by auto
   103   then have *:
   104     "\<And>n. (indicator (A (n + i)) x :: 'a) = 1"
   105     "(indicator (\<Union>i. A i) x :: 'a) = 1"
   106     using incseqD[OF \<open>incseq A\<close>, of i "n + i" for n] \<open>x \<in> A i\<close> by (auto simp: indicator_def)
   107   show ?thesis
   108     by (rule LIMSEQ_offset[of _ i]) (use * in simp)
   109 next
   110   case False
   111   then show ?thesis by (simp add: indicator_def)
   112 qed
   113 
   114 lemma LIMSEQ_indicator_UN:
   115   "(\<lambda>k. indicator (\<Union>i<k. A i) x :: 'a::{topological_space,one,zero}) \<longlonglongrightarrow> indicator (\<Union>i. A i) x"
   116 proof -
   117   have "(\<lambda>k. indicator (\<Union>i<k. A i) x::'a) \<longlonglongrightarrow> indicator (\<Union>k. \<Union>i<k. A i) x"
   118     by (intro LIMSEQ_indicator_incseq) (auto simp: incseq_def intro: less_le_trans)
   119   also have "(\<Union>k. \<Union>i<k. A i) = (\<Union>i. A i)"
   120     by auto
   121   finally show ?thesis .
   122 qed
   123 
   124 lemma LIMSEQ_indicator_decseq:
   125   assumes "decseq A"
   126   shows "(\<lambda>i. indicator (A i) x :: 'a::{topological_space,one,zero}) \<longlonglongrightarrow> indicator (\<Inter>i. A i) x"
   127 proof (cases "\<exists>i. x \<notin> A i")
   128   case True
   129   then obtain i where "x \<notin> A i"
   130     by auto
   131   then have *:
   132     "\<And>n. (indicator (A (n + i)) x :: 'a) = 0"
   133     "(indicator (\<Inter>i. A i) x :: 'a) = 0"
   134     using decseqD[OF \<open>decseq A\<close>, of i "n + i" for n] \<open>x \<notin> A i\<close> by (auto simp: indicator_def)
   135   show ?thesis
   136     by (rule LIMSEQ_offset[of _ i]) (use * in simp)
   137 next
   138   case False
   139   then show ?thesis by (simp add: indicator_def)
   140 qed
   141 
   142 lemma LIMSEQ_indicator_INT:
   143   "(\<lambda>k. indicator (\<Inter>i<k. A i) x :: 'a::{topological_space,one,zero}) \<longlonglongrightarrow> indicator (\<Inter>i. A i) x"
   144 proof -
   145   have "(\<lambda>k. indicator (\<Inter>i<k. A i) x::'a) \<longlonglongrightarrow> indicator (\<Inter>k. \<Inter>i<k. A i) x"
   146     by (intro LIMSEQ_indicator_decseq) (auto simp: decseq_def intro: less_le_trans)
   147   also have "(\<Inter>k. \<Inter>i<k. A i) = (\<Inter>i. A i)"
   148     by auto
   149   finally show ?thesis .
   150 qed
   151 
   152 lemma indicator_add:
   153   "A \<inter> B = {} \<Longrightarrow> (indicator A x::_::monoid_add) + indicator B x = indicator (A \<union> B) x"
   154   unfolding indicator_def by auto
   155 
   156 lemma of_real_indicator: "of_real (indicator A x) = indicator A x"
   157   by (simp split: split_indicator)
   158 
   159 lemma real_of_nat_indicator: "real (indicator A x :: nat) = indicator A x"
   160   by (simp split: split_indicator)
   161 
   162 lemma abs_indicator: "\<bar>indicator A x :: 'a::linordered_idom\<bar> = indicator A x"
   163   by (simp split: split_indicator)
   164 
   165 lemma mult_indicator_subset:
   166   "A \<subseteq> B \<Longrightarrow> indicator A x * indicator B x = (indicator A x :: 'a::comm_semiring_1)"
   167   by (auto split: split_indicator simp: fun_eq_iff)
   168 
   169 lemma indicator_sums:
   170   assumes "\<And>i j. i \<noteq> j \<Longrightarrow> A i \<inter> A j = {}"
   171   shows "(\<lambda>i. indicator (A i) x::real) sums indicator (\<Union>i. A i) x"
   172 proof (cases "\<exists>i. x \<in> A i")
   173   case True
   174   then obtain i where i: "x \<in> A i" ..
   175   with assms have "(\<lambda>i. indicator (A i) x::real) sums (\<Sum>i\<in>{i}. indicator (A i) x)"
   176     by (intro sums_finite) (auto split: split_indicator)
   177   also have "(\<Sum>i\<in>{i}. indicator (A i) x) = indicator (\<Union>i. A i) x"
   178     using i by (auto split: split_indicator)
   179   finally show ?thesis .
   180 next
   181   case False
   182   then show ?thesis by simp
   183 qed
   184 
   185 text \<open>
   186   The indicator function of the union of a disjoint family of sets is the
   187   sum over all the individual indicators.
   188 \<close>
   189 
   190 lemma indicator_UN_disjoint:
   191   "finite A \<Longrightarrow> disjoint_family_on f A \<Longrightarrow> indicator (UNION A f) x = (\<Sum>y\<in>A. indicator (f y) x)"
   192   by (induct A rule: finite_induct)
   193     (auto simp: disjoint_family_on_def indicator_def split: if_splits)
   194 
   195 end