src/HOL/Codatatype/BNF_GFP.thy
author blanchet
Wed Sep 12 10:35:56 2012 +0200 (2012-09-12)
changeset 49325 340844cbf7af
parent 49314 f252c7c2ac7b
child 49328 a1c10b46fecd
permissions -rw-r--r--
tuning
blanchet@48975
     1
(*  Title:      HOL/Codatatype/BNF_GFP.thy
blanchet@48975
     2
    Author:     Dmitriy Traytel, TU Muenchen
blanchet@48975
     3
    Copyright   2012
blanchet@48975
     4
blanchet@48975
     5
Greatest fixed point operation on bounded natural functors.
blanchet@48975
     6
*)
blanchet@48975
     7
blanchet@48975
     8
header {* Greatest Fixed Point Operation on Bounded Natural Functors *}
blanchet@48975
     9
blanchet@48975
    10
theory BNF_GFP
blanchet@49314
    11
imports BNF_FP Equiv_Relations_More "~~/src/HOL/Library/Prefix_Order"
blanchet@48975
    12
keywords
blanchet@49308
    13
  "codata_raw" :: thy_decl and
blanchet@49308
    14
  "codata" :: thy_decl
blanchet@48975
    15
begin
blanchet@48975
    16
blanchet@49312
    17
lemma sum_case_comp_Inl:
blanchet@49312
    18
"sum_case f g \<circ> Inl = f"
blanchet@49312
    19
unfolding comp_def by simp
blanchet@49312
    20
blanchet@49312
    21
lemma sum_case_expand_Inr: "f o Inl = g \<Longrightarrow> f x = sum_case g (f o Inr) x"
blanchet@49312
    22
by (auto split: sum.splits)
blanchet@49312
    23
blanchet@49312
    24
lemma converse_Times: "(A \<times> B) ^-1 = B \<times> A"
blanchet@49312
    25
by auto
blanchet@49312
    26
blanchet@49312
    27
lemma equiv_triv1:
blanchet@49312
    28
assumes "equiv A R" and "(a, b) \<in> R" and "(a, c) \<in> R"
blanchet@49312
    29
shows "(b, c) \<in> R"
blanchet@49312
    30
using assms unfolding equiv_def sym_def trans_def by blast
blanchet@49312
    31
blanchet@49312
    32
lemma equiv_triv2:
blanchet@49312
    33
assumes "equiv A R" and "(a, b) \<in> R" and "(b, c) \<in> R"
blanchet@49312
    34
shows "(a, c) \<in> R"
blanchet@49312
    35
using assms unfolding equiv_def trans_def by blast
blanchet@49312
    36
blanchet@49312
    37
lemma equiv_proj:
blanchet@49312
    38
  assumes e: "equiv A R" and "z \<in> R"
blanchet@49312
    39
  shows "(proj R o fst) z = (proj R o snd) z"
blanchet@49312
    40
proof -
blanchet@49312
    41
  from assms(2) have z: "(fst z, snd z) \<in> R" by auto
blanchet@49312
    42
  have P: "\<And>x. (fst z, x) \<in> R \<Longrightarrow> (snd z, x) \<in> R" by (erule equiv_triv1[OF e z])
blanchet@49312
    43
  have "\<And>x. (snd z, x) \<in> R \<Longrightarrow> (fst z, x) \<in> R" by (erule equiv_triv2[OF e z])
blanchet@49312
    44
  with P show ?thesis unfolding proj_def[abs_def] by auto
blanchet@49312
    45
qed
blanchet@49312
    46
blanchet@49312
    47
(* Operators: *)
blanchet@49312
    48
definition diag where "diag A \<equiv> {(a,a) | a. a \<in> A}"
blanchet@49312
    49
definition image2 where "image2 A f g = {(f a, g a) | a. a \<in> A}"
blanchet@49312
    50
blanchet@49312
    51
lemma diagI: "x \<in> A \<Longrightarrow> (x, x) \<in> diag A"
blanchet@49312
    52
unfolding diag_def by simp
blanchet@49312
    53
blanchet@49312
    54
lemma diagE: "(a, b) \<in> diag A \<Longrightarrow> a = b"
blanchet@49312
    55
unfolding diag_def by simp
blanchet@49312
    56
blanchet@49312
    57
lemma diagE': "x \<in> diag A \<Longrightarrow> fst x = snd x"
blanchet@49312
    58
unfolding diag_def by auto
blanchet@49312
    59
blanchet@49312
    60
