src/HOL/Lambda/Type.thy
author wenzelm
Tue Sep 12 22:13:23 2000 +0200 (2000-09-12)
changeset 9941 fe05af7ec816
parent 9906 5c027cca6262
child 10155 6263a4a60e38
permissions -rw-r--r--
renamed atts: rulify to rule_format, elimify to elim_format;
berghofe@9114
     1
(*  Title:      HOL/Lambda/Type.thy
berghofe@9114
     2
    ID:         $Id$
berghofe@9114
     3
    Author:     Stefan Berghofer
berghofe@9114
     4
    Copyright   2000 TU Muenchen
wenzelm@9811
     5
*)
berghofe@9114
     6
wenzelm@9811
     7
header {* Simply-typed lambda terms: subject reduction and strong
wenzelm@9811
     8
  normalization *}
berghofe@9114
     9
wenzelm@9622
    10
theory Type = InductTermi:
berghofe@9114
    11
wenzelm@9811
    12
text_raw {*
wenzelm@9811
    13
  \footnote{Formalization by Stefan Berghofer.  Partly based on a
wenzelm@9811
    14
  paper proof by Ralph Matthes.}
wenzelm@9811
    15
*}
wenzelm@9811
    16
wenzelm@9811
    17
wenzelm@9811
    18
subsection {* Types and typing rules *}
wenzelm@9811
    19
wenzelm@9641
    20
datatype type =
wenzelm@9622
    21
    Atom nat
wenzelm@9811
    22
  | Fun type type  (infixr "=>" 200)
berghofe@9114
    23
berghofe@9114
    24
consts
wenzelm@9641
    25
  typing :: "((nat => type) \<times> dB \<times> type) set"
berghofe@9114
    26
berghofe@9114
    27
syntax
wenzelm@9811
    28
  "_typing" :: "[nat => type, dB, type] => bool"  ("_ |- _ : _" [50,50,50] 50)
wenzelm@9811
    29
  "_funs" :: "[type list, type] => type"  (infixl "=>>" 150)
berghofe@9114
    30
translations
wenzelm@9811
    31
  "env |- t : T" == "(env, t, T) \<in> typing"
berghofe@9114
    32
  "Ts =>> T" == "foldr Fun Ts T"
berghofe@9114
    33
berghofe@9114
    34
inductive typing
wenzelm@9811
    35
  intros [intro!]
wenzelm@9811
    36
    Var: "env x = T ==> env |- Var x : T"
wenzelm@9811
    37
    Abs: "(nat_case T env) |- t : U ==> env |- Abs t : (T => U)"
wenzelm@9811
    38
    App: "env |- s : T => U ==> env |- t : T ==> env |- (s $ t) : U"
wenzelm@9622
    39
wenzelm@9641
    40
inductive_cases [elim!]:
wenzelm@9641
    41
  "e |- Var i : T"
wenzelm@9641
    42
  "e |- t $ u : T"
wenzelm@9641
    43
  "e |- Abs t : T"
berghofe@9114
    44
berghofe@9114
    45
consts
wenzelm@9641
    46
  "types" :: "[nat => type, dB list, type list] => bool"
berghofe@9114
    47
primrec
berghofe@9114
    48
  "types e [] Ts = (Ts = [])"
wenzelm@9622
    49
  "types e (t # ts) Ts =
