< Module walkthrough:host.

 < Extensible_Theorem
      typeOf_unique : forall Ctx T TyA TyB,
         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, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
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, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
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, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
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, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
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

 < TyB: case TyB.

Subgoal 2:

Variables: Ctx Ty2 Ty1 Body X Ty4
IH : forall Ctx T TyA TyB, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
TyA : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty2) @
TyA1 : typeOf ((X, Ty1)::Ctx) Body Ty2 *
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, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
TyA : typeOf Ctx (abs X Ty1 Body) (arrowTy Ty1 Ty4) @
TyA1 : typeOf ((X, Ty1)::Ctx) Body Ty4 *
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, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
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

 < TyB: case TyB.

Subgoal 3:

Variables: Ctx TyA TyB Ty1 T2 T1 Ty2
IH : forall Ctx T TyA TyB, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
TyA : typeOf Ctx (app T1 T2) TyA @
TyA1 : typeOf Ctx T1 (arrowTy Ty1 TyA) *
TyA2 : typeOf Ctx T2 Ty1 *
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, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
TyA : typeOf Ctx (app T1 T2) TyB @
TyA1 : typeOf Ctx T1 (arrowTy Ty2 TyB) *
TyA2 : typeOf Ctx T2 Ty2 *
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, typeOf Ctx T TyA * -> typeOf Ctx T TyB -> TyA = TyB
TyA : typeOf Ctx (app T1 T2) TyB @
TyA1 : typeOf Ctx T1 (arrowTy Ty2 TyB) *
TyA2 : typeOf Ctx T2 Ty2 *
TyB : typeOf Ctx T1 (arrowTy Ty2 TyB)
TyB1 : typeOf Ctx T2 Ty2
============================
 TyB = TyB

 < 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.

Proof completed.

 < Theorem empty_ty_any :
     forall T Ty Ctx, typeOf [] T Ty -> typeOf Ctx T Ty.

============================
 forall T Ty Ctx, typeOf [] T Ty -> typeOf Ctx T Ty

 < intros T.

Variables: T Ty Ctx
T : typeOf [] T Ty
============================
 typeOf Ctx T Ty

 < backchain ty_lookup.

Variables: T Ty Ctx
T : typeOf [] T Ty
============================
 forall X XTy, lookup [] X XTy -> lookup Ctx X XTy

 < intros L.

Variables: T Ty Ctx X XTy
T : typeOf [] T Ty
L : lookup [] X XTy
============================
 lookup Ctx X XTy

 < case L.

Proof completed.

 < Extensible_Theorem
      subst_type_preservation : forall T Ctx X XTy Ty R S,
         TTy : typeOf ((X, XTy)::Ctx) T Ty ->
         S : subst X R T S ->
         RTy : typeOf [] R XTy ->
         typeOf Ctx S Ty
      on S.

Subgoal 1:

Variables: Ctx X XTy Ty R Y
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (var Y) Ty
S : subst X R (var Y) (var Y) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
============================
 typeOf Ctx (var Y) Ty

 < Ty: case TTy.

Subgoal 1:

Variables: Ctx X XTy Ty R Y
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (var Y) (var Y) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
Ty : lookup ((X, XTy)::Ctx) Y Ty
============================
 typeOf Ctx (var Y) Ty

 < Lkp: case Ty.

Subgoal 1.1:

Variables: Ctx Ty R Y
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst Y R (var Y) (var Y) @
RTy : typeOf [] R Ty
S1 : Y = Y -> false
============================
 typeOf Ctx (var Y) Ty

 < apply S1 to _.

Subgoal 1.2:

Variables: Ctx X XTy Ty R Y
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (var Y) (var Y) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
Lkp : X = Y -> false
Lkp1 : lookup Ctx Y Ty
============================
 typeOf Ctx (var Y) Ty

 < search.

Subgoal 2:

Variables: Ctx X XTy Ty S
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (var X) Ty
S : subst X S (var X) S @
RTy : typeOf [] S XTy
============================
 typeOf Ctx S Ty

 < Ty: case TTy.

Subgoal 2:

Variables: Ctx X XTy Ty S
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X S (var X) S @
RTy : typeOf [] S XTy
Ty : lookup ((X, XTy)::Ctx) X Ty
============================
 typeOf Ctx S Ty

 < L: case Ty.

Subgoal 2.1:

Variables: Ctx X Ty S
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X S (var X) S @
RTy : typeOf [] S Ty
============================
 typeOf Ctx S Ty

 < backchain empty_ty_any.

Subgoal 2.2:

Variables: Ctx X XTy Ty S
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X S (var X) S @
RTy : typeOf [] S XTy
L : X = X -> false
L1 : lookup Ctx X Ty
============================
 typeOf Ctx S Ty

 < apply L to _.

Subgoal 3:

Variables: Ctx X XTy Ty R S1 Ty1 Y B
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (abs Y Ty1 B) Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
============================
 typeOf Ctx (abs Y Ty1 S1) Ty

 < Ty: case TTy.

Subgoal 3:

Variables: Ctx X XTy R S1 Ty1 Y B Ty3
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
============================
 typeOf Ctx (abs Y Ty1 S1) (arrowTy Ty1 Ty3)

 < Ty': apply ty_lookup to Ty _ with
          Ctx2 = (X, XTy)::((Y, Ty1)::Ctx).

Subgoal 3.1:

Variables: Ctx X XTy R S1 Ty1 Y B Ty3
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
============================
 forall X1 XTy1,
   lookup ((Y, Ty1)::((X, XTy)::Ctx)) X1 XTy1 -> lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1

 < intros L.

Subgoal 3.1:

Variables: Ctx X XTy R S1 Ty1 Y B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
L : lookup ((Y, Ty1)::((X, XTy)::Ctx)) X1 XTy1
============================
 lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1

 < L: case L.

Subgoal 3.1.1:

Variables: Ctx X XTy R S1 B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X1 XTy1 B) (abs X1 XTy1 S1) @
RTy : typeOf [] R XTy
S1 : X = X1 -> false
S2 : subst X R B S1 *
Ty : typeOf ((X1, XTy1)::((X, XTy)::Ctx)) B Ty3
============================
 lookup ((X, XTy)::((X1, XTy1)::Ctx)) X1 XTy1

 < search.

Subgoal 3.1.2:

Variables: Ctx X XTy R S1 Ty1 Y B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
L : Y = X1 -> false
L1 : lookup ((X, XTy)::Ctx) X1 XTy1
============================
 lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1

 < L: case L1.

Subgoal 3.1.2.1:

Variables: Ctx R S1 Ty1 Y B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X1 R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy1
S1 : X1 = Y -> false
S2 : subst X1 R B S1 *
Ty : typeOf ((Y, Ty1)::((X1, XTy1)::Ctx)) B Ty3
L : Y = X1 -> false
============================
 lookup ((X1, XTy1)::((Y, Ty1)::Ctx)) X1 XTy1

 < search.

Subgoal 3.1.2.2:

Variables: Ctx X XTy R S1 Ty1 Y B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
L : Y = X1 -> false
L1 : X = X1 -> false
L2 : lookup Ctx X1 XTy1
============================
 lookup ((X, XTy)::((Y, Ty1)::Ctx)) X1 XTy1

 < search.

Subgoal 3:

Variables: Ctx X XTy R S1 Ty1 Y B Ty3
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
Ty' : typeOf ((X, XTy)::((Y, Ty1)::Ctx)) B Ty3
============================
 typeOf Ctx (abs Y Ty1 S1) (arrowTy Ty1 Ty3)

 < apply IH to Ty' S2 _.

Subgoal 3:

Variables: Ctx X XTy R S1 Ty1 Y B Ty3
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs Y Ty1 B) (abs Y Ty1 S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R B S1 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::Ctx)) B Ty3
Ty' : typeOf ((X, XTy)::((Y, Ty1)::Ctx)) B Ty3
H1 : typeOf ((Y, Ty1)::Ctx) S1 Ty3
============================
 typeOf Ctx (abs Y Ty1 S1) (arrowTy Ty1 Ty3)

 < search.