lemma diag_fst: "x \<in> diag A \<Longrightarrow> fst x \<in> A"
blanchet@49312
    61
unfolding diag_def by auto
blanchet@49312
    62
blanchet@49312
    63
lemma diag_UNIV: "diag UNIV = Id"
blanchet@49312
    64
unfolding diag_def by auto
blanchet@49312
    65
blanchet@49312
    66
lemma diag_converse: "diag A = (diag A) ^-1"
blanchet@49312
    67
unfolding diag_def by auto
blanchet@49312
    68
blanchet@49312
    69
lemma diag_Comp: "diag A = diag A O diag A"
blanchet@49312
    70
unfolding diag_def by auto
blanchet@49312
    71
blanchet@49312
    72
lemma diag_Gr: "diag A = Gr A id"
blanchet@49312
    73
unfolding diag_def Gr_def by simp
blanchet@49312
    74
blanchet@49312
    75
lemma diag_UNIV_I: "x = y \<Longrightarrow> (x, y) \<in> diag UNIV"
blanchet@49312
    76
unfolding diag_def by auto
blanchet@49312
    77
blanchet@49312
    78
lemma image2_eqI: "\<lbrakk>b = f x; c = g x; x \<in> A\<rbrakk> \<Longrightarrow> (b, c) \<in> image2 A f g"
blanchet@49312
    79
unfolding image2_def by auto
blanchet@49312
    80
blanchet@49312
    81
lemma Id_subset: "Id \<subseteq> {(a, b). P a b \<or> a = b}"
blanchet@49312
    82
by auto
blanchet@49312
    83
blanchet@49312
    84
lemma IdD: "(a, b) \<in> Id \<Longrightarrow> a = b"
blanchet@49312
    85
by auto
blanchet@49312
    86
blanchet@49312
    87
lemma image2_Gr: "image2 A f g = (Gr A f)^-1 O (Gr A g)"
blanchet@49312
    88
unfolding image2_def Gr_def by auto
blanchet@49312
    89
blanchet@49312
    90
lemma GrI: "\<lbrakk>x \<in> A; f x = fx\<rbrakk> \<Longrightarrow> (x, fx) \<in> Gr A f"
blanchet@49312
    91
unfolding Gr_def by simp
blanchet@49312
    92
blanchet@49312
    93
lemma GrE: "(x, fx) \<in> Gr A f \<Longrightarrow> (x \<in> A \<Longrightarrow> f x = fx \<Longrightarrow> P) \<Longrightarrow> P"
blanchet@49312
    94
unfolding Gr_def by simp
blanchet@49312
    95
blanchet@49312
    96
lemma GrD1: "(x, fx) \<in> Gr A f \<Longrightarrow> x \<in> A"
blanchet@49312
    97
unfolding Gr_def by simp
blanchet@49312
    98
blanchet@49312
    99
lemma GrD2: "(x, fx) \<in> Gr A f \<Longrightarrow> f x = fx"
blanchet@49312
   100
unfolding Gr_def by simp
blanchet@49312
   101
blanchet@49312
   102
lemma Gr_incl: "Gr A f \<subseteq> A <*> B \<longleftrightarrow> f ` A \<subseteq> B"
blanchet@49312
   103
unfolding Gr_def by auto
blanchet@49312
   104
blanchet@49312
   105
definition relImage where
blanchet@49312
   106
"relImage R f \<equiv> {(f a1, f a2) | a1 a2. (a1,a2) \<in> R}"
blanchet@49312
   107
blanchet@49312
   108
definition relInvImage where
blanchet@49312
   109
"relInvImage A R f \<equiv> {(a1, a2) | a1 a2. a1 \<in> A \<and> a2 \<in> A \<and> (f a1, f a2) \<in> R}"
blanchet@49312
   110
blanchet@49312
   111
lemma relImage_Gr:
blanchet@49312
   112
"\<lbrakk>R \<subseteq> A \<times> A\<rbrakk> \<Longrightarrow> relImage R f = (Gr A f)^-1 O R O Gr A f"
blanchet@49312
   113
unfolding relImage_def Gr_def relcomp_def by auto
blanchet@49312
   114
blanchet@49312
   115
lemma relInvImage_Gr: "\<lbrakk>R \<subseteq> B \<times> B\<rbrakk> \<Longrightarrow> relInvImage A R f = Gr A f O R O (Gr A f)^-1"
blanchet@49312
   116
unfolding Gr_def relcomp_def image_def relInvImage_def by auto
blanchet@49312
   117
blanchet@49312
   118