wenzelm@9622
    50
    (case Ts of
berghofe@9114
    51
      [] => False
wenzelm@9641
    52
    | T # Ts => e |- t : T \<and> types e ts Ts)"
wenzelm@9622
    53
wenzelm@9622
    54
inductive_cases [elim!]:
wenzelm@9811
    55
  "x # xs \<in> lists S"
wenzelm@9622
    56
wenzelm@9641
    57
declare IT.intros [intro!]
wenzelm@9641
    58
wenzelm@9622
    59
wenzelm@9811
    60
subsection {* Some examples *}
wenzelm@9622
    61
wenzelm@9622
    62
lemma "\<exists>T U. e |- Abs (Abs (Abs (Var 1 $ (Var 2 $ Var 1 $ Var 0)))) : T \<and> U = T"
wenzelm@9622
    63
  apply (intro exI conjI)
wenzelm@9641
    64
   apply force
wenzelm@9622
    65
  apply (rule refl)
wenzelm@9622
    66
  done
wenzelm@9622
    67
wenzelm@9622
    68
lemma "\<exists>T U. e |- Abs (Abs (Abs (Var 2 $ Var 0 $ (Var 1 $ Var 0)))) : T \<and> U = T";
wenzelm@9622
    69
  apply (intro exI conjI)
wenzelm@9641
    70
   apply force
wenzelm@9622
    71
  apply (rule refl)
wenzelm@9622
    72
  done
wenzelm@9622
    73
wenzelm@9622
    74
wenzelm@9811
    75
text {* Iterated function types *}
wenzelm@9622
    76
wenzelm@9941
    77
lemma list_app_typeD [rule_format]:
wenzelm@9622
    78
    "\<forall>t T. e |- t $$ ts : T --> (\<exists>Ts. e |- t : Ts =>> T \<and> types e ts Ts)"
wenzelm@9622
    79
  apply (induct_tac ts)
wenzelm@9622
    80
   apply simp
wenzelm@9622
    81
  apply (intro strip)
wenzelm@9622
    82
  apply simp
wenzelm@9622
    83
  apply (erule_tac x = "t $ a" in allE)
wenzelm@9622
    84
  apply (erule_tac x = T in allE)
wenzelm@9622
    85
  apply (erule impE)
wenzelm@9622
    86
   apply assumption
wenzelm@9622
    87
  apply (elim exE conjE)
wenzelm@9622
    88
  apply (ind_cases "e |- t $ u : T")
wenzelm@9622
    89
  apply (rule_tac x = "Ta # Ts" in exI)
wenzelm@9622
    90
  apply simp
wenzelm@9622
    91
  done
wenzelm@9622
    92
wenzelm@9941
    93
lemma list_app_typeI [rule_format]:
wenzelm@9811
    94
    "\<forall>t T Ts. e |- t : Ts =>> T --> types e ts Ts --> e |- t $$ ts : T"
wenzelm@9622
    95
  apply (induct_tac ts)
wenzelm@9622
    96
   apply (intro strip)
wenzelm@9622
    97
   apply simp
wenzelm@9622
    98
  apply (intro strip)
wenzelm@9622
    99
  apply (case_tac Ts)
wenzelm@9622
   100
   apply simp
wenzelm@9622
   101
  apply simp
wenzelm@9622
   102
  apply (erule_tac x = "t $ a" in allE)
wenzelm@9622
   103
  apply (erule_tac x = T in allE)
wenzelm@9622
   104
  apply (erule_tac x = lista in allE)
wenzelm@9622
   105
  apply (erule impE)
wenzelm@9622
   106
   apply (erule conjE)
wenzelm@9622
   107
   apply (erule typing.App)
wenzelm@9622
   108
   apply assumption
wenzelm@9622
   109
  apply blast
wenzelm@9622
   110
  done
wenzelm@9622
   111
wenzelm@9941
   112
lemma lists_types [rule_format]:
wenzelm@9811
   113
    "\<forall>Ts. types e ts Ts --> ts \<in> lists {t. \<exists>T. e |- t : T}"
wenzelm@9622
   114
  apply (induct_tac ts)
wenzelm@9622
   115
   apply (intro strip)
wenzelm@9622
   116
   apply (case_tac Ts)
wenzelm@9622
   117
     apply simp
wenzelm@9622
   118
     apply (rule lists.Nil)
wenzelm@9622
   119
    apply simp
wenzelm@9622
   120
  apply (intro strip)
wenzelm@9622
   121
  apply (case_tac Ts)
wenzelm@9622
   122
   apply simp
wenzelm@9622
   123
  apply simp
wenzelm@9622
   124
  apply (rule lists.Cons)
wenzelm@9622
   125
   apply blast
wenzelm@9622
   126
  apply blast
wenzelm@9622
   127
  done
wenzelm@9622
   128
wenzelm@9622
   129
wenzelm@9811
   130
subsection {* Lifting preserves termination and well-typedness *}
wenzelm@9622
   131
wenzelm@9941
   132
lemma lift_map [rule_format, simp]:
wenzelm@9622
   133
    "\<forall>t. lift (t $$ ts) i = lift t i $$ map (\<lambda>t. lift t i) ts"
wenzelm@9622
   134
  apply (induct_tac ts)
wenzelm@9641
   135
   apply simp_all
wenzelm@9622
   136
  done
wenzelm@9622
   137
wenzelm@9941
   138
lemma subst_map [rule_format, simp]:
wenzelm@9622
   139
  "\<forall>t. subst (t $$ ts) u i = subst t u i $$ map (\<lambda>t. subst t u i) ts"
wenzelm@9622
   140
  apply (induct_tac ts)
wenzelm@9641
   141
   apply simp_all
wenzelm@9622
   142
  done
wenzelm@9622
   143
wenzelm@9941
   144
lemma lift_IT [rule_format, intro!]:
wenzelm@9811
   145
    "t \<in> IT ==> \<forall>i. lift t i \<in> IT"
wenzelm@9622
   146
  apply (erule IT.induct)
wenzelm@9622
   147
    apply (rule allI)
wenzelm@9622
   148
    apply (simp (no_asm))
wenzelm@9622
   149
    apply (rule conjI)
wenzelm@9622
   150
     apply
wenzelm@9622
   151
      (rule impI,
wenzelm@9716
   152
       rule IT.Var,
wenzelm@9622
   153
       erule lists.induct,
wenzelm@9622
   154
       simp (no_asm),
wenzelm@9622
   155
       rule lists.Nil,
wenzelm@9622
   156
       simp (no_asm),
wenzelm@9622
   157
       erule IntE,
wenzelm@9622
   158
       rule lists.Cons,
wenzelm@9622
   159
       blast,
wenzelm@9622
   160
       assumption)+
wenzelm@9622
   161
     apply auto
wenzelm@9622
   162
   done
wenzelm@9622
   163
wenzelm@9941
   164
lemma lifts_IT [rule_format]:
wenzelm@9811
   165
    "ts \<in> lists IT --> map (\<lambda>t. lift t 0) ts \<in> lists IT"
wenzelm@9622
   166
  apply (induct_tac ts)
wenzelm@9622
   167
   apply auto
wenzelm@9622
   168
  done
wenzelm@9622
   169
wenzelm@9622
   170
wenzelm@9622
   171
lemma shift_env [simp]:
wenzelm@9811
   172
  "nat_case T
wenzelm@9622
   173
    (\<lambda>j. if j < i then e j else if j = i then Ua else e (j - 1)) =
wenzelm@9622
   174
    (\<lambda>j. if j < Suc i then nat_case T e j else if j = Suc i then Ua
wenzelm@9622
   175
          else nat_case T e (j - 1))"
wenzelm@9622
   176
  apply (rule ext)
wenzelm@9622
   177
  apply (case_tac j)
wenzelm@9622
   178
   apply simp
wenzelm@9622
   179
  apply (case_tac nat)
wenzelm@9641
   180
   apply simp_all
wenzelm@9622
   181
  done
wenzelm@9622
   182
wenzelm@9941
   183
lemma lift_type' [rule_format]:
wenzelm@9622
   184
  "e |- t : T ==> \<forall>i U.
wenzelm@9622
   185
    (\<lambda>j. if j < i then e j
wenzelm@9641
   186
          else if j = i then U
wenzelm@9622
   187
          else e (j - 1)) |- lift t i : T"
wenzelm@9622
   188
  apply (erule typing.induct)
wenzelm@9622
   189
    apply auto
wenzelm@9622
   190
  done
wenzelm@9622
   191
wenzelm@9622
   192
lemma lift_type [intro!]:
wenzelm@9811
   193
    "e |- t : T ==> nat_case U e |- lift t 0 : T"
wenzelm@9622
   194
  apply (subgoal_tac
wenzelm@9622
   195
    "nat_case U e =
wenzelm@9622
   196
      (\<lambda>j. if j < 0 then e j
wenzelm@9622
   197
            else if j = 0 then U else e (j - 1))")
wenzelm@9622
   198
   apply (erule ssubst)
wenzelm@9622
   199
   apply (erule lift_type')
wenzelm@9622
   200
  apply (rule ext)
wenzelm@9622
   201
  apply (case_tac j)
wenzelm@9622
   202
   apply simp_all
wenzelm@9622
   203
  done
wenzelm@9622
   204
wenzelm@9941
   205
lemma lift_types [rule_format]:
wenzelm@9622
   206
  "\<forall>Ts. types e ts Ts -->
wenzelm@9622
   207
    types (\<lambda>j. if j < i then e j
wenzelm@9622
   208
                else if j = i then U
wenzelm@9622
   209
                else e (j - 1)) (map (\<lambda>t. lift t i) ts) Ts"
wenzelm@9622
   210
  apply (induct_tac ts)
wenzelm@9622
   211
   apply simp
wenzelm@9622
   212
  apply (intro strip)
wenzelm@9622
   213
  apply (case_tac Ts)
wenzelm@9622
   214
   apply simp_all
wenzelm@9622
   215
  apply (rule lift_type')
wenzelm@9622
   216
  apply (erule conjunct1)
wenzelm@9622
   217
  done
wenzelm@9622
   218
wenzelm@9622
   219
wenzelm@9811
   220
subsection {* Substitution lemmas *}
wenzelm@9622
   221
wenzelm@9941
   222
lemma subst_lemma [rule_format]:
wenzelm@9811
   223
  "e |- t : T ==> \<forall>e' i U u.
wenzelm@9622
   224
    e = (\<lambda>j. if j < i then e' j
wenzelm@9622
   225
              else if j = i then U
wenzelm@9622
   226
              else e' (j-1)) -->
wenzelm@9622
   227
    e' |- u : U --> e' |- t[u/i] : T"
wenzelm@9622
   228
  apply (erule typing.induct)
wenzelm@9622
   229
    apply (intro strip)
wenzelm@9622
   230
    apply (case_tac "x = i")
wenzelm@9622
   231
     apply simp
wenzelm@9622
   232
    apply (frule linorder_neq_iff [THEN iffD1])
wenzelm@9622
   233
    apply (erule disjE)
wenzelm@9622
   234
     apply simp
wenzelm@9622
   235
     apply (rule typing.Var)
wenzelm@9622
   236
     apply assumption
wenzelm@9622
   237
    apply (frule order_less_not_sym)
wenzelm@9622
   238
    apply (simp only: subst_gt split: split_if add: if_False)
wenzelm@9622
   239
    apply (rule typing.Var)
wenzelm@9622
   240
    apply assumption
wenzelm@9622
   241
   apply fastsimp
wenzelm@9622
   242
  apply fastsimp
wenzelm@9622
   243
  done
wenzelm@9622
   244
wenzelm@9941
   245
lemma substs_lemma [rule_format]:
wenzelm@9622
   246
  "e |- u : T ==>
wenzelm@9622
   247
    \<forall>Ts. types (\<lambda>j. if j < i then e j
wenzelm@9622
   248
                     else if j = i then T else e (j - 1)) ts Ts -->
wenzelm@9641
   249
      types e (map (\<lambda>t. t[u/i]) ts) Ts"
wenzelm@9622
   250
  apply (induct_tac ts)
wenzelm@9622
   251
   apply (intro strip)
wenzelm@9622
   252
   apply (case_tac Ts)
wenzelm@9622
   253
    apply simp
wenzelm@9622
   254
   apply simp
wenzelm@9622
   255
  apply (intro strip)
wenzelm@9622
   256
  apply (case_tac Ts)
wenzelm@9622
   257
   apply simp
wenzelm@9622
   258
  apply simp
wenzelm@9622
   259
  apply (erule conjE)
wenzelm@9622
   260
  apply (erule subst_lemma)
wenzelm@9641
   261
   apply (rule refl)
wenzelm@9622
   262
  apply assumption
wenzelm@9622
   263
  done
wenzelm@9622
   264
wenzelm@9622
   265
wenzelm@9811
   266
subsection {* Subject reduction *}
wenzelm@9622
   267
wenzelm@9941
   268
lemma subject_reduction [rule_format]:
wenzelm@9622
   269
    "e |- t : T ==> \<forall>t'. t -> t' --> e |- t' : T"
wenzelm@9622
   270
  apply (erule typing.induct)
wenzelm@9622
   271
    apply blast
wenzelm@9622
   272
   apply blast
wenzelm@9622
   273
  apply (intro strip)
wenzelm@9622
   274
  apply (ind_cases "s $ t -> t'")
wenzelm@9622
   275
    apply hypsubst
wenzelm@9622
   276
    apply (ind_cases "env |- Abs t : T => U")
wenzelm@9622
   277
    apply (rule subst_lemma)
wenzelm@9622
   278
      apply assumption
wenzelm@9622
   279
     prefer 2
wenzelm@9622
   280
     apply assumption
wenzelm@9622
   281
    apply (rule ext)
wenzelm@9622
   282
    apply (case_tac j)
wenzelm@9641
   283
     apply auto
wenzelm@9622
   284
  done
wenzelm@9622
   285
wenzelm@9811
   286
wenzelm@9811
   287
subsection {* Additional lemmas *}
wenzelm@9622
   288
wenzelm@9622
   289
lemma app_last: "(t $$ ts) $ u = t $$ (ts @ [u])"
wenzelm@9622
   290
  apply simp
wenzelm@9622
   291
  done
wenzelm@9622
   292
wenzelm@9941
   293
lemma subst_Var_IT [rule_format]: "r \<in> IT ==> \<forall>i j. r[Var i/j] \<in> IT"
wenzelm@9622
   294
  apply (erule IT.induct)
wenzelm@9811
   295
    txt {* Case @{term Var}: *}
wenzelm@9622
   296
    apply (intro strip)
wenzelm@9622
   297
    apply (simp (no_asm) add: subst_Var)
wenzelm@9622
   298
    apply
wenzelm@9622
   299
    ((rule conjI impI)+,
wenzelm@9716
   300
      rule IT.Var,
wenzelm@9622
   301
      erule lists.induct,
wenzelm@9622
   302
      simp (no_asm),
wenzelm@9622
   303
      rule lists.Nil,
wenzelm@9622
   304
      simp (no_asm),
wenzelm@9622
   305
      erule IntE,
wenzelm@9622
   306
      erule CollectE,
wenzelm@9622
   307
      rule lists.Cons,
wenzelm@9622
   308
      fast,
wenzelm@9622
   309
      assumption)+
wenzelm@9811
   310
   txt {* Case @{term Lambda}: *}
wenzelm@9622
   311
   apply (intro strip)
wenzelm@9622
   312
   apply simp
wenzelm@9716
   313
   apply (rule IT.Lambda)
wenzelm@9622
   314
   apply fast
wenzelm@9811
   315
  txt {* Case @{term Beta}: *}
wenzelm@9622
   316
  apply (intro strip)
wenzelm@9622
   317
  apply (simp (no_asm_use) add: subst_subst [symmetric])
wenzelm@9716
   318
  apply (rule IT.Beta)
wenzelm@9622
   319
   apply auto
wenzelm@9622
   320
  done
wenzelm@9622
   321
wenzelm@9622
   322
lemma Var_IT: "Var n \<in> IT"
wenzelm@9622
   323
  apply (subgoal_tac "Var n $$ [] \<in> IT")
wenzelm@9622
   324
   apply simp
wenzelm@9716
   325
  apply (rule IT.Var)
wenzelm@9622
   326
  apply (rule lists.Nil)
wenzelm@9622
   327
  done
wenzelm@9622
   328
wenzelm@9811
   329
lemma app_Var_IT: "t \<in> IT ==> t $ Var i \<in> IT"
wenzelm@9622
   330
  apply (erule IT.induct)
wenzelm@9622
   331
    apply (subst app_last)
wenzelm@9716
   332
    apply (rule IT.Var)
wenzelm@9622
   333
    apply simp
wenzelm@9622
   334
    apply (rule lists.Cons)
wenzelm@9622
   335
     apply (rule Var_IT)
wenzelm@9622
   336
    apply (rule lists.Nil)
wenzelm@9906
   337
   apply (rule IT.Beta [where ?ss = "[]", unfolded foldl_Nil [THEN eq_reflection]])
wenzelm@9622
   338
    apply (erule subst_Var_IT)
wenzelm@9622
   339
   apply (rule Var_IT)
wenzelm@9622
   340
  apply (subst app_last)
wenzelm@9716
   341
  apply (rule IT.Beta)
wenzelm@9622
   342
   apply (subst app_last [symmetric])
wenzelm@9622
   343
   apply assumption
wenzelm@9622
   344
  apply assumption
wenzelm@9622
   345
  done
wenzelm@9622
   346
wenzelm@9622
   347
wenzelm@9811
   348
subsection {* Well-typed substitution preserves termination *}
wenzelm@9622
   349
wenzelm@9941
   350
lemma subst_type_IT [rule_format]:
wenzelm@9811
   351
  "\<forall>t. t \<in> IT --> (\<forall>e T u i.
wenzelm@9622
   352
    (\<lambda>j. if j < i then e j
wenzelm@9622
   353
          else if j = i then U
wenzelm@9622
   354
          else e (j - 1)) |- t : T -->
wenzelm@9811
   355
    u \<in> IT --> e |- u : U --> t[u/i] \<in> IT)"
wenzelm@9622
   356
  apply (rule_tac f = size and a = U in measure_induct)
wenzelm@9622
   357
  apply (rule allI)
wenzelm@9622
   358
  apply (rule impI)
wenzelm@9622
   359
  apply (erule IT.induct)
wenzelm@9811
   360
    txt {* Case @{term Var}: *}
wenzelm@9622
   361
    apply (intro strip)
wenzelm@9622
   362
    apply (case_tac "n = i")
wenzelm@9811
   363
     txt {* Case @{term "n = i"}: *}
wenzelm@9622
   364
     apply (case_tac rs)
wenzelm@9622
   365
      apply simp
wenzelm@9622
   366
     apply simp
wenzelm@9622
   367
     apply (drule list_app_typeD)
wenzelm@9622
   368
     apply (elim exE conjE)
wenzelm@9622
   369
     apply (ind_cases "e |- t $ u : T")
wenzelm@9622
   370
     apply (ind_cases "e |- Var i : T")
wenzelm@9641
   371
     apply (drule_tac s = "(?T::type) => ?U" in sym)
wenzelm@9622
   372
     apply simp
wenzelm@9811
   373
     apply (subgoal_tac "lift u 0 $ Var 0 \<in> IT")
wenzelm@9622
   374
      prefer 2
wenzelm@9622
   375
      apply (rule app_Var_IT)
wenzelm@9622
   376
      apply (erule lift_IT)
wenzelm@9811
   377
     apply (subgoal_tac "(lift u 0 $ Var 0)[a[u/i]/0] \<in> IT")
wenzelm@9622
   378
      apply (simp (no_asm_use))
wenzelm@9641
   379
      apply (subgoal_tac "(Var 0 $$ map (\<lambda>t. lift t 0)
wenzelm@9811
   380
        (map (\<lambda>t. t[u/i]) list))[(u $ a[u/i])/0] \<in> IT")
wenzelm@9771
   381
       apply (simp (no_asm_use) del: map_compose
wenzelm@9771
   382
	 add: map_compose [symmetric] o_def)
wenzelm@9622
   383
      apply (erule_tac x = "Ts =>> T" in allE)
wenzelm@9622
   384
      apply (erule impE)
wenzelm@9622
   385
       apply simp
wenzelm@9622
   386
      apply (erule_tac x = "Var 0 $$
wenzelm@9641
   387
        map (\<lambda>t. lift t 0) (map (\<lambda>t. t[u/i]) list)" in allE)
wenzelm@9622
   388
      apply (erule impE)
wenzelm@9716
   389
       apply (rule IT.Var)
wenzelm@9622
   390
       apply (rule lifts_IT)
wenzelm@9622
   391
       apply (drule lists_types)
wenzelm@9622
   392
       apply
wenzelm@9811
   393
        (ind_cases "x # xs \<in> lists (Collect P)",
wenzelm@9641
   394
         erule lists_IntI [THEN lists.induct],
wenzelm@9641
   395
         assumption)
wenzelm@9641
   396
        apply fastsimp
wenzelm@9622
   397
       apply fastsimp
wenzelm@9622
   398
      apply (erule_tac x = e in allE)
wenzelm@9622
   399
      apply (erule_tac x = T in allE)
wenzelm@9622
   400
      apply (erule_tac x = "u $ a[u/i]" in allE)
wenzelm@9622
   401
      apply (erule_tac x = 0 in allE)
wenzelm@9622
   402
      apply (fastsimp intro!: list_app_typeI lift_types subst_lemma substs_lemma)
wenzelm@9622
   403
     apply (erule_tac x = Ta in allE)
wenzelm@9622
   404
     apply (erule impE)
wenzelm@9622
   405
      apply simp
wenzelm@9622
   406
     apply (erule_tac x = "lift u 0 $ Var 0" in allE)
wenzelm@9622
   407
     apply (erule impE)
wenzelm@9622
   408
      apply assumption
wenzelm@9622
   409
     apply (erule_tac x = e in allE)
wenzelm@9622
   410
     apply (erule_tac x = "Ts =>> T" in allE)
wenzelm@9622
   411
     apply (erule_tac x = "a[u/i]" in allE)
wenzelm@9622
   412
     apply (erule_tac x = 0 in allE)
wenzelm@9622
   413
     apply (erule impE)
wenzelm@9622
   414
      apply (rule typing.App)
wenzelm@9622
   415
       apply (erule lift_type')
wenzelm@9622
   416
      apply (rule typing.Var)
wenzelm@9622
   417
      apply simp
wenzelm@9622
   418
     apply (fast intro!: subst_lemma)
wenzelm@9811
   419
    txt {* Case @{term "n ~= i"}: *}
wenzelm@9622
   420
    apply (drule list_app_typeD)
wenzelm@9622
   421
    apply (erule exE)
wenzelm@9622
   422
    apply (erule conjE)
wenzelm@9622
   423
    apply (drule lists_types)
wenzelm@9811
   424
    apply (subgoal_tac "map (\<lambda>x. x[u/i]) rs \<in> lists IT")
wenzelm@9622
   425
     apply (simp add: subst_Var)
wenzelm@9622
   426
     apply fast
wenzelm@9622
   427
    apply (erule lists_IntI [THEN lists.induct])
wenzelm@9622
   428
      apply assumption
wenzelm@9622
   429
     apply fastsimp
wenzelm@9622
   430
    apply fastsimp
wenzelm@9811
   431
   txt {* Case @{term Lambda}: *}
wenzelm@9622
   432
   apply fastsimp
wenzelm@9811
   433
  txt {* Case @{term Beta}: *}
wenzelm@9622
   434
  apply (intro strip)
wenzelm@9622
   435
  apply (simp (no_asm))
wenzelm@9716
   436
  apply (rule IT.Beta)
wenzelm@9622
   437
   apply (simp (no_asm) del: subst_map add: subst_subst subst_map [symmetric])
wenzelm@9622
   438
   apply (drule subject_reduction)
wenzelm@9622
   439
    apply (rule apps_preserves_beta)
wenzelm@9622
   440
    apply (rule beta.beta)
wenzelm@9622
   441
   apply fast
wenzelm@9622
   442
  apply (drule list_app_typeD)
wenzelm@9622
   443
  apply fast
wenzelm@9622
   444
  done
wenzelm@9622
   445
wenzelm@9622
   446
wenzelm@9811
   447
subsection {* Main theorem: well-typed terms are strongly normalizing *}
wenzelm@9622
   448
wenzelm@9811
   449
lemma type_implies_IT: "e |- t : T ==> t \<in> IT"
wenzelm@9622
   450
  apply (erule typing.induct)
wenzelm@9622
   451
    apply (rule Var_IT)
wenzelm@9716
   452
   apply (erule IT.Lambda)
wenzelm@9811
   453
  apply (subgoal_tac "(Var 0 $ lift t 0)[s/0] \<in> IT")
wenzelm@9622
   454
   apply simp
wenzelm@9622
   455
  apply (rule subst_type_IT)
wenzelm@9771
   456
  apply (rule lists.Nil
wenzelm@9906
   457
    [THEN 2 lists.Cons [THEN IT.Var], unfolded foldl_Nil [THEN eq_reflection]
wenzelm@9771
   458
      foldl_Cons [THEN eq_reflection]])
wenzelm@9622
   459
      apply (erule lift_IT)
wenzelm@9622
   460
     apply (rule typing.App)
wenzelm@9622
   461
     apply (rule typing.Var)
wenzelm@9622
   462
     apply simp
wenzelm@9622
   463
    apply (erule lift_type')
wenzelm@9622
   464
   apply assumption
wenzelm@9622
   465
  apply assumption
wenzelm@9622
   466
  done
wenzelm@9622
   467
wenzelm@9811
   468
theorem type_implies_termi: "e |- t : T ==> t \<in> termi beta"
wenzelm@9622
   469
  apply (rule IT_implies_termi)
wenzelm@9622
   470
  apply (erule type_implies_IT)
wenzelm@9622
   471
  done
wenzelm@9622
   472
wenzelm@9811
   473
end