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