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