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