src/CCL/Hered.thy
author haftmann
Tue, 10 Jul 2007 17:30:50 +0200
changeset 23709 fd31da8f752a
parent 20140 98acc6d0fab6
child 27146 443c19953137
permissions -rw-r--r--
moved lfp_induct2 here
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
17456
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
     1
(*  Title:      CCL/Hered.thy
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     2
    ID:         $Id$
1474
3f7d67927fe2 expanded tabs
clasohm
parents: 1149
diff changeset
     3
    Author:     Martin Coen
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     4
    Copyright   1993  University of Cambridge
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     5
*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     6
17456
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
     7
header {* Hereditary Termination -- cf. Martin Lo\"f *}
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
     8
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
     9
theory Hered
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    10
imports Type
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    11
begin
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    12
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    13
text {*
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    14
  Note that this is based on an untyped equality and so @{text "lam
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    15
  x. b(x)"} is only hereditarily terminating if @{text "ALL x. b(x)"}
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    16
  is.  Not so useful for functions!
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    17
*}
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    18
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    19
consts
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    20
      (*** Predicates ***)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    21
  HTTgen     ::       "i set => i set"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    22
  HTT        ::       "i set"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    23
17456
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    24
axioms
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    25
  (*** Definitions of Hereditary Termination ***)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    26
17456
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    27
  HTTgen_def:
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    28
  "HTTgen(R) == {t. t=true | t=false | (EX a b. t=<a,b>      & a : R & b : R) |
3837
d7f033c74b38 fixed dots;
wenzelm
parents: 1474
diff changeset
    29
                                      (EX f.  t=lam x. f(x) & (ALL x. f(x) : R))}"
17456
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    30
  HTT_def:       "HTT == gfp(HTTgen)"
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 3837
diff changeset
    31
20140
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    32
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    33
subsection {* Hereditary Termination *}
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    34
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    35
lemma HTTgen_mono: "mono(%X. HTTgen(X))"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    36
  apply (unfold HTTgen_def)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    37
  apply (rule monoI)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    38
  apply blast
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    39
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    40
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    41
lemma HTTgenXH: 
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    42
  "t : HTTgen(A) <-> t=true | t=false | (EX a b. t=<a,b> & a : A & b : A) |  
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    43
                                        (EX f. t=lam x. f(x) & (ALL x. f(x) : A))"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    44
  apply (unfold HTTgen_def)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    45
  apply blast
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    46
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    47
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    48
lemma HTTXH: 
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    49
  "t : HTT <-> t=true | t=false | (EX a b. t=<a,b> & a : HTT & b : HTT) |  
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    50
                                   (EX f. t=lam x. f(x) & (ALL x. f(x) : HTT))"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    51
  apply (rule HTTgen_mono [THEN HTT_def [THEN def_gfp_Tarski], THEN XHlemma1, unfolded HTTgen_def])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    52
  apply blast
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    53
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    54
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    55
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    56
subsection {* Introduction Rules for HTT *}
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    57
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    58
lemma HTT_bot: "~ bot : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    59
  by (blast dest: HTTXH [THEN iffD1])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    60
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    61
lemma HTT_true: "true : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    62
  by (blast intro: HTTXH [THEN iffD2])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    63
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    64
lemma HTT_false: "false : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    65
  by (blast intro: HTTXH [THEN iffD2])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    66
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    67
lemma HTT_pair: "<a,b> : HTT <->  a : HTT  & b : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    68
  apply (rule HTTXH [THEN iff_trans])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    69
  apply blast
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    70
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    71
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    72
lemma HTT_lam: "lam x. f(x) : HTT <-> (ALL x. f(x) : HTT)"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    73
  apply (rule HTTXH [THEN iff_trans])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    74
  apply auto
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    75
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    76
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    77
lemmas HTT_rews1 = HTT_bot HTT_true HTT_false HTT_pair HTT_lam
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    78
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    79
lemma HTT_rews2:
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    80
  "one : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    81
  "inl(a) : HTT <-> a : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    82
  "inr(b) : HTT <-> b : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    83
  "zero : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    84
  "succ(n) : HTT <-> n : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    85
  "[] : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    86
  "x$xs : HTT <-> x : HTT & xs : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    87
  by (simp_all add: data_defs HTT_rews1)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    88
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    89
lemmas HTT_rews = HTT_rews1 HTT_rews2
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    90
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    91
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    92
subsection {* Coinduction for HTT *}
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    93
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    94
lemma HTT_coinduct: "[|  t : R;  R <= HTTgen(R) |] ==> t : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    95
  apply (erule HTT_def [THEN def_coinduct])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    96
  apply assumption
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    97
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    98
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    99
ML {*
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   100
  local val HTT_coinduct = thm "HTT_coinduct"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   101
  in fun HTT_coinduct_tac s i = res_inst_tac [("R", s)] HTT_coinduct i end
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   102
*}
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   103
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   104
lemma HTT_coinduct3:
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   105
  "[|  t : R;   R <= HTTgen(lfp(%x. HTTgen(x) Un R Un HTT)) |] ==> t : HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   106
  apply (erule HTTgen_mono [THEN [3] HTT_def [THEN def_coinduct3]])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   107
  apply assumption
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   108
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   109
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   110
ML {*
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   111
local
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   112
  val HTT_coinduct3 = thm "HTT_coinduct3"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   113
  val HTTgen_def = thm "HTTgen_def"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   114
in
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   115
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   116
val HTT_coinduct3_raw = rewrite_rule [HTTgen_def] HTT_coinduct3
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   117
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   118
fun HTT_coinduct3_tac s i = res_inst_tac [("R",s)] HTT_coinduct3 i
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   119
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   120
val HTTgenIs =
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   121
  map (mk_genIs (the_context ()) (thms "data_defs") (thm "HTTgenXH") (thm "HTTgen_mono"))
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   122
  ["true : HTTgen(R)",
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   123
   "false : HTTgen(R)",
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   124
   "[| a : R;  b : R |] ==> <a,b> : HTTgen(R)",
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   125
   "[| !!x. b(x) : R |] ==> lam x. b(x) : HTTgen(R)",
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   126
   "one : HTTgen(R)",
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   127
   "a : lfp(%x. HTTgen(x) Un R Un HTT) ==> inl(a) : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))",
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   128
   "b : lfp(%x. HTTgen(x) Un R Un HTT) ==> inr(b) : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))",
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   129
   "zero : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))",
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   130
   "n : lfp(%x. HTTgen(x) Un R Un HTT) ==> succ(n) : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))",
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   131
   "[] : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))",
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   132
   "[| h : lfp(%x. HTTgen(x) Un R Un HTT); t : lfp(%x. HTTgen(x) Un R Un HTT) |] ==> h$t : HTTgen(lfp(%x. HTTgen(x) Un R Un HTT))"]
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   133
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   134
end
20140
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   135
*}
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   136
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   137
ML {* bind_thms ("HTTgenIs", HTTgenIs) *}
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   138
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   139
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   140
subsection {* Formation Rules for Types *}
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   141
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   142
lemma UnitF: "Unit <= HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   143
  by (simp add: subsetXH UnitXH HTT_rews)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   144
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   145
lemma BoolF: "Bool <= HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   146
  by (fastsimp simp: subsetXH BoolXH iff: HTT_rews)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   147
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   148
lemma PlusF: "[| A <= HTT;  B <= HTT |] ==> A + B  <= HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   149
  by (fastsimp simp: subsetXH PlusXH iff: HTT_rews)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   150
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   151
lemma SigmaF: "[| A <= HTT;  !!x. x:A ==> B(x) <= HTT |] ==> SUM x:A. B(x) <= HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   152
  by (fastsimp simp: subsetXH SgXH HTT_rews)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   153
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   154
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   155
(*** Formation Rules for Recursive types - using coinduction these only need ***)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   156
(***                                          exhaution rule for type-former ***)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   157
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   158
(*Proof by induction - needs induction rule for type*)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   159
lemma "Nat <= HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   160
  apply (simp add: subsetXH)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   161
  apply clarify
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   162
  apply (erule Nat_ind)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   163
   apply (fastsimp iff: HTT_rews)+
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   164
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   165
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   166
lemma NatF: "Nat <= HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   167
  apply clarify
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   168
  apply (erule HTT_coinduct3)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   169
  apply (fast intro: HTTgenIs elim!: HTTgen_mono [THEN ci3_RI] dest: NatXH [THEN iffD1])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   170
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   171
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   172
lemma ListF: "A <= HTT ==> List(A) <= HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   173
  apply clarify
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   174
  apply (erule HTT_coinduct3)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   175
  apply (fast intro!: HTTgenIs elim!: HTTgen_mono [THEN ci3_RI]
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   176
    subsetD [THEN HTTgen_mono [THEN ci3_AI]]
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   177
    dest: ListXH [THEN iffD1])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   178
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   179
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   180
lemma ListsF: "A <= HTT ==> Lists(A) <= HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   181
  apply clarify
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   182
  apply (erule HTT_coinduct3)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   183
  apply (fast intro!: HTTgenIs elim!: HTTgen_mono [THEN ci3_RI]
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   184
    subsetD [THEN HTTgen_mono [THEN ci3_AI]] dest: ListsXH [THEN iffD1])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   185
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   186
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   187
lemma IListsF: "A <= HTT ==> ILists(A) <= HTT"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   188
  apply clarify
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   189
  apply (erule HTT_coinduct3)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   190
  apply (fast intro!: HTTgenIs elim!: HTTgen_mono [THEN ci3_RI]
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   191
    subsetD [THEN HTTgen_mono [THEN ci3_AI]] dest: IListsXH [THEN iffD1])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   192
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   193
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
   194
end