< Module soundX: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.
< 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.
< 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.
< Theorem lookup_desugar_ctx :
forall Ctx X Ty Ctx',
lookup Ctx X Ty -> desugar_ctx Ctx Ctx' -> exists Ty',
lookup Ctx' X Ty' /\ desugar_ty Ty Ty'.
============================
forall Ctx X Ty Ctx',
lookup Ctx X Ty -> desugar_ctx Ctx Ctx' -> exists Ty',
lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
< induction on 1.
IH : forall Ctx X Ty Ctx',
lookup Ctx X Ty * -> desugar_ctx Ctx Ctx' -> exists Ty',
lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
============================
forall Ctx X Ty Ctx',
lookup Ctx X Ty @ -> desugar_ctx Ctx Ctx' -> exists Ty',
lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
< intros L D.
Variables: Ctx X Ty Ctx'
IH : forall Ctx X Ty Ctx',
lookup Ctx X Ty * -> desugar_ctx Ctx Ctx' -> exists Ty',
lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
L : lookup Ctx X Ty @
D : desugar_ctx Ctx Ctx'
============================
exists Ty', lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
< L: case L.
Subgoal 1:
Variables: X Ty Ctx' Rest
IH : forall Ctx X Ty Ctx',
lookup Ctx X Ty * -> desugar_ctx Ctx Ctx' -> exists Ty',
lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
D : desugar_ctx ((X, Ty)::Rest) Ctx'
============================
exists Ty', lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
< case D.
Subgoal 1:
Variables: X Ty Rest DRest DTy
IH : forall Ctx X Ty Ctx',
lookup Ctx X Ty * -> desugar_ctx Ctx Ctx' -> exists Ty',
lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
H1 : desugar_ty Ty DTy
H2 : desugar_ctx Rest DRest
============================
exists Ty', lookup ((X, DTy)::DRest) X Ty' /\ desugar_ty Ty Ty'
< search.
Subgoal 2:
Variables: X Ty Ctx' Rest V K
IH : forall Ctx X Ty Ctx',
lookup Ctx X Ty * -> desugar_ctx Ctx Ctx' -> exists Ty',
lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
D : desugar_ctx ((K, V)::Rest) Ctx'
L : K = X -> false
L1 : lookup Rest X Ty *
============================
exists Ty', lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
< D: case D.
Subgoal 2:
Variables: X Ty Rest V K DRest DTy
IH : forall Ctx X Ty Ctx',
lookup Ctx X Ty * -> desugar_ctx Ctx Ctx' -> exists Ty',
lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
L : K = X -> false
L1 : lookup Rest X Ty *
D : desugar_ty V DTy
D1 : desugar_ctx Rest DRest
============================
exists Ty', lookup ((K, DTy)::DRest) X Ty' /\ desugar_ty Ty Ty'
< apply IH to L1 D1.
Subgoal 2:
Variables: X Ty Rest V K DRest DTy Ty'
IH : forall Ctx X Ty Ctx',
lookup Ctx X Ty * -> desugar_ctx Ctx Ctx' -> exists Ty',
lookup Ctx' X Ty' /\ desugar_ty Ty Ty'
L : K = X -> false
L1 : lookup Rest X Ty *
D : desugar_ty V DTy
D1 : desugar_ctx Rest DRest
H1 : lookup DRest X Ty'
H2 : desugar_ty Ty Ty'
============================
exists Ty', lookup ((K, DTy)::DRest) X Ty' /\ desugar_ty Ty Ty'
< search.
Proof completed.
< Theorem desugar_ty_unique :
forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA -> desugar_ty Ty TyB -> TyA = TyB.
============================
forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA -> desugar_ty Ty TyB -> TyA = TyB
< induction on 2.
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
============================
forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA @ -> desugar_ty Ty TyB -> TyA = TyB
< intros IsTy DA DB.
Variables: Ty TyA TyB
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty Ty
DA : desugar_ty Ty TyA @
DB : desugar_ty Ty TyB
============================
TyA = TyB
< DA: case DA.
Subgoal 1:
Variables: TyB DB DA B A
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty (arrowTy A B)
DB : desugar_ty (arrowTy A B) TyB
DA : desugar_ty A DA *
DA1 : desugar_ty B DB *
============================
arrowTy DA DB = TyB
< DB: case DB.
Subgoal 1.1:
Variables: DB DA B A DB1 DA1
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty (arrowTy A B)
DA : desugar_ty A DA *
DA1 : desugar_ty B DB *
DB : desugar_ty A DA1
DB1 : desugar_ty B DB1
============================
arrowTy DA DB = arrowTy DA1 DB1
< case IsTy.
Subgoal 1.1:
Variables: DB DA B A DB1 DA1
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
DA : desugar_ty A DA *
DA1 : desugar_ty B DB *
DB : desugar_ty A DA1
DB1 : desugar_ty B DB1
H1 : is_ty A
H2 : is_ty B
============================
arrowTy DA DB = arrowTy DA1 DB1
< apply IH to _ DA DB.
Subgoal 1.1:
Variables: DB B A DB1 DA1
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
DA : desugar_ty A DA1 *
DA1 : desugar_ty B DB *
DB : desugar_ty A DA1
DB1 : desugar_ty B DB1
H1 : is_ty A
H2 : is_ty B
============================
arrowTy DA1 DB = arrowTy DA1 DB1
< apply IH to _ DA1 DB1.
Subgoal 1.1:
Variables: B A DB1 DA1
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
DA : desugar_ty A DA1 *
DA1 : desugar_ty B DB1 *
DB : desugar_ty A DA1
DB1 : desugar_ty B DB1
H1 : is_ty A
H2 : is_ty B
============================
arrowTy DA1 DB1 = arrowTy DA1 DB1
< search.
Subgoal 1.2:
Variables: TyB DB DA B A Ty_P
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty (arrowTy A B)
DA : desugar_ty A DA *
DA1 : desugar_ty B DB *
DB : |{ty}- arrowTy A B ~~> Ty_P
DB1 : desugar_ty Ty_P TyB
============================
arrowTy DA DB = TyB
< case DB.
Subgoal 2:
Variables: TyB
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty intTy
DB : desugar_ty intTy TyB
============================
intTy = TyB
< DB: case DB.
Subgoal 2.1:
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty intTy
============================
intTy = intTy
< search.
Subgoal 2.2:
Variables: TyB Ty_P
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty intTy
DB : |{ty}- intTy ~~> Ty_P
DB1 : desugar_ty Ty_P TyB
============================
intTy = TyB
< case DB.
Subgoal 3:
Variables: Ty TyA TyB Ty_P
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty Ty
DB : desugar_ty Ty TyB
DA : |{ty}- Ty ~~> Ty_P
DA1 : desugar_ty Ty_P TyA *
============================
TyA = TyB
< DB: case DB.
Subgoal 3.1:
Variables: TyA Ty_P DB DA B A
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty (arrowTy A B)
DA : |{ty}- arrowTy A B ~~> Ty_P
DA1 : desugar_ty Ty_P TyA *
DB : desugar_ty A DA
DB1 : desugar_ty B DB
============================
TyA = arrowTy DA DB
< case DA.
Subgoal 3.2:
Variables: TyA Ty_P
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty intTy
DA : |{ty}- intTy ~~> Ty_P
DA1 : desugar_ty Ty_P TyA *
============================
TyA = intTy
< case DA.
Subgoal 3.3:
Variables: Ty TyA TyB Ty_P Ty_P1
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty Ty
DA : |{ty}- Ty ~~> Ty_P
DA1 : desugar_ty Ty_P TyA *
DB : |{ty}- Ty ~~> Ty_P1
DB1 : desugar_ty Ty_P1 TyB
============================
TyA = TyB
< apply proj_ty_unique to DA DB _.
Subgoal 3.3:
Variables: Ty TyA TyB Ty_P1
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty Ty
DA : |{ty}- Ty ~~> Ty_P1
DA1 : desugar_ty Ty_P1 TyA *
DB : |{ty}- Ty ~~> Ty_P1
DB1 : desugar_ty Ty_P1 TyB
============================
TyA = TyB
< apply proj_ty_is to DA _.
Subgoal 3.3:
Variables: Ty TyA TyB Ty_P1
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty Ty
DA : |{ty}- Ty ~~> Ty_P1
DA1 : desugar_ty Ty_P1 TyA *
DB : |{ty}- Ty ~~> Ty_P1
DB1 : desugar_ty Ty_P1 TyB
H1 : is_ty Ty_P1
============================
TyA = TyB
< apply IH to _ DA1 DB1.
Subgoal 3.3:
Variables: Ty TyB Ty_P1
IH : forall Ty TyA TyB,
is_ty Ty -> desugar_ty Ty TyA * -> desugar_ty Ty TyB -> TyA = TyB
IsTy : is_ty Ty
DA : |{ty}- Ty ~~> Ty_P1
DA1 : desugar_ty Ty_P1 TyB *
DB : |{ty}- Ty ~~> Ty_P1
DB1 : desugar_ty Ty_P1 TyB
H1 : is_ty Ty_P1
============================
TyB = TyB
< search.
Proof completed.
< Theorem desugar_tm_unique :
forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA ->
desugar_tm Ctx T TB -> TA = TB.
============================
forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA -> desugar_tm Ctx T TB ->
TA = TB
< induction on 3.
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
============================
forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA @ -> desugar_tm Ctx T TB ->
TA = TB
< intros IsCtx IsT DA DB.
Variables: Ctx T TA TB
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm T
DA : desugar_tm Ctx T TA @
DB : desugar_tm Ctx T TB
============================
TA = TB
< DA: case DA.
Subgoal 1:
Variables: Ctx TB X
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (var X)
DB : desugar_tm Ctx (var X) TB
============================
var X = TB
< DB: case DB.
Subgoal 1.1:
Variables: Ctx X
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (var X)
============================
var X = var X
< search.
Subgoal 1.2:
Variables: Ctx TB X T_P
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (var X)
DB : Ctx |{tm}- var X ~~> T_P
DB1 : desugar_tm Ctx T_P TB
============================
var X = TB
< case DB.
Subgoal 2:
Variables: Ctx TB DTm DTy X Tm Ty
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (abs X Ty Tm)
DB : desugar_tm Ctx (abs X Ty Tm) TB
DA : desugar_ty Ty DTy
DA1 : desugar_tm ((X, Ty)::Ctx) Tm DTm *
============================
abs X DTy DTm = TB
< DB: case DB.
Subgoal 2.1:
Variables: Ctx DTm DTy X Tm Ty DTm1 DTy1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (abs X Ty Tm)
DA : desugar_ty Ty DTy
DA1 : desugar_tm ((X, Ty)::Ctx) Tm DTm *
DB : desugar_ty Ty DTy1
DB1 : desugar_tm ((X, Ty)::Ctx) Tm DTm1
============================
abs X DTy DTm = abs X DTy1 DTm1
< case IsT.
Subgoal 2.1:
Variables: Ctx DTm DTy X Tm Ty DTm1 DTy1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
DA : desugar_ty Ty DTy
DA1 : desugar_tm ((X, Ty)::Ctx) Tm DTm *
DB : desugar_ty Ty DTy1
DB1 : desugar_tm ((X, Ty)::Ctx) Tm DTm1
H1 : is_string X
H2 : is_ty Ty
H3 : is_tm Tm
============================
abs X DTy DTm = abs X DTy1 DTm1
< apply IH to _ _ DA1 DB1.
Subgoal 2.1:
Variables: Ctx DTy X Tm Ty DTm1 DTy1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
DA : desugar_ty Ty DTy
DA1 : desugar_tm ((X, Ty)::Ctx) Tm DTm1 *
DB : desugar_ty Ty DTy1
DB1 : desugar_tm ((X, Ty)::Ctx) Tm DTm1
H1 : is_string X
H2 : is_ty Ty
H3 : is_tm Tm
============================
abs X DTy DTm1 = abs X DTy1 DTm1
< apply desugar_ty_unique to _ DA DB.
Subgoal 2.1:
Variables: Ctx X Tm Ty DTm1 DTy1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
DA : desugar_ty Ty DTy1
DA1 : desugar_tm ((X, Ty)::Ctx) Tm DTm1 *
DB : desugar_ty Ty DTy1
DB1 : desugar_tm ((X, Ty)::Ctx) Tm DTm1
H1 : is_string X
H2 : is_ty Ty
H3 : is_tm Tm
============================
abs X DTy1 DTm1 = abs X DTy1 DTm1
< search.
Subgoal 2.2:
Variables: Ctx TB DTm DTy X Tm Ty T_P
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (abs X Ty Tm)
DA : desugar_ty Ty DTy
DA1 : desugar_tm ((X, Ty)::Ctx) Tm DTm *
DB : Ctx |{tm}- abs X Ty Tm ~~> T_P
DB1 : desugar_tm Ctx T_P TB
============================
abs X DTy DTm = TB
< case DB.
Subgoal 3:
Variables: Ctx TB DB DA B A
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (app A B)
DB : desugar_tm Ctx (app A B) TB
DA : desugar_tm Ctx A DA *
DA1 : desugar_tm Ctx B DB *
============================
app DA DB = TB
< DB: case DB.
Subgoal 3.1:
Variables: Ctx DB DA B A DB1 DA1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (app A B)
DA : desugar_tm Ctx A DA *
DA1 : desugar_tm Ctx B DB *
DB : desugar_tm Ctx A DA1
DB1 : desugar_tm Ctx B DB1
============================
app DA DB = app DA1 DB1
< case IsT.
Subgoal 3.1:
Variables: Ctx DB DA B A DB1 DA1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
DA : desugar_tm Ctx A DA *
DA1 : desugar_tm Ctx B DB *
DB : desugar_tm Ctx A DA1
DB1 : desugar_tm Ctx B DB1
H1 : is_tm A
H2 : is_tm B
============================
app DA DB = app DA1 DB1
< apply IH to _ _ DA DB.
Subgoal 3.1:
Variables: Ctx DB B A DB1 DA1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
DA : desugar_tm Ctx A DA1 *
DA1 : desugar_tm Ctx B DB *
DB : desugar_tm Ctx A DA1
DB1 : desugar_tm Ctx B DB1
H1 : is_tm A
H2 : is_tm B
============================
app DA1 DB = app DA1 DB1
< apply IH to _ _ DA1 DB1.
Subgoal 3.1:
Variables: Ctx B A DB1 DA1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
DA : desugar_tm Ctx A DA1 *
DA1 : desugar_tm Ctx B DB1 *
DB : desugar_tm Ctx A DA1
DB1 : desugar_tm Ctx B DB1
H1 : is_tm A
H2 : is_tm B
============================
app DA1 DB1 = app DA1 DB1
< search.
Subgoal 3.2:
Variables: Ctx TB DB DA B A T_P
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (app A B)
DA : desugar_tm Ctx A DA *
DA1 : desugar_tm Ctx B DB *
DB : Ctx |{tm}- app A B ~~> T_P
DB1 : desugar_tm Ctx T_P TB
============================
app DA DB = TB
< case DB.
Subgoal 4:
Variables: Ctx TB I
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (num I)
DB : desugar_tm Ctx (num I) TB
============================
num I = TB
< DB: case DB.
Subgoal 4.1:
Variables: Ctx I
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (num I)
============================
num I = num I
< search.
Subgoal 4.2:
Variables: Ctx TB I T_P
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (num I)
DB : Ctx |{tm}- num I ~~> T_P
DB1 : desugar_tm Ctx T_P TB
============================
num I = TB
< case DB.
Subgoal 5:
Variables: Ctx TB DB DA B A
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (plus A B)
DB : desugar_tm Ctx (plus A B) TB
DA : desugar_tm Ctx A DA *
DA1 : desugar_tm Ctx B DB *
============================
plus DA DB = TB
< DB: case DB.
Subgoal 5.1:
Variables: Ctx DB DA B A DB1 DA1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (plus A B)
DA : desugar_tm Ctx A DA *
DA1 : desugar_tm Ctx B DB *
DB : desugar_tm Ctx A DA1
DB1 : desugar_tm Ctx B DB1
============================
plus DA DB = plus DA1 DB1
< case IsT.
Subgoal 5.1:
Variables: Ctx DB DA B A DB1 DA1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
DA : desugar_tm Ctx A DA *
DA1 : desugar_tm Ctx B DB *
DB : desugar_tm Ctx A DA1
DB1 : desugar_tm Ctx B DB1
H1 : is_tm A
H2 : is_tm B
============================
plus DA DB = plus DA1 DB1
< apply IH to _ _ DA DB.
Subgoal 5.1:
Variables: Ctx DB B A DB1 DA1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
DA : desugar_tm Ctx A DA1 *
DA1 : desugar_tm Ctx B DB *
DB : desugar_tm Ctx A DA1
DB1 : desugar_tm Ctx B DB1
H1 : is_tm A
H2 : is_tm B
============================
plus DA1 DB = plus DA1 DB1
< apply IH to _ _ DA1 DB1.
Subgoal 5.1:
Variables: Ctx B A DB1 DA1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
DA : desugar_tm Ctx A DA1 *
DA1 : desugar_tm Ctx B DB1 *
DB : desugar_tm Ctx A DA1
DB1 : desugar_tm Ctx B DB1
H1 : is_tm A
H2 : is_tm B
============================
plus DA1 DB1 = plus DA1 DB1
< search.
Subgoal 5.2:
Variables: Ctx TB DB DA B A T_P
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (plus A B)
DA : desugar_tm Ctx A DA *
DA1 : desugar_tm Ctx B DB *
DB : Ctx |{tm}- plus A B ~~> T_P
DB1 : desugar_tm Ctx T_P TB
============================
plus DA DB = TB
< case DB.
Subgoal 6:
Variables: Ctx T TA TB T_P
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm T
DB : desugar_tm Ctx T TB
DA : Ctx |{tm}- T ~~> T_P
DA1 : desugar_tm Ctx T_P TA *
============================
TA = TB
< DB: case DB.
Subgoal 6.1:
Variables: Ctx TA T_P X
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (var X)
DA : Ctx |{tm}- var X ~~> T_P
DA1 : desugar_tm Ctx T_P TA *
============================
TA = var X
< case DA.
Subgoal 6.2:
Variables: Ctx TA T_P DTm DTy X Tm Ty
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (abs X Ty Tm)
DA : Ctx |{tm}- abs X Ty Tm ~~> T_P
DA1 : desugar_tm Ctx T_P TA *
DB : desugar_ty Ty DTy
DB1 : desugar_tm ((X, Ty)::Ctx) Tm DTm
============================
TA = abs X DTy DTm
< case DA.
Subgoal 6.3:
Variables: Ctx TA T_P DB DA B A
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (app A B)
DA : Ctx |{tm}- app A B ~~> T_P
DA1 : desugar_tm Ctx T_P TA *
DB : desugar_tm Ctx A DA
DB1 : desugar_tm Ctx B DB
============================
TA = app DA DB
< case DA.
Subgoal 6.4:
Variables: Ctx TA T_P I
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (num I)
DA : Ctx |{tm}- num I ~~> T_P
DA1 : desugar_tm Ctx T_P TA *
============================
TA = num I
< case DA.
Subgoal 6.5:
Variables: Ctx TA T_P DB DA B A
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm (plus A B)
DA : Ctx |{tm}- plus A B ~~> T_P
DA1 : desugar_tm Ctx T_P TA *
DB : desugar_tm Ctx A DA
DB1 : desugar_tm Ctx B DB
============================
TA = plus DA DB
< case DA.
Subgoal 6.6:
Variables: Ctx T TA TB T_P T_P1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm T
DA : Ctx |{tm}- T ~~> T_P
DA1 : desugar_tm Ctx T_P TA *
DB : Ctx |{tm}- T ~~> T_P1
DB1 : desugar_tm Ctx T_P1 TB
============================
TA = TB
< apply proj_tm_unique to DA DB _ _.
Subgoal 6.6:
Variables: Ctx T TA TB T_P1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm T
DA : Ctx |{tm}- T ~~> T_P1
DA1 : desugar_tm Ctx T_P1 TA *
DB : Ctx |{tm}- T ~~> T_P1
DB1 : desugar_tm Ctx T_P1 TB
============================
TA = TB
< apply proj_is to DA _ _.
Subgoal 6.6:
Variables: Ctx T TA TB T_P1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm T
DA : Ctx |{tm}- T ~~> T_P1
DA1 : desugar_tm Ctx T_P1 TA *
DB : Ctx |{tm}- T ~~> T_P1
DB1 : desugar_tm Ctx T_P1 TB
H1 : is_tm T_P1
============================
TA = TB
< apply IH to _ _ DA1 DB1.
Subgoal 6.6:
Variables: Ctx T TB T_P1
IH : forall Ctx T TA TB,
is_list (is_pair is_string is_ty) Ctx -> is_tm T -> desugar_tm Ctx T TA * ->
desugar_tm Ctx T TB -> TA = TB
IsCtx : is_list (is_pair is_string is_ty) Ctx
IsT : is_tm T
DA : Ctx |{tm}- T ~~> T_P1
DA1 : desugar_tm Ctx T_P1 TB *
DB : Ctx |{tm}- T ~~> T_P1
DB1 : desugar_tm Ctx T_P1 TB
H1 : is_tm T_P1
============================
TB = TB
< search.
Proof completed.
< Extensible_Theorem
desugar_ty_exists : forall Ty,
IsTy : is_ty Ty ->
exists Ty',
desugar_ty Ty Ty'
on IsTy.
Subgoal 1:
Variables: Ty2 Ty1
IH : forall Ty, is_ty Ty * -> exists Ty', desugar_ty Ty Ty'
IsTy : is_ty (arrowTy Ty1 Ty2) @
IsTy1 : is_ty Ty1 *
IsTy2 : is_ty Ty2 *
============================
exists Ty', desugar_ty (arrowTy Ty1 Ty2) Ty'
< apply IH to IsTy1.
Subgoal 1:
Variables: Ty2 Ty1 Ty'
IH : forall Ty, is_ty Ty * -> exists Ty', desugar_ty Ty Ty'
IsTy : is_ty (arrowTy Ty1 Ty2) @
IsTy1 : is_ty Ty1 *
IsTy2 : is_ty Ty2 *
H1 : desugar_ty Ty1 Ty'
============================
exists Ty', desugar_ty (arrowTy Ty1 Ty2) Ty'
< apply IH to IsTy2.
Subgoal 1:
Variables: Ty2 Ty1 Ty' Ty'1
IH : forall Ty, is_ty Ty * -> exists Ty', desugar_ty Ty Ty'
IsTy : is_ty (arrowTy Ty1 Ty2) @
IsTy1 : is_ty Ty1 *
IsTy2 : is_ty Ty2 *
H1 : desugar_ty Ty1 Ty'
H2 : desugar_ty Ty2 Ty'1
============================
exists Ty', desugar_ty (arrowTy Ty1 Ty2) Ty'
< search.
Subgoal 2:
IH : forall Ty, is_ty Ty * -> exists Ty', desugar_ty Ty Ty'
IsTy : is_ty intTy @
============================
exists Ty', desugar_ty intTy Ty'
< search.
Proof completed.
< Define host_is_ty : ty -> prop by
host_is_ty (arrowTy Ty1 Ty2) :=
host_is_ty Ty1 /\ host_is_ty Ty2;
host_is_ty intTy.
< Define host_is_tm : tm -> prop by
host_is_tm (var X) :=
is_string X;
host_is_tm (abs X Ty B) :=
(is_string X /\ host_is_ty Ty) /\ host_is_tm B;
host_is_tm (app A B) :=
host_is_tm A /\ host_is_tm B;
host_is_tm (num I) :=
is_integer I;
host_is_tm (plus A B) :=
host_is_tm A /\ host_is_tm B.
< Theorem desugar_ty_host_is_ty :
forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy -> host_is_ty DTy.
============================
forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy -> host_is_ty DTy
< induction on 2.
IH : forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy * -> host_is_ty DTy
============================
forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy @ -> host_is_ty DTy
< intros IsTy DS.
Variables: Ty DTy
IH : forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy * -> host_is_ty DTy
IsTy : is_ty Ty
DS : desugar_ty Ty DTy @
============================
host_is_ty DTy
< DS: case DS.
Subgoal 1:
Variables: DB DA B A
IH : forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy * -> host_is_ty DTy
IsTy : is_ty (arrowTy A B)
DS : desugar_ty A DA *
DS1 : desugar_ty B DB *
============================
host_is_ty (arrowTy DA DB)
< case IsTy.
Subgoal 1:
Variables: DB DA B A
IH : forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy * -> host_is_ty DTy
DS : desugar_ty A DA *
DS1 : desugar_ty B DB *
H1 : is_ty A
H2 : is_ty B
============================
host_is_ty (arrowTy DA DB)
< apply IH to _ DS.
Subgoal 1:
Variables: DB DA B A
IH : forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy * -> host_is_ty DTy
DS : desugar_ty A DA *
DS1 : desugar_ty B DB *
H1 : is_ty A
H2 : is_ty B
H3 : host_is_ty DA
============================
host_is_ty (arrowTy DA DB)
< apply IH to _ DS1.
Subgoal 1:
Variables: DB DA B A
IH : forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy * -> host_is_ty DTy
DS : desugar_ty A DA *
DS1 : desugar_ty B DB *
H1 : is_ty A
H2 : is_ty B
H3 : host_is_ty DA
H4 : host_is_ty DB
============================
host_is_ty (arrowTy DA DB)
< search.
Subgoal 2:
IH : forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy * -> host_is_ty DTy
IsTy : is_ty intTy
============================
host_is_ty intTy
< search.
Subgoal 3:
Variables: Ty DTy Ty_P
IH : forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy * -> host_is_ty DTy
IsTy : is_ty Ty
DS : |{ty}- Ty ~~> Ty_P
DS1 : desugar_ty Ty_P DTy *
============================
host_is_ty DTy
< apply proj_ty_is to DS _.
Subgoal 3:
Variables: Ty DTy Ty_P
IH : forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy * -> host_is_ty DTy
IsTy : is_ty Ty
DS : |{ty}- Ty ~~> Ty_P
DS1 : desugar_ty Ty_P DTy *
H1 : is_ty Ty_P
============================
host_is_ty DTy
< apply IH to _ DS1.
Subgoal 3:
Variables: Ty DTy Ty_P
IH : forall Ty DTy, is_ty Ty -> desugar_ty Ty DTy * -> host_is_ty DTy
IsTy : is_ty Ty
DS : |{ty}- Ty ~~> Ty_P
DS1 : desugar_ty Ty_P DTy *
H1 : is_ty Ty_P
H2 : host_is_ty DTy
============================
host_is_ty DTy
< search.
Proof completed.
< Theorem desugar_tm_host_is_tm :
forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT ->
host_is_tm DT.
============================
forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT -> host_is_tm DT
< induction on 3.
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
============================
forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT @ -> host_is_tm DT
< intros IsT IsCtx DS.
Variables: Ctx T DT
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsT : is_tm T
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_tm Ctx T DT @
============================
host_is_tm DT
< DS: case DS.
Subgoal 1:
Variables: Ctx X
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsT : is_tm (var X)
IsCtx : is_list (is_pair is_string is_ty) Ctx
============================
host_is_tm (var X)
< case IsT.
Subgoal 1:
Variables: Ctx X
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsCtx : is_list (is_pair is_string is_ty) Ctx
H1 : is_string X
============================
host_is_tm (var X)
< search.
Subgoal 2:
Variables: Ctx DTm DTy X Tm Ty
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsT : is_tm (abs X Ty Tm)
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_ty Ty DTy
DS1 : desugar_tm ((X, Ty)::Ctx) Tm DTm *
============================
host_is_tm (abs X DTy DTm)
< case IsT.
Subgoal 2:
Variables: Ctx DTm DTy X Tm Ty
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_ty Ty DTy
DS1 : desugar_tm ((X, Ty)::Ctx) Tm DTm *
H1 : is_string X
H2 : is_ty Ty
H3 : is_tm Tm
============================
host_is_tm (abs X DTy DTm)
< apply desugar_ty_host_is_ty to _ DS.
Subgoal 2:
Variables: Ctx DTm DTy X Tm Ty
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_ty Ty DTy
DS1 : desugar_tm ((X, Ty)::Ctx) Tm DTm *
H1 : is_string X
H2 : is_ty Ty
H3 : is_tm Tm
H4 : host_is_ty DTy
============================
host_is_tm (abs X DTy DTm)
< apply IH to _ _ DS1.
Subgoal 2:
Variables: Ctx DTm DTy X Tm Ty
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_ty Ty DTy
DS1 : desugar_tm ((X, Ty)::Ctx) Tm DTm *
H1 : is_string X
H2 : is_ty Ty
H3 : is_tm Tm
H4 : host_is_ty DTy
H5 : host_is_tm DTm
============================
host_is_tm (abs X DTy DTm)
< search.
Subgoal 3:
Variables: Ctx DB DA B A
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsT : is_tm (app A B)
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_tm Ctx A DA *
DS1 : desugar_tm Ctx B DB *
============================
host_is_tm (app DA DB)
< case IsT.
Subgoal 3:
Variables: Ctx DB DA B A
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_tm Ctx A DA *
DS1 : desugar_tm Ctx B DB *
H1 : is_tm A
H2 : is_tm B
============================
host_is_tm (app DA DB)
< apply IH to _ _ DS.
Subgoal 3:
Variables: Ctx DB DA B A
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_tm Ctx A DA *
DS1 : desugar_tm Ctx B DB *
H1 : is_tm A
H2 : is_tm B
H3 : host_is_tm DA
============================
host_is_tm (app DA DB)
< apply IH to _ _ DS1.
Subgoal 3:
Variables: Ctx DB DA B A
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_tm Ctx A DA *
DS1 : desugar_tm Ctx B DB *
H1 : is_tm A
H2 : is_tm B
H3 : host_is_tm DA
H4 : host_is_tm DB
============================
host_is_tm (app DA DB)
< search.
Subgoal 4:
Variables: Ctx I
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsT : is_tm (num I)
IsCtx : is_list (is_pair is_string is_ty) Ctx
============================
host_is_tm (num I)
< case IsT.
Subgoal 4:
Variables: Ctx I
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsCtx : is_list (is_pair is_string is_ty) Ctx
H1 : is_integer I
============================
host_is_tm (num I)
< search.
Subgoal 5:
Variables: Ctx DB DA B A
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsT : is_tm (plus A B)
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_tm Ctx A DA *
DS1 : desugar_tm Ctx B DB *
============================
host_is_tm (plus DA DB)
< case IsT.
Subgoal 5:
Variables: Ctx DB DA B A
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_tm Ctx A DA *
DS1 : desugar_tm Ctx B DB *
H1 : is_tm A
H2 : is_tm B
============================
host_is_tm (plus DA DB)
< apply IH to _ _ DS.
Subgoal 5:
Variables: Ctx DB DA B A
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_tm Ctx A DA *
DS1 : desugar_tm Ctx B DB *
H1 : is_tm A
H2 : is_tm B
H3 : host_is_tm DA
============================
host_is_tm (plus DA DB)
< apply IH to _ _ DS1.
Subgoal 5:
Variables: Ctx DB DA B A
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : desugar_tm Ctx A DA *
DS1 : desugar_tm Ctx B DB *
H1 : is_tm A
H2 : is_tm B
H3 : host_is_tm DA
H4 : host_is_tm DB
============================
host_is_tm (plus DA DB)
< search.
Subgoal 6:
Variables: Ctx T DT T_P
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsT : is_tm T
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : Ctx |{tm}- T ~~> T_P
DS1 : desugar_tm Ctx T_P DT *
============================
host_is_tm DT
< apply proj_is to DS _ _.
Subgoal 6:
Variables: Ctx T DT T_P
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsT : is_tm T
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : Ctx |{tm}- T ~~> T_P
DS1 : desugar_tm Ctx T_P DT *
H1 : is_tm T_P
============================
host_is_tm DT
< apply IH to _ _ DS1.
Subgoal 6:
Variables: Ctx T DT T_P
IH : forall Ctx T DT,
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> desugar_tm Ctx T DT * ->
host_is_tm DT
IsT : is_tm T
IsCtx : is_list (is_pair is_string is_ty) Ctx
DS : Ctx |{tm}- T ~~> T_P
DS1 : desugar_tm Ctx T_P DT *
H1 : is_tm T_P
H2 : host_is_tm DT
============================
host_is_tm DT
< search.
Proof completed.
< Extensible_Theorem
desugar_ty_rel : forall Ctx T Ty T' Ty' Ctx',
IsT : is_tm T ->
IsCtx : is_list (is_pair is_string is_ty) Ctx ->
Ty : typeOf Ctx T Ty ->
DT : desugar_tm Ctx T T' ->
DTy : desugar_ty Ty Ty' ->
DCtx : desugar_ctx Ctx Ctx' ->
typeOf Ctx' T' Ty'
on Ty.
Subgoal 1:
Variables: Ctx Ty T' Ty' Ctx' X
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (var X)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (var X) Ty @
DT : desugar_tm Ctx (var X) T'
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : lookup Ctx X Ty
============================
typeOf Ctx' T' Ty'
< L: apply lookup_desugar_ctx to Ty1 DCtx.
Subgoal 1:
Variables: Ctx Ty T' Ty' Ctx' X Ty'1
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (var X)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (var X) Ty @
DT : desugar_tm Ctx (var X) T'
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : lookup Ctx X Ty
L : lookup Ctx' X Ty'1
L1 : desugar_ty Ty Ty'1
============================
typeOf Ctx' T' Ty'
< DT: case DT.
Subgoal 1.1:
Variables: Ctx Ty Ty' Ctx' X Ty'1
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (var X)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (var X) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : lookup Ctx X Ty
L : lookup Ctx' X Ty'1
L1 : desugar_ty Ty Ty'1
============================
typeOf Ctx' (var X) Ty'
< apply lookup_ty_is to _ Ty1.
Subgoal 1.1:
Variables: Ctx Ty Ty' Ctx' X Ty'1
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (var X)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (var X) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : lookup Ctx X Ty
L : lookup Ctx' X Ty'1
L1 : desugar_ty Ty Ty'1
H1 : is_ty Ty
============================
typeOf Ctx' (var X) Ty'
< apply desugar_ty_unique to _ L1 DTy.
Subgoal 1.1:
Variables: Ctx Ty Ty' Ctx' X
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (var X)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (var X) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : lookup Ctx X Ty
L : lookup Ctx' X Ty'
L1 : desugar_ty Ty Ty'
H1 : is_ty Ty
============================
typeOf Ctx' (var X) Ty'
< search.
Subgoal 1.2:
Variables: Ctx Ty T' Ty' Ctx' X Ty'1 T_P
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (var X)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (var X) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : lookup Ctx X Ty
L : lookup Ctx' X Ty'1
L1 : desugar_ty Ty Ty'1
DT : Ctx |{tm}- var X ~~> T_P
DT1 : desugar_tm Ctx T_P T'
============================
typeOf Ctx' T' Ty'
< case DT.
Subgoal 2:
Variables: Ctx T' Ty' Ctx' Ty2 Ty1 Body X
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (abs X Ty1 Body)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
DT : desugar_tm Ctx (abs X Ty1 Body) T'
DTy : desugar_ty (arrowTy Ty1 Ty2) Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
============================
typeOf Ctx' T' Ty'
< case IsT.
Subgoal 2:
Variables: Ctx T' Ty' Ctx' Ty2 Ty1 Body X
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
DT : desugar_tm Ctx (abs X Ty1 Body) T'
DTy : desugar_ty (arrowTy Ty1 Ty2) Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
H1 : is_string X
H2 : is_ty Ty1
H3 : is_tm Body
============================
typeOf Ctx' T' Ty'
< DT: case DT.
Subgoal 2.1:
Variables: Ctx Ty' Ctx' Ty2 Ty1 Body X DTm DTy
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
DTy : desugar_ty (arrowTy Ty1 Ty2) Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
H1 : is_string X
H2 : is_ty Ty1
H3 : is_tm Body
DT : desugar_ty Ty1 DTy
DT1 : desugar_tm ((X, Ty1)::Ctx) Body DTm
============================
typeOf Ctx' (abs X DTy DTm) Ty'
< DTy: case DTy.
Subgoal 2.1.1:
Variables: Ctx Ctx' Ty2 Ty1 Body X DTm DTy DB DA
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
H1 : is_string X
H2 : is_ty Ty1
H3 : is_tm Body
DT : desugar_ty Ty1 DTy
DT1 : desugar_tm ((X, Ty1)::Ctx) Body DTm
DTy : desugar_ty Ty1 DA
DTy1 : desugar_ty Ty2 DB
============================
typeOf Ctx' (abs X DTy DTm) (arrowTy DA DB)
< apply desugar_ty_unique to _ DT DTy.
Subgoal 2.1.1:
Variables: Ctx Ctx' Ty2 Ty1 Body X DTm DB DA
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
H1 : is_string X
H2 : is_ty Ty1
H3 : is_tm Body
DT : desugar_ty Ty1 DA
DT1 : desugar_tm ((X, Ty1)::Ctx) Body DTm
DTy : desugar_ty Ty1 DA
DTy1 : desugar_ty Ty2 DB
============================
typeOf Ctx' (abs X DA DTm) (arrowTy DA DB)
< apply IH to _ _ Ty1 DT1 DTy1 _.
Subgoal 2.1.1:
Variables: Ctx Ctx' Ty2 Ty1 Body X DTm DB DA
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
H1 : is_string X
H2 : is_ty Ty1
H3 : is_tm Body
DT : desugar_ty Ty1 DA
DT1 : desugar_tm ((X, Ty1)::Ctx) Body DTm
DTy : desugar_ty Ty1 DA
DTy1 : desugar_ty Ty2 DB
H4 : typeOf ((X, DA)::Ctx') DTm DB
============================
typeOf Ctx' (abs X DA DTm) (arrowTy DA DB)
< search.
Subgoal 2.1.2:
Variables: Ctx Ty' Ctx' Ty2 Ty1 Body X DTm DTy Ty_P
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
H1 : is_string X
H2 : is_ty Ty1
H3 : is_tm Body
DT : desugar_ty Ty1 DTy
DT1 : desugar_tm ((X, Ty1)::Ctx) Body DTm
DTy : |{ty}- arrowTy Ty1 Ty2 ~~> Ty_P
DTy1 : desugar_ty Ty_P Ty'
============================
typeOf Ctx' (abs X DTy DTm) Ty'
< case DTy.
Subgoal 2.2:
Variables: Ctx T' Ty' Ctx' Ty2 Ty1 Body X T_P
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
DTy : desugar_ty (arrowTy Ty1 Ty2) Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
H1 : is_string X
H2 : is_ty Ty1
H3 : is_tm Body
DT : Ctx |{tm}- abs X Ty1 Body ~~> T_P
DT1 : desugar_tm Ctx T_P T'
============================
typeOf Ctx' T' Ty'
< case DT.
Subgoal 3:
Variables: Ctx Ty T' Ty' Ctx' Ty1 T2 T1
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (app T1 T2)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
DT : desugar_tm Ctx (app T1 T2) T'
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
============================
typeOf Ctx' T' Ty'
< case IsT.
Subgoal 3:
Variables: Ctx Ty T' Ty' Ctx' Ty1 T2 T1
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
DT : desugar_tm Ctx (app T1 T2) T'
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
============================
typeOf Ctx' T' Ty'
< DT: case DT.
Subgoal 3.1:
Variables: Ctx Ty Ty' Ctx' Ty1 T2 T1 DB DA
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
============================
typeOf Ctx' (app DA DB) Ty'
< IsTy: apply type_is to _ _ Ty1.
Subgoal 3.1:
Variables: Ctx Ty Ty' Ctx' Ty1 T2 T1 DB DA
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
IsTy : is_ty (arrowTy Ty1 Ty)
============================
typeOf Ctx' (app DA DB) Ty'
< Is: case IsTy.
Subgoal 3.1:
Variables: Ctx Ty Ty' Ctx' Ty1 T2 T1 DB DA
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
Is : is_ty Ty1
Is1 : is_ty Ty
============================
typeOf Ctx' (app DA DB) Ty'
< apply desugar_ty_exists to Is.
Subgoal 3.1:
Variables: Ctx Ty Ty' Ctx' Ty1 T2 T1 DB DA Ty'1
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
Is : is_ty Ty1
Is1 : is_ty Ty
H3 : desugar_ty Ty1 Ty'1
============================
typeOf Ctx' (app DA DB) Ty'
< apply desugar_ty_exists to Is1.
Subgoal 3.1:
Variables: Ctx Ty Ty' Ctx' Ty1 T2 T1 DB DA Ty'1 Ty'2
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
Is : is_ty Ty1
Is1 : is_ty Ty
H3 : desugar_ty Ty1 Ty'1
H4 : desugar_ty Ty Ty'2
============================
typeOf Ctx' (app DA DB) Ty'
< apply IH to _ _ Ty1 DT _ _.
Subgoal 3.1:
Variables: Ctx Ty Ty' Ctx' Ty1 T2 T1 DB DA Ty'1 Ty'2
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
Is : is_ty Ty1
Is1 : is_ty Ty
H3 : desugar_ty Ty1 Ty'1
H4 : desugar_ty Ty Ty'2
H5 : typeOf Ctx' DA (arrowTy Ty'1 Ty')
============================
typeOf Ctx' (app DA DB) Ty'
< apply IH to _ _ Ty2 DT1 _ _.
Subgoal 3.1:
Variables: Ctx Ty Ty' Ctx' Ty1 T2 T1 DB DA Ty'1 Ty'2
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
Is : is_ty Ty1
Is1 : is_ty Ty
H3 : desugar_ty Ty1 Ty'1
H4 : desugar_ty Ty Ty'2
H5 : typeOf Ctx' DA (arrowTy Ty'1 Ty')
H6 : typeOf Ctx' DB Ty'1
============================
typeOf Ctx' (app DA DB) Ty'
< search.
Subgoal 3.2:
Variables: Ctx Ty T' Ty' Ctx' Ty1 T2 T1 T_P
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (app T1 T2) Ty @
DTy : desugar_ty Ty Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 (arrowTy Ty1 Ty) *
Ty2 : typeOf Ctx T2 Ty1 *
H1 : is_tm T1
H2 : is_tm T2
DT : Ctx |{tm}- app T1 T2 ~~> T_P
DT1 : desugar_tm Ctx T_P T'
============================
typeOf Ctx' T' Ty'
< case DT.
Subgoal 4:
Variables: Ctx T' Ty' Ctx' I
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (num I)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (num I) intTy @
DT : desugar_tm Ctx (num I) T'
DTy : desugar_ty intTy Ty'
DCtx : desugar_ctx Ctx Ctx'
============================
typeOf Ctx' T' Ty'
< DT: case DT.
Subgoal 4.1:
Variables: Ctx Ty' Ctx' I
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (num I)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (num I) intTy @
DTy : desugar_ty intTy Ty'
DCtx : desugar_ctx Ctx Ctx'
============================
typeOf Ctx' (num I) Ty'
< DTy: case DTy.
Subgoal 4.1.1:
Variables: Ctx Ctx' I
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (num I)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (num I) intTy @
DCtx : desugar_ctx Ctx Ctx'
============================
typeOf Ctx' (num I) intTy
< search.
Subgoal 4.1.2:
Variables: Ctx Ty' Ctx' I Ty_P
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (num I)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (num I) intTy @
DCtx : desugar_ctx Ctx Ctx'
DTy : |{ty}- intTy ~~> Ty_P
DTy1 : desugar_ty Ty_P Ty'
============================
typeOf Ctx' (num I) Ty'
< case DTy.
Subgoal 4.2:
Variables: Ctx T' Ty' Ctx' I T_P
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (num I)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (num I) intTy @
DTy : desugar_ty intTy Ty'
DCtx : desugar_ctx Ctx Ctx'
DT : Ctx |{tm}- num I ~~> T_P
DT1 : desugar_tm Ctx T_P T'
============================
typeOf Ctx' T' Ty'
< case DT.
Subgoal 5:
Variables: Ctx T' Ty' Ctx' T2 T1
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsT : is_tm (plus T1 T2)
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (plus T1 T2) intTy @
DT : desugar_tm Ctx (plus T1 T2) T'
DTy : desugar_ty intTy Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 intTy *
Ty2 : typeOf Ctx T2 intTy *
============================
typeOf Ctx' T' Ty'
< case IsT.
Subgoal 5:
Variables: Ctx T' Ty' Ctx' T2 T1
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (plus T1 T2) intTy @
DT : desugar_tm Ctx (plus T1 T2) T'
DTy : desugar_ty intTy Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 intTy *
Ty2 : typeOf Ctx T2 intTy *
H1 : is_tm T1
H2 : is_tm T2
============================
typeOf Ctx' T' Ty'
< DT: case DT.
Subgoal 5.1:
Variables: Ctx Ty' Ctx' T2 T1 DB DA
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (plus T1 T2) intTy @
DTy : desugar_ty intTy Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 intTy *
Ty2 : typeOf Ctx T2 intTy *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
============================
typeOf Ctx' (plus DA DB) Ty'
< DTy: case DTy.
Subgoal 5.1.1:
Variables: Ctx Ctx' T2 T1 DB DA
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (plus T1 T2) intTy @
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 intTy *
Ty2 : typeOf Ctx T2 intTy *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
============================
typeOf Ctx' (plus DA DB) intTy
< apply IH to _ _ Ty1 DT _ _.
Subgoal 5.1.1:
Variables: Ctx Ctx' T2 T1 DB DA
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (plus T1 T2) intTy @
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 intTy *
Ty2 : typeOf Ctx T2 intTy *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
H3 : typeOf Ctx' DA intTy
============================
typeOf Ctx' (plus DA DB) intTy
< apply IH to _ _ Ty2 DT1 _ _.
Subgoal 5.1.1:
Variables: Ctx Ctx' T2 T1 DB DA
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (plus T1 T2) intTy @
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 intTy *
Ty2 : typeOf Ctx T2 intTy *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
H3 : typeOf Ctx' DA intTy
H4 : typeOf Ctx' DB intTy
============================
typeOf Ctx' (plus DA DB) intTy
< search.
Subgoal 5.1.2:
Variables: Ctx Ty' Ctx' T2 T1 DB DA Ty_P
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (plus T1 T2) intTy @
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 intTy *
Ty2 : typeOf Ctx T2 intTy *
H1 : is_tm T1
H2 : is_tm T2
DT : desugar_tm Ctx T1 DA
DT1 : desugar_tm Ctx T2 DB
DTy : |{ty}- intTy ~~> Ty_P
DTy1 : desugar_ty Ty_P Ty'
============================
typeOf Ctx' (plus DA DB) Ty'
< case DTy.
Subgoal 5.2:
Variables: Ctx T' Ty' Ctx' T2 T1 T_P
IH : forall Ctx T Ty T' Ty' Ctx',
is_tm T -> is_list (is_pair is_string is_ty) Ctx -> typeOf Ctx T Ty * -> desugar_tm Ctx T T' ->
desugar_ty Ty Ty' -> desugar_ctx Ctx Ctx' -> typeOf Ctx' T' Ty'
IsCtx : is_list (is_pair is_string is_ty) Ctx
Ty : typeOf Ctx (plus T1 T2) intTy @
DTy : desugar_ty intTy Ty'
DCtx : desugar_ctx Ctx Ctx'
Ty1 : typeOf Ctx T1 intTy *
Ty2 : typeOf Ctx T2 intTy *
H1 : is_tm T1
H2 : is_tm T2
DT : Ctx |{tm}- plus T1 T2 ~~> T_P
DT1 : desugar_tm Ctx T_P T'
============================
typeOf Ctx' T' Ty'
< case DT.
Proof completed.
< Theorem subst_is :
forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S -> is_tm S.
============================
forall X R T S, is_tm T -> is_string X -> is_tm R -> subst X R T S -> is_tm S
< induction on 4.
IH : forall X R T S,
is_tm T -> is_string X -> is_tm R -> subst X R T S * -> is_tm S
============================
forall X R T S, is_tm T -> is_string X -> is_tm R -> subst X R T S @ -> is_tm S
< intros IsT IsX IsR S.
Variables: X R T 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 T
IsX : is_string X
IsR : is_tm R
S : subst X R T S @
============================
is_tm S
< S: case 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 : 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
============================
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 : X = Y -> false
S1 : 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 : X = Y -> false
S1 : 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 _ _ _ S1.
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 : X = Y -> false
S1 : 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
============================
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 T1 S1 *
S1 : 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 T1 S1 *
S1 : subst X R T2 S2 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (app S1 S2)
< apply IH to _ _ _ S.
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 T1 S1 *
S1 : 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 _ _ _ 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 T1 S1 *
S1 : 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
============================
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 T1 S1 *
S1 : 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 T1 S1 *
S1 : subst X R T2 S2 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (plus S1 S2)
< apply IH to _ _ _ S.
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 T1 S1 *
S1 : 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 _ _ _ 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 T1 S1 *
S1 : 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.
< Theorem eval_is :
forall T T', is_tm T -> eval T T' -> is_tm T'.
============================
forall T T', is_tm T -> eval T T' -> is_tm T'
< induction on 2.
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
============================
forall T T', is_tm T -> eval T T' @ -> is_tm T'
< intros IsT Ev.
Variables: T T'
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
IsT : is_tm T
Ev : eval T T' @
============================
is_tm T'
< Ev: case 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 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 T1 T11 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (app T11 T2)
< apply IH to _ Ev.
Subgoal 1:
Variables: T2 T11 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : 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 : value T1
Ev1 : 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 : value T1
Ev1 : eval T2 T21 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (app T1 T21)
< apply IH to _ Ev1.
Subgoal 2:
Variables: T21 T1 T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : value T1
Ev1 : 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 : value T2
Ev1 : 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 : value T2
Ev1 : 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 : value T2
Ev1 : 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 _ _ _ Ev1.
Subgoal 3:
Variables: T' T2 Body Ty X
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : value T2
Ev1 : 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 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 T1 T11 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (plus T11 T2)
< apply IH to _ Ev.
Subgoal 4:
Variables: T2 T11 T1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : 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 : value T1
Ev1 : 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 : value T1
Ev1 : eval T2 T21 *
Is : is_tm T1
Is1 : is_tm T2
============================
is_tm (plus T1 T21)
< apply IH to _ Ev1.
Subgoal 5:
Variables: T21 T1 T2
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : value T1
Ev1 : 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 : 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 : 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 : 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 : I1 + I2 = I
H1 : is_integer I1
H2 : is_integer I2
============================
is_tm (num I)
< apply plus_integer_is_integer to _ _ Ev.
Subgoal 6:
Variables: I I2 I1
IH : forall T T', is_tm T -> eval T T' * -> is_tm T'
Ev : I1 + I2 = I
H1 : is_integer I1
H2 : is_integer I2
H3 : is_integer I
============================
is_tm (num I)
< search.
Proof completed.
< Theorem subst_unique :
forall X R T VA VB, subst X R T VA -> subst X R T VB -> VA = VB.
============================
forall X R T VA VB, subst X R T VA -> subst X R T VB -> VA = VB
< induction on 1.
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
============================
forall X R T VA VB, subst X R T VA @ -> subst X R T VB -> VA = VB
< intros SA SB.
Variables: X R T VA VB
IH : forall X R T VA VB, subst X R T VA * -> subst X R T VB -> VA = VB
SA : subst X R T VA @
SB : subst X R T VB
============================
VA = VB
< SA: case 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
SB : subst X R (var Y) VB
SA : 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 : 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 : Y = Y -> false
============================
var Y = VB
< apply SA 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
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
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
============================
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
SB : subst X R (abs Y Ty B) VB
SA : X = Y -> false
SA1 : 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 : X = Y -> false
SA1 : 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 SA1 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 : X = Y -> false
SA1 : 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 : Y = Y -> false
SA1 : subst Y R B S *
============================
abs Y Ty S = abs Y Ty B
< apply SA 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
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
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
============================
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
SB : subst X R (app T1 T2) VB
SA : subst X R T1 S1 *
SA1 : 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 T1 S1 *
SA1 : 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 SA 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 T1 S3 *
SA1 : 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 SA1 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 T1 S3 *
SA1 : 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
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
============================
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
SB : subst X R (plus T1 T2) VB
SA : subst X R T1 S1 *
SA1 : 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 T1 S1 *
SA1 : 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 SA 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 T1 S3 *
SA1 : 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 SA1 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 T1 S3 *
SA1 : 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.
< Theorem value_eval_false :
forall T V, value T -> eval T V -> false.
============================
forall T V, value T -> eval T V -> false
< intros V Ev.
Variables: T V
V : value T
Ev : eval T V
============================
false
< V: case V.
Subgoal 1:
Variables: V T1 Ty X
Ev : eval (abs X Ty T1) V
============================
false
< case Ev.
Subgoal 2:
Variables: V I
Ev : eval (num I) V
============================
false
< case Ev.
Proof completed.
< Theorem eval_unique :
forall T VA VB, eval T VA -> eval T VB -> VA = VB.
============================
forall T VA VB, eval T VA -> eval T VB -> VA = VB
< induction on 1.
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
============================
forall T VA VB, eval T VA @ -> eval T VB -> VA = VB
< intros EvA EvB.
Variables: T VA VB
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval T VA @
EvB : eval T VB
============================
VA = VB
< EvA: case EvA.
Subgoal 1:
Variables: VB T2 T11 T1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvB : eval (app T1 T2) VB
EvA : 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 T1 T11 *
EvB : eval T1 T5
============================
app T11 T2 = app T5 T2
< apply IH to EvA EvB.
Subgoal 1.1:
Variables: T2 T1 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : 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 T1 T11 *
EvB : value T1
EvB1 : eval T2 T21
============================
app T11 T2 = app T1 T21
< apply value_eval_false to EvB EvA.
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 (abs X Ty Body) T11 *
EvB : value T2
EvB1 : subst X T2 Body VB
============================
app T11 T2 = VB
< apply value_eval_false to _ EvA.
Subgoal 2:
Variables: VB T21 T1 T2
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvB : eval (app T1 T2) VB
EvA : value T1
EvA1 : 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 : value T1
EvA1 : eval T2 T21 *
EvB : eval T1 T11
============================
app T1 T21 = app T11 T2
< apply value_eval_false to EvA EvB.
Subgoal 2.2:
Variables: T21 T1 T2 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : value T1
EvA1 : eval T2 T21 *
EvB : value T1
EvB1 : eval T2 T5
============================
app T1 T21 = app T1 T5
< apply IH to EvA1 EvB1.
Subgoal 2.2:
Variables: T1 T2 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : value T1
EvA1 : 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 : value (abs X Ty Body)
EvA1 : 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 EvA1.
Subgoal 3:
Variables: VA VB T2 Body Ty X
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvB : eval (app (abs X Ty Body) T2) VB
EvA : value T2
EvA1 : 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 : value T2
EvA1 : 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 : value T2
EvA1 : 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 EvA 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 : value T2
EvA1 : subst X T2 Body VA
EvB : value T2
EvB1 : subst X T2 Body VB
============================
VA = VB
< apply subst_unique to EvA1 EvB1.
Subgoal 3.3:
Variables: VB T2 Body Ty X
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : value T2
EvA1 : 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
EvB : eval (plus T1 T2) VB
EvA : 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 T1 T11 *
EvB : eval T1 T5
============================
plus T11 T2 = plus T5 T2
< apply IH to EvA EvB.
Subgoal 4.1:
Variables: T2 T1 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : 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 T1 T11 *
EvB : value T1
EvB1 : eval T2 T21
============================
plus T11 T2 = plus T1 T21
< apply value_eval_false to EvB EvA.
Subgoal 4.3:
Variables: T11 I I2 I1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : eval (num I1) T11 *
EvB : I1 + I2 = I
============================
plus T11 (num I2) = num I
< case EvA.
Subgoal 5:
Variables: VB T21 T1 T2
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvB : eval (plus T1 T2) VB
EvA : value T1
EvA1 : 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 : value T1
EvA1 : eval T2 T21 *
EvB : eval T1 T11
============================
plus T1 T21 = plus T11 T2
< apply value_eval_false to EvA EvB.
Subgoal 5.2:
Variables: T21 T1 T2 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : value T1
EvA1 : eval T2 T21 *
EvB : value T1
EvB1 : eval T2 T5
============================
plus T1 T21 = plus T1 T5
< apply IH to EvA1 EvB1.
Subgoal 5.2:
Variables: T1 T2 T5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : value T1
EvA1 : 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 : value (num I1)
EvA1 : eval (num I2) T21 *
EvB : I1 + I2 = I
============================
plus (num I1) T21 = num I
< case EvA1.
Subgoal 6:
Variables: VB I I2 I1
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvB : eval (plus (num I1) (num I2)) VB
EvA : 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 : 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 : 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 : I1 + I2 = I
EvB : I1 + I2 = I5
============================
num I = num I5
< apply plus_integer_unique to EvA EvB.
Subgoal 6.3:
Variables: I2 I1 I5
IH : forall T VA VB, eval T VA * -> eval T VB -> VA = VB
EvA : I1 + I2 = I5
EvB : I1 + I2 = I5
============================
num I5 = num I5
< search.
Proof completed.
< Theorem subst_type_preservation :
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.
============================
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
< induction on 2.
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
============================
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
< intros TTy S RTy.
Variables: T Ctx X XTy Ty R 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) T Ty
S : subst X R T S @
RTy : typeOf [] R XTy
============================
typeOf Ctx S Ty
< S: case 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
RTy : typeOf [] R XTy
S : 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
RTy : typeOf [] R XTy
S : 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
RTy : typeOf [] R Ty
S : Y = Y -> false
============================
typeOf Ctx (var Y) Ty
< apply S 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
RTy : typeOf [] R XTy
S : 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
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
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
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
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
RTy : typeOf [] R XTy
S : X = Y -> false
S1 : 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
RTy : typeOf [] R XTy
S : X = Y -> false
S1 : 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
RTy : typeOf [] R XTy
S : X = Y -> false
S1 : 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
RTy : typeOf [] R XTy
S : X = Y -> false
S1 : 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
RTy : typeOf [] R XTy
S : X = X1 -> false
S1 : 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
RTy : typeOf [] R XTy
S : X = Y -> false
S1 : 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
RTy : typeOf [] R XTy1
S : X1 = Y -> false
S1 : 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
RTy : typeOf [] R XTy
S : X = Y -> false
S1 : 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
RTy : typeOf [] R XTy
S : X = Y -> false
S1 : 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' S1 _.
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
RTy : typeOf [] R XTy
S : X = Y -> false
S1 : 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
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
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
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
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
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
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
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
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
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
RTy : typeOf [] R XTy
S : subst X R T1 S1 *
S1 : 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
RTy : typeOf [] R XTy
S : subst X R T1 S1 *
S1 : 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 S _.
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
RTy : typeOf [] R XTy
S : subst X R T1 S1 *
S1 : 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 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
RTy : typeOf [] R XTy
S : subst X R T1 S1 *
S1 : 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
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
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
RTy : typeOf [] R XTy
S : subst X R T1 S1 *
S1 : 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
RTy : typeOf [] R XTy
S : subst X R T1 S1 *
S1 : 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 S _.
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
RTy : typeOf [] R XTy
S : subst X R T1 S1 *
S1 : 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 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
RTy : typeOf [] R XTy
S : subst X R T1 S1 *
S1 : 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.
< Theorem type_preservation :
forall T Ty T', typeOf [] T Ty -> eval T T' -> typeOf [] T' Ty.
============================
forall T Ty T', typeOf [] T Ty -> eval T T' -> typeOf [] T' Ty
< induction on 2.
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
============================
forall T Ty T', typeOf [] T Ty -> eval T T' @ -> typeOf [] T' Ty
< intros Ty Ev.
Variables: T Ty T'
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] T Ty
Ev : eval T T' @
============================
typeOf [] T' Ty
< Ev: case 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 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 T1 T11 *
Ty : typeOf [] T1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] T2 Ty1
============================
typeOf [] (app T11 T2) Ty
< apply IH to Ty Ev.
Subgoal 1:
Variables: Ty T2 T11 T1 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : 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 : value T1
Ev1 : 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 : value T1
Ev1 : eval T2 T21 *
Ty : typeOf [] T1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] T2 Ty1
============================
typeOf [] (app T1 T21) Ty
< apply IH to Ty1 Ev1.
Subgoal 2:
Variables: Ty T21 T1 T2 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : value T1
Ev1 : 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 : value T2
Ev1 : 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 : value T2
Ev1 : 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 : value T2
Ev1 : subst X T2 Body T'
Ty1 : typeOf [] T2 Ty2
Ty : typeOf [(X, Ty2)] Body Ty
============================
typeOf [] T' Ty
< apply subst_type_preservation to Ty Ev1 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 : value T2
Ev1 : 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 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 T1 T11 *
Ty : typeOf [] T1 intTy
Ty1 : typeOf [] T2 intTy
============================
typeOf [] (plus T11 T2) intTy
< apply IH to Ty Ev.
Subgoal 4:
Variables: T2 T11 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : 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 : value T1
Ev1 : 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 : value T1
Ev1 : eval T2 T21 *
Ty : typeOf [] T1 intTy
Ty1 : typeOf [] T2 intTy
============================
typeOf [] (plus T1 T21) intTy
< apply IH to Ty1 Ev1.
Subgoal 5:
Variables: T21 T1 T2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : value T1
Ev1 : 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 : 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 : I1 + I2 = I
Ty : typeOf [] (num I1) intTy
Ty1 : typeOf [] (num I2) intTy
============================
typeOf [] (num I) intTy
< search.
Proof completed.
< Theorem subst_total :
forall X R T, host_is_tm T -> is_string X -> exists S, subst X R T S.
============================
forall X R T, host_is_tm T -> is_string X -> exists S, subst X R T S
< induction on 1.
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
============================
forall X R T, host_is_tm T @ -> is_string X -> exists S, subst X R T S
< intros IsT IsX.
Variables: X R T
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsT : host_is_tm T @
IsX : is_string X
============================
exists S, subst X R T S
< IsT: case IsT.
Subgoal 1:
Variables: X R X1
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : is_string X1
============================
exists S, subst X R (var X1) S
< Or: apply is_string_eq_or_not to IsX IsT.
Subgoal 1:
Variables: X R X1
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : is_string X1
Or : X = X1 \/ (X = X1 -> false)
============================
exists S, subst X R (var X1) S
< E: case Or.
Subgoal 1.1:
Variables: R X1
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X1
IsT : is_string X1
============================
exists S, subst X1 R (var X1) S
< search.
Subgoal 1.2:
Variables: X R X1
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : is_string X1
E : X = X1 -> false
============================
exists S, subst X R (var X1) S
< search.
Subgoal 2:
Variables: X R B Ty X1
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : is_string X1
IsT1 : host_is_ty Ty
IsT2 : host_is_tm B *
============================
exists S, subst X R (abs X1 Ty B) S
< Or: apply is_string_eq_or_not to IsX IsT.
Subgoal 2:
Variables: X R B Ty X1
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : is_string X1
IsT1 : host_is_ty Ty
IsT2 : host_is_tm B *
Or : X = X1 \/ (X = X1 -> false)
============================
exists S, subst X R (abs X1 Ty B) S
< E: case Or.
Subgoal 2.1:
Variables: R B Ty X1
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X1
IsT : is_string X1
IsT1 : host_is_ty Ty
IsT2 : host_is_tm B *
============================
exists S, subst X1 R (abs X1 Ty B) S
< search.
Subgoal 2.2:
Variables: X R B Ty X1
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : is_string X1
IsT1 : host_is_ty Ty
IsT2 : host_is_tm B *
E : X = X1 -> false
============================
exists S, subst X R (abs X1 Ty B) S
< apply IH to IsT2 IsX with
R = R.
Subgoal 2.2:
Variables: X R B Ty X1 S
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : is_string X1
IsT1 : host_is_ty Ty
IsT2 : host_is_tm B *
E : X = X1 -> false
H1 : subst X R B S
============================
exists S, subst X R (abs X1 Ty B) S
< search.
Subgoal 3:
Variables: X R B A
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : host_is_tm A *
IsT1 : host_is_tm B *
============================
exists S, subst X R (app A B) S
< apply IH to IsT IsX with
R = R.
Subgoal 3:
Variables: X R B A S
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : host_is_tm A *
IsT1 : host_is_tm B *
H1 : subst X R A S
============================
exists S, subst X R (app A B) S
< apply IH to IsT1 IsX with
R = R.
Subgoal 3:
Variables: X R B A S S1
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : host_is_tm A *
IsT1 : host_is_tm B *
H1 : subst X R A S
H2 : subst X R B S1
============================
exists S, subst X R (app A B) S
< search.
Subgoal 4:
Variables: X R I
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : is_integer I
============================
exists S, subst X R (num I) S
< search.
Subgoal 5:
Variables: X R B A
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : host_is_tm A *
IsT1 : host_is_tm B *
============================
exists S, subst X R (plus A B) S
< apply IH to IsT IsX with
R = R.
Subgoal 5:
Variables: X R B A S
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : host_is_tm A *
IsT1 : host_is_tm B *
H1 : subst X R A S
============================
exists S, subst X R (plus A B) S
< apply IH to IsT1 IsX with
R = R.
Subgoal 5:
Variables: X R B A S S1
IH : forall X R T, host_is_tm T * -> is_string X -> exists S, subst X R T S
IsX : is_string X
IsT : host_is_tm A *
IsT1 : host_is_tm B *
H1 : subst X R A S
H2 : subst X R B S1
============================
exists S, subst X R (plus A B) S
< 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
< case V.
Subgoal 1:
Variables: T Ty X
Ty : typeOf [] (abs X Ty T) intTy
============================
exists I, abs X Ty T = num I
< case Ty.
Subgoal 2:
Variables: 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
< case V.
Subgoal 1:
Variables: Ty1 Ty2 T Ty X
Ty : typeOf [] (abs X Ty T) (arrowTy Ty1 Ty2)
============================
exists X1 B, abs X Ty T = abs X1 Ty1 B
< case Ty.
Subgoal 1:
Variables: Ty1 Ty2 T X
H1 : typeOf [(X, Ty1)] T Ty2
============================
exists X1 B, abs X Ty1 T = abs X1 Ty1 B
< search.
Subgoal 2:
Variables: Ty1 Ty2 I
Ty : typeOf [] (num I) (arrowTy Ty1 Ty2)
============================
exists X B, num I = abs X Ty1 B
< case Ty.
Proof completed.
< Theorem progress :
forall T Ty,
host_is_tm T -> typeOf [] T Ty -> (exists T', eval T T') \/ value T.
============================
forall T Ty,
host_is_tm T -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
< induction on 1.
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
============================
forall T Ty,
host_is_tm T @ -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
< intros IsT Ty.
Variables: T Ty
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm T @
Ty : typeOf [] T Ty
============================
(exists T', eval T T') \/ value T
< IsT: case IsT.
Subgoal 1:
Variables: Ty X
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
Ty : typeOf [] (var X) Ty
IsT : is_string X
============================
(exists T', eval (var X) T') \/ value (var X)
< Ty: case Ty.
Subgoal 1:
Variables: Ty X
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : is_string X
Ty : lookup [] X Ty
============================
(exists T', eval (var X) T') \/ value (var X)
< case Ty.
Subgoal 2:
Variables: Ty B Ty1 X
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
Ty : typeOf [] (abs X Ty1 B) Ty
IsT : is_string X
IsT1 : host_is_ty Ty1
IsT2 : host_is_tm B *
============================
(exists T', eval (abs X Ty1 B) T') \/ value (abs X Ty1 B)
< search.
Subgoal 3:
Variables: Ty B A
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
Ty : typeOf [] (app A B) Ty
IsT : host_is_tm A *
IsT1 : host_is_tm B *
============================
(exists T', eval (app A B) T') \/ value (app A B)
< Ty: case Ty.
Subgoal 3:
Variables: Ty B A Ty1
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A (arrowTy Ty1 Ty)
Ty1 : typeOf [] B Ty1
============================
(exists T', eval (app A B) T') \/ value (app A B)
< Or1: apply IH to IsT Ty.
Subgoal 3:
Variables: Ty B A Ty1
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A (arrowTy Ty1 Ty)
Ty1 : typeOf [] B Ty1
Or1 : (exists T', eval A T') \/ value A
============================
(exists T', eval (app A B) T') \/ value (app A B)
< Or2: apply IH to IsT1 Ty1.
Subgoal 3:
Variables: Ty B A Ty1
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A (arrowTy Ty1 Ty)
Ty1 : typeOf [] B Ty1
Or1 : (exists T', eval A T') \/ value A
Or2 : (exists T', eval B T') \/ value B
============================
(exists T', eval (app A B) T') \/ value (app A B)
< Ev1: case Or1.
Subgoal 3.1:
Variables: Ty B A Ty1 T'
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A (arrowTy Ty1 Ty)
Ty1 : typeOf [] B Ty1
Or2 : (exists T', eval B T') \/ value B
Ev1 : eval A T'
============================
(exists T', eval (app A B) T') \/ value (app A B)
< search.
Subgoal 3.2:
Variables: Ty B A Ty1
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A (arrowTy Ty1 Ty)
Ty1 : typeOf [] B Ty1
Or2 : (exists T', eval B T') \/ value B
Ev1 : value A
============================
(exists T', eval (app A B) T') \/ value (app A B)
< Ev2: case Or2.
Subgoal 3.2.1:
Variables: Ty B A Ty1 T'
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A (arrowTy Ty1 Ty)
Ty1 : typeOf [] B Ty1
Ev1 : value A
Ev2 : eval B T'
============================
(exists T', eval (app A B) T') \/ value (app A B)
< search.
Subgoal 3.2.2:
Variables: Ty B A Ty1
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A (arrowTy Ty1 Ty)
Ty1 : typeOf [] B Ty1
Ev1 : value A
Ev2 : value B
============================
(exists T', eval (app A B) T') \/ value (app A B)
< apply canonical_form_arrowTy to _ Ty.
Subgoal 3.2.2:
Variables: Ty B Ty1 X B1
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm (abs X Ty1 B1) *
IsT1 : host_is_tm B *
Ty : typeOf [] (abs X Ty1 B1) (arrowTy Ty1 Ty)
Ty1 : typeOf [] B Ty1
Ev1 : value (abs X Ty1 B1)
Ev2 : value B
============================
(exists T', eval (app (abs X Ty1 B1) B) T') \/ value (app (abs X Ty1 B1) B)
< IsAbs: case IsT.
Subgoal 3.2.2:
Variables: Ty B Ty1 X B1
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT1 : host_is_tm B *
Ty : typeOf [] (abs X Ty1 B1) (arrowTy Ty1 Ty)
Ty1 : typeOf [] B Ty1
Ev1 : value (abs X Ty1 B1)
Ev2 : value B
IsAbs : is_string X
IsAbs1 : host_is_ty Ty1
IsAbs2 : host_is_tm B1 *
============================
(exists T', eval (app (abs X Ty1 B1) B) T') \/ value (app (abs X Ty1 B1) B)
< apply subst_total to IsAbs2 IsAbs with
R = B.
Subgoal 3.2.2:
Variables: Ty B Ty1 X B1 S
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT1 : host_is_tm B *
Ty : typeOf [] (abs X Ty1 B1) (arrowTy Ty1 Ty)
Ty1 : typeOf [] B Ty1
Ev1 : value (abs X Ty1 B1)
Ev2 : value B
IsAbs : is_string X
IsAbs1 : host_is_ty Ty1
IsAbs2 : host_is_tm B1 *
H1 : subst X B B1 S
============================
(exists T', eval (app (abs X Ty1 B1) B) T') \/ value (app (abs X Ty1 B1) B)
< search.
Subgoal 4:
Variables: Ty I
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
Ty : typeOf [] (num I) Ty
IsT : is_integer I
============================
(exists T', eval (num I) T') \/ value (num I)
< search.
Subgoal 5:
Variables: Ty B A
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
Ty : typeOf [] (plus A B) Ty
IsT : host_is_tm A *
IsT1 : host_is_tm B *
============================
(exists T', eval (plus A B) T') \/ value (plus A B)
< Ty: case Ty.
Subgoal 5:
Variables: B A
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A intTy
Ty1 : typeOf [] B intTy
============================
(exists T', eval (plus A B) T') \/ value (plus A B)
< Or1: apply IH to IsT Ty.
Subgoal 5:
Variables: B A
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A intTy
Ty1 : typeOf [] B intTy
Or1 : (exists T', eval A T') \/ value A
============================
(exists T', eval (plus A B) T') \/ value (plus A B)
< Or2: apply IH to IsT1 Ty1.
Subgoal 5:
Variables: B A
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A intTy
Ty1 : typeOf [] B intTy
Or1 : (exists T', eval A T') \/ value A
Or2 : (exists T', eval B T') \/ value B
============================
(exists T', eval (plus A B) T') \/ value (plus A B)
< Ev1: case Or1.
Subgoal 5.1:
Variables: B A T'
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A intTy
Ty1 : typeOf [] B intTy
Or2 : (exists T', eval B T') \/ value B
Ev1 : eval A T'
============================
(exists T', eval (plus A B) T') \/ value (plus A B)
< search.
Subgoal 5.2:
Variables: B A
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A intTy
Ty1 : typeOf [] B intTy
Or2 : (exists T', eval B T') \/ value B
Ev1 : value A
============================
(exists T', eval (plus A B) T') \/ value (plus A B)
< Ev2: case Or2.
Subgoal 5.2.1:
Variables: B A T'
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A intTy
Ty1 : typeOf [] B intTy
Ev1 : value A
Ev2 : eval B T'
============================
(exists T', eval (plus A B) T') \/ value (plus A B)
< search.
Subgoal 5.2.2:
Variables: B A
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm A *
IsT1 : host_is_tm B *
Ty : typeOf [] A intTy
Ty1 : typeOf [] B intTy
Ev1 : value A
Ev2 : value B
============================
(exists T', eval (plus A B) T') \/ value (plus A B)
< apply canonical_form_intTy to _ Ty.
Subgoal 5.2.2:
Variables: B I
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT : host_is_tm (num I) *
IsT1 : host_is_tm B *
Ty : typeOf [] (num I) intTy
Ty1 : typeOf [] B intTy
Ev1 : value (num I)
Ev2 : value B
============================
(exists T', eval (plus (num I) B) T') \/ value (plus (num I) B)
< Is1: case IsT.
Subgoal 5.2.2:
Variables: B I
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT1 : host_is_tm B *
Ty : typeOf [] (num I) intTy
Ty1 : typeOf [] B intTy
Ev1 : value (num I)
Ev2 : value B
Is1 : is_integer I
============================
(exists T', eval (plus (num I) B) T') \/ value (plus (num I) B)
< apply canonical_form_intTy to _ Ty1.
Subgoal 5.2.2:
Variables: I I1
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
IsT1 : host_is_tm (num I1) *
Ty : typeOf [] (num I) intTy
Ty1 : typeOf [] (num I1) intTy
Ev1 : value (num I)
Ev2 : value (num I1)
Is1 : is_integer I
============================
(exists T', eval (plus (num I) (num I1)) T') \/ value (plus (num I) (num I1))
< Is2: case IsT1.
Subgoal 5.2.2:
Variables: I I1
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
Ty : typeOf [] (num I) intTy
Ty1 : typeOf [] (num I1) intTy
Ev1 : value (num I)
Ev2 : value (num I1)
Is1 : is_integer I
Is2 : is_integer I1
============================
(exists T', eval (plus (num I) (num I1)) T') \/ value (plus (num I) (num I1))
< apply plus_integer_total to Is1 Is2.
Subgoal 5.2.2:
Variables: I I1 N3
IH : forall T Ty,
host_is_tm T * -> typeOf [] T Ty -> (exists T', eval T T') \/ value T
Ty : typeOf [] (num I) intTy
Ty1 : typeOf [] (num I1) intTy
Ev1 : value (num I)
Ev2 : value (num I1)
Is1 : is_integer I
Is2 : 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.