lemma relImage_mono:
blanchet@49312
   119
"R1 \<subseteq> R2 \<Longrightarrow> relImage R1 f \<subseteq> relImage R2 f"
blanchet@49312
   120
unfolding relImage_def by auto
blanchet@49312
   121
blanchet@49312
   122
lemma relInvImage_mono:
blanchet@49312
   123
"R1 \<subseteq> R2 \<Longrightarrow> relInvImage A R1 f \<subseteq> relInvImage A R2 f"
blanchet@49312
   124
unfolding relInvImage_def by auto
blanchet@49312
   125
blanchet@49312
   126
lemma relInvImage_diag:
blanchet@49312
   127
"(\<And>a1 a2. f a1 = f a2 \<longleftrightarrow> a1 = a2) \<Longrightarrow> relInvImage A (diag B) f \<subseteq> Id"
blanchet@49312
   128
unfolding relInvImage_def diag_def by auto
blanchet@49312
   129
blanchet@49312
   130
lemma relInvImage_UNIV_relImage:
blanchet@49312
   131
"R \<subseteq> relInvImage UNIV (relImage R f) f"
blanchet@49312
   132
unfolding relInvImage_def relImage_def by auto
blanchet@49312
   133
blanchet@49312
   134
lemma equiv_Image: "equiv A R \<Longrightarrow> (\<And>a b. (a, b) \<in> R \<Longrightarrow> a \<in> A \<and> b \<in> A \<and> R `` {a} = R `` {b})"
blanchet@49312
   135
unfolding equiv_def refl_on_def Image_def by (auto intro: transD symD)
blanchet@49312
   136
blanchet@49312
   137
lemma relImage_proj:
blanchet@49312
   138
assumes "equiv A R"
blanchet@49312
   139
shows "relImage R (proj R) \<subseteq> diag (A//R)"
blanchet@49312
   140
unfolding relImage_def diag_def apply safe
blanchet@49312
   141
using proj_iff[OF assms]
blanchet@49312
   142
by (metis assms equiv_Image proj_def proj_preserves)
blanchet@49312
   143
blanchet@49312
   144
lemma relImage_relInvImage:
blanchet@49312
   145
assumes "R \<subseteq> f ` A <*> f ` A"
blanchet@49312
   146
shows "relImage (relInvImage A R f) f = R"
blanchet@49312
   147
using assms unfolding relImage_def relInvImage_def by fastforce
blanchet@49312
   148
blanchet@49312
   149
lemma subst_Pair: "P x y \<Longrightarrow> a = (x, y) \<Longrightarrow> P (fst a) (snd a)"
blanchet@49312
   150
by simp
blanchet@49312
   151
blanchet@49312
   152
lemma fst_diag_id: "(fst \<circ> (%x. (x, x))) z = id z"
blanchet@49312
   153
by simp
blanchet@49312
   154
blanchet@49312
   155
lemma snd_diag_id: "(snd \<circ> (%x. (x, x))) z = id z"
blanchet@49312
   156
by simp
blanchet@49312
   157
blanchet@49312
   158
lemma Collect_restrict': "{(x, y) | x y. phi x y \<and> P x y} \<subseteq> {(x, y) | x y. phi x y}"
blanchet@49312
   159
by auto
blanchet@49312
   160
blanchet@49312
   161
lemma image_convolD: "\<lbrakk>(a, b) \<in> <f, g> ` X\<rbrakk> \<Longrightarrow> \<exists>x. x \<in> X \<and> a = f x \<and> b = g x"
blanchet@49312
   162
unfolding convol_def by auto
blanchet@49312
   163
blanchet@49312
   164
(*Extended Sublist*)
blanchet@49312
   165
blanchet@49312
   166
definition prefCl where
blanchet@49312
   167
  "prefCl Kl = (\<forall> kl1 kl2. kl1 \<le> kl2 \<and> kl2 \<in> Kl \<longrightarrow> kl1 \<in> Kl)"
blanchet@49312
   168
definition PrefCl where
blanchet@49312
   169
  "PrefCl A n = (\<forall>kl kl'. kl \<in> A n \<and> kl' \<le> kl \<longrightarrow> (\<exists>m\<le>n. kl' \<in> A m))"
blanchet@49312
   170
blanchet@49312
   171
lemma prefCl_UN:
blanchet@49312
   172
  "\<lbrakk>\<And>n. PrefCl A n\<rbrakk> \<Longrightarrow> prefCl (\<Union>n. A n)"
blanchet@49312
   173
