src/HOL/BNF_Comp.thy
author blanchet
Mon Jan 20 18:24:56 2014 +0100 (2014-01-20)
changeset 55066 4e5ddf3162ac
parent 55062 6d3fad6f01c9
child 55705 a98a045a6169
permissions -rw-r--r--
tuning
blanchet@55059
     1
(*  Title:      HOL/BNF_Comp.thy
blanchet@48975
     2
    Author:     Dmitriy Traytel, TU Muenchen
blanchet@48975
     3
    Copyright   2012
blanchet@48975
     4
blanchet@48975
     5
Composition of bounded natural functors.
blanchet@48975
     6
*)
blanchet@48975
     7
blanchet@48975
     8
header {* Composition of Bounded Natural Functors *}
blanchet@48975
     9
blanchet@48975
    10
theory BNF_Comp
blanchet@48975
    11
imports Basic_BNFs
blanchet@48975
    12
begin
blanchet@48975
    13
blanchet@49312
    14
lemma empty_natural: "(\<lambda>_. {}) o f = image g o (\<lambda>_. {})"
blanchet@49312
    15
by (rule ext) simp
blanchet@49312
    16
blanchet@49312
    17
lemma Union_natural: "Union o image (image f) = image f o Union"
blanchet@55066
    18
by (rule ext) (auto simp only: comp_apply)
blanchet@49312
    19
blanchet@49312
    20
lemma in_Union_o_assoc: "x \<in> (Union o gset o gmap) A \<Longrightarrow> x \<in> (Union o (gset o gmap)) A"
blanchet@55066
    21
by (unfold comp_assoc)
blanchet@49312
    22
blanchet@49312
    23
lemma comp_single_set_bd:
blanchet@49312
    24
  assumes fbd_Card_order: "Card_order fbd" and
blanchet@49312
    25
    fset_bd: "\<And>x. |fset x| \<le>o fbd" and
blanchet@49312
    26
    gset_bd: "\<And>x. |gset x| \<le>o gbd"
haftmann@52141
    27
  shows "|\<Union>(fset ` gset x)| \<le>o gbd *c fbd"
blanchet@49312
    28
apply (subst sym[OF SUP_def])
blanchet@49312
    29
apply (rule ordLeq_transitive)
blanchet@49312
    30
apply (rule card_of_UNION_Sigma)
blanchet@49312
    31
apply (subst SIGMA_CSUM)
blanchet@49312
    32
apply (rule ordLeq_transitive)
blanchet@49312
    33
apply (rule card_of_Csum_Times')
blanchet@49312
    34
apply (rule fbd_Card_order)
blanchet@49312
    35
apply (rule ballI)
blanchet@49312
    36
apply (rule fset_bd)
blanchet@49312
    37
apply (rule ordLeq_transitive)
blanchet@49312
    38
apply (rule cprod_mono1)
blanchet@49312
    39
apply (rule gset_bd)
blanchet@49312
    40
apply (rule ordIso_imp_ordLeq)
blanchet@49312
    41
apply (rule ordIso_refl)
blanchet@49312
    42
apply (rule Card_order_cprod)
blanchet@49312
    43
done
blanchet@49312
    44
haftmann@52141
    45
lemma Union_image_insert: "\<Union>(f ` insert a B) = f a \<union> \<Union>(f ` B)"
blanchet@49312
    46
by simp
blanchet@49312
    47
haftmann@52141
    48
lemma Union_image_empty: "A \<union> \<Union>(f ` {}) = A"
blanchet@49312
    49
by simp
blanchet@49312
    50
blanchet@49312
    51
lemma image_o_collect: "collect ((\<lambda>f. image g o f) ` F) = image g o collect F"
blanchet@49312
    52
by (rule ext) (auto simp add: collect_def)
blanchet@49312
    53
blanchet@49312
    54
lemma conj_subset_def: "A \<subseteq> {x. P x \<and> Q x} = (A \<subseteq> {x. P x} \<and> A \<subseteq> {x. Q x})"
blanchet@49312
    55
by blast
blanchet@49312
    56
haftmann@52141
    57
lemma UN_image_subset: "\<Union>(f ` g x) \<subseteq> X = (g x \<subseteq> {x. f x \<subseteq> X})"
blanchet@49312
    58
by blast
blanchet@49312
    59
haftmann@52141
    60
lemma comp_set_bd_Union_o_collect: "|\<Union>\<Union>((\<lambda>f. f x) ` X)| \<le>o hbd \<Longrightarrow> |(Union \<circ> collect X) x| \<le>o hbd"
blanchet@55066
    61
by (unfold comp_apply collect_def SUP_def)
blanchet@49312
    62
blanchet@49312
    63
lemma wpull_cong:
blanchet@49312
    64
"\<lbrakk>A' = A; B1' = B1; B2' = B2; wpull A B1 B2 f1 f2 p1 p2\<rbrakk> \<Longrightarrow> wpull A' B1' B2' f1 f2 p1 p2"
blanchet@49312
    65
by simp
blanchet@49312
    66
traytel@51893
    67
lemma Grp_fst_snd: "(Grp (Collect (split R)) fst)^--1 OO Grp (Collect (split R)) snd = R"
traytel@51893
    68
unfolding Grp_def fun_eq_iff relcompp.simps by auto
traytel@51893
    69
traytel@51893
    70
lemma OO_Grp_cong: "A = B \<Longrightarrow> (Grp A f)^--1 OO Grp A g = (Grp B f)^--1 OO Grp B g"
traytel@51893
    71
by simp
traytel@51893
    72
blanchet@55062
    73
ML_file "Tools/BNF/bnf_comp_tactics.ML"
blanchet@55062
    74
ML_file "Tools/BNF/bnf_comp.ML"
blanchet@49309
    75
blanchet@48975
    76
end