< Module stlc:host.
< Theorem lookup_ty_is :
forall Ctx X Ty,
is_list (is_pair is_string is_ty) Ctx -> lookup Ctx X Ty -> is_ty Ty.
============================
forall Ctx X Ty,
is_list (is_pair is_string is_ty) Ctx -> lookup Ctx X Ty -> is_ty Ty
< induction on 2.
IH : forall Ctx X Ty,
is_list (is_pair is_string is_ty) Ctx -> lookup Ctx X Ty * -> is_ty Ty
============================
forall Ctx X Ty,
is_list (is_pair is_string is_ty) Ctx -> lookup Ctx X Ty @ -> is_ty Ty
< intros Is L.
Variables: Ctx X Ty
IH : forall Ctx X Ty,
is_list (is_pair is_string is_ty) Ctx -> lookup Ctx X Ty * -> is_ty Ty
Is : is_list (is_pair is_string is_ty) Ctx
L : lookup Ctx X Ty @
============================
is_ty Ty
< L: case L.
Subgoal 1:
Variables: X Ty Rest
IH : forall Ctx X Ty,
is_list (is_pair is_string is_ty) Ctx -> lookup Ctx X Ty * -> is_ty Ty
Is : is_list (is_pair is_string is_ty) ((X, Ty)::Rest)
============================
is_ty Ty
< Is: case Is.
Subgoal 1:
Variables: X Ty Rest
IH : forall Ctx X Ty,
is_list (is_pair is_string is_ty) Ctx -> lookup Ctx X Ty * -> is_ty Ty
Is : is_pair is_string is_ty (X, Ty)
Is1 : is_list (is_pair is_string is_ty) Rest
============================
is_ty Ty
< case Is.
Subgoal 1:
Variables: X Ty Rest
IH : forall Ctx X Ty,
is_list (is_pair is_string is_ty) Ctx -> lookup Ctx X Ty * -> is_ty Ty
Is1 : is_list (is_pair is_string is_ty) Rest
H1 : is_string X
H2 : is_ty Ty
============================
is_ty Ty
< search.
Subgoal 2:
Variables: X Ty Rest V K
IH : forall Ctx X Ty,
is_list (is_pair is_string is_ty) Ctx -> lookup Ctx X Ty * -> is_ty Ty
Is : is_list (is_pair is_string is_ty) ((K, V)::Rest)
L : K = X -> false
L1 : lookup Rest X Ty *
============================
is_ty Ty
< Is: case Is.
Subgoal 2:
Variables: X Ty Rest V K
IH : forall Ctx X Ty,
is_list (is_pair is_string is_ty) Ctx -> lookup Ctx X Ty * -> is_ty Ty
L : K = X -> false
L1 : lookup Rest X Ty *
Is : is_pair is_string is_ty (K, V)
Is1 : is_list (is_pair is_string is_ty) Rest
============================
is_ty Ty
< apply IH to _ L1.
Subgoal 2:
Variables: X Ty Rest V K
IH : forall Ctx X Ty,
is_list (is_pair is_string is_ty) Ctx -> lookup Ctx X Ty * -> is_ty Ty
L : K = X -> false
L1 : lookup Rest X Ty *
Is : is_pair is_string is_ty (K, V)
Is1 : is_list (is_pair is_string is_ty) Rest
H1 : is_ty Ty
============================
is_ty Ty
< search.
Proof completed.
< Projection_Constraint proj_ty_is :
forall Ty Ty',
Proj : |{ty}- Ty ~~> Ty' ->
IsTy : is_ty Ty ->
is_ty Ty'.
Proof completed.
< Extensible_Theorem
type_is : forall Ctx T Ty,
IsCtx : is_list (is_pair is_string is_ty) Ctx ->
IsT : is_tm T ->
Ty : typeOf Ctx T Ty ->
is_ty Ty
on Ty.
Subgoal 1:
Variables: Ctx Ty X
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (var X)
Ty : typeOf Ctx (var X) Ty @
Ty1 : lookup Ctx X Ty
============================
is_ty Ty
< apply lookup_ty_is to _ Ty1.
Subgoal 1:
Variables: Ctx Ty X
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (var X)
Ty : typeOf Ctx (var X) Ty @
Ty1 : lookup Ctx X Ty
H1 : is_ty Ty
============================
is_ty Ty
< search.
Subgoal 2:
Variables: Ctx Ty2 Ty1 Body X
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (abs X Ty1 Body)
Ty : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
Ty1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
============================
is_ty (arrowTy Ty1 Ty2)
< Is: case IsT.
Subgoal 2:
Variables: Ctx Ty2 Ty1 Body X
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
Ty1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
Is : is_string X
Is1 : is_ty Ty1
Is2 : is_tm Body
============================
is_ty (arrowTy Ty1 Ty2)
< apply IH to _ _ Ty1.
Subgoal 2:
Variables: Ctx Ty2 Ty1 Body X
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
Ty1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
Is : is_string X
Is1 : is_ty Ty1
Is2 : is_tm Body
H1 : is_ty Ty2
============================
is_ty (arrowTy Ty1 Ty2)
< search.
Subgoal 3:
Variables: Ctx Ty Ty1 T2 T1
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (app T1 T2)
Ty : typeOf Ctx (app T1 T2) Ty @
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
============================
is_ty Ty
< Is: case IsT.
Subgoal 3:
Variables: Ctx Ty Ty1 T2 T1
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_ty Ty
< IsTy: apply IH to _ _ Ty1.
Subgoal 3:
Variables: Ctx Ty Ty1 T2 T1
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
IsTy : is_ty (arrowTy Ty1 Ty)
============================
is_ty Ty
< case IsTy.
Subgoal 3:
Variables: Ctx Ty Ty1 T2 T1
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_ty Ty1
H2 : is_ty Ty
============================
is_ty Ty
< search.
Subgoal 4:
Variables: Ctx I
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (num I)
Ty : typeOf Ctx (num I) intTy @
============================
is_ty intTy
< search.
Subgoal 5:
Variables: Ctx T2 T1
IH : forall Ctx T Ty,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T Ty * -> is_ty Ty
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (plus T1 T2)
Ty : typeOf Ctx (plus T1 T2) intTy @
Ty1 : typeOf Ctx T1 intTy *
Ty2 : typeOf Ctx T2 intTy *
============================
is_ty intTy
< search.
Proof completed.
< Projection_Constraint proj_is :
forall Ctx T T',
Proj : Ctx |{tm}- T ~~> T' ->
IsCtx : is_list (is_pair is_string is_ty) Ctx ->
IsT : is_tm T ->
is_tm T'.
Proof completed.
< Extensible_Theorem
type_unique : forall Ctx T TyA TyB,
IsCtx : is_list (is_pair is_string is_ty) Ctx ->
IsT : is_tm T ->
TyA : typeOf Ctx T TyA ->
TyB : typeOf Ctx T TyB ->
TyA = TyB
on TyA.
Subgoal 1:
Variables: Ctx TyA TyB X
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (var X)
TyA : typeOf Ctx (var X) TyA @
TyB : typeOf Ctx (var X) TyB
TyA1 : lookup Ctx X TyA
============================
TyA = TyB
< TyB: case TyB.
Subgoal 1:
Variables: Ctx TyA TyB X
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (var X)
TyA : typeOf Ctx (var X) TyA @
TyA1 : lookup Ctx X TyA
TyB : lookup Ctx X TyB
============================
TyA = TyB
< apply lookup_unique to TyA1 TyB.
Subgoal 1:
Variables: Ctx TyB X
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (var X)
TyA : typeOf Ctx (var X) TyB @
TyA1 : lookup Ctx X TyB
TyB : lookup Ctx X TyB
============================
TyB = TyB
< search.
Subgoal 2:
Variables: Ctx TyB Ty2 Ty1 Body X
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (abs X Ty1 Body)
TyA : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
TyB : typeOf Ctx (abs X Ty1 Body) TyB
TyA1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
============================
arrowTy Ty1 Ty2 = TyB
< case IsT.
Subgoal 2:
Variables: Ctx TyB Ty2 Ty1 Body X
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
TyA : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
TyB : typeOf Ctx (abs X Ty1 Body) TyB
TyA1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
H1 : is_string X
H2 : is_ty Ty1
H3 : is_tm Body
============================
arrowTy Ty1 Ty2 = TyB
< TyB: case TyB.
Subgoal 2:
Variables: Ctx Ty2 Ty1 Body X Ty4
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
TyA : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
TyA1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
H1 : is_string X
H2 : is_ty Ty1
H3 : is_tm Body
TyB : typeOf ((X, Ty1)::Ctx) Body Ty4
============================
arrowTy Ty1 Ty2 = arrowTy Ty1 Ty4
< apply IH to _ _ TyA1 TyB.
Subgoal 2:
Variables: Ctx Ty1 Body X Ty4
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
TyA : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty4) @
TyA1 : typeOf ((X, Ty1)::Ctx) Body Ty4 *
H1 : is_string X
H2 : is_ty Ty1
H3 : is_tm Body
TyB : typeOf ((X, Ty1)::Ctx) Body Ty4
============================
arrowTy Ty1 Ty4 = arrowTy Ty1 Ty4
< search.
Subgoal 3:
Variables: Ctx TyA TyB Ty1 T2 T1
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (app T1 T2)
TyA : typeOf Ctx (app T1 T2) TyA @
TyB : typeOf Ctx (app T1 T2) TyB
TyA1 : typeOf Ctx T1 (arrowTy Ty1 TyA) *
TyA2 : typeOf Ctx T2 Ty1 *
============================
TyA = TyB
< case IsT.
Subgoal 3:
Variables: Ctx TyA TyB Ty1 T2 T1
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
TyA : typeOf Ctx (app T1 T2) TyA @
TyB : typeOf Ctx (app T1 T2) TyB
TyA1 : typeOf Ctx T1 (arrowTy Ty1 TyA) *
TyA2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
============================
TyA = TyB
< TyB: case TyB.
Subgoal 3:
Variables: Ctx TyA TyB Ty1 T2 T1 Ty2
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
TyA : typeOf Ctx (app T1 T2) TyA @
TyA1 : typeOf Ctx T1 (arrowTy Ty1 TyA) *
TyA2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
TyB : typeOf Ctx T1 (arrowTy Ty2 TyB)
TyB1 : typeOf Ctx T2 Ty2
============================
TyA = TyB
< apply IH to _ _ TyA1 TyB.
Subgoal 3:
Variables: Ctx TyB T2 T1 Ty2
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
TyA : typeOf Ctx (app T1 T2) TyB @
TyA1 : typeOf Ctx T1 (arrowTy Ty2 TyB) *
TyA2 : typeOf Ctx T2 Ty2 *
H1 : is_tm T1
H2 : is_tm T2
TyB : typeOf Ctx T1 (arrowTy Ty2 TyB)
TyB1 : typeOf Ctx T2 Ty2
============================
TyB = TyB
< apply IH to _ _ TyA2 TyB1.
Subgoal 3:
Variables: Ctx TyB T2 T1 Ty2
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
TyA : typeOf Ctx (app T1 T2) TyB @
TyA1 : typeOf Ctx T1 (arrowTy Ty2 TyB) *
TyA2 : typeOf Ctx T2 Ty2 *
H1 : is_tm T1
H2 : is_tm T2
TyB : typeOf Ctx T1 (arrowTy Ty2 TyB)
TyB1 : typeOf Ctx T2 Ty2
============================
TyB = TyB
< search.
Subgoal 4:
Variables: Ctx TyB I
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (num I)
TyA : typeOf Ctx (num I) intTy @
TyB : typeOf Ctx (num I) TyB
============================
intTy = TyB
< case TyB.
Subgoal 4:
Variables: Ctx I
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (num I)
TyA : typeOf Ctx (num I) intTy @
============================
intTy = intTy
< search.
Subgoal 5:
Variables: Ctx TyB T2 T1
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (plus T1 T2)
TyA : typeOf Ctx (plus T1 T2) intTy @
TyB : typeOf Ctx (plus T1 T2) TyB
TyA1 : typeOf Ctx T1 intTy *
TyA2 : typeOf Ctx T2 intTy *
============================
intTy = TyB
< case TyB.
Subgoal 5:
Variables: Ctx T2 T1
IH : forall Ctx T TyA TyB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> typeOf Ctx T TyA * ->
typeOf Ctx T TyB -> TyA = TyB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (plus T1 T2)
TyA : typeOf Ctx (plus T1 T2) intTy @
TyA1 : typeOf Ctx T1 intTy *
TyA2 : typeOf Ctx T2 intTy *
H1 : typeOf Ctx T1 intTy
H2 : typeOf Ctx T2 intTy
============================
intTy = intTy
< search.
Proof completed.
< Projection_Constraint proj_ty_unique :
forall Ty TyA TyB,
|{ty}- Ty ~~> TyA -> |{ty}- Ty ~~> TyB -> is_ty Ty -> TyA = TyB.
Proof completed.
< Projection_Constraint proj_tm_unique :
forall Ctx T TA TB,
Ctx |{tm}- T ~~> TA -> Ctx |{tm}- T ~~> TB -> is_tm T -> is_list (is_pair is_string is_ty) Ctx ->
TA = TB.
Proof completed.
< Extensible_Theorem
subst_is : forall X R T S,
IsT : is_tm T ->
IsX : is_string X ->
IsR : is_tm R ->
S : subst X R T S ->
is_tm S
on S.
Subgoal 1:
Variables: X R Y
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsT : is_tm (var Y)
IsX : is_string X
IsR : is_tm R
S : subst X R (var Y) (var Y) @
S1 : X = Y -> false
============================
is_tm (var Y)
< search.
Subgoal 2:
Variables: X S
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsT : is_tm (var X)
IsX : is_string X
IsR : is_tm S
S : subst X S (var X) S @
============================
is_tm S
< search.
Subgoal 3:
Variables: X R S1 Ty Y B
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsT : is_tm (abs Y Ty B)
IsX : is_string X
IsR : is_tm R
S : subst X R (abs Y Ty B) (abs Y Ty S1) @
S1 : X = Y -> false
S2 : subst X R B S1 *
============================
is_tm (abs Y Ty S1)
< Is: case IsT.
Subgoal 3:
Variables: X R S1 Ty Y B
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (abs Y Ty B) (abs Y Ty S1) @
S1 : X = Y -> false
S2 : subst X R B S1 *
Is : is_string Y
Is1 : is_ty Ty
Is2 : is_tm B
============================
is_tm (abs Y Ty S1)
< apply IH to _ _ _ S2.
Subgoal 3:
Variables: X R S1 Ty Y B
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (abs Y Ty B) (abs Y Ty S1) @
S1 : X = Y -> false
S2 : subst X R B S1 *
Is : is_string Y
Is1 : is_ty Ty
Is2 : is_tm B
H1 : is_tm S1
============================
is_tm (abs Y Ty S1)
< search.
Subgoal 4:
Variables: X R B Ty
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsT : is_tm (abs X Ty B)
IsX : is_string X
IsR : is_tm R
S : subst X R (abs X Ty B) (abs X Ty B) @
============================
is_tm (abs X Ty B)
< search.
Subgoal 5:
Variables: X R S2 S1 T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsT : is_tm (app T1 T2)
IsX : is_string X
IsR : is_tm R
S : subst X R (app T1 T2) (app S1 S2) @
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
============================
is_tm (app S1 S2)
< Is: case IsT.
Subgoal 5:
Variables: X R S2 S1 T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (app T1 T2) (app S1 S2) @
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (app S1 S2)
< apply IH to _ _ _ S1.
Subgoal 5:
Variables: X R S2 S1 T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (app T1 T2) (app S1 S2) @
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm S1
============================
is_tm (app S1 S2)
< apply IH to _ _ _ S2.
Subgoal 5:
Variables: X R S2 S1 T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (app T1 T2) (app S1 S2) @
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm S1
H2 : is_tm S2
============================
is_tm (app S1 S2)
< search.
Subgoal 6:
Variables: X R I
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsT : is_tm (num I)
IsX : is_string X
IsR : is_tm R
S : subst X R (num I) (num I) @
============================
is_tm (num I)
< search.
Subgoal 7:
Variables: X R S2 S1 T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsT : is_tm (plus T1 T2)
IsX : is_string X
IsR : is_tm R
S : subst X R (plus T1 T2) (plus S1 S2) @
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
============================
is_tm (plus S1 S2)
< Is: case IsT.
Subgoal 7:
Variables: X R S2 S1 T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (plus T1 T2) (plus S1 S2) @
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (plus S1 S2)
< apply IH to _ _ _ S1.
Subgoal 7:
Variables: X R S2 S1 T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (plus T1 T2) (plus S1 S2) @
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm S1
============================
is_tm (plus S1 S2)
< apply IH to _ _ _ S2.
Subgoal 7:
Variables: X R S2 S1 T2 T1
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
IsX : is_string X
IsR : is_tm R
S : subst X R (plus T1 T2) (plus S1 S2) @
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm S1
H2 : is_tm S2
============================
is_tm (plus S1 S2)
< search.
Proof completed.
< Extensible_Theorem
eval_is : forall T T',
IsT : is_tm T ->
Ev : eval T T' ->
is_tm T'
on Ev.
Subgoal 1:
Variables: T2 T11 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (app T1 T2)
Ev : eval (app T1 T2) (app T11 T2) @
Ev1 : eval T1 T11 *
============================
is_tm (app T11 T2)
< Is: case IsT.
Subgoal 1:
Variables: T2 T11 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (app T1 T2) (app T11 T2) @
Ev1 : eval T1 T11 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (app T11 T2)
< apply IH to _ Ev1.
Subgoal 1:
Variables: T2 T11 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (app T1 T2) (app T11 T2) @
Ev1 : eval T1 T11 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm T11
============================
is_tm (app T11 T2)
< search.
Subgoal 2:
Variables: T21 T1 T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (app T1 T2)
Ev : eval (app T1 T2) (app T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
============================
is_tm (app T1 T21)
< Is: case IsT.
Subgoal 2:
Variables: T21 T1 T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (app T1 T2) (app T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (app T1 T21)
< apply IH to _ Ev2.
Subgoal 2:
Variables: T21 T1 T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (app T1 T2) (app T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm T21
============================
is_tm (app T1 T21)
< search.
Subgoal 3:
Variables: T' T2 Body Ty X
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (app (abs X Ty Body) T2)
Ev : eval (app (abs X Ty Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
============================
is_tm T'
< Is: case IsT.
Subgoal 3:
Variables: T' T2 Body Ty X
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (app (abs X Ty Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
Is : is_tm (abs X Ty Body)
Is1 : is_tm T2
============================
is_tm T'
< case Is.
Subgoal 3:
Variables: T' T2 Body Ty X
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (app (abs X Ty Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
Is1 : is_tm T2
H1 : is_string X
H2 : is_ty Ty
H3 : is_tm Body
============================
is_tm T'
< apply subst_is to _ _ _ Ev2.
Subgoal 3:
Variables: T' T2 Body Ty X
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (app (abs X Ty Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
Is1 : is_tm T2
H1 : is_string X
H2 : is_ty Ty
H3 : is_tm Body
H4 : is_tm T'
============================
is_tm T'
< search.
Subgoal 4:
Variables: T2 T11 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (plus T1 T2)
Ev : eval (plus T1 T2) (plus T11 T2) @
Ev1 : eval T1 T11 *
============================
is_tm (plus T11 T2)
< Is: case IsT.
Subgoal 4:
Variables: T2 T11 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (plus T1 T2) (plus T11 T2) @
Ev1 : eval T1 T11 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (plus T11 T2)
< apply IH to _ Ev1.
Subgoal 4:
Variables: T2 T11 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (plus T1 T2) (plus T11 T2) @
Ev1 : eval T1 T11 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm T11
============================
is_tm (plus T11 T2)
< search.
Subgoal 5:
Variables: T21 T1 T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (plus T1 T2)
Ev : eval (plus T1 T2) (plus T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
============================
is_tm (plus T1 T21)
< Is: case IsT.
Subgoal 5:
Variables: T21 T1 T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (plus T1 T2) (plus T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (plus T1 T21)
< apply IH to _ Ev2.
Subgoal 5:
Variables: T21 T1 T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (plus T1 T2) (plus T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Is : is_tm T1
Is1 : is_tm T2
H1 : is_tm T21
============================
is_tm (plus T1 T21)
< search.
Subgoal 6:
Variables: I I2 I1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm (plus (num I1) (num I2))
Ev : eval (plus (num I1) (num I2)) (num I) @
Ev1 : I1 + I2 = I
============================
is_tm (num I)
< Is: case IsT.
Subgoal 6:
Variables: I I2 I1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (plus (num I1) (num I2)) (num I) @
Ev1 : I1 + I2 = I
Is : is_tm (num I1)
Is1 : is_tm (num I2)
============================
is_tm (num I)
< case Is.
Subgoal 6:
Variables: I I2 I1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (plus (num I1) (num I2)) (num I) @
Ev1 : I1 + I2 = I
Is1 : is_tm (num I2)
H1 : is_integer I1
============================
is_tm (num I)
< case Is1.
Subgoal 6:
Variables: I I2 I1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (plus (num I1) (num I2)) (num I) @
Ev1 : I1 + I2 = I
H1 : is_integer I1
H2 : is_integer I2
============================
is_tm (num I)
< apply plus_integer_is_integer to _ _ Ev1.
Subgoal 6:
Variables: I I2 I1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : eval (plus (num I1) (num I2)) (num I) @
Ev1 : I1 + I2 = I
H1 : is_integer I1
H2 : is_integer I2
H3 : is_integer I
============================
is_tm (num I)
< search.
Proof completed.
< Extensible_Theorem
subst_unique : forall X R T VA VB,
SA : subst X R T VA ->
SB : subst X R T VB ->
VA = VB
on SA.
Subgoal 1:
Variables: X R VB Y
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (var Y) (var Y) @
SB : subst X R (var Y) VB
SA1 : X = Y -> false
============================
var Y = VB
< SB: case SB.
Subgoal 1.1:
Variables: X R Y
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (var Y) (var Y) @
SA1 : X = Y -> false
SB : X = Y -> false
============================
var Y = var Y
< search.
Subgoal 1.2:
Variables: VB Y
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst Y VB (var Y) (var Y) @
SA1 : Y = Y -> false
============================
var Y = VB
< apply SA1 to _.
Subgoal 2:
Variables: X VA VB
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X VA (var X) VA @
SB : subst X VA (var X) VB
============================
VA = VB
< SB: case SB.
Subgoal 2.1:
Variables: X VA
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X VA (var X) VA @
SB : X = X -> false
============================
VA = var X
< apply SB to _.
Subgoal 2.2:
Variables: X VB
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X VB (var X) VB @
============================
VB = VB
< search.
Subgoal 3:
Variables: X R VB S Ty Y B
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (abs Y Ty B) (abs Y Ty S) @
SB : subst X R (abs Y Ty B) VB
SA1 : X = Y -> false
SA2 : subst X R B S *
============================
abs Y Ty S = VB
< SB: case SB.
Subgoal 3.1:
Variables: X R S Ty Y B S1
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (abs Y Ty B) (abs Y Ty S) @
SA1 : X = Y -> false
SA2 : subst X R B S *
SB : X = Y -> false
SB1 : subst X R B S1
============================
abs Y Ty S = abs Y Ty S1
< apply IH to SA2 SB1.
Subgoal 3.1:
Variables: X R Ty Y B S1
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (abs Y Ty B) (abs Y Ty S1) @
SA1 : X = Y -> false
SA2 : subst X R B S1 *
SB : X = Y -> false
SB1 : subst X R B S1
============================
abs Y Ty S1 = abs Y Ty S1
< search.
Subgoal 3.2:
Variables: R S Ty Y B
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst Y R (abs Y Ty B) (abs Y Ty S) @
SA1 : Y = Y -> false
SA2 : subst Y R B S *
============================
abs Y Ty S = abs Y Ty B
< apply SA1 to _.
Subgoal 4:
Variables: X R VB B Ty
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (abs X Ty B) (abs X Ty B) @
SB : subst X R (abs X Ty B) VB
============================
abs X Ty B = VB
< SB: case SB.
Subgoal 4.1:
Variables: X R B Ty S
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (abs X Ty B) (abs X Ty B) @
SB : X = X -> false
SB1 : subst X R B S
============================
abs X Ty B = abs X Ty S
< apply SB to _.
Subgoal 4.2:
Variables: X R B Ty
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (abs X Ty B) (abs X Ty B) @
============================
abs X Ty B = abs X Ty B
< search.
Subgoal 5:
Variables: X R VB S2 S1 T2 T1
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (app T1 T2) (app S1 S2) @
SB : subst X R (app T1 T2) VB
SA1 : subst X R T1 S1 *
SA2 : subst X R T2 S2 *
============================
app S1 S2 = VB
< SB: case SB.
Subgoal 5:
Variables: X R S2 S1 T2 T1 S4 S3
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (app T1 T2) (app S1 S2) @
SA1 : subst X R T1 S1 *
SA2 : subst X R T2 S2 *
SB : subst X R T1 S3
SB1 : subst X R T2 S4
============================
app S1 S2 = app S3 S4
< apply IH to SA1 SB.
Subgoal 5:
Variables: X R S2 T2 T1 S4 S3
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (app T1 T2) (app S3 S2) @
SA1 : subst X R T1 S3 *
SA2 : subst X R T2 S2 *
SB : subst X R T1 S3
SB1 : subst X R T2 S4
============================
app S3 S2 = app S3 S4
< apply IH to SA2 SB1.
Subgoal 5:
Variables: X R T2 T1 S4 S3
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (app T1 T2) (app S3 S4) @
SA1 : subst X R T1 S3 *
SA2 : subst X R T2 S4 *
SB : subst X R T1 S3
SB1 : subst X R T2 S4
============================
app S3 S4 = app S3 S4
< search.
Subgoal 6:
Variables: X R VB I
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (num I) (num I) @
SB : subst X R (num I) VB
============================
num I = VB
< SB: case SB.
Subgoal 6:
Variables: X R I
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (num I) (num I) @
============================
num I = num I
< search.
Subgoal 7:
Variables: X R VB S2 S1 T2 T1
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (plus T1 T2) (plus S1 S2) @
SB : subst X R (plus T1 T2) VB
SA1 : subst X R T1 S1 *
SA2 : subst X R T2 S2 *
============================
plus S1 S2 = VB
< SB: case SB.
Subgoal 7:
Variables: X R S2 S1 T2 T1 S4 S3
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (plus T1 T2) (plus S1 S2) @
SA1 : subst X R T1 S1 *
SA2 : subst X R T2 S2 *
SB : subst X R T1 S3
SB1 : subst X R T2 S4
============================
plus S1 S2 = plus S3 S4
< apply IH to SA1 SB.
Subgoal 7:
Variables: X R S2 T2 T1 S4 S3
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (plus T1 T2) (plus S3 S2) @
SA1 : subst X R T1 S3 *
SA2 : subst X R T2 S2 *
SB : subst X R T1 S3
SB1 : subst X R T2 S4
============================
plus S3 S2 = plus S3 S4
< apply IH to SA2 SB1.
Subgoal 7:
Variables: X R T2 T1 S4 S3
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R (plus T1 T2) (plus S3 S4) @
SA1 : subst X R T1 S3 *
SA2 : subst X R T2 S4 *
SB : subst X R T1 S3
SB1 : subst X R T2 S4
============================
plus S3 S4 = plus S3 S4
< search.
Proof completed.
< Extensible_Theorem
value_eval_false : forall T V,
Val : value T ->
Ev : eval T V ->
false
on Val.
Subgoal 1:
Variables: V T1 Ty X
IH : forall T V, value T * -> eval T V -> false
Val : value (abs X Ty T1) @
Ev : eval (abs X Ty T1) V
============================
false
< case Ev.
Subgoal 2:
Variables: V I
IH : forall T V, value T * -> eval T V -> false
Val : value (num I) @
Ev : eval (num I) V
============================
false
< case Ev.
Proof completed.
< Extensible_Theorem
eval_unique : forall T VA VB,
EvA : eval T VA ->
EvB : eval T VB ->
VA = VB
on EvA.
Subgoal 1:
Variables: VB T2 T11 T1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app T1 T2) (app T11 T2) @
EvB : eval (app T1 T2) VB
EvA1 : eval T1 T11 *
============================
app T11 T2 = VB
< EvB: case EvB.
Subgoal 1.1:
Variables: T2 T11 T1 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app T1 T2) (app T11 T2) @
EvA1 : eval T1 T11 *
EvB : eval T1 T5
============================
app T11 T2 = app T5 T2
< apply IH to EvA1 EvB.
Subgoal 1.1:
Variables: T2 T1 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app T1 T2) (app T5 T2) @
EvA1 : eval T1 T5 *
EvB : eval T1 T5
============================
app T5 T2 = app T5 T2
< search.
Subgoal 1.2:
Variables: T2 T11 T1 T21
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app T1 T2) (app T11 T2) @
EvA1 : eval T1 T11 *
EvB : value T1
EvB1 : eval T2 T21
============================
app T11 T2 = app T1 T21
< apply value_eval_false to EvB EvA1.
Subgoal 1.3:
Variables: VB T2 T11 Body Ty X
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app (abs X Ty Body) T2) (app T11 T2) @
EvA1 : eval (abs X Ty Body) T11 *
EvB : value T2
EvB1 : subst X T2 Body VB
============================
app T11 T2 = VB
< apply value_eval_false to _ EvA1.
Subgoal 2:
Variables: VB T21 T1 T2
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app T1 T2) (app T1 T21) @
EvB : eval (app T1 T2) VB
EvA1 : value T1
EvA2 : eval T2 T21 *
============================
app T1 T21 = VB
< EvB: case EvB.
Subgoal 2.1:
Variables: T21 T1 T2 T11
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app T1 T2) (app T1 T21) @
EvA1 : value T1
EvA2 : eval T2 T21 *
EvB : eval T1 T11
============================
app T1 T21 = app T11 T2
< apply value_eval_false to EvA1 EvB.
Subgoal 2.2:
Variables: T21 T1 T2 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app T1 T2) (app T1 T21) @
EvA1 : value T1
EvA2 : eval T2 T21 *
EvB : value T1
EvB1 : eval T2 T5
============================
app T1 T21 = app T1 T5
< apply IH to EvA2 EvB1.
Subgoal 2.2:
Variables: T1 T2 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app T1 T2) (app T1 T5) @
EvA1 : value T1
EvA2 : eval T2 T5 *
EvB : value T1
EvB1 : eval T2 T5
============================
app T1 T5 = app T1 T5
< search.
Subgoal 2.3:
Variables: VB T21 T2 Body Ty X
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app (abs X Ty Body) T2) (app (abs X Ty Body) T21) @
EvA1 : value (abs X Ty Body)
EvA2 : eval T2 T21 *
EvB : value T2
EvB1 : subst X T2 Body VB
============================
app (abs X Ty Body) T21 = VB
< apply value_eval_false to EvB EvA2.
Subgoal 3:
Variables: VA VB T2 Body Ty X
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app (abs X Ty Body) T2) VA @
EvB : eval (app (abs X Ty Body) T2) VB
EvA1 : value T2
EvA2 : subst X T2 Body VA
============================
VA = VB
< EvB: case EvB.
Subgoal 3.1:
Variables: VA T2 Body Ty X T11
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app (abs X Ty Body) T2) VA @
EvA1 : value T2
EvA2 : subst X T2 Body VA
EvB : eval (abs X Ty Body) T11
============================
VA = app T11 T2
< case EvB.
Subgoal 3.2:
Variables: VA T2 Body Ty X T21
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app (abs X Ty Body) T2) VA @
EvA1 : value T2
EvA2 : subst X T2 Body VA
EvB : value (abs X Ty Body)
EvB1 : eval T2 T21
============================
VA = app (abs X Ty Body) T21
< apply value_eval_false to EvA1 EvB1.
Subgoal 3.3:
Variables: VA VB T2 Body Ty X
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app (abs X Ty Body) T2) VA @
EvA1 : value T2
EvA2 : subst X T2 Body VA
EvB : value T2
EvB1 : subst X T2 Body VB
============================
VA = VB
< apply subst_unique to EvA2 EvB1.
Subgoal 3.3:
Variables: VB T2 Body Ty X
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (app (abs X Ty Body) T2) VB @
EvA1 : value T2
EvA2 : subst X T2 Body VB
EvB : value T2
EvB1 : subst X T2 Body VB
============================
VB = VB
< search.
Subgoal 4:
Variables: VB T2 T11 T1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus T1 T2) (plus T11 T2) @
EvB : eval (plus T1 T2) VB
EvA1 : eval T1 T11 *
============================
plus T11 T2 = VB
< EvB: case EvB.
Subgoal 4.1:
Variables: T2 T11 T1 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus T1 T2) (plus T11 T2) @
EvA1 : eval T1 T11 *
EvB : eval T1 T5
============================
plus T11 T2 = plus T5 T2
< apply IH to EvA1 EvB.
Subgoal 4.1:
Variables: T2 T1 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus T1 T2) (plus T5 T2) @
EvA1 : eval T1 T5 *
EvB : eval T1 T5
============================
plus T5 T2 = plus T5 T2
< search.
Subgoal 4.2:
Variables: T2 T11 T1 T21
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus T1 T2) (plus T11 T2) @
EvA1 : eval T1 T11 *
EvB : value T1
EvB1 : eval T2 T21
============================
plus T11 T2 = plus T1 T21
< apply value_eval_false to EvB EvA1.
Subgoal 4.3:
Variables: T11 I I2 I1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus (num I1) (num I2)) (plus T11 (num I2)) @
EvA1 : eval (num I1) T11 *
EvB : I1 + I2 = I
============================
plus T11 (num I2) = num I
< case EvA1.
Subgoal 5:
Variables: VB T21 T1 T2
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus T1 T2) (plus T1 T21) @
EvB : eval (plus T1 T2) VB
EvA1 : value T1
EvA2 : eval T2 T21 *
============================
plus T1 T21 = VB
< EvB: case EvB.
Subgoal 5.1:
Variables: T21 T1 T2 T11
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus T1 T2) (plus T1 T21) @
EvA1 : value T1
EvA2 : eval T2 T21 *
EvB : eval T1 T11
============================
plus T1 T21 = plus T11 T2
< apply value_eval_false to EvA1 EvB.
Subgoal 5.2:
Variables: T21 T1 T2 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus T1 T2) (plus T1 T21) @
EvA1 : value T1
EvA2 : eval T2 T21 *
EvB : value T1
EvB1 : eval T2 T5
============================
plus T1 T21 = plus T1 T5
< apply IH to EvA2 EvB1.
Subgoal 5.2:
Variables: T1 T2 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus T1 T2) (plus T1 T5) @
EvA1 : value T1
EvA2 : eval T2 T5 *
EvB : value T1
EvB1 : eval T2 T5
============================
plus T1 T5 = plus T1 T5
< search.
Subgoal 5.3:
Variables: T21 I I2 I1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus (num I1) (num I2)) (plus (num I1) T21) @
EvA1 : value (num I1)
EvA2 : eval (num I2) T21 *
EvB : I1 + I2 = I
============================
plus (num I1) T21 = num I
< case EvA2.
Subgoal 6:
Variables: VB I I2 I1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus (num I1) (num I2)) (num I) @
EvB : eval (plus (num I1) (num I2)) VB
EvA1 : I1 + I2 = I
============================
num I = VB
< EvB: case EvB.
Subgoal 6.1:
Variables: I I2 I1 T11
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus (num I1) (num I2)) (num I) @
EvA1 : I1 + I2 = I
EvB : eval (num I1) T11
============================
num I = plus T11 (num I2)
< case EvB.
Subgoal 6.2:
Variables: I I2 I1 T21
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus (num I1) (num I2)) (num I) @
EvA1 : I1 + I2 = I
EvB : value (num I1)
EvB1 : eval (num I2) T21
============================
num I = plus (num I1) T21
< case EvB1.
Subgoal 6.3:
Variables: I I2 I1 I5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus (num I1) (num I2)) (num I) @
EvA1 : I1 + I2 = I
EvB : I1 + I2 = I5
============================
num I = num I5
< apply plus_integer_unique to EvA1 EvB.
Subgoal 6.3:
Variables: I2 I1 I5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (plus (num I1) (num I2)) (num I5) @
EvA1 : I1 + I2 = I5
EvB : I1 + I2 = I5
============================
num I5 = num I5
< search.
Proof completed.
< Extensible_Theorem
ty_lookup : forall Ctx1 Ctx2 T Ty,
Ty : typeOf Ctx1 T Ty ->
L : (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) ->
typeOf Ctx2 T Ty
on Ty.
Subgoal 1:
Variables: Ctx1 Ctx2 Ty X
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (var X) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : lookup Ctx1 X Ty
============================
typeOf Ctx2 (var X) Ty
< apply L to Ty1.
Subgoal 1:
Variables: Ctx1 Ctx2 Ty X
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (var X) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : lookup Ctx1 X Ty
H1 : lookup Ctx2 X Ty
============================
typeOf Ctx2 (var X) Ty
< search.
Subgoal 2:
Variables: Ctx1 Ctx2 Ty2 Ty1 Body X
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf ((X, Ty1)::Ctx1) Body Ty2 *
============================
typeOf Ctx2 (abs X Ty1 Body) (arrowTy Ty1 Ty2)
< apply IH to Ty1 _ with
Ctx2 = (X, Ty1)::Ctx2.
Subgoal 2.1:
Variables: Ctx1 Ctx2 Ty2 Ty1 Body X
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf ((X, Ty1)::Ctx1) Body Ty2 *
============================
forall X1 XTy, lookup ((X, Ty1)::Ctx1) X1 XTy -> lookup ((X, Ty1)::Ctx2) X1 XTy
< intros LkpX.
Subgoal 2.1:
Variables: Ctx1 Ctx2 Ty2 Ty1 Body X X1 XTy
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf ((X, Ty1)::Ctx1) Body Ty2 *
LkpX : lookup ((X, Ty1)::Ctx1) X1 XTy
============================
lookup ((X, Ty1)::Ctx2) X1 XTy
< LkpX: case LkpX.
Subgoal 2.1.1:
Variables: Ctx1 Ctx2 Ty2 Body X1 XTy
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (abs X1 XTy Body) (arrowTy XTy Ty2) @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf ((X1, XTy)::Ctx1) Body Ty2 *
============================
lookup ((X1, XTy)::Ctx2) X1 XTy
< search.
Subgoal 2.1.2:
Variables: Ctx1 Ctx2 Ty2 Ty1 Body X X1 XTy
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf ((X, Ty1)::Ctx1) Body Ty2 *
LkpX : X = X1 -> false
LkpX1 : lookup Ctx1 X1 XTy
============================
lookup ((X, Ty1)::Ctx2) X1 XTy
< apply L to LkpX1.
Subgoal 2.1.2:
Variables: Ctx1 Ctx2 Ty2 Ty1 Body X X1 XTy
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf ((X, Ty1)::Ctx1) Body Ty2 *
LkpX : X = X1 -> false
LkpX1 : lookup Ctx1 X1 XTy
H1 : lookup Ctx2 X1 XTy
============================
lookup ((X, Ty1)::Ctx2) X1 XTy
< search.
Subgoal 2:
Variables: Ctx1 Ctx2 Ty2 Ty1 Body X
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf ((X, Ty1)::Ctx1) Body Ty2 *
H1 : typeOf ((X, Ty1)::Ctx2) Body Ty2
============================
typeOf Ctx2 (abs X Ty1 Body) (arrowTy Ty1 Ty2)
< search.
Subgoal 3:
Variables: Ctx1 Ctx2 Ty Ty1 T2 T1
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (app T1 T2) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx1 T2 Ty1 *
============================
typeOf Ctx2 (app T1 T2) Ty
< apply IH to Ty1 L.
Subgoal 3:
Variables: Ctx1 Ctx2 Ty Ty1 T2 T1
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (app T1 T2) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx1 T2 Ty1 *
H1 : typeOf Ctx2 T1 (arrowTy Ty1 Ty)
============================
typeOf Ctx2 (app T1 T2) Ty
< apply IH to Ty2 L.
Subgoal 3:
Variables: Ctx1 Ctx2 Ty Ty1 T2 T1
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (app T1 T2) Ty @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx1 T2 Ty1 *
H1 : typeOf Ctx2 T1 (arrowTy Ty1 Ty)
H2 : typeOf Ctx2 T2 Ty1
============================
typeOf Ctx2 (app T1 T2) Ty
< search.
Subgoal 4:
Variables: Ctx1 Ctx2 I
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (num I) intTy @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
============================
typeOf Ctx2 (num I) intTy
< search.
Subgoal 5:
Variables: Ctx1 Ctx2 T2 T1
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (plus T1 T2) intTy @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 intTy *
Ty2 : typeOf Ctx1 T2 intTy *
============================
typeOf Ctx2 (plus T1 T2) intTy
< apply IH to Ty1 L.
Subgoal 5:
Variables: Ctx1 Ctx2 T2 T1
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (plus T1 T2) intTy @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 intTy *
Ty2 : typeOf Ctx1 T2 intTy *
H1 : typeOf Ctx2 T1 intTy
============================
typeOf Ctx2 (plus T1 T2) intTy
< apply IH to Ty2 L.
Subgoal 5:
Variables: Ctx1 Ctx2 T2 T1
IH : forall Ctx1 Ctx2 T Ty,
typeOf Ctx1 T Ty * -> (forall X XTy,
lookup Ctx1 X XTy -> lookup Ctx2 X XTy) -> typeOf Ctx2 T Ty
Ty : typeOf Ctx1 (plus T1 T2) intTy @
L : forall X XTy, lookup Ctx1 X XTy -> lookup Ctx2 X XTy
Ty1 : typeOf Ctx1 T1 intTy *
Ty2 : typeOf Ctx1 T2 intTy *
H1 : typeOf Ctx2 T1 intTy
H2 : typeOf Ctx2 T2 intTy
============================
typeOf Ctx2 (plus T1 T2) intTy
< search.
Proof completed.
< Theorem empty_ty_any :
forall T Ty Ctx, typeOf [] T Ty -> typeOf Ctx T Ty.
============================
forall T Ty Ctx, typeOf [] T Ty -> typeOf Ctx T Ty
< intros T.
Variables: T Ty Ctx
T : typeOf [] T Ty
============================
typeOf Ctx T Ty
< backchain ty_lookup.
Variables: T Ty Ctx
T : typeOf [] T Ty
============================
forall X XTy, lookup [] X XTy -> lookup Ctx X XTy
< intros L.
Variables: T Ty Ctx X XTy
T : typeOf [] T Ty
L : lookup [] X XTy
============================
lookup Ctx X XTy
< case L.
Proof completed.
< Extensible_Theorem
subst_type_preservation : forall T Ctx X XTy Ty R S,
TTy : typeOf ((X, XTy)::Ctx) T Ty ->
S : subst X R T S ->
RTy : typeOf [] R XTy ->
typeOf Ctx S Ty
on S.
Subgoal 1:
Variables: Ctx X XTy Ty R Y
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (var Y) Ty
S : subst X R (var Y) (var Y) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
============================
typeOf Ctx (var Y) Ty
< Ty: case TTy.
Subgoal 1:
Variables: Ctx X XTy Ty R Y
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (var Y) (var Y) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
Ty : lookup ((X, XTy)::Ctx) Y Ty
============================
typeOf Ctx (var Y) Ty
< Lkp: case Ty.
Subgoal 1.1:
Variables: Ctx Ty R Y
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst Y R (var Y) (var Y) @
RTy : typeOf [] R Ty
S1 : Y = Y -> false
============================
typeOf Ctx (var Y) Ty
< apply S1 to _.
Subgoal 1.2:
Variables: Ctx X XTy Ty R Y
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (var Y) (var Y) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
Lkp : X = Y -> false
Lkp1 : lookup Ctx Y Ty
============================
typeOf Ctx (var Y) Ty
< search.
Subgoal 2:
Variables: Ctx X XTy Ty S
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (var X) Ty
S : subst X S (var X) S @
RTy : typeOf [] S XTy
============================
typeOf Ctx S Ty
< Ty: case TTy.
Subgoal 2:
Variables: Ctx X XTy Ty S
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X S (var X) S @
RTy : typeOf [] S XTy
Ty : lookup ((X, XTy)::Ctx) X Ty
============================
typeOf Ctx S Ty
< L: case Ty.
Subgoal 2.1:
Variables: Ctx X Ty S
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X S (var X) S @
RTy : typeOf [] S Ty
============================
typeOf Ctx S Ty
< backchain empty_ty_any.
Subgoal 2.2:
Variables: Ctx X XTy Ty S
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X S (var X) S @
RTy : typeOf [] S XTy
L : X = X -> false
L1 : lookup Ctx X Ty
============================
typeOf Ctx S Ty
< apply L to _.
Subgoal 3:
Variables: Ctx X XTy Ty R S1 Ty1 Y B
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (abs Y Ty1 B) Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
============================
typeOf Ctx (abs Y Ty1 S1) Ty
< Ty: case TTy.
Subgoal 3:
Variables: Ctx X XTy R S1 Ty1 Y B Ty3
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
============================
typeOf Ctx (abs Y Ty1 S1) (arrowTy Ty1 Ty3)
< Ty': apply ty_lookup to Ty _ with
Ctx2 = (X, XTy)::((Y, Ty1)::Ctx).
Subgoal 3.1:
Variables: Ctx X XTy R S1 Ty1 Y B Ty3
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
============================
forall X1 XTy1,
lookup ((Y, Ty1)::((X, XTy)::Ctx)) X1 XTy1 -> lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1
< intros L.
Subgoal 3.1:
Variables: Ctx X XTy R S1 Ty1 Y B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
L : lookup ((Y, Ty1)::((X, XTy)::Ctx)) X1 XTy1
============================
lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1
< L: case L.
Subgoal 3.1.1:
Variables: Ctx X XTy R S1 B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X1 XTy1 B) (abs X1 XTy1 S1) @
RTy : typeOf [] R XTy
S1 : X = X1 -> false
S2 : subst X R B S1 *
Ty : typeOf ((X1, XTy1)::((X, XTy)::Ctx)) B Ty3
============================
lookup ((X, XTy)::((X1, XTy1)::Ctx)) X1 XTy1
< search.
Subgoal 3.1.2:
Variables: Ctx X XTy R S1 Ty1 Y B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
L : Y = X1 -> false
L1 : lookup ((X, XTy)::Ctx) X1 XTy1
============================
lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1
< L: case L1.
Subgoal 3.1.2.1:
Variables: Ctx R S1 Ty1 Y B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X1 R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy1
S1 : X1 = Y -> false
S2 : subst X1 R B S1 *
Ty : typeOf ((Y, Ty1)::((X1, XTy1)::Ctx)) B Ty3
L : Y = X1 -> false
============================
lookup ((X1, XTy1)::((Y, Ty1)::Ctx)) X1 XTy1
< search.
Subgoal 3.1.2.2:
Variables: Ctx X XTy R S1 Ty1 Y B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
L : Y = X1 -> false
L1 : X = X1 -> false
L2 : lookup Ctx X1 XTy1
============================
lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1
< search.
Subgoal 3:
Variables: Ctx X XTy R S1 Ty1 Y B Ty3
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
Ty' : typeOf ((X, XTy)::((Y, Ty1)::Ctx)) B Ty3
============================
typeOf Ctx (abs Y Ty1 S1) (arrowTy Ty1 Ty3)
< apply IH to Ty' S2 _.
Subgoal 3:
Variables: Ctx X XTy R S1 Ty1 Y B Ty3
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
Ty' : typeOf ((X, XTy)::((Y, Ty1)::Ctx)) B Ty3
H1 : typeOf ((Y, Ty1)::Ctx) S1 Ty3
============================
typeOf Ctx (abs Y Ty1 S1) (arrowTy Ty1 Ty3)
< search.
Subgoal 4:
Variables: Ctx X XTy Ty R B Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (abs X Ty1 B) Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
============================
typeOf Ctx (abs X Ty1 B) Ty
< Ty: case TTy.
Subgoal 4:
Variables: Ctx X XTy R B Ty1 Ty3
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
============================
typeOf Ctx (abs X Ty1 B) (arrowTy Ty1 Ty3)
< apply ty_lookup to Ty _ with
Ctx2 = (X, Ty1)::Ctx.
Subgoal 4.1:
Variables: Ctx X XTy R B Ty1 Ty3
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
============================
forall X1 XTy1,
lookup ((X, Ty1)::((X, XTy)::Ctx)) X1 XTy1 -> lookup ((X, Ty1)::Ctx) X1 XTy1
< intros L.
Subgoal 4.1:
Variables: Ctx X XTy R B Ty1 Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
L : lookup ((X, Ty1)::((X, XTy)::Ctx)) X1 XTy1
============================
lookup ((X, Ty1)::Ctx) X1 XTy1
< L: case L.
Subgoal 4.1.1:
Variables: Ctx XTy R B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X1 R (abs X1 XTy1 B) (abs X1 XTy1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X1, XTy1)::((X1, XTy)::Ctx)) B Ty3
============================
lookup ((X1, XTy1)::Ctx) X1 XTy1
< search.
Subgoal 4.1.2:
Variables: Ctx X XTy R B Ty1 Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
L : X = X1 -> false
L1 : lookup ((X, XTy)::Ctx) X1 XTy1
============================
lookup ((X, Ty1)::Ctx) X1 XTy1
< L: case L1.
Subgoal 4.1.2.1:
Variables: Ctx R B Ty1 Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X1 R (abs X1 Ty1 B) (abs X1 Ty1 B) @
RTy : typeOf [] R XTy1
Ty : typeOf ((X1, Ty1)::((X1, XTy1)::Ctx)) B Ty3
L : X1 = X1 -> false
============================
lookup ((X1, Ty1)::Ctx) X1 XTy1
< apply L to _.
Subgoal 4.1.2.2:
Variables: Ctx X XTy R B Ty1 Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
L : X = X1 -> false
L1 : X = X1 -> false
L2 : lookup Ctx X1 XTy1
============================
lookup ((X, Ty1)::Ctx) X1 XTy1
< search.
Subgoal 4:
Variables: Ctx X XTy R B Ty1 Ty3
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
H1 : typeOf ((X, Ty1)::Ctx) B Ty3
============================
typeOf Ctx (abs X Ty1 B) (arrowTy Ty1 Ty3)
< search.
Subgoal 5:
Variables: Ctx X XTy Ty R S2 S1 T2 T1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (app T1 T2) Ty
S : subst X R (app T1 T2) (app S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
============================
typeOf Ctx (app S1 S2) Ty
< Ty: case TTy.
Subgoal 5:
Variables: Ctx X XTy Ty R S2 S1 T2 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (app T1 T2) (app S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 (arrowTy Ty1 Ty)
Ty1 : typeOf ((X, XTy)::Ctx) T2 Ty1
============================
typeOf Ctx (app S1 S2) Ty
< apply IH to Ty S1 _.
Subgoal 5:
Variables: Ctx X XTy Ty R S2 S1 T2 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (app T1 T2) (app S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 (arrowTy Ty1 Ty)
Ty1 : typeOf ((X, XTy)::Ctx) T2 Ty1
H1 : typeOf Ctx S1 (arrowTy Ty1 Ty)
============================
typeOf Ctx (app S1 S2) Ty
< apply IH to Ty1 S2 _.
Subgoal 5:
Variables: Ctx X XTy Ty R S2 S1 T2 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (app T1 T2) (app S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 (arrowTy Ty1 Ty)
Ty1 : typeOf ((X, XTy)::Ctx) T2 Ty1
H1 : typeOf Ctx S1 (arrowTy Ty1 Ty)
H2 : typeOf Ctx S2 Ty1
============================
typeOf Ctx (app S1 S2) Ty
< search.
Subgoal 6:
Variables: Ctx X XTy Ty R I
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (num I) Ty
S : subst X R (num I) (num I) @
RTy : typeOf [] R XTy
============================
typeOf Ctx (num I) Ty
< case TTy.
Subgoal 6:
Variables: Ctx X XTy R I
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (num I) (num I) @
RTy : typeOf [] R XTy
============================
typeOf Ctx (num I) intTy
< search.
Subgoal 7:
Variables: Ctx X XTy Ty R S2 S1 T2 T1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (plus T1 T2) Ty
S : subst X R (plus T1 T2) (plus S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
============================
typeOf Ctx (plus S1 S2) Ty
< Ty: case TTy.
Subgoal 7:
Variables: Ctx X XTy R S2 S1 T2 T1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (plus T1 T2) (plus S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 intTy
Ty1 : typeOf ((X, XTy)::Ctx) T2 intTy
============================
typeOf Ctx (plus S1 S2) intTy
< apply IH to Ty S1 _.
Subgoal 7:
Variables: Ctx X XTy R S2 S1 T2 T1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (plus T1 T2) (plus S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 intTy
Ty1 : typeOf ((X, XTy)::Ctx) T2 intTy
H1 : typeOf Ctx S1 intTy
============================
typeOf Ctx (plus S1 S2) intTy
< apply IH to Ty1 S2 _.
Subgoal 7:
Variables: Ctx X XTy R S2 S1 T2 T1
IH : forall T Ctx X XTy Ty R S,
typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (plus T1 T2) (plus S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 intTy
Ty1 : typeOf ((X, XTy)::Ctx) T2 intTy
H1 : typeOf Ctx S1 intTy
H2 : typeOf Ctx S2 intTy
============================
typeOf Ctx (plus S1 S2) intTy
< search.
Proof completed.
< Extensible_Theorem
type_preservation : forall T Ty T',
Ty : typeOf [] T Ty ->
Ev : eval T T' ->
typeOf [] T' Ty
on Ev.
Subgoal 1:
Variables: Ty T2 T11 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (app T1 T2) Ty
Ev : eval (app T1 T2) (app T11 T2) @
Ev1 : eval T1 T11 *
============================
typeOf [] (app T11 T2) Ty
< Ty: case Ty.
Subgoal 1:
Variables: Ty T2 T11 T1 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app T1 T2) (app T11 T2) @
Ev1 : eval T1 T11 *
Ty : typeOf [] T1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] T2 Ty1
============================
typeOf [] (app T11 T2) Ty
< apply IH to Ty Ev1.
Subgoal 1:
Variables: Ty T2 T11 T1 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app T1 T2) (app T11 T2) @
Ev1 : eval T1 T11 *
Ty : typeOf [] T1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] T2 Ty1
H1 : typeOf [] T11 (arrowTy Ty1 Ty)
============================
typeOf [] (app T11 T2) Ty
< search.
Subgoal 2:
Variables: Ty T21 T1 T2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (app T1 T2) Ty
Ev : eval (app T1 T2) (app T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
============================
typeOf [] (app T1 T21) Ty
< Ty: case Ty.
Subgoal 2:
Variables: Ty T21 T1 T2 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app T1 T2) (app T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Ty : typeOf [] T1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] T2 Ty1
============================
typeOf [] (app T1 T21) Ty
< apply IH to Ty1 Ev2.
Subgoal 2:
Variables: Ty T21 T1 T2 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app T1 T2) (app T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Ty : typeOf [] T1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] T2 Ty1
H1 : typeOf [] T21 Ty1
============================
typeOf [] (app T1 T21) Ty
< search.
Subgoal 3:
Variables: Ty T' T2 Body Ty1 X
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (app (abs X Ty1 Body) T2) Ty
Ev : eval (app (abs X Ty1 Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
============================
typeOf [] T' Ty
< Ty: case Ty.
Subgoal 3:
Variables: Ty T' T2 Body Ty1 X Ty2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app (abs X Ty1 Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
Ty : typeOf [] (abs X Ty1 Body) (arrowTy Ty2 Ty)
Ty1 : typeOf [] T2 Ty2
============================
typeOf [] T' Ty
< Ty: case Ty.
Subgoal 3:
Variables: Ty T' T2 Body X Ty2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app (abs X Ty2 Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
Ty1 : typeOf [] T2 Ty2
Ty : typeOf [(X, Ty2)] Body Ty
============================
typeOf [] T' Ty
< apply subst_type_preservation to Ty Ev2 Ty1.
Subgoal 3:
Variables: Ty T' T2 Body X Ty2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app (abs X Ty2 Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
Ty1 : typeOf [] T2 Ty2
Ty : typeOf [(X, Ty2)] Body Ty
H1 : typeOf [] T' Ty
============================
typeOf [] T' Ty
< search.
Subgoal 4:
Variables: Ty T2 T11 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (plus T1 T2) Ty
Ev : eval (plus T1 T2) (plus T11 T2) @
Ev1 : eval T1 T11 *
============================
typeOf [] (plus T11 T2) Ty
< Ty: case Ty.
Subgoal 4:
Variables: T2 T11 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (plus T1 T2) (plus T11 T2) @
Ev1 : eval T1 T11 *
Ty : typeOf [] T1 intTy
Ty1 : typeOf [] T2 intTy
============================
typeOf [] (plus T11 T2) intTy
< apply IH to Ty Ev1.
Subgoal 4:
Variables: T2 T11 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (plus T1 T2) (plus T11 T2) @
Ev1 : eval T1 T11 *
Ty : typeOf [] T1 intTy
Ty1 : typeOf [] T2 intTy
H1 : typeOf [] T11 intTy
============================
typeOf [] (plus T11 T2) intTy
< search.
Subgoal 5:
Variables: Ty T21 T1 T2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (plus T1 T2) Ty
Ev : eval (plus T1 T2) (plus T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
============================
typeOf [] (plus T1 T21) Ty
< Ty: case Ty.
Subgoal 5:
Variables: T21 T1 T2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (plus T1 T2) (plus T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Ty : typeOf [] T1 intTy
Ty1 : typeOf [] T2 intTy
============================
typeOf [] (plus T1 T21) intTy
< apply IH to Ty1 Ev2.
Subgoal 5:
Variables: T21 T1 T2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (plus T1 T2) (plus T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Ty : typeOf [] T1 intTy
Ty1 : typeOf [] T2 intTy
H1 : typeOf [] T21 intTy
============================
typeOf [] (plus T1 T21) intTy
< search.
Subgoal 6:
Variables: Ty I I2 I1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (plus (num I1) (num I2)) Ty
Ev : eval (plus (num I1) (num I2)) (num I) @
Ev1 : I1 + I2 = I
============================
typeOf [] (num I) Ty
< Ty: case Ty.
Subgoal 6:
Variables: I I2 I1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (plus (num I1) (num I2)) (num I) @
Ev1 : I1 + I2 = I
Ty : typeOf [] (num I1) intTy
Ty1 : typeOf [] (num I2) intTy
============================
typeOf [] (num I) intTy
< search.
Proof completed.
< Extensible_Theorem
subst_total : forall X R T,
IsT : is_tm T ->
IsX : is_string X ->
exists S,
subst X R T S
on IsT.
Subgoal 1:
Variables: X R S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (var S) @
IsX : is_string X
IsT1 : is_string S
============================
exists S1, subst X R (var S) S1
< Or: apply is_string_eq_or_not to IsX IsT1.
Subgoal 1:
Variables: X R S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (var S) @
IsX : is_string X
IsT1 : is_string S
Or : X = S \/ (X = S -> false)
============================
exists S1, subst X R (var S) S1
< E: case Or.
Subgoal 1.1:
Variables: R S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (var S) @
IsX : is_string S
IsT1 : is_string S
============================
exists S1, subst S R (var S) S1
< search.
Subgoal 1.2:
Variables: X R S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (var S) @
IsX : is_string X
IsT1 : is_string S
E : X = S -> false
============================
exists S1, subst X R (var S) S1
< search.
Subgoal 2:
Variables: X R Tm Ty S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (abs S Ty Tm) @
IsX : is_string X
IsT1 : is_string S
IsT2 : is_ty Ty
IsT3 : is_tm Tm *
============================
exists S1, subst X R (abs S Ty Tm) S1
< Or: apply is_string_eq_or_not to IsX IsT1.
Subgoal 2:
Variables: X R Tm Ty S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (abs S Ty Tm) @
IsX : is_string X
IsT1 : is_string S
IsT2 : is_ty Ty
IsT3 : is_tm Tm *
Or : X = S \/ (X = S -> false)
============================
exists S1, subst X R (abs S Ty Tm) S1
< E: case Or.
Subgoal 2.1:
Variables: R Tm Ty S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (abs S Ty Tm) @
IsX : is_string S
IsT1 : is_string S
IsT2 : is_ty Ty
IsT3 : is_tm Tm *
============================
exists S1, subst S R (abs S Ty Tm) S1
< search.
Subgoal 2.2:
Variables: X R Tm Ty S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (abs S Ty Tm) @
IsX : is_string X
IsT1 : is_string S
IsT2 : is_ty Ty
IsT3 : is_tm Tm *
E : X = S -> false
============================
exists S1, subst X R (abs S Ty Tm) S1
< apply IH to IsT3 IsX with
R = R.
Subgoal 2.2:
Variables: X R Tm Ty S S1
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (abs S Ty Tm) @
IsX : is_string X
IsT1 : is_string S
IsT2 : is_ty Ty
IsT3 : is_tm Tm *
E : X = S -> false
H1 : subst X R Tm S1
============================
exists S1, subst X R (abs S Ty Tm) S1
< search.
Subgoal 3:
Variables: X R Tm Tm1
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (app Tm1 Tm) @
IsX : is_string X
IsT1 : is_tm Tm1 *
IsT2 : is_tm Tm *
============================
exists S, subst X R (app Tm1 Tm) S
< apply IH to IsT1 IsX with
R = R.
Subgoal 3:
Variables: X R Tm Tm1 S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (app Tm1 Tm) @
IsX : is_string X
IsT1 : is_tm Tm1 *
IsT2 : is_tm Tm *
H1 : subst X R Tm1 S
============================
exists S, subst X R (app Tm1 Tm) S
< apply IH to IsT2 IsX with
R = R.
Subgoal 3:
Variables: X R Tm Tm1 S S1
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (app Tm1 Tm) @
IsX : is_string X
IsT1 : is_tm Tm1 *
IsT2 : is_tm Tm *
H1 : subst X R Tm1 S
H2 : subst X R Tm S1
============================
exists S, subst X R (app Tm1 Tm) S
< search.
Subgoal 4:
Variables: X R I
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (num I) @
IsX : is_string X
IsT1 : is_integer I
============================
exists S, subst X R (num I) S
< search.
Subgoal 5:
Variables: X R Tm Tm1
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (plus Tm1 Tm) @
IsX : is_string X
IsT1 : is_tm Tm1 *
IsT2 : is_tm Tm *
============================
exists S, subst X R (plus Tm1 Tm) S
< apply IH to IsT1 IsX with
R = R.
Subgoal 5:
Variables: X R Tm Tm1 S
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (plus Tm1 Tm) @
IsX : is_string X
IsT1 : is_tm Tm1 *
IsT2 : is_tm Tm *
H1 : subst X R Tm1 S
============================
exists S, subst X R (plus Tm1 Tm) S
< apply IH to IsT2 IsX with
R = R.
Subgoal 5:
Variables: X R Tm Tm1 S S1
IH : forall X R T, is_tm T * -> is_string X -> exists S, subst X R T S
IsT : is_tm (plus Tm1 Tm) @
IsX : is_string X
IsT1 : is_tm Tm1 *
IsT2 : is_tm Tm *
H1 : subst X R Tm1 S
H2 : subst X R Tm S1
============================
exists S, subst X R (plus Tm1 Tm) S
< search.
Proof completed.
< Extensible_Theorem
canonical_forms : forall V Ty,
V : value V ->
Ty : typeOf [] V Ty ->
canonicalForm Ty V
on V.
Subgoal 1:
Variables: Ty T Ty1 X
IH : forall V Ty, value V * -> typeOf [] V Ty -> canonicalForm Ty V
V : value (abs X Ty1 T) @
Ty : typeOf [] (abs X Ty1 T) Ty
============================
canonicalForm Ty (abs X Ty1 T)
< case Ty.
Subgoal 1:
Variables: T Ty1 X Ty3
IH : forall V Ty, value V * -> typeOf [] V Ty -> canonicalForm Ty V
V : value (abs X Ty1 T) @
H1 : typeOf [(X, Ty1)] T Ty3
============================
canonicalForm (arrowTy Ty1 Ty3) (abs X Ty1 T)
< search.
Subgoal 2:
Variables: Ty I
IH : forall V Ty, value V * -> typeOf [] V Ty -> canonicalForm Ty V
V : value (num I) @
Ty : typeOf [] (num I) Ty
============================
canonicalForm Ty (num I)
< case Ty.
Subgoal 2:
Variables: I
IH : forall V Ty, value V * -> typeOf [] V Ty -> canonicalForm Ty V
V : value (num I) @
============================
canonicalForm intTy (num I)
< search.
Proof completed.
< Theorem canonical_form_intTy :
forall V, value V -> typeOf [] V intTy -> exists I, V = num I.
============================
forall V, value V -> typeOf [] V intTy -> exists I, V = num I
< intros V Ty.
Variables: V
V : value V
Ty : typeOf [] V intTy
============================
exists I, V = num I
< CF: apply canonical_forms to V Ty.
Variables: V
V : value V
Ty : typeOf [] V intTy
CF : canonicalForm intTy V
============================
exists I, V = num I
< case CF.
Variables: I
V : value (num I)
Ty : typeOf [] (num I) intTy
============================
exists I1, num I = num I1
< search.
Proof completed.
< Theorem canonical_form_arrowTy :
forall V Ty1 Ty2,
value V -> typeOf [] V (arrowTy Ty1 Ty2) -> exists X B, V = abs X Ty1 B.
============================
forall V Ty1 Ty2,
value V -> typeOf [] V (arrowTy Ty1 Ty2) -> exists X B, V = abs X Ty1 B
< intros V Ty.
Variables: V Ty1 Ty2
V : value V
Ty : typeOf [] V (arrowTy Ty1 Ty2)
============================
exists X B, V = abs X Ty1 B
< CF: apply canonical_forms to V Ty.
Variables: V Ty1 Ty2
V : value V
Ty : typeOf [] V (arrowTy Ty1 Ty2)
CF : canonicalForm (arrowTy Ty1 Ty2) V
============================
exists X B, V = abs X Ty1 B
< case CF.
Variables: Ty1 Ty2 B X
V : value (abs X Ty1 B)
Ty : typeOf [] (abs X Ty1 B) (arrowTy Ty1 Ty2)
============================
exists X1 B1, abs X Ty1 B = abs X1 Ty1 B1
< search.
Proof completed.
< Extensible_Theorem
progress : forall T Ty,
IsT : is_tm T ->
Ty : typeOf [] T Ty ->
(exists T', eval T T') \/
value T
on Ty.
Subgoal 1:
Variables: Ty X
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
IsT : is_tm (var X)
Ty : typeOf [] (var X) Ty @
Ty1 : lookup [] X Ty
============================
(exists T', eval (var X) T') \/ value (var X)
< case Ty1.
Subgoal 2:
Variables: Ty2 Ty1 Body X
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
IsT : is_tm (abs X Ty1 Body)
Ty : typeOf [] (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
Ty1 : typeOf [(X, Ty1)] Body Ty2 *
============================
(exists T', eval (abs X Ty1 Body) T') \/ value (abs X Ty1 Body)
< search.
Subgoal 3:
Variables: Ty Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
IsT : is_tm (app T1 T2)
Ty : typeOf [] (app T1 T2) Ty @
Ty1 : typeOf [] T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] T2 Ty1 *
============================
(exists T', eval (app T1 T2) T') \/ value (app T1 T2)
< Is: case IsT.
Subgoal 3:
Variables: Ty Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (app T1 T2) Ty @
Ty1 : typeOf [] T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
============================
(exists T', eval (app T1 T2) T') \/ value (app T1 T2)
< Or1: apply IH to _ Ty1.
Subgoal 3:
Variables: Ty Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (app T1 T2) Ty @
Ty1 : typeOf [] T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
Or1 : (exists T', eval T1 T') \/ value T1
============================
(exists T', eval (app T1 T2) T') \/ value (app T1 T2)
< Or2: apply IH to _ Ty2.
Subgoal 3:
Variables: Ty Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (app T1 T2) Ty @
Ty1 : typeOf [] T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
Or1 : (exists T', eval T1 T') \/ value T1
Or2 : (exists T', eval T2 T') \/ value T2
============================
(exists T', eval (app T1 T2) T') \/ value (app T1 T2)
< EV1: case Or1.
Subgoal 3.1:
Variables: Ty Ty1 T2 T1 T'
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (app T1 T2) Ty @
Ty1 : typeOf [] T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
Or2 : (exists T', eval T2 T') \/ value T2
EV1 : eval T1 T'
============================
(exists T', eval (app T1 T2) T') \/ value (app T1 T2)
< search.
Subgoal 3.2:
Variables: Ty Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (app T1 T2) Ty @
Ty1 : typeOf [] T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
Or2 : (exists T', eval T2 T') \/ value T2
EV1 : value T1
============================
(exists T', eval (app T1 T2) T') \/ value (app T1 T2)
< EV2: case Or2.
Subgoal 3.2.1:
Variables: Ty Ty1 T2 T1 T'
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (app T1 T2) Ty @
Ty1 : typeOf [] T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
EV1 : value T1
EV2 : eval T2 T'
============================
(exists T', eval (app T1 T2) T') \/ value (app T1 T2)
< search.
Subgoal 3.2.2:
Variables: Ty Ty1 T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (app T1 T2) Ty @
Ty1 : typeOf [] T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm T1
Is1 : is_tm T2
EV1 : value T1
EV2 : value T2
============================
(exists T', eval (app T1 T2) T') \/ value (app T1 T2)
< apply canonical_form_arrowTy to _ Ty1.
Subgoal 3.2.2:
Variables: Ty Ty1 T2 X B
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (app (abs X Ty1 B) T2) Ty @
Ty1 : typeOf [] (abs X Ty1 B) (arrowTy Ty1 Ty) *
Ty2 : typeOf [] T2 Ty1 *
Is : is_tm (abs X Ty1 B)
Is1 : is_tm T2
EV1 : value (abs X Ty1 B)
EV2 : value T2
============================
(exists T', eval (app (abs X Ty1 B) T2) T') \/ value (app (abs X Ty1 B) T2)
< IsAbs: case Is.
Subgoal 3.2.2:
Variables: Ty Ty1 T2 X B
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (app (abs X Ty1 B) T2) Ty @
Ty1 : typeOf [] (abs X Ty1 B) (arrowTy Ty1 Ty) *
Ty2 : typeOf [] T2 Ty1 *
Is1 : is_tm T2
EV1 : value (abs X Ty1 B)
EV2 : value T2
IsAbs : is_string X
IsAbs1 : is_ty Ty1
IsAbs2 : is_tm B
============================
(exists T', eval (app (abs X Ty1 B) T2) T') \/ value (app (abs X Ty1 B) T2)
< apply subst_total to IsAbs2 IsAbs with
R = T2.
Subgoal 3.2.2:
Variables: Ty Ty1 T2 X B S
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (app (abs X Ty1 B) T2) Ty @
Ty1 : typeOf [] (abs X Ty1 B) (arrowTy Ty1 Ty) *
Ty2 : typeOf [] T2 Ty1 *
Is1 : is_tm T2
EV1 : value (abs X Ty1 B)
EV2 : value T2
IsAbs : is_string X
IsAbs1 : is_ty Ty1
IsAbs2 : is_tm B
H1 : subst X T2 B S
============================
(exists T', eval (app (abs X Ty1 B) T2) T') \/ value (app (abs X Ty1 B) T2)
< search.
Subgoal 4:
Variables: I
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
IsT : is_tm (num I)
Ty : typeOf [] (num I) intTy @
============================
(exists T', eval (num I) T') \/ value (num I)
< search.
Subgoal 5:
Variables: T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
IsT : is_tm (plus T1 T2)
Ty : typeOf [] (plus T1 T2) intTy @
Ty1 : typeOf [] T1 intTy *
Ty2 : typeOf [] T2 intTy *
============================
(exists T', eval (plus T1 T2) T') \/ value (plus T1 T2)
< Is: case IsT.
Subgoal 5:
Variables: T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus T1 T2) intTy @
Ty1 : typeOf [] T1 intTy *
Ty2 : typeOf [] T2 intTy *
Is : is_tm T1
Is1 : is_tm T2
============================
(exists T', eval (plus T1 T2) T') \/ value (plus T1 T2)
< Or1: apply IH to _ Ty1.
Subgoal 5:
Variables: T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus T1 T2) intTy @
Ty1 : typeOf [] T1 intTy *
Ty2 : typeOf [] T2 intTy *
Is : is_tm T1
Is1 : is_tm T2
Or1 : (exists T', eval T1 T') \/ value T1
============================
(exists T', eval (plus T1 T2) T') \/ value (plus T1 T2)
< Or2: apply IH to _ Ty2.
Subgoal 5:
Variables: T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus T1 T2) intTy @
Ty1 : typeOf [] T1 intTy *
Ty2 : typeOf [] T2 intTy *
Is : is_tm T1
Is1 : is_tm T2
Or1 : (exists T', eval T1 T') \/ value T1
Or2 : (exists T', eval T2 T') \/ value T2
============================
(exists T', eval (plus T1 T2) T') \/ value (plus T1 T2)
< EV1: case Or1.
Subgoal 5.1:
Variables: T2 T1 T'
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus T1 T2) intTy @
Ty1 : typeOf [] T1 intTy *
Ty2 : typeOf [] T2 intTy *
Is : is_tm T1
Is1 : is_tm T2
Or2 : (exists T', eval T2 T') \/ value T2
EV1 : eval T1 T'
============================
(exists T', eval (plus T1 T2) T') \/ value (plus T1 T2)
< search.
Subgoal 5.2:
Variables: T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus T1 T2) intTy @
Ty1 : typeOf [] T1 intTy *
Ty2 : typeOf [] T2 intTy *
Is : is_tm T1
Is1 : is_tm T2
Or2 : (exists T', eval T2 T') \/ value T2
EV1 : value T1
============================
(exists T', eval (plus T1 T2) T') \/ value (plus T1 T2)
< EV2: case Or2.
Subgoal 5.2.1:
Variables: T2 T1 T'
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus T1 T2) intTy @
Ty1 : typeOf [] T1 intTy *
Ty2 : typeOf [] T2 intTy *
Is : is_tm T1
Is1 : is_tm T2
EV1 : value T1
EV2 : eval T2 T'
============================
(exists T', eval (plus T1 T2) T') \/ value (plus T1 T2)
< search.
Subgoal 5.2.2:
Variables: T2 T1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus T1 T2) intTy @
Ty1 : typeOf [] T1 intTy *
Ty2 : typeOf [] T2 intTy *
Is : is_tm T1
Is1 : is_tm T2
EV1 : value T1
EV2 : value T2
============================
(exists T', eval (plus T1 T2) T') \/ value (plus T1 T2)
< apply canonical_form_intTy to _ Ty1.
Subgoal 5.2.2:
Variables: T2 I
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus (num I) T2) intTy @
Ty1 : typeOf [] (num I) intTy *
Ty2 : typeOf [] T2 intTy *
Is : is_tm (num I)
Is1 : is_tm T2
EV1 : value (num I)
EV2 : value T2
============================
(exists T', eval (plus (num I) T2) T') \/ value (plus (num I) T2)
< Is: case Is.
Subgoal 5.2.2:
Variables: T2 I
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus (num I) T2) intTy @
Ty1 : typeOf [] (num I) intTy *
Ty2 : typeOf [] T2 intTy *
Is1 : is_tm T2
EV1 : value (num I)
EV2 : value T2
Is : is_integer I
============================
(exists T', eval (plus (num I) T2) T') \/ value (plus (num I) T2)
< apply canonical_form_intTy to _ Ty2.
Subgoal 5.2.2:
Variables: I I1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus (num I) (num I1)) intTy @
Ty1 : typeOf [] (num I) intTy *
Ty2 : typeOf [] (num I1) intTy *
Is1 : is_tm (num I1)
EV1 : value (num I)
EV2 : value (num I1)
Is : is_integer I
============================
(exists T', eval (plus (num I) (num I1)) T') \/ value (plus (num I) (num I1))
< Is1: case Is1.
Subgoal 5.2.2:
Variables: I I1
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus (num I) (num I1)) intTy @
Ty1 : typeOf [] (num I) intTy *
Ty2 : typeOf [] (num I1) intTy *
EV1 : value (num I)
EV2 : value (num I1)
Is : is_integer I
Is1 : is_integer I1
============================
(exists T', eval (plus (num I) (num I1)) T') \/ value (plus (num I) (num I1))
< apply plus_integer_total to Is Is1.
Subgoal 5.2.2:
Variables: I I1 N3
IH : forall T Ty,
is_tm T -> typeOf [] T Ty * -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus (num I) (num I1)) intTy @
Ty1 : typeOf [] (num I) intTy *
Ty2 : typeOf [] (num I1) intTy *
EV1 : value (num I)
EV2 : value (num I1)
Is : is_integer I
Is1 : is_integer I1
H1 : I + I1 = N3
============================
(exists T', eval (plus (num I) (num I1)) T') \/ value (plus (num I) (num I1))
< search.
Proof completed.