unfolding prefCl_def PrefCl_def by fastforce
blanchet@49312
   174
blanchet@49312
   175
definition Succ where "Succ Kl kl = {k . kl @ [k] \<in> Kl}"
blanchet@49312
   176
definition Shift where "Shift Kl k = {kl. k # kl \<in> Kl}"
blanchet@49312
   177
definition shift where "shift lab k = (\<lambda>kl. lab (k # kl))"
blanchet@49312
   178
blanchet@49312
   179
lemma empty_Shift: "\<lbrakk>[] \<in> Kl; k \<in> Succ Kl []\<rbrakk> \<Longrightarrow> [] \<in> Shift Kl k"
blanchet@49312
   180
unfolding Shift_def Succ_def by simp
blanchet@49312
   181
blanchet@49312
   182
lemma Shift_clists: "Kl \<subseteq> Field (clists r) \<Longrightarrow> Shift Kl k \<subseteq> Field (clists r)"
blanchet@49312
   183
unfolding Shift_def clists_def Field_card_of by auto
blanchet@49312
   184
blanchet@49312
   185
lemma Shift_prefCl: "prefCl Kl \<Longrightarrow> prefCl (Shift Kl k)"
blanchet@49312
   186
unfolding prefCl_def Shift_def
blanchet@49312
   187
proof safe
blanchet@49312
   188
  fix kl1 kl2
blanchet@49312
   189
  assume "\<forall>kl1 kl2. kl1 \<le> kl2 \<and> kl2 \<in> Kl \<longrightarrow> kl1 \<in> Kl"
blanchet@49312
   190
    "kl1 \<le> kl2" "k # kl2 \<in> Kl"
blanchet@49312
   191
  thus "k # kl1 \<in> Kl" using Cons_prefix_Cons[of k kl1 k kl2] by blast
blanchet@49312
   192
qed
blanchet@49312
   193
blanchet@49312
   194
lemma not_in_Shift: "kl \<notin> Shift Kl x \<Longrightarrow> x # kl \<notin> Kl"
blanchet@49312
   195
unfolding Shift_def by simp
blanchet@49312
   196
blanchet@49312
   197
lemma prefCl_Succ: "\<lbrakk>prefCl Kl; k # kl \<in> Kl\<rbrakk> \<Longrightarrow> k \<in> Succ Kl []"
blanchet@49312
   198
unfolding Succ_def proof
blanchet@49312
   199
  assume "prefCl Kl" "k # kl \<in> Kl"
blanchet@49312
   200
  moreover have "k # [] \<le> k # kl" by auto
blanchet@49312
   201
  ultimately have "k # [] \<in> Kl" unfolding prefCl_def by blast
blanchet@49312
   202
  thus "[] @ [k] \<in> Kl" by simp
blanchet@49312
   203
qed
blanchet@49312
   204
blanchet@49312
   205
lemma SuccD: "k \<in> Succ Kl kl \<Longrightarrow> kl @ [k] \<in> Kl"
blanchet@49312
   206
unfolding Succ_def by simp
blanchet@49312
   207
blanchet@49312
   208
lemmas SuccE = SuccD[elim_format]
blanchet@49312
   209
blanchet@49312
   210
lemma SuccI: "kl @ [k] \<in> Kl \<Longrightarrow> k \<in> Succ Kl kl"
blanchet@49312
   211
unfolding Succ_def by simp
blanchet@49312
   212
blanchet@49312
   213
lemma ShiftD: "kl \<in> Shift Kl k \<Longrightarrow> k # kl \<in> Kl"
blanchet@49312
   214
unfolding Shift_def by simp
blanchet@49312
   215
blanchet@49312
   216
lemma Succ_Shift: "Succ (Shift Kl k) kl = Succ Kl (k # kl)"
blanchet@49312
   217
unfolding Succ_def Shift_def by auto
blanchet@49312
   218
blanchet@49312
   219
lemma ShiftI: "k # kl \<in> Kl \<Longrightarrow> kl \<in> Shift Kl k"
blanchet@49312
   220
unfolding Shift_def by simp
blanchet@49312
   221
blanchet@49312
   222
lemma Func_cexp: "|Func A B| =o |B| ^c |A|"
blanchet@49312
   223
unfolding cexp_def Field_card_of by (simp only: card_of_refl)
blanchet@49312
   224
blanchet@49312
   225
lemma clists_bound: "A \<in> Field (cpow (clists r)) - {{}} \<Longrightarrow> |A| \<le>o clists r"
blanchet@49312
   226