Subgoal 4:

Variables: Ctx X XTy Ty R B Ty1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (abs X Ty1 B) Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
============================
 typeOf Ctx (abs X Ty1 B) Ty

 < Ty: case TTy.

Subgoal 4:

Variables: Ctx X XTy R B Ty1 Ty3
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
============================
 typeOf Ctx (abs X Ty1 B) (arrowTy Ty1 Ty3)

 < apply ty_lookup to Ty _ with
     Ctx2 = (X, Ty1)::Ctx.

Subgoal 4.1:

Variables: Ctx X XTy R B Ty1 Ty3
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
============================
 forall X1 XTy1,
   lookup ((X, Ty1)::((X, XTy)::Ctx)) X1 XTy1 -> lookup ((X, Ty1)::Ctx) X1 XTy1

 < intros L.

Subgoal 4.1:

Variables: Ctx X XTy R B Ty1 Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
L : lookup ((X, Ty1)::((X, XTy)::Ctx)) X1 XTy1
============================
 lookup ((X, Ty1)::Ctx) X1 XTy1

 < L: case L.

Subgoal 4.1.1:

Variables: Ctx XTy R B Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X1 R (abs X1 XTy1 B) (abs X1 XTy1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X1, XTy1)::((X1, XTy)::Ctx)) B Ty3
============================
 lookup ((X1, XTy1)::Ctx) X1 XTy1

 < search.

Subgoal 4.1.2:

Variables: Ctx X XTy R B Ty1 Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
L : X = X1 -> false
L1 : lookup ((X, XTy)::Ctx) X1 XTy1
============================
 lookup ((X, Ty1)::Ctx) X1 XTy1

 < L: case L1.

Subgoal 4.1.2.1:

Variables: Ctx R B Ty1 Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X1 R (abs X1 Ty1 B) (abs X1 Ty1 B) @
RTy : typeOf [] R XTy1
Ty : typeOf ((X1, Ty1)::((X1, XTy1)::Ctx)) B Ty3
L : X1 = X1 -> false
============================
 lookup ((X1, Ty1)::Ctx) X1 XTy1

 < apply L to _.

Subgoal 4.1.2.2:

Variables: Ctx X XTy R B Ty1 Ty3 X1 XTy1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
L : X = X1 -> false
L1 : X = X1 -> false
L2 : lookup Ctx X1 XTy1
============================
 lookup ((X, Ty1)::Ctx) X1 XTy1

 < search.

Subgoal 4:

Variables: Ctx X XTy R B Ty1 Ty3
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (abs X Ty1 B) (abs X Ty1 B) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::Ctx)) B Ty3
H1 : typeOf ((X, Ty1)::Ctx) B Ty3
============================
 typeOf Ctx (abs X Ty1 B) (arrowTy Ty1 Ty3)

 < search.

Subgoal 5:

