440 ultimately show "emeasure M X = emeasure N X" |
444 ultimately show "emeasure M X = emeasure N X" |
441 using P[THEN prob_space.emeasure_space_1] |
445 using P[THEN prob_space.emeasure_space_1] |
442 by (cases "xs = []") (auto simp: * space_stream_space del: in_listsD) |
446 by (cases "xs = []") (auto simp: * space_stream_space del: in_listsD) |
443 qed (auto simp: * ae sets_M del: in_listsD intro!: streams_sets) |
447 qed (auto simp: * ae sets_M del: in_listsD intro!: streams_sets) |
444 |
448 |
|
449 primrec scylinder :: "'a set \<Rightarrow> 'a set list \<Rightarrow> 'a stream set" |
|
450 where |
|
451 "scylinder S [] = streams S" |
|
452 | "scylinder S (A # As) = {\<omega>\<in>streams S. shd \<omega> \<in> A \<and> stl \<omega> \<in> scylinder S As}" |
|
453 |
|
454 lemma scylinder_streams: "scylinder S xs \<subseteq> streams S" |
|
455 by (induction xs) auto |
|
456 |
|
457 lemma sets_scylinder: "(\<forall>x\<in>set xs. x \<in> sets S) \<Longrightarrow> scylinder (space S) xs \<in> sets (stream_space S)" |
|
458 by (induction xs) (auto simp: space_stream_space[symmetric]) |
|
459 |
|
460 lemma stream_space_eq_scylinder: |
|
461 assumes P: "prob_space M" "prob_space N" |
|
462 assumes "Int_stable G" and S: "sets S = sets (sigma (space S) G)" |
|
463 and C: "countable C" "C \<subseteq> G" "\<Union>C = space S" and G: "G \<subseteq> Pow (space S)" |
|
464 assumes sets_M: "sets M = sets (stream_space S)" |
|
465 assumes sets_N: "sets N = sets (stream_space S)" |
|
466 assumes *: "\<And>xs. xs \<noteq> [] \<Longrightarrow> xs \<in> lists G \<Longrightarrow> emeasure M (scylinder (space S) xs) = emeasure N (scylinder (space S) xs)" |
|
467 shows "M = N" |
|
468 proof (rule measure_eqI_generator_eq) |
|
469 interpret M: prob_space M by fact |
|
470 interpret N: prob_space N by fact |
|
471 |
|
472 let ?G = "scylinder (space S) ` lists G" |
|
473 show sc_Pow: "?G \<subseteq> Pow (streams (space S))" |
|
474 using scylinder_streams by auto |
|
475 |
|
476 have "sets (stream_space S) = sets (sigma (streams (space S)) ?G)" |
|
477 (is "?S = sets ?R") |
|
478 proof (rule antisym) |
|
479 let ?V = "\<lambda>i. vimage_algebra (streams (space S)) (\<lambda>s. s !! i) S" |
|
480 show "?S \<subseteq> sets ?R" |
|
481 unfolding sets_stream_space_eq |
|
482 proof (safe intro!: sets_Sup_in_sets del: subsetI equalityI) |
|
483 fix i :: nat |
|
484 show "space (?V i) = space ?R" |
|
485 using scylinder_streams by (subst space_measure_of) (auto simp: ) |
|
486 { fix A assume "A \<in> G" |
|
487 then have "scylinder (space S) (replicate i (space S) @ [A]) = (\<lambda>s. s !! i) -` A \<inter> streams (space S)" |
|
488 by (induction i) (auto simp add: streams_shd streams_stl cong: conj_cong) |
|
489 also have "scylinder (space S) (replicate i (space S) @ [A]) = (\<Union>xs\<in>{xs\<in>lists C. length xs = i}. scylinder (space S) (xs @ [A]))" |
|
490 apply (induction i) |
|
491 apply auto [] |
|
492 apply (simp add: length_Suc_conv set_eq_iff ex_simps(1,2)[symmetric] cong: conj_cong del: ex_simps(1,2)) |
|
493 apply rule |
|
494 subgoal for i x |
|
495 apply (cases x) |
|
496 apply (subst (2) C(3)[symmetric]) |
|
497 apply (simp del: ex_simps(1,2) add: ex_simps(1,2)[symmetric] ac_simps Bex_def) |
|
498 apply auto |
|
499 done |
|
500 done |
|
501 finally have "(\<lambda>s. s !! i) -` A \<inter> streams (space S) = (\<Union>xs\<in>{xs\<in>lists C. length xs = i}. scylinder (space S) (xs @ [A]))" |
|
502 .. |
|
503 also have "\<dots> \<in> ?R" |
|
504 using C(2) \<open>A\<in>G\<close> |
|
505 by (intro sets.countable_UN' countable_Collect countable_lists C) |
|
506 (auto intro!: in_measure_of[OF sc_Pow] imageI) |
|
507 finally have "(\<lambda>s. s !! i) -` A \<inter> streams (space S) \<in> ?R" . } |
|
508 then show "sets (?V i) \<subseteq> ?R" |
|
509 apply (subst vimage_algebra_cong[OF refl refl S]) |
|
510 apply (subst vimage_algebra_sigma[OF G]) |
|
511 apply (simp add: streams_iff_snth) [] |
|
512 apply (subst sigma_le_sets) |
|
513 apply auto |
|
514 done |
|
515 qed |
|
516 have "G \<subseteq> sets S" |
|
517 unfolding S using G by auto |
|
518 with C(2) show "sets ?R \<subseteq> ?S" |
|
519 unfolding sigma_le_sets[OF sc_Pow] by (auto intro!: sets_scylinder) |
|
520 qed |
|
521 then show "sets M = sigma_sets (streams (space S)) (scylinder (space S) ` lists G)" |
|
522 "sets N = sigma_sets (streams (space S)) (scylinder (space S) ` lists G)" |
|
523 unfolding sets_M sets_N by (simp_all add: sc_Pow) |
|
524 |
|
525 show "Int_stable ?G" |
|
526 proof (rule Int_stableI_image) |
|
527 fix xs ys assume "xs \<in> lists G" "ys \<in> lists G" |
|
528 then show "\<exists>zs\<in>lists G. scylinder (space S) xs \<inter> scylinder (space S) ys = scylinder (space S) zs" |
|
529 proof (induction xs arbitrary: ys) |
|
530 case Nil then show ?case |
|
531 by (auto simp add: Int_absorb1 scylinder_streams) |
|
532 next |
|
533 case xs: (Cons x xs) |
|
534 show ?case |
|
535 proof (cases ys) |
|
536 case Nil with xs.hyps show ?thesis |
|
537 by (auto simp add: Int_absorb2 scylinder_streams intro!: bexI[of _ "x#xs"]) |
|
538 next |
|
539 case ys: (Cons y ys') |
|
540 with xs.IH[of ys'] xs.prems obtain zs where |
|
541 "zs \<in> lists G" and eq: "scylinder (space S) xs \<inter> scylinder (space S) ys' = scylinder (space S) zs" |
|
542 by auto |
|
543 show ?thesis |
|
544 proof (intro bexI[of _ "(x \<inter> y)#zs"]) |
|
545 show "x \<inter> y # zs \<in> lists G" |
|
546 using \<open>zs\<in>lists G\<close> \<open>x\<in>G\<close> \<open>ys\<in>lists G\<close> ys \<open>Int_stable G\<close>[THEN Int_stableD, of x y] by auto |
|
547 show "scylinder (space S) (x # xs) \<inter> scylinder (space S) ys = scylinder (space S) (x \<inter> y # zs)" |
|
548 by (auto simp add: eq[symmetric] ys) |
|
549 qed |
|
550 qed |
|
551 qed |
|
552 qed |
|
553 |
|
554 show "range (\<lambda>_::nat. streams (space S)) \<subseteq> scylinder (space S) ` lists G" |
|
555 "(\<Union>i. streams (space S)) = streams (space S)" |
|
556 "emeasure M (streams (space S)) \<noteq> \<infinity>" |
|
557 by (auto intro!: image_eqI[of _ _ "[]"]) |
|
558 |
|
559 fix X assume "X \<in> scylinder (space S) ` lists G" |
|
560 then obtain xs where xs: "xs \<in> lists G" and eq: "X = scylinder (space S) xs" |
|
561 by auto |
|
562 then show "emeasure M X = emeasure N X" |
|
563 proof (cases "xs = []") |
|
564 assume "xs = []" then show ?thesis |
|
565 unfolding eq |
|
566 using sets_M[THEN sets_eq_imp_space_eq] sets_N[THEN sets_eq_imp_space_eq] |
|
567 M.emeasure_space_1 N.emeasure_space_1 |
|
568 by (simp add: space_stream_space[symmetric]) |
|
569 next |
|
570 assume "xs \<noteq> []" with xs show ?thesis |
|
571 unfolding eq by (intro *) |
|
572 qed |
|
573 qed |
|
574 |
|
575 lemma stream_space_coinduct: |
|
576 fixes R :: "'a stream measure \<Rightarrow> 'a stream measure \<Rightarrow> bool" |
|
577 assumes "R A B" |
|
578 assumes R: "\<And>A B. R A B \<Longrightarrow> \<exists>K\<in>space (prob_algebra M). |
|
579 \<exists>A'\<in>M \<rightarrow>\<^sub>M prob_algebra (stream_space M). \<exists>B'\<in>M \<rightarrow>\<^sub>M prob_algebra (stream_space M). |
|
580 (AE y in K. R (A' y) (B' y) \<or> A' y = B' y) \<and> |
|
581 A = do { y \<leftarrow> K; \<omega> \<leftarrow> A' y; return (stream_space M) (y ## \<omega>) } \<and> |
|
582 B = do { y \<leftarrow> K; \<omega> \<leftarrow> B' y; return (stream_space M) (y ## \<omega>) }" |
|
583 shows "A = B" |
|
584 proof (rule stream_space_eq_scylinder) |
|
585 let ?step = "\<lambda>K L. do { y \<leftarrow> K; \<omega> \<leftarrow> L y; return (stream_space M) (y ## \<omega>) }" |
|
586 { fix K A A' assume K: "K \<in> space (prob_algebra M)" |
|
587 and A'[measurable]: "A' \<in> M \<rightarrow>\<^sub>M prob_algebra (stream_space M)" and A_eq: "A = ?step K A'" |
|
588 have ps: "prob_space A" |
|
589 unfolding A_eq by (rule prob_space_bind'[OF K]) measurable |
|
590 have "sets A = sets (stream_space M)" |
|
591 unfolding A_eq by (rule sets_bind'[OF K]) measurable |
|
592 note ps this } |
|
593 note ** = this |
|
594 |
|
595 { fix A B assume "R A B" |
|
596 obtain K A' B' where K: "K \<in> space (prob_algebra M)" |
|
597 and A': "A' \<in> M \<rightarrow>\<^sub>M prob_algebra (stream_space M)" "A = ?step K A'" |
|
598 and B': "B' \<in> M \<rightarrow>\<^sub>M prob_algebra (stream_space M)" "B = ?step K B'" |
|
599 using R[OF \<open>R A B\<close>] by blast |
|
600 have "prob_space A" "prob_space B" "sets A = sets (stream_space M)" "sets B = sets (stream_space M)" |
|
601 using **[OF K A'] **[OF K B'] by auto } |
|
602 note R_D = this |
|
603 |
|
604 show "prob_space A" "prob_space B" "sets A = sets (stream_space M)" "sets B = sets (stream_space M)" |
|
605 using R_D[OF \<open>R A B\<close>] by auto |
|
606 |
|
607 show "Int_stable (sets M)" "sets M = sets (sigma (space M) (sets M))" "countable {space M}" |
|
608 "{space M} \<subseteq> sets M" "\<Union>{space M} = space M" "sets M \<subseteq> Pow (space M)" |
|
609 using sets.space_closed[of M] by (auto simp: Int_stable_def) |
|
610 |
|
611 { fix A As L K assume K[measurable]: "K \<in> space (prob_algebra M)" and A: "A \<in> sets M" "As \<in> lists (sets M)" |
|
612 and L[measurable]: "L \<in> M \<rightarrow>\<^sub>M prob_algebra (stream_space M)" |
|
613 from A have [measurable]: "\<forall>x\<in>set (A # As). x \<in> sets M" "\<forall>x\<in>set As. x \<in> sets M" |
|
614 by auto |
|
615 have [simp]: "space K = space M" "sets K = sets M" |
|
616 using K by (auto simp: space_prob_algebra intro!: sets_eq_imp_space_eq) |
|
617 have [simp]: "x \<in> space M \<Longrightarrow> sets (L x) = sets (stream_space M)" for x |
|
618 using measurable_space[OF L] by (auto simp: space_prob_algebra) |
|
619 note sets_scylinder[measurable] |
|
620 have *: "indicator (scylinder (space M) (A # As)) (x ## \<omega>) = |
|
621 (indicator A x * indicator (scylinder (space M) As) \<omega> :: ennreal)" for \<omega> x |
|
622 using scylinder_streams[of "space M" As] \<open>A \<in> sets M\<close>[THEN sets.sets_into_space] |
|
623 by (auto split: split_indicator) |
|
624 have "emeasure (?step K L) (scylinder (space M) (A # As)) = (\<integral>\<^sup>+y. L y (scylinder (space M) As) * indicator A y \<partial>K)" |
|
625 apply (subst emeasure_bind_prob_algebra[OF K]) |
|
626 apply measurable |
|
627 apply (rule nn_integral_cong) |
|
628 apply (subst emeasure_bind_prob_algebra[OF L[THEN measurable_space]]) |
|
629 apply (simp_all add: ac_simps * nn_integral_cmult_indicator del: scylinder.simps) |
|
630 apply measurable |
|
631 done } |
|
632 note emeasure_step = this |
|
633 |
|
634 fix Xs assume "Xs \<in> lists (sets M)" |
|
635 from this \<open>R A B\<close> show "emeasure A (scylinder (space M) Xs) = emeasure B (scylinder (space M) Xs)" |
|
636 proof (induction Xs arbitrary: A B) |
|
637 case (Cons X Xs) |
|
638 obtain K A' B' where K: "K \<in> space (prob_algebra M)" |
|
639 and A'[measurable]: "A' \<in> M \<rightarrow>\<^sub>M prob_algebra (stream_space M)" and A: "A = ?step K A'" |
|
640 and B'[measurable]: "B' \<in> M \<rightarrow>\<^sub>M prob_algebra (stream_space M)" and B: "B = ?step K B'" |
|
641 and AE_R: "AE x in K. R (A' x) (B' x) \<or> A' x = B' x" |
|
642 using R[OF \<open>R A B\<close>] by blast |
|
643 |
|
644 show ?case |
|
645 unfolding A B emeasure_step[OF K Cons.hyps A'] emeasure_step[OF K Cons.hyps B'] |
|
646 apply (rule nn_integral_cong_AE) |
|
647 using AE_R by eventually_elim (auto simp add: Cons.IH) |
|
648 next |
|
649 case Nil |
|
650 note R_D[OF this] |
|
651 from this(1,2)[THEN prob_space.emeasure_space_1] this(3,4)[THEN sets_eq_imp_space_eq] |
|
652 show ?case |
|
653 by (simp add: space_stream_space) |
|
654 qed |
|
655 qed |
|
656 |
445 end |
657 end |