52 then obtain X where "finite X" "card X = Suc (Suc n)" "X \<subseteq> ?X" |
52 then obtain X where "finite X" "card X = Suc (Suc n)" "X \<subseteq> ?X" |
53 by (metis infinite_arbitrarily_large) |
53 by (metis infinite_arbitrarily_large) |
54 from this(3) have *: "\<And>x. x \<in> X \<Longrightarrow> ?M / Suc n \<le> ?m x" |
54 from this(3) have *: "\<And>x. x \<in> X \<Longrightarrow> ?M / Suc n \<le> ?m x" |
55 by auto |
55 by auto |
56 { fix x assume "x \<in> X" |
56 { fix x assume "x \<in> X" |
57 from `?M \<noteq> 0` *[OF this] have "?m x \<noteq> 0" by (auto simp: field_simps measure_le_0_iff) |
57 from \<open>?M \<noteq> 0\<close> *[OF this] have "?m x \<noteq> 0" by (auto simp: field_simps measure_le_0_iff) |
58 then have "{x} \<in> sets M" by (auto dest: measure_notin_sets) } |
58 then have "{x} \<in> sets M" by (auto dest: measure_notin_sets) } |
59 note singleton_sets = this |
59 note singleton_sets = this |
60 have "?M < (\<Sum>x\<in>X. ?M / Suc n)" |
60 have "?M < (\<Sum>x\<in>X. ?M / Suc n)" |
61 using `?M \<noteq> 0` |
61 using \<open>?M \<noteq> 0\<close> |
62 by (simp add: `card X = Suc (Suc n)` of_nat_Suc field_simps less_le measure_nonneg) |
62 by (simp add: \<open>card X = Suc (Suc n)\<close> of_nat_Suc field_simps less_le measure_nonneg) |
63 also have "\<dots> \<le> (\<Sum>x\<in>X. ?m x)" |
63 also have "\<dots> \<le> (\<Sum>x\<in>X. ?m x)" |
64 by (rule setsum_mono) fact |
64 by (rule setsum_mono) fact |
65 also have "\<dots> = measure M (\<Union>x\<in>X. {x})" |
65 also have "\<dots> = measure M (\<Union>x\<in>X. {x})" |
66 using singleton_sets `finite X` |
66 using singleton_sets \<open>finite X\<close> |
67 by (intro finite_measure_finite_Union[symmetric]) (auto simp: disjoint_family_on_def) |
67 by (intro finite_measure_finite_Union[symmetric]) (auto simp: disjoint_family_on_def) |
68 finally have "?M < measure M (\<Union>x\<in>X. {x})" . |
68 finally have "?M < measure M (\<Union>x\<in>X. {x})" . |
69 moreover have "measure M (\<Union>x\<in>X. {x}) \<le> ?M" |
69 moreover have "measure M (\<Union>x\<in>X. {x}) \<le> ?M" |
70 using singleton_sets[THEN sets.sets_into_space] by (intro finite_measure_mono) auto |
70 using singleton_sets[THEN sets.sets_into_space] by (intro finite_measure_mono) auto |
71 ultimately show False by simp |
71 ultimately show False by simp |
397 by (auto simp add: nn_integral_0_iff_AE AE_measure_pmf_iff set_pmf_eq not_le less_le pmf_nonneg) |
397 by (auto simp add: nn_integral_0_iff_AE AE_measure_pmf_iff set_pmf_eq not_le less_le pmf_nonneg) |
398 |
398 |
399 lemma bind_pmf_cong: |
399 lemma bind_pmf_cong: |
400 assumes "p = q" |
400 assumes "p = q" |
401 shows "(\<And>x. x \<in> set_pmf q \<Longrightarrow> f x = g x) \<Longrightarrow> bind_pmf p f = bind_pmf q g" |
401 shows "(\<And>x. x \<in> set_pmf q \<Longrightarrow> f x = g x) \<Longrightarrow> bind_pmf p f = bind_pmf q g" |
402 unfolding `p = q`[symmetric] measure_pmf_inject[symmetric] bind_pmf.rep_eq |
402 unfolding \<open>p = q\<close>[symmetric] measure_pmf_inject[symmetric] bind_pmf.rep_eq |
403 by (auto simp: AE_measure_pmf_iff Pi_iff space_subprob_algebra subprob_space_measure_pmf |
403 by (auto simp: AE_measure_pmf_iff Pi_iff space_subprob_algebra subprob_space_measure_pmf |
404 sets_bind[where N="count_space UNIV"] emeasure_bind[where N="count_space UNIV"] |
404 sets_bind[where N="count_space UNIV"] emeasure_bind[where N="count_space UNIV"] |
405 intro!: nn_integral_cong_AE measure_eqI) |
405 intro!: nn_integral_cong_AE measure_eqI) |
406 |
406 |
407 lemma bind_pmf_cong_simp: |
407 lemma bind_pmf_cong_simp: |
734 setup_lifting td_pmf_embed_pmf |
734 setup_lifting td_pmf_embed_pmf |
735 |
735 |
736 lemma set_pmf_transfer[transfer_rule]: |
736 lemma set_pmf_transfer[transfer_rule]: |
737 assumes "bi_total A" |
737 assumes "bi_total A" |
738 shows "rel_fun (pcr_pmf A) (rel_set A) (\<lambda>f. {x. f x \<noteq> 0}) set_pmf" |
738 shows "rel_fun (pcr_pmf A) (rel_set A) (\<lambda>f. {x. f x \<noteq> 0}) set_pmf" |
739 using `bi_total A` |
739 using \<open>bi_total A\<close> |
740 by (auto simp: pcr_pmf_def cr_pmf_def rel_fun_def rel_set_def bi_total_def Bex_def set_pmf_iff) |
740 by (auto simp: pcr_pmf_def cr_pmf_def rel_fun_def rel_set_def bi_total_def Bex_def set_pmf_iff) |
741 metis+ |
741 metis+ |
742 |
742 |
743 end |
743 end |
744 |
744 |
1077 using in_quotient_imp_in_rel[of UNIV ?R C x y] C assms |
1077 using in_quotient_imp_in_rel[of UNIV ?R C x y] C assms |
1078 by (simp add: equivp_equiv) |
1078 by (simp add: equivp_equiv) |
1079 with in_set eq have "measure p {x. R x y} = measure q {y. R x y}" |
1079 with in_set eq have "measure p {x. R x y} = measure q {y. R x y}" |
1080 by auto |
1080 by auto |
1081 moreover have "{y. R x y} = C" |
1081 moreover have "{y. R x y} = C" |
1082 using assms `x \<in> C` C quotientD[of UNIV ?R C x] by (simp add: equivp_equiv) |
1082 using assms \<open>x \<in> C\<close> C quotientD[of UNIV ?R C x] by (simp add: equivp_equiv) |
1083 moreover have "{x. R x y} = C" |
1083 moreover have "{x. R x y} = C" |
1084 using assms `y \<in> C` C quotientD[of UNIV "?R" C y] sympD[of R] |
1084 using assms \<open>y \<in> C\<close> C quotientD[of UNIV "?R" C y] sympD[of R] |
1085 by (auto simp add: equivp_equiv elim: equivpE) |
1085 by (auto simp add: equivp_equiv elim: equivpE) |
1086 ultimately show ?thesis |
1086 ultimately show ?thesis |
1087 by auto |
1087 by auto |
1088 qed |
1088 qed |
1089 next |
1089 next |
1112 unfolding measure_pmf_zero_iff by auto |
1112 unfolding measure_pmf_zero_iff by auto |
1113 qed |
1113 qed |
1114 |
1114 |
1115 fix x y assume "x \<in> set_pmf p" "y \<in> set_pmf q" "R x y" |
1115 fix x y assume "x \<in> set_pmf p" "y \<in> set_pmf q" "R x y" |
1116 have "{y. R x y} \<in> UNIV // ?R" "{x. R x y} = {y. R x y}" |
1116 have "{y. R x y} \<in> UNIV // ?R" "{x. R x y} = {y. R x y}" |
1117 using assms `R x y` by (auto simp: quotient_def dest: equivp_symp equivp_transp) |
1117 using assms \<open>R x y\<close> by (auto simp: quotient_def dest: equivp_symp equivp_transp) |
1118 with eq show "measure p {x. R x y} = measure q {y. R x y}" |
1118 with eq show "measure p {x. R x y} = measure q {y. R x y}" |
1119 by auto |
1119 by auto |
1120 qed |
1120 qed |
1121 |
1121 |
1122 bnf pmf: "'a pmf" map: map_pmf sets: set_pmf bd : "natLeq" rel: rel_pmf |
1122 bnf pmf: "'a pmf" map: map_pmf sets: set_pmf bd : "natLeq" rel: rel_pmf |
1196 then obtain pq where *: "\<And>a b. (a, b) \<in> set_pmf pq \<Longrightarrow> R a b" |
1196 then obtain pq where *: "\<And>a b. (a, b) \<in> set_pmf pq \<Longrightarrow> R a b" |
1197 and eq: "return_pmf x = map_pmf fst pq" "M = map_pmf snd pq" |
1197 and eq: "return_pmf x = map_pmf fst pq" "M = map_pmf snd pq" |
1198 by (force elim: rel_pmf.cases) |
1198 by (force elim: rel_pmf.cases) |
1199 moreover have "set_pmf (return_pmf x) = {x}" |
1199 moreover have "set_pmf (return_pmf x) = {x}" |
1200 by simp |
1200 by simp |
1201 with `a \<in> M` have "(x, a) \<in> pq" |
1201 with \<open>a \<in> M\<close> have "(x, a) \<in> pq" |
1202 by (force simp: eq) |
1202 by (force simp: eq) |
1203 with * show "R x a" |
1203 with * show "R x a" |
1204 by auto |
1204 by auto |
1205 qed (auto intro!: rel_pmf.intros[where pq="pair_pmf (return_pmf x) M"] |
1205 qed (auto intro!: rel_pmf.intros[where pq="pair_pmf (return_pmf x) M"] |
1206 simp: map_fst_pair_pmf map_snd_pair_pmf) |
1206 simp: map_fst_pair_pmf map_snd_pair_pmf) |
1364 shows "rel_pmf P (bind_pmf p f) (bind_pmf q g)" |
1364 shows "rel_pmf P (bind_pmf p f) (bind_pmf q g)" |
1365 unfolding bind_eq_join_pmf |
1365 unfolding bind_eq_join_pmf |
1366 by (rule rel_pmf_joinI) |
1366 by (rule rel_pmf_joinI) |
1367 (auto simp add: pmf.rel_map intro: pmf.rel_mono[THEN le_funD, THEN le_funD, THEN le_boolD, THEN mp, OF _ pq] fg) |
1367 (auto simp add: pmf.rel_map intro: pmf.rel_mono[THEN le_funD, THEN le_funD, THEN le_boolD, THEN mp, OF _ pq] fg) |
1368 |
1368 |
1369 text {* |
1369 text \<open> |
1370 Proof that @{const rel_pmf} preserves orders. |
1370 Proof that @{const rel_pmf} preserves orders. |
1371 Antisymmetry proof follows Thm. 1 in N. Saheb-Djahromi, Cpo's of measures for nondeterminism, |
1371 Antisymmetry proof follows Thm. 1 in N. Saheb-Djahromi, Cpo's of measures for nondeterminism, |
1372 Theoretical Computer Science 12(1):19--37, 1980, |
1372 Theoretical Computer Science 12(1):19--37, 1980, |
1373 @{url "http://dx.doi.org/10.1016/0304-3975(80)90003-1"} |
1373 @{url "http://dx.doi.org/10.1016/0304-3975(80)90003-1"} |
1374 *} |
1374 \<close> |
1375 |
1375 |
1376 lemma |
1376 lemma |
1377 assumes *: "rel_pmf R p q" |
1377 assumes *: "rel_pmf R p q" |
1378 and refl: "reflp R" and trans: "transp R" |
1378 and refl: "reflp R" and trans: "transp R" |
1379 shows measure_Ici: "measure p {y. R x y} \<le> measure q {y. R x y}" (is ?thesis1) |
1379 shows measure_Ici: "measure p {y. R x y} \<le> measure q {y. R x y}" (is ?thesis1) |