Variables: Ctx X XTy Ty R S2 S1 T2 T1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
TTy : typeOf ((X, XTy)::Ctx) (app T1 T2) Ty
S : subst X R (app T1 T2) (app S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
============================
 typeOf Ctx (app S1 S2) Ty

 < Ty: case TTy.

Subgoal 5:

Variables: Ctx X XTy Ty R S2 S1 T2 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (app T1 T2) (app S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 (arrowTy Ty1 Ty)
Ty1 : typeOf ((X, XTy)::Ctx) T2 Ty1
============================
 typeOf Ctx (app S1 S2) Ty

 < apply IH to Ty S1 _.

Subgoal 5:

Variables: Ctx X XTy Ty R S2 S1 T2 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (app T1 T2) (app S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 (arrowTy Ty1 Ty)
Ty1 : typeOf ((X, XTy)::Ctx) T2 Ty1
H1 : typeOf Ctx S1 (arrowTy Ty1 Ty)
============================
 typeOf Ctx (app S1 S2) Ty

 < apply IH to Ty1 S2 _.

Subgoal 5:

Variables: Ctx X XTy Ty R S2 S1 T2 T1 Ty1
IH : forall T Ctx X XTy Ty R S,
       typeOf ((X, XTy)::Ctx) T Ty -> subst X R T S * -> typeOf [] R XTy -> typeOf Ctx S Ty
S : subst X R (app T1 T2) (app S1 S2) @
RTy : typeOf [] R XTy
S1 : subst X R T1 S1 *
S2 : subst X R T2 S2 *
Ty : typeOf ((X, XTy)::Ctx) T1 (arrowTy Ty1 Ty)
Ty1 : typeOf ((X, XTy)::Ctx) T2 Ty1
H1 : typeOf Ctx S1 (arrowTy Ty1 Ty)
H2 : typeOf Ctx S2 Ty1
============================
 typeOf Ctx (app S1 S2) Ty

 < search.

Proof completed.

 < Extensible_Theorem
      type_preservation : forall T Ty T',
         Ty : typeOf [] T Ty ->
         Ev : eval T T' ->
         typeOf [] T' Ty
      on Ev.

Subgoal 1:

Variables: Ty T2 T11 T1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (app T1 T2) Ty
Ev : eval (app T1 T2) (app T11 T2) @
Ev1 : eval T1 T11 *
============================
 typeOf [] (app T11 T2) Ty

 < Ty: case Ty.

Subgoal 1:

Variables: Ty T2 T11 T1 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app T1 T2) (app T11 T2) @
Ev1 : eval T1 T11 *
Ty : typeOf [] T1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] T2 Ty1
============================
 typeOf [] (app T11 T2) Ty

 < apply IH to Ty Ev1.

Subgoal 1:

Variables: Ty T2 T11 T1 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app T1 T2) (app T11 T2) @
Ev1 : eval T1 T11 *
Ty : typeOf [] T1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] T2 Ty1
H1 : typeOf [] T11 (arrowTy Ty1 Ty)
============================
 typeOf [] (app T11 T2) Ty

 < search.

Subgoal 2:

Variables: Ty T21 T1 T2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (app T1 T2) Ty
Ev : eval (app T1 T2) (app T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
============================
 typeOf [] (app T1 T21) Ty

 < Ty: case Ty.

Subgoal 2:

Variables: Ty T21 T1 T2 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app T1 T2) (app T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Ty : typeOf [] T1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] T2 Ty1
============================
 typeOf [] (app T1 T21) Ty

 < apply IH to Ty1 Ev2.

Subgoal 2:

Variables: Ty T21 T1 T2 Ty1
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app T1 T2) (app T1 T21) @
Ev1 : value T1
Ev2 : eval T2 T21 *
Ty : typeOf [] T1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] T2 Ty1
H1 : typeOf [] T21 Ty1
============================
 typeOf [] (app T1 T21) Ty

 < search.

Subgoal 3:

Variables: Ty T' T2 Body Ty1 X
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ty : typeOf [] (app (abs X Ty1 Body) T2) Ty
Ev : eval (app (abs X Ty1 Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
============================
 typeOf [] T' Ty

 < Ty: case Ty.

Subgoal 3:

Variables: Ty T' T2 Body Ty1 X Ty2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app (abs X Ty1 Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
Ty : typeOf [] (abs X Ty1 Body) (arrowTy Ty2 Ty)
Ty1 : typeOf [] T2 Ty2
============================
 typeOf [] T' Ty

 < Ty: case Ty.

Subgoal 3:

Variables: Ty T' T2 Body X Ty2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app (abs X Ty2 Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
Ty1 : typeOf [] T2 Ty2
Ty : typeOf [(X, Ty2)] Body Ty
============================
 typeOf [] T' Ty

 < apply subst_type_preservation to Ty Ev2 Ty1.

Subgoal 3:

Variables: Ty T' T2 Body X Ty2
IH : forall T Ty T', typeOf [] T Ty -> eval T T' * -> typeOf [] T' Ty
Ev : eval (app (abs X Ty2 Body) T2) T' @
Ev1 : value T2
Ev2 : subst X T2 Body T'
Ty1 : typeOf [] T2 Ty2
Ty : typeOf [(X, Ty2)] Body Ty
H1 : typeOf [] T' Ty
============================
 typeOf [] T' Ty

 < search.

Proof completed.

 < Projection_Constraint proj_type_same :
   forall G T Ty T_T,
   G |{tm}- T ~~> T_T -> typeOf G T Ty -> typeOf G T_T Ty.

Proof completed.

 < Ext_Size eval T T'.

Proof completed.

 < Proj_Rel eval T T'.

Proof completed.

 < Ext_Ind forall G T T' Ty, eval T T' with Ty : typeOf G T Ty.

Subgoal 1:

Variables: N G Ty T2 T11 T1
IH : forall N G T T' Ty,
       <eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
        <eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (app T1 T2) (app T11 T2) N @@
Acc : acc N @
Ty : typeOf G (app T1 T2) Ty
R1 : <eval {ES}> T1 T11 N **
============================
 <eval {P}> (app T1 T2) (app T11 T2)

 < Ty: case Ty.

Subgoal 1:

Variables: N G Ty T2 T11 T1 Ty1
IH : forall N G T T' Ty,
       <eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
        <eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (app T1 T2) (app T11 T2) N @@
Acc : acc N @
R1 : <eval {ES}> T1 T11 N **
Ty : typeOf G T1 (arrowTy Ty1 Ty)
Ty1 : typeOf G T2 Ty1
============================
 <eval {P}> (app T1 T2) (app T11 T2)

 < apply IH1 to R1 Acc Ty.

Subgoal 1:

Variables: N G Ty T2 T11 T1 Ty1
IH : forall N G T T' Ty,
       <eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
        <eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (app T1 T2) (app T11 T2) N @@
Acc : acc N @
R1 : <eval {ES}> T1 T11 N **
Ty : typeOf G T1 (arrowTy Ty1 Ty)
Ty1 : typeOf G T2 Ty1
H1 : <eval {P}> T1 T11
============================
 <eval {P}> (app T1 T2) (app T11 T2)

 < search.

Subgoal 2:

Variables: N G Ty T21 T1 T2
IH : forall N G T T' Ty,
       <eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
        <eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (app T1 T2) (app T1 T21) N @@
Acc : acc N @
Ty : typeOf G (app T1 T2) Ty
R1 : value T1
R2 : <eval {ES}> T2 T21 N **
============================
 <eval {P}> (app T1 T2) (app T1 T21)

 < Ty: case Ty.

Subgoal 2:

Variables: N G Ty T21 T1 T2 Ty1
IH : forall N G T T' Ty,
       <eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
        <eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (app T1 T2) (app T1 T21) N @@
Acc : acc N @
R1 : value T1
R2 : <eval {ES}> T2 T21 N **
Ty : typeOf G T1 (arrowTy Ty1 Ty)
Ty1 : typeOf G T2 Ty1
============================
 <eval {P}> (app T1 T2) (app T1 T21)

 < apply IH1 to R2 Acc Ty1.

Subgoal 2:

Variables: N G Ty T21 T1 T2 Ty1
IH : forall N G T T' Ty,
       <eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
        <eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (app T1 T2) (app T1 T21) N @@
Acc : acc N @
R1 : value T1
R2 : <eval {ES}> T2 T21 N **
Ty : typeOf G T1 (arrowTy Ty1 Ty)
Ty1 : typeOf G T2 Ty1
H1 : <eval {P}> T2 T21
============================
 <eval {P}> (app T1 T2) (app T1 T21)

 < search.

Subgoal 3:

Variables: G T' Ty T2 Body Ty1 X
IH : forall N G T T' Ty,
       <eval {ES}> T T' N -> acc N * -> typeOf G T Ty -> <eval {P}> T T'
IH1 : forall N G T T' Ty,
        <eval {ES}> T T' N ** -> acc N @ -> typeOf G T Ty -> <eval {P}> T T'
R : <eval {ES}> (app (abs X Ty1 Body) T2) T' 0 @@
Acc : acc 0 @
Ty : typeOf G (app (abs X Ty1 Body) T2) Ty
R1 : value T2
R2 : subst X T2 Body T'
============================
 <eval {P}> (app (abs X Ty1 Body) T2) T'

 < search.

Proof completed.

Back to example home