unfolding cpow_def clists_def Field_card_of by (auto simp: card_of_mono1)
blanchet@49312
   227
blanchet@49312
   228
lemma cpow_clists_czero: "\<lbrakk>A \<in> Field (cpow (clists r)) - {{}}; |A| =o czero\<rbrakk> \<Longrightarrow> False"
blanchet@49312
   229
unfolding cpow_def clists_def
blanchet@49312
   230
by (auto simp add: card_of_ordIso_czero_iff_empty[symmetric])
blanchet@49312
   231
   (erule notE, erule ordIso_transitive, rule czero_ordIso)
blanchet@49312
   232
blanchet@49312
   233
lemma incl_UNION_I:
blanchet@49312
   234
assumes "i \<in> I" and "A \<subseteq> F i"
blanchet@49312
   235
shows "A \<subseteq> UNION I F"
blanchet@49312
   236
using assms by auto
blanchet@49312
   237
blanchet@49312
   238
lemma Nil_clists: "{[]} \<subseteq> Field (clists r)"
blanchet@49312
   239
unfolding clists_def Field_card_of by auto
blanchet@49312
   240
blanchet@49312
   241
lemma Cons_clists:
blanchet@49312
   242
  "\<lbrakk>x \<in> Field r; xs \<in> Field (clists r)\<rbrakk> \<Longrightarrow> x # xs \<in> Field (clists r)"
blanchet@49312
   243
unfolding clists_def Field_card_of by auto
blanchet@49312
   244
blanchet@49312
   245
lemma length_Cons: "length (x # xs) = Suc (length xs)"
blanchet@49312
   246
by simp
blanchet@49312
   247
blanchet@49312
   248
lemma length_append_singleton: "length (xs @ [x]) = Suc (length xs)"
blanchet@49312
   249
by simp
blanchet@49312
   250
blanchet@49312
   251
(*injection into the field of a cardinal*)
blanchet@49312
   252
definition "toCard_pred A r f \<equiv> inj_on f A \<and> f ` A \<subseteq> Field r \<and> Card_order r"
blanchet@49312
   253
definition "toCard A r \<equiv> SOME f. toCard_pred A r f"
blanchet@49312
   254
blanchet@49312
   255
lemma ex_toCard_pred:
blanchet@49312
   256
"\<lbrakk>|A| \<le>o r; Card_order r\<rbrakk> \<Longrightarrow> \<exists> f. toCard_pred A r f"
blanchet@49312
   257
unfolding toCard_pred_def
blanchet@49312
   258
using card_of_ordLeq[of A "Field r"]
blanchet@49312
   259
      ordLeq_ordIso_trans[OF _ card_of_unique[of "Field r" r], of "|A|"]
blanchet@49312
   260
by blast
blanchet@49312
   261
blanchet@49312
   262
lemma toCard_pred_toCard:
blanchet@49312
   263
  "\<lbrakk>|A| \<le>o r; Card_order r\<rbrakk> \<Longrightarrow> toCard_pred A r (toCard A r)"
blanchet@49312
   264
unfolding toCard_def using someI_ex[OF ex_toCard_pred] .
blanchet@49312
   265
blanchet@49312
   266
lemma toCard_inj: "\<lbrakk>|A| \<le>o r; Card_order r; x \<in> A; y \<in> A\<rbrakk> \<Longrightarrow>
blanchet@49312
   267
  toCard A r x = toCard A r y \<longleftrightarrow> x = y"
blanchet@49312
   268
using toCard_pred_toCard unfolding inj_on_def toCard_pred_def by blast
blanchet@49312
   269
blanchet@49312
   270
lemma toCard: "\<lbrakk>|A| \<le>o r; Card_order r; b \<in> A\<rbrakk> \<Longrightarrow> toCard A r b \<in> Field r"
blanchet@49312
   271
using toCard_pred_toCard unfolding toCard_pred_def by blast
blanchet@49312
   272
blanchet@49312
   273
definition "fromCard A r k \<equiv> SOME b. b \<in> A \<and> toCard A r b = k"
blanchet@49312
   274
blanchet@49312
   275
lemma fromCard_toCard:
blanchet@49312
   276
"\<lbrakk>|A| \<le>o r; Card_order r; b \<in> A\<rbrakk> \<Longrightarrow> fromCard A r (toCard A r b) = b"
blanchet@49312
   277
unfolding fromCard_def by (rule some_equality) (auto simp add: toCard_inj)
blanchet@49312
   278
blanchet@49312
   279
(* pick according to the weak pullback *)
blanchet@49312
   280
definition pickWP_pred where
blanchet@49325
   281
"pickWP_pred A p1 p2 b1 b2 a \<equiv> a \<in> A \<and> p1 a = b1 \<and> p2 a = b2"
blanchet@49312
   282
blanchet@49312
   283
definition pickWP where
blanchet@49325
   284
"pickWP A p1 p2 b1 b2 \<equiv> SOME a. pickWP_pred A p1 p2 b1 b2 a"
blanchet@49312
   285
blanchet@49312
   286
lemma pickWP_pred:
blanchet@49312
   287
assumes "wpull A B1 B2 f1 f2 p1 p2" and
blanchet@49312
   288
"b1 \<in> B1" and "b2 \<in> B2" and "f1 b1 = f2 b2"
blanchet@49312
   289
shows "\<exists> a. pickWP_pred A p1 p2 b1 b2 a"
blanchet@49312
   290
using assms unfolding wpull_def pickWP_pred_def by blast
blanchet@49312
   291
blanchet@49312
   292
lemma pickWP_pred_pickWP:
blanchet@49312
   293
assumes "wpull A B1 B2 f1 f2 p1 p2" and
blanchet@49312
   294
"b1 \<in> B1" and "b2 \<in> B2" and "f1 b1 = f2 b2"
blanchet@49312
   295
shows "pickWP_pred A p1 p2 b1 b2 (pickWP A p1 p2 b1 b2)"
blanchet@49312
   296
unfolding pickWP_def using assms by(rule someI_ex[OF pickWP_pred])
blanchet@49312
   297
blanchet@49312
   298
lemma pickWP:
blanchet@49312
   299
assumes "wpull A B1 B2 f1 f2 p1 p2" and
blanchet@49312
   300
"b1 \<in> B1" and "b2 \<in> B2" and "f1 b1 = f2 b2"
blanchet@49312
   301
shows "pickWP A p1 p2 b1 b2 \<in> A"
blanchet@49312
   302
      "p1 (pickWP A p1 p2 b1 b2) = b1"
blanchet@49312
   303
      "p2 (pickWP A p1 p2 b1 b2) = b2"
blanchet@49312
   304
using assms pickWP_pred_pickWP unfolding pickWP_pred_def by fastforce+
blanchet@49312
   305
blanchet@49312
   306
lemma Inl_Field_csum: "a \<in> Field r \<Longrightarrow> Inl a \<in> Field (r +c s)"
blanchet@49312
   307
unfolding Field_card_of csum_def by auto
blanchet@49312
   308
blanchet@49312
   309
lemma Inr_Field_csum: "a \<in> Field s \<Longrightarrow> Inr a \<in> Field (r +c s)"
blanchet@49312
   310
unfolding Field_card_of csum_def by auto
blanchet@49312
   311
blanchet@49312
   312
lemma nat_rec_0: "f = nat_rec f1 (%n rec. f2 n rec) \<Longrightarrow> f 0 = f1"
blanchet@49312
   313
by auto
blanchet@49312
   314
blanchet@49312
   315
lemma nat_rec_Suc: "f = nat_rec f1 (%n rec. f2 n rec) \<Longrightarrow> f (Suc n) = f2 n (f n)"
blanchet@49312
   316
by auto
blanchet@49312
   317
blanchet@49312
   318
lemma list_rec_Nil: "f = list_rec f1 (%x xs rec. f2 x xs rec) \<Longrightarrow> f [] = f1"
blanchet@49312
   319
by auto
blanchet@49312
   320
blanchet@49312
   321
lemma list_rec_Cons: "f = list_rec f1 (%x xs rec. f2 x xs rec) \<Longrightarrow> f (x # xs) = f2 x xs (f xs)"
blanchet@49312
   322
by auto
blanchet@49312
   323
blanchet@49312
   324
lemma sum_case_cong: "p = q \<Longrightarrow> sum_case f g p = sum_case f g q"
blanchet@49312
   325
by simp
blanchet@49312
   326
blanchet@49312
   327
lemma not_arg_cong_Inr: "x \<noteq> y \<Longrightarrow> Inr x \<noteq> Inr y"
blanchet@49312
   328
by simp
blanchet@49312
   329
blanchet@49309
   330
ML_file "Tools/bnf_gfp_util.ML"
blanchet@49309
   331
ML_file "Tools/bnf_gfp_tactics.ML"
blanchet@49309
   332
ML_file "Tools/bnf_gfp.ML"
blanchet@49309
   333
blanchet@48975
   334
end