< Module mtc:lambda.

 < Theorem typeOfCtx_lookups :
     forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty -> lookup EG X V -> valueType V Ty.

============================
 forall TG EG X Ty V,
   typeOfCtx TG EG -> lookup TG X Ty -> lookup EG X V -> valueType V Ty

 < induction on 2.

IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
============================
 forall TG EG X Ty V,
   typeOfCtx TG EG -> lookup TG X Ty @ -> lookup EG X V -> valueType V Ty

 < intros TOC LT LV.

Variables: TG EG X Ty V
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
TOC : typeOfCtx TG EG
LT : lookup TG X Ty @
LV : lookup EG X V
============================
 valueType V Ty

 < LT: case LT.

Subgoal 1:

Variables: EG X Ty V Rest
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
TOC : typeOfCtx ((X, Ty)::Rest) EG
LV : lookup EG X V
============================
 valueType V Ty

 < LV: case LV.

Subgoal 1.1:

Variables: X Ty V Rest Rest1
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
TOC : typeOfCtx ((X, Ty)::Rest) ((X, V)::Rest1)
============================
 valueType V Ty

 < case TOC.

Subgoal 1.1:

Variables: X Ty V Rest Rest1
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
H1 : valueType V Ty
H2 : typeOfCtx Rest Rest1
============================
 valueType V Ty

 < search.

Subgoal 1.2:

Variables: X Ty V Rest Rest1 V1 K
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
TOC : typeOfCtx ((X, Ty)::Rest) ((K, V1)::Rest1)
LV : K = X -> false
LV1 : lookup Rest1 X V
============================
 valueType V Ty

 < case TOC.

Subgoal 1.2:

Variables: Ty V Rest Rest1 V1 K
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
LV : K = K -> false
LV1 : lookup Rest1 K V
H1 : valueType V1 Ty
H2 : typeOfCtx Rest Rest1
============================
 valueType V Ty

 < apply LV to _.

Subgoal 2:

Variables: EG X Ty V Rest V1 K
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
TOC : typeOfCtx ((K, V1)::Rest) EG
LV : lookup EG X V
LT : K = X -> false
LT1 : lookup Rest X Ty *
============================
 valueType V Ty

 < LV: case LV.

Subgoal 2.1:

Variables: X Ty V Rest V1 K Rest1
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
TOC : typeOfCtx ((K, V1)::Rest) ((X, V)::Rest1)
LT : K = X -> false
LT1 : lookup Rest X Ty *
============================
 valueType V Ty

 < case TOC.

Subgoal 2.1:

Variables: X Ty V Rest V1 Rest1
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
LT : X = X -> false
LT1 : lookup Rest X Ty *
H1 : valueType V V1
H2 : typeOfCtx Rest Rest1
============================
 valueType V Ty

 < apply LT to _.

Subgoal 2.2:

Variables: X Ty V Rest V1 K Rest1 V2 K1
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
TOC : typeOfCtx ((K, V1)::Rest) ((K1, V2)::Rest1)
LT : K = X -> false
LT1 : lookup Rest X Ty *
LV : K1 = X -> false
LV1 : lookup Rest1 X V
============================
 valueType V Ty

 < TOC: case TOC.

Subgoal 2.2:

Variables: X Ty V Rest V1 Rest1 V2 K1
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
LT : K1 = X -> false
LT1 : lookup Rest X Ty *
LV : K1 = X -> false
LV1 : lookup Rest1 X V
TOC : valueType V2 V1
TOC1 : typeOfCtx Rest Rest1
============================
 valueType V Ty

 < apply IH to _ LT1 LV1.

Subgoal 2.2:

Variables: X Ty V Rest V1 Rest1 V2 K1
IH : forall TG EG X Ty V,
       typeOfCtx TG EG -> lookup TG X Ty * -> lookup EG X V -> valueType V Ty
LT : K1 = X -> false
LT1 : lookup Rest X Ty *
LV : K1 = X -> false
LV1 : lookup Rest1 X V
TOC : valueType V2 V1
TOC1 : typeOfCtx Rest Rest1
H1 : valueType V Ty
============================
 valueType V Ty

 < search.

Proof completed.

 < Prove mtc:shared_declarations:type_preservation.

Subgoal 1:

Variables: TG Ty EG E1 X Ty1
IH : forall TG E Ty EG V,
       typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ty : typeOf TG (abs X Ty1 E1) Ty
Ev : eval EG (abs X Ty1 E1) (closure EG X E1) @
============================
 valueType (closure EG X E1) Ty

 < case Ty.

Subgoal 1:

Variables: TG EG E1 X Ty1 Ty3
IH : forall TG E Ty EG V,
       typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (abs X Ty1 E1) (closure EG X E1) @
H1 : typeOf ((X, Ty1)::TG) E1 Ty3
============================
 valueType (closure EG X E1) (arrowTy Ty1 Ty3)

 < search.

Subgoal 2:

Variables: TG Ty EG V GC X Body V2 E2 E1
IH : forall TG E Ty EG V,
       typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ty : typeOf TG (app E1 E2) Ty
Ev : eval EG (app E1 E2) V @
Ev1 : eval EG E1 (closure GC X Body) *
Ev2 : eval EG E2 V2 *
Ev3 : eval ((X, V2)::GC) Body V *
============================
 valueType V Ty

 < Ty: case Ty.

Subgoal 2:

Variables: TG Ty EG V GC X Body V2 E2 E1 Ty1
IH : forall TG E Ty EG V,
       typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (app E1 E2) V @
Ev1 : eval EG E1 (closure GC X Body) *
Ev2 : eval EG E2 V2 *
Ev3 : eval ((X, V2)::GC) Body V *
Ty : typeOf TG E1 (arrowTy Ty1 Ty)
Ty1 : typeOf TG E2 Ty1
============================
 valueType V Ty

 < VT1: apply IH to _ Ty Ev1.

Subgoal 2:

Variables: TG Ty EG V GC X Body V2 E2 E1 Ty1
IH : forall TG E Ty EG V,
       typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (app E1 E2) V @
Ev1 : eval EG E1 (closure GC X Body) *
Ev2 : eval EG E2 V2 *
Ev3 : eval ((X, V2)::GC) Body V *
Ty : typeOf TG E1 (arrowTy Ty1 Ty)
Ty1 : typeOf TG E2 Ty1
VT1 : valueType (closure GC X Body) (arrowTy Ty1 Ty)
============================
 valueType V Ty

 < VT2: apply IH to _ Ty1 Ev2.

Subgoal 2:

Variables: TG Ty EG V GC X Body V2 E2 E1 Ty1
IH : forall TG E Ty EG V,
       typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (app E1 E2) V @
Ev1 : eval EG E1 (closure GC X Body) *
Ev2 : eval EG E2 V2 *
Ev3 : eval ((X, V2)::GC) Body V *
Ty : typeOf TG E1 (arrowTy Ty1 Ty)
Ty1 : typeOf TG E2 Ty1
VT1 : valueType (closure GC X Body) (arrowTy Ty1 Ty)
VT2 : valueType V2 Ty1
============================
 valueType V Ty

 < VTC: case VT1.

Subgoal 2:

Variables: TG Ty EG V GC X Body V2 E2 E1 Ty1 TG1
IH : forall TG E Ty EG V,
       typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (app E1 E2) V @
Ev1 : eval EG E1 (closure GC X Body) *
Ev2 : eval EG E2 V2 *
Ev3 : eval ((X, V2)::GC) Body V *
Ty : typeOf TG E1 (arrowTy Ty1 Ty)
Ty1 : typeOf TG E2 Ty1
VT2 : valueType V2 Ty1
VTC : typeOfCtx TG1 GC
VTC1 : typeOf ((X, Ty1)::TG1) Body Ty
============================
 valueType V Ty

 < apply IH to _ VTC1 Ev3.

Subgoal 2:

Variables: TG Ty EG V GC X Body V2 E2 E1 Ty1 TG1
IH : forall TG E Ty EG V,
       typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (app E1 E2) V @
Ev1 : eval EG E1 (closure GC X Body) *
Ev2 : eval EG E2 V2 *
Ev3 : eval ((X, V2)::GC) Body V *
Ty : typeOf TG E1 (arrowTy Ty1 Ty)
Ty1 : typeOf TG E2 Ty1
VT2 : valueType V2 Ty1
VTC : typeOfCtx TG1 GC
VTC1 : typeOf ((X, Ty1)::TG1) Body Ty
H1 : valueType V Ty
============================
 valueType V Ty

 < search.

Subgoal 3:

Variables: TG Ty EG V X
IH : forall TG E Ty EG V,
       typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ty : typeOf TG (var X) Ty
Ev : eval EG (var X) V @
Ev1 : lookup EG X V
============================
 valueType V Ty

 < Ty: case Ty.

Subgoal 3:

Variables: TG Ty EG V X
IH : forall TG E Ty EG V,
       typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (var X) V @
Ev1 : lookup EG X V
Ty : lookup TG X Ty
============================
 valueType V Ty

 < apply typeOfCtx_lookups to _ Ty Ev1.

Subgoal 3:

Variables: TG Ty EG V X
IH : forall TG E Ty EG V,
       typeOfCtx TG EG -> typeOf TG E Ty -> eval EG E V * -> valueType V Ty
Rel : typeOfCtx TG EG
Ev : eval EG (var X) V @
Ev1 : lookup EG X V
Ty : lookup TG X Ty
H1 : valueType V Ty
============================
 valueType V Ty

 < search.

Proof completed.

 < Prove mtc:shared_declarations:value_evalStep_false.

Subgoal 1:

Variables: E' E1 Ty X
IH : forall E E', value E * -> evalStep E E' -> false
V : value (abs X Ty E1) @
Ev : evalStep (abs X Ty E1) E'
============================
 false

 < case Ev.

Proof completed.

 < Prove mtc:shared_declarations:subst_unique.

Subgoal 1:

Variables: X R EB E1 Ty
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (abs X Ty E1) (abs X Ty E1) @
SB : subst X R (abs X Ty E1) EB
============================
 abs X Ty E1 = EB

 < SB: case SB.

Subgoal 1.1:

Variables: X R E1 Ty
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (abs X Ty E1) (abs X Ty E1) @
============================
 abs X Ty E1 = abs X Ty E1

 < search.

Subgoal 1.2:

Variables: X R E1 Ty E3
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (abs X Ty E1) (abs X Ty E1) @
SB : X = X -> false
SB1 : subst X R E1 E3
============================
 abs X Ty E1 = abs X Ty E3

 < apply SB to _.

Subgoal 2:

Variables: X R EB E2 Ty Y E1
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (abs Y Ty E1) (abs Y Ty E2) @
SB : subst X R (abs Y Ty E1) EB
SA1 : X = Y -> false
SA2 : subst X R E1 E2 *
============================
 abs Y Ty E2 = EB

 < SB: case SB.

Subgoal 2.1:

Variables: R E2 Ty Y E1
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst Y R (abs Y Ty E1) (abs Y Ty E2) @
SA1 : Y = Y -> false
SA2 : subst Y R E1 E2 *
============================
 abs Y Ty E2 = abs Y Ty E1

 < apply SA1 to _.

Subgoal 2.2:

Variables: X R E2 Ty Y E1 E4
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (abs Y Ty E1) (abs Y Ty E2) @
SA1 : X = Y -> false
SA2 : subst X R E1 E2 *
SB : X = Y -> false
SB1 : subst X R E1 E4
============================
 abs Y Ty E2 = abs Y Ty E4

 < apply IH to SA2 SB1.

Subgoal 2.2:

Variables: X R Ty Y E1 E4
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (abs Y Ty E1) (abs Y Ty E4) @
SA1 : X = Y -> false
SA2 : subst X R E1 E4 *
SB : X = Y -> false
SB1 : subst X R E1 E4
============================
 abs Y Ty E4 = abs Y Ty E4

 < search.

Subgoal 3:

Variables: X R EB E21 E11 E2 E1
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (app E1 E2) (app E11 E21) @
SB : subst X R (app E1 E2) EB
SA1 : subst X R E1 E11 *
SA2 : subst X R E2 E21 *
============================
 app E11 E21 = EB

 < SB: case SB.

Subgoal 3:

Variables: X R E21 E11 E2 E1 E6 E5
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (app E1 E2) (app E11 E21) @
SA1 : subst X R E1 E11 *
SA2 : subst X R E2 E21 *
SB : subst X R E1 E5
SB1 : subst X R E2 E6
============================
 app E11 E21 = app E5 E6

 < apply IH to SA1 SB.

Subgoal 3:

Variables: X R E21 E2 E1 E6 E5
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (app E1 E2) (app E5 E21) @
SA1 : subst X R E1 E5 *
SA2 : subst X R E2 E21 *
SB : subst X R E1 E5
SB1 : subst X R E2 E6
============================
 app E5 E21 = app E5 E6

 < apply IH to SA2 SB1.

Subgoal 3:

Variables: X R E2 E1 E6 E5
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (app E1 E2) (app E5 E6) @
SA1 : subst X R E1 E5 *
SA2 : subst X R E2 E6 *
SB : subst X R E1 E5
SB1 : subst X R E2 E6
============================
 app E5 E6 = app E5 E6

 < search.

Subgoal 4:

Variables: X EA EB
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X EA (var X) EA @
SB : subst X EA (var X) EB
============================
 EA = EB

 < SB: case SB.

Subgoal 4.1:

Variables: X EB
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X EB (var X) EB @
============================
 EB = EB

 < search.

Subgoal 4.2:

Variables: X EA
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X EA (var X) EA @
SB : X = X -> false
============================
 EA = var X

 < apply SB to _.

Subgoal 5:

Variables: X R EB Y
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (var Y) (var Y) @
SB : subst X R (var Y) EB
SA1 : X = Y -> false
============================
 var Y = EB

 < SB: case SB.

Subgoal 5.1:

Variables: EB Y
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst Y EB (var Y) (var Y) @
SA1 : Y = Y -> false
============================
 var Y = EB

 < apply SA1 to _.

Subgoal 5.2:

Variables: X R Y
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (var Y) (var Y) @
SA1 : X = Y -> false
SB : X = Y -> false
============================
 var Y = var Y

 < search.

Proof completed.

 < Prove mtc:shared_declarations:evalStep_unique.

Subgoal 1:

Variables: EB E2 E11 E1
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app E1 E2) (app E11 E2) @
EvB : evalStep (app E1 E2) EB
EvA1 : evalStep E1 E11 *
============================
 app E11 E2 = EB

 < EvB: case EvB.

Subgoal 1.1:

Variables: E2 E11 E1 E5
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app E1 E2) (app E11 E2) @
EvA1 : evalStep E1 E11 *
EvB : evalStep E1 E5
============================
 app E11 E2 = app E5 E2

 < apply IH to EvA1 EvB.

Subgoal 1.1:

Variables: E2 E1 E5
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app E1 E2) (app E5 E2) @
EvA1 : evalStep E1 E5 *
EvB : evalStep E1 E5
============================
 app E5 E2 = app E5 E2

 < search.

Subgoal 1.2:

Variables: E2 E11 E1 E21
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app E1 E2) (app E11 E2) @
EvA1 : evalStep E1 E11 *
EvB : value E1
EvB1 : evalStep E2 E21
============================
 app E11 E2 = app E1 E21

 < apply value_evalStep_false to EvB EvA1.

Subgoal 1.3:

Variables: EB E2 E11 E3 Ty X
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app (abs X Ty E3) E2) (app E11 E2) @
EvA1 : evalStep (abs X Ty E3) E11 *
EvB : value E2
EvB1 : subst X E2 E3 EB
============================
 app E11 E2 = EB

 < case EvA1.

Subgoal 2:

Variables: EB E21 E1 E2
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app E1 E2) (app E1 E21) @
EvB : evalStep (app E1 E2) EB
EvA1 : value E1
EvA2 : evalStep E2 E21 *
============================
 app E1 E21 = EB

 < EvB: case EvB.

Subgoal 2.1:

Variables: E21 E1 E2 E11
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app E1 E2) (app E1 E21) @
EvA1 : value E1
EvA2 : evalStep E2 E21 *
EvB : evalStep E1 E11
============================
 app E1 E21 = app E11 E2

 < apply value_evalStep_false to EvA1 EvB.

Subgoal 2.2:

Variables: E21 E1 E2 E5
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app E1 E2) (app E1 E21) @
EvA1 : value E1
EvA2 : evalStep E2 E21 *
EvB : value E1
EvB1 : evalStep E2 E5
============================
 app E1 E21 = app E1 E5

 < apply IH to EvA2 EvB1.

Subgoal 2.2:

Variables: E1 E2 E5
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app E1 E2) (app E1 E5) @
EvA1 : value E1
EvA2 : evalStep E2 E5 *
EvB : value E1
EvB1 : evalStep E2 E5
============================
 app E1 E5 = app E1 E5

 < search.

Subgoal 2.3:

Variables: EB E21 E2 E3 Ty X
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app (abs X Ty E3) E2) (app (abs X Ty E3) E21) @
EvA1 : value (abs X Ty E3)
EvA2 : evalStep E2 E21 *
EvB : value E2
EvB1 : subst X E2 E3 EB
============================
 app (abs X Ty E3) E21 = EB

 < apply value_evalStep_false to EvB EvA2.

Subgoal 3:

Variables: EA EB E2 E1 Ty X
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app (abs X Ty E1) E2) EA @
EvB : evalStep (app (abs X Ty E1) E2) EB
EvA1 : value E2
EvA2 : subst X E2 E1 EA
============================
 EA = EB

 < EvB: case EvB.

Subgoal 3.1:

Variables: EA E2 E1 Ty X E11
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app (abs X Ty E1) E2) EA @
EvA1 : value E2
EvA2 : subst X E2 E1 EA
EvB : evalStep (abs X Ty E1) E11
============================
 EA = app E11 E2

 < case EvB.

Subgoal 3.2:

Variables: EA E2 E1 Ty X E21
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app (abs X Ty E1) E2) EA @
EvA1 : value E2
EvA2 : subst X E2 E1 EA
EvB : value (abs X Ty E1)
EvB1 : evalStep E2 E21
============================
 EA = app (abs X Ty E1) E21

 < apply value_evalStep_false to EvA1 EvB1.

Subgoal 3.3:

Variables: EA EB E2 E1 Ty X
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app (abs X Ty E1) E2) EA @
EvA1 : value E2
EvA2 : subst X E2 E1 EA
EvB : value E2
EvB1 : subst X E2 E1 EB
============================
 EA = EB

 < apply subst_unique to EvA2 EvB1.

Subgoal 3.3:

Variables: EB E2 E1 Ty X
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (app (abs X Ty E1) E2) EB @
EvA1 : value E2
EvA2 : subst X E2 E1 EB
EvB : value E2
EvB1 : subst X E2 E1 EB
============================
 EB = EB

 < search.

Proof completed.

 < Prove mtc:shared_declarations:ty_lookup.

Subgoal 1:

Variables: G1 G2 Ty2 Ty1 E1 X
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (abs X Ty1 E1) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf ((X, Ty1)::G1) E1 Ty2 *
============================
 typeOf G2 (abs X Ty1 E1) (arrowTy Ty1 Ty2)

 < apply IH to Ty1 _ with
     G2 = (X, Ty1)::G2.

Subgoal 1.1:

Variables: G1 G2 Ty2 Ty1 E1 X
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (abs X Ty1 E1) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf ((X, Ty1)::G1) E1 Ty2 *
============================
 forall X1 XTy, lookup ((X, Ty1)::G1) X1 XTy -> lookup ((X, Ty1)::G2) X1 XTy

 < intros L'.

Subgoal 1.1:

Variables: G1 G2 Ty2 Ty1 E1 X X1 XTy
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (abs X Ty1 E1) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf ((X, Ty1)::G1) E1 Ty2 *
L' : lookup ((X, Ty1)::G1) X1 XTy
============================
 lookup ((X, Ty1)::G2) X1 XTy

 < L': case L'.

Subgoal 1.1.1:

Variables: G1 G2 Ty2 E1 X1 XTy
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (abs X1 XTy E1) (arrowTy XTy Ty2) @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf ((X1, XTy)::G1) E1 Ty2 *
============================
 lookup ((X1, XTy)::G2) X1 XTy

 < search.

Subgoal 1.1.2:

Variables: G1 G2 Ty2 Ty1 E1 X X1 XTy
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (abs X Ty1 E1) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf ((X, Ty1)::G1) E1 Ty2 *
L' : X = X1 -> false
L'1 : lookup G1 X1 XTy
============================
 lookup ((X, Ty1)::G2) X1 XTy

 < apply L to L'1.

Subgoal 1.1.2:

Variables: G1 G2 Ty2 Ty1 E1 X X1 XTy
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (abs X Ty1 E1) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf ((X, Ty1)::G1) E1 Ty2 *
L' : X = X1 -> false
L'1 : lookup G1 X1 XTy
H1 : lookup G2 X1 XTy
============================
 lookup ((X, Ty1)::G2) X1 XTy

 < search.

Subgoal 1:

Variables: G1 G2 Ty2 Ty1 E1 X
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (abs X Ty1 E1) (arrowTy Ty1 Ty2) @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf ((X, Ty1)::G1) E1 Ty2 *
H1 : typeOf ((X, Ty1)::G2) E1 Ty2
============================
 typeOf G2 (abs X Ty1 E1) (arrowTy Ty1 Ty2)

 < search.

Subgoal 2:

Variables: G1 G2 Ty Ty1 E2 E1
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (app E1 E2) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf G1 E2 Ty1 *
============================
 typeOf G2 (app E1 E2) Ty

 < apply IH to Ty1 L.

Subgoal 2:

Variables: G1 G2 Ty Ty1 E2 E1
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (app E1 E2) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf G1 E2 Ty1 *
H1 : typeOf G2 E1 (arrowTy Ty1 Ty)
============================
 typeOf G2 (app E1 E2) Ty

 < apply IH to Ty2 L.

Subgoal 2:

Variables: G1 G2 Ty Ty1 E2 E1
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (app E1 E2) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf G1 E2 Ty1 *
H1 : typeOf G2 E1 (arrowTy Ty1 Ty)
H2 : typeOf G2 E2 Ty1
============================
 typeOf G2 (app E1 E2) Ty

 < search.

Subgoal 3:

Variables: G1 G2 Ty X
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (var X) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : lookup G1 X Ty
============================
 typeOf G2 (var X) Ty

 < apply L to Ty1.

Subgoal 3:

Variables: G1 G2 Ty X
IH : forall G1 G2 E Ty,
       typeOf G1 E Ty * -> (forall X XTy, lookup G1 X XTy -> lookup G2 X XTy) ->
       typeOf G2 E Ty
Ty : typeOf G1 (var X) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : lookup G1 X Ty
H1 : lookup G2 X Ty
============================
 typeOf G2 (var X) Ty

 < search.

Proof completed.

 < Prove mtc:shared_declarations:subst_preservation.

Subgoal 1:

Variables: X XTy TG Ty R E1 Ty1
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
Ty : typeOf ((X, XTy)::TG) (abs X Ty1 E1) Ty
S : subst X R (abs X Ty1 E1) (abs X Ty1 E1) @
RTy : typeOf [] R XTy
============================
 typeOf TG (abs X Ty1 E1) Ty

 < Ty: case Ty.

Subgoal 1:

Variables: X XTy TG R E1 Ty1 Ty3
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (abs X Ty1 E1) (abs X Ty1 E1) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::TG)) E1 Ty3
============================
 typeOf TG (abs X Ty1 E1) (arrowTy Ty1 Ty3)

 < apply ty_lookup to Ty _ with
     G2 = (X, Ty1)::TG.

Subgoal 1.1:

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

 < intros L.

Subgoal 1.1:

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

 < L: case L.

Subgoal 1.1.1:

Variables: XTy TG R E1 Ty3 X1 XTy1
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X1 R (abs X1 XTy1 E1) (abs X1 XTy1 E1) @
RTy : typeOf [] R XTy
Ty : typeOf ((X1, XTy1)::((X1, XTy)::TG)) E1 Ty3
============================
 lookup ((X1, XTy1)::TG) X1 XTy1

 < search.

Subgoal 1.1.2:

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

 < L': case L1.

Subgoal 1.1.2.1:

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

 < apply L to _.

Subgoal 1.1.2.2:

Variables: X XTy TG R E1 Ty1 Ty3 X1 XTy1
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (abs X Ty1 E1) (abs X Ty1 E1) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::TG)) E1 Ty3
L : X = X1 -> false
L' : X = X1 -> false
L'1 : lookup TG X1 XTy1
============================
 lookup ((X, Ty1)::TG) X1 XTy1

 < search.

Subgoal 1:

Variables: X XTy TG R E1 Ty1 Ty3
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (abs X Ty1 E1) (abs X Ty1 E1) @
RTy : typeOf [] R XTy
Ty : typeOf ((X, Ty1)::((X, XTy)::TG)) E1 Ty3
H1 : typeOf ((X, Ty1)::TG) E1 Ty3
============================
 typeOf TG (abs X Ty1 E1) (arrowTy Ty1 Ty3)

 < search.

Subgoal 2:

Variables: X XTy TG Ty R E2 Ty1 Y E1
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
Ty : typeOf ((X, XTy)::TG) (abs Y Ty1 E1) Ty
S : subst X R (abs Y Ty1 E1) (abs Y Ty1 E2) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
============================
 typeOf TG (abs Y Ty1 E2) Ty

 < Ty: case Ty.

Subgoal 2:

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

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

Subgoal 2.1:

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

 < intros L.

Subgoal 2.1:

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

 < L: case L.

Subgoal 2.1.1:

Variables: X XTy TG R E2 E1 Ty3 X1 XTy1
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (abs X1 XTy1 E1) (abs X1 XTy1 E2) @
RTy : typeOf [] R XTy
S1 : X = X1 -> false
S2 : subst X R E1 E2 *
Ty : typeOf ((X1, XTy1)::((X, XTy)::TG)) E1 Ty3
============================
 lookup ((X, XTy)::((X1, XTy1)::TG)) X1 XTy1

 < search.

Subgoal 2.1.2:

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

 < L': case L1.

Subgoal 2.1.2.1:

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

 < search.

Subgoal 2.1.2.2:

Variables: X XTy TG R E2 Ty1 Y E1 Ty3 X1 XTy1
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (abs Y Ty1 E1) (abs Y Ty1 E2) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
Ty : typeOf ((Y, Ty1)::((X, XTy)::TG)) E1 Ty3
L : Y = X1 -> false
L' : X = X1 -> false
L'1 : lookup TG X1 XTy1
============================
 lookup ((X, XTy)::((Y, Ty1)::TG)) X1 XTy1

 < search.

Subgoal 2:

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

 < apply IH to Ty' S2 RTy.

Subgoal 2:

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

 < search.

Subgoal 3:

Variables: X XTy TG Ty R E21 E11 E2 E1
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
Ty : typeOf ((X, XTy)::TG) (app E1 E2) Ty
S : subst X R (app E1 E2) (app E11 E21) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
============================
 typeOf TG (app E11 E21) Ty

 < Ty: case Ty.

Subgoal 3:

Variables: X XTy TG Ty R E21 E11 E2 E1 Ty1
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (app E1 E2) (app E11 E21) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
Ty : typeOf ((X, XTy)::TG) E1 (arrowTy Ty1 Ty)
Ty1 : typeOf ((X, XTy)::TG) E2 Ty1
============================
 typeOf TG (app E11 E21) Ty

 < apply IH to Ty S1 RTy.

Subgoal 3:

Variables: X XTy TG Ty R E21 E11 E2 E1 Ty1
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (app E1 E2) (app E11 E21) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
Ty : typeOf ((X, XTy)::TG) E1 (arrowTy Ty1 Ty)
Ty1 : typeOf ((X, XTy)::TG) E2 Ty1
H1 : typeOf TG E11 (arrowTy Ty1 Ty)
============================
 typeOf TG (app E11 E21) Ty

 < apply IH to Ty1 S2 RTy.

Subgoal 3:

Variables: X XTy TG Ty R E21 E11 E2 E1 Ty1
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (app E1 E2) (app E11 E21) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
Ty : typeOf ((X, XTy)::TG) E1 (arrowTy Ty1 Ty)
Ty1 : typeOf ((X, XTy)::TG) E2 Ty1
H1 : typeOf TG E11 (arrowTy Ty1 Ty)
H2 : typeOf TG E21 Ty1
============================
 typeOf TG (app E11 E21) Ty

 < search.

Subgoal 4:

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

 < Ty: case Ty.

Subgoal 4:

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

 < L: case Ty.

Subgoal 4.1:

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

 < backchain empty_ty_any.

Subgoal 4.2:

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

 < apply L to _.

Subgoal 5:

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

 < Ty: case Ty.

Subgoal 5:

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

 < L: case Ty.

Subgoal 5.1:

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

 < apply S1 to _.

Subgoal 5.2:

Variables: X XTy TG Ty R Y
IH : forall X XTy TG E Ty R E',
       typeOf ((X, XTy)::TG) E Ty -> subst X R E E' * -> typeOf [] R XTy -> typeOf TG E' Ty
S : subst X R (var Y) (var Y) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
L : X = Y -> false
L1 : lookup TG Y Ty
============================
 typeOf TG (var Y) Ty

 < search.

Proof completed.

 < Prove mtc:shared_declarations:evalStep_type_preservation.

Subgoal 1:

Variables: Ty E2 E11 E1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ty : typeOf [] (app E1 E2) Ty
Ev : evalStep (app E1 E2) (app E11 E2) @
Ev1 : evalStep E1 E11 *
============================
 typeOf [] (app E11 E2) Ty

 < Ty: case Ty.

Subgoal 1:

Variables: Ty E2 E11 E1 Ty1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (app E1 E2) (app E11 E2) @
Ev1 : evalStep E1 E11 *
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
============================
 typeOf [] (app E11 E2) Ty

 < apply IH to Ty Ev1.

Subgoal 1:

Variables: Ty E2 E11 E1 Ty1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (app E1 E2) (app E11 E2) @
Ev1 : evalStep E1 E11 *
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
H1 : typeOf [] E11 (arrowTy Ty1 Ty)
============================
 typeOf [] (app E11 E2) Ty

 < search.

Subgoal 2:

Variables: Ty E21 E1 E2
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ty : typeOf [] (app E1 E2) Ty
Ev : evalStep (app E1 E2) (app E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
============================
 typeOf [] (app E1 E21) Ty

 < Ty: case Ty.

Subgoal 2:

Variables: Ty E21 E1 E2 Ty1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (app E1 E2) (app E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
============================
 typeOf [] (app E1 E21) Ty

 < apply IH to Ty1 Ev2.

Subgoal 2:

Variables: Ty E21 E1 E2 Ty1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (app E1 E2) (app E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
Ty : typeOf [] E1 (arrowTy Ty1 Ty)
Ty1 : typeOf [] E2 Ty1
H1 : typeOf [] E21 Ty1
============================
 typeOf [] (app E1 E21) Ty

 < search.

Subgoal 3:

Variables: Ty E' E2 E1 Ty1 X
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ty : typeOf [] (app (abs X Ty1 E1) E2) Ty
Ev : evalStep (app (abs X Ty1 E1) E2) E' @
Ev1 : value E2
Ev2 : subst X E2 E1 E'
============================
 typeOf [] E' Ty

 < Ty: case Ty.

Subgoal 3:

Variables: Ty E' E2 E1 Ty1 X Ty2
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (app (abs X Ty1 E1) E2) E' @
Ev1 : value E2
Ev2 : subst X E2 E1 E'
Ty : typeOf [] (abs X Ty1 E1) (arrowTy Ty2 Ty)
Ty1 : typeOf [] E2 Ty2
============================
 typeOf [] E' Ty

 < Ty: case Ty.

Subgoal 3:

Variables: Ty E' E2 E1 X Ty2
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (app (abs X Ty2 E1) E2) E' @
Ev1 : value E2
Ev2 : subst X E2 E1 E'
Ty1 : typeOf [] E2 Ty2
Ty : typeOf [(X, Ty2)] E1 Ty
============================
 typeOf [] E' Ty

 < apply subst_preservation to Ty Ev2 Ty1.

Subgoal 3:

Variables: Ty E' E2 E1 X Ty2
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (app (abs X Ty2 E1) E2) E' @
Ev1 : value E2
Ev2 : subst X E2 E1 E'
Ty1 : typeOf [] E2 Ty2
Ty : typeOf [(X, Ty2)] E1 Ty
H1 : typeOf [] E' Ty
============================
 typeOf [] E' Ty

 < search.

Proof completed.

 < Prove mtc:shared_declarations:canonical_form.

Subgoal 1:

Variables: Ty E Ty1 X
IH : forall V Ty, value V * -> typeOf [] V Ty -> canon Ty V
V : value (abs X Ty1 E) @
Ty : typeOf [] (abs X Ty1 E) Ty
============================
 canon Ty (abs X Ty1 E)

 < case Ty.

Subgoal 1:

Variables: E Ty1 X Ty3
IH : forall V Ty, value V * -> typeOf [] V Ty -> canon Ty V
V : value (abs X Ty1 E) @
H1 : typeOf [(X, Ty1)] E Ty3
============================
 canon (arrowTy Ty1 Ty3) (abs X Ty1 E)

 < search.

Proof completed.

 < Prove mtc:shared_declarations:subst_is.

Subgoal 1:

Variables: X R E1 Ty
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsE : is_e (abs X Ty E1)
IsR : is_e R
S : subst X R (abs X Ty E1) (abs X Ty E1) @
============================
 is_e (abs X Ty E1)

 < search.

Subgoal 2:

Variables: X R E2 Ty Y E1
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsE : is_e (abs Y Ty E1)
IsR : is_e R
S : subst X R (abs Y Ty E1) (abs Y Ty E2) @
S1 : X = Y -> false
S2 : subst X R E1 E2 *
============================
 is_e (abs Y Ty E2)

 < Is: case IsE.

Subgoal 2:

Variables: X R E2 Ty Y E1
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsR : is_e R
S : subst X R (abs Y Ty E1) (abs Y Ty E2) @
S1 : X = Y -> false
S2 : subst X R E1 E2 *
Is : is_string Y
Is1 : is_ty Ty
Is2 : is_e E1
============================
 is_e (abs Y Ty E2)

 < apply IH to _ _ S2.

Subgoal 2:

Variables: X R E2 Ty Y E1
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsR : is_e R
S : subst X R (abs Y Ty E1) (abs Y Ty E2) @
S1 : X = Y -> false
S2 : subst X R E1 E2 *
Is : is_string Y
Is1 : is_ty Ty
Is2 : is_e E1
H1 : is_e E2
============================
 is_e (abs Y Ty E2)

 < search.

Subgoal 3:

Variables: X R E21 E11 E2 E1
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsE : is_e (app E1 E2)
IsR : is_e R
S : subst X R (app E1 E2) (app E11 E21) @
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
============================
 is_e (app E11 E21)

 < case IsE.

Subgoal 3:

Variables: X R E21 E11 E2 E1
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsR : is_e R
S : subst X R (app E1 E2) (app E11 E21) @
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
H1 : is_e E1
H2 : is_e E2
============================
 is_e (app E11 E21)

 < apply IH to _ _ S1.

Subgoal 3:

Variables: X R E21 E11 E2 E1
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsR : is_e R
S : subst X R (app E1 E2) (app E11 E21) @
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
H1 : is_e E1
H2 : is_e E2
H3 : is_e E11
============================
 is_e (app E11 E21)

 < apply IH to _ _ S2.

Subgoal 3:

Variables: X R E21 E11 E2 E1
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsR : is_e R
S : subst X R (app E1 E2) (app E11 E21) @
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
H1 : is_e E1
H2 : is_e E2
H3 : is_e E11
H4 : is_e E21
============================
 is_e (app E11 E21)

 < search.

Subgoal 4:

Variables: X E'
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsE : is_e (var X)
IsR : is_e E'
S : subst X E' (var X) E' @
============================
 is_e E'

 < search.

Subgoal 5:

Variables: X R Y
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsE : is_e (var Y)
IsR : is_e R
S : subst X R (var Y) (var Y) @
S1 : X = Y -> false
============================
 is_e (var Y)

 < search.

Proof completed.

 < Prove mtc:shared_declarations:evalStep_is.

Subgoal 1:

Variables: E2 E11 E1
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
IsE : is_e (app E1 E2)
Ev : evalStep (app E1 E2) (app E11 E2) @
Ev1 : evalStep E1 E11 *
============================
 is_e (app E11 E2)

 < case IsE.

Subgoal 1:

Variables: E2 E11 E1
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (app E1 E2) (app E11 E2) @
Ev1 : evalStep E1 E11 *
H1 : is_e E1
H2 : is_e E2
============================
 is_e (app E11 E2)

 < apply IH to _ Ev1.

Subgoal 1:

Variables: E2 E11 E1
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (app E1 E2) (app E11 E2) @
Ev1 : evalStep E1 E11 *
H1 : is_e E1
H2 : is_e E2
H3 : is_e E11
============================
 is_e (app E11 E2)

 < search.

Subgoal 2:

Variables: E21 E1 E2
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
IsE : is_e (app E1 E2)
Ev : evalStep (app E1 E2) (app E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
============================
 is_e (app E1 E21)

 < case IsE.

Subgoal 2:

Variables: E21 E1 E2
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (app E1 E2) (app E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
H1 : is_e E1
H2 : is_e E2
============================
 is_e (app E1 E21)

 < apply IH to _ Ev2.

Subgoal 2:

Variables: E21 E1 E2
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (app E1 E2) (app E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
H1 : is_e E1
H2 : is_e E2
H3 : is_e E21
============================
 is_e (app E1 E21)

 < search.

Subgoal 3:

Variables: E' E2 E1 Ty X
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
IsE : is_e (app (abs X Ty E1) E2)
Ev : evalStep (app (abs X Ty E1) E2) E' @
Ev1 : value E2
Ev2 : subst X E2 E1 E'
============================
 is_e E'

 < Is: case IsE.

Subgoal 3:

Variables: E' E2 E1 Ty X
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (app (abs X Ty E1) E2) E' @
Ev1 : value E2
Ev2 : subst X E2 E1 E'
Is : is_e (abs X Ty E1)
Is1 : is_e E2
============================
 is_e E'

 < case Is.

Subgoal 3:

Variables: E' E2 E1 Ty X
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (app (abs X Ty E1) E2) E' @
Ev1 : value E2
Ev2 : subst X E2 E1 E'
Is1 : is_e E2
H1 : is_string X
H2 : is_ty Ty
H3 : is_e E1
============================
 is_e E'

 < apply subst_is to _ _ Ev2.

Subgoal 3:

Variables: E' E2 E1 Ty X
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (app (abs X Ty E1) E2) E' @
Ev1 : value E2
Ev2 : subst X E2 E1 E'
Is1 : is_e E2
H1 : is_string X
H2 : is_ty Ty
H3 : is_e E1
H4 : is_e E'
============================
 is_e E'

 < search.

Proof completed.

 < Prove mtc:shared_declarations:subst_total.

Subgoal 2:

Variables: X R E1 Ty S
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (abs S Ty E1) @
IsX : is_string X
IsR : is_e R
IsE1 : is_string S
IsE2 : is_ty Ty
IsE3 : is_e E1 *
============================
 exists E', subst X R (abs S Ty E1) E'

 < Or: apply is_string_eq_or_not to IsX IsE1.

Subgoal 2:

Variables: X R E1 Ty S
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (abs S Ty E1) @
IsX : is_string X
IsR : is_e R
IsE1 : is_string S
IsE2 : is_ty Ty
IsE3 : is_e E1 *
Or : X = S \/ (X = S -> false)
============================
 exists E', subst X R (abs S Ty E1) E'

 < case Or.

Subgoal 2.1:

Variables: R E1 Ty S
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (abs S Ty E1) @
IsX : is_string S
IsR : is_e R
IsE1 : is_string S
IsE2 : is_ty Ty
IsE3 : is_e E1 *
============================
 exists E', subst S R (abs S Ty E1) E'

 < search.

Subgoal 2.2:

Variables: X R E1 Ty S
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (abs S Ty E1) @
IsX : is_string X
IsR : is_e R
IsE1 : is_string S
IsE2 : is_ty Ty
IsE3 : is_e E1 *
H1 : X = S -> false
============================
 exists E', subst X R (abs S Ty E1) E'

 < apply IH to IsE3 IsX IsR.

Subgoal 2.2:

Variables: X R E1 Ty S E'
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (abs S Ty E1) @
IsX : is_string X
IsR : is_e R
IsE1 : is_string S
IsE2 : is_ty Ty
IsE3 : is_e E1 *
H1 : X = S -> false
H2 : subst X R E1 E'
============================
 exists E', subst X R (abs S Ty E1) E'

 < search.

Subgoal 3:

Variables: X R E2 E1
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (app E1 E2) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E1 *
IsE2 : is_e E2 *
============================
 exists E', subst X R (app E1 E2) E'

 < apply IH to IsE1 IsX IsR.

Subgoal 3:

Variables: X R E2 E1 E'
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (app E1 E2) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E1 *
IsE2 : is_e E2 *
H1 : subst X R E1 E'
============================
 exists E', subst X R (app E1 E2) E'

 < apply IH to IsE2 IsX IsR.

Subgoal 3:

Variables: X R E2 E1 E' E'1
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (app E1 E2) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E1 *
IsE2 : is_e E2 *
H1 : subst X R E1 E'
H2 : subst X R E2 E'1
============================
 exists E', subst X R (app E1 E2) E'

 < search.

Subgoal 4:

Variables: X R S
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (var S) @
IsX : is_string X
IsR : is_e R
IsE1 : is_string S
============================
 exists E', subst X R (var S) E'

 < Or: apply is_string_eq_or_not to IsX IsE1.

Subgoal 4:

Variables: X R S
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (var S) @
IsX : is_string X
IsR : is_e R
IsE1 : is_string S
Or : X = S \/ (X = S -> false)
============================
 exists E', subst X R (var S) E'

 < case Or.

Subgoal 4.1:

Variables: R S
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (var S) @
IsX : is_string S
IsR : is_e R
IsE1 : is_string S
============================
 exists E', subst S R (var S) E'

 < search.

Subgoal 4.2:

Variables: X R S
IH : forall X R E,
       is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (var S) @
IsX : is_string X
IsR : is_e R
IsE1 : is_string S
H1 : X = S -> false
============================
 exists E', subst X R (var S) E'

 < search.

Proof completed.

 < Prove mtc:shared_declarations:progress.

Subgoal 1:

Variables: Ty2 Ty1 E1 X
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
IsE : is_e (abs X Ty1 E1)
Ty : typeOf [] (abs X Ty1 E1) (arrowTy Ty1 Ty2) @
Ty1 : typeOf [(X, Ty1)] E1 Ty2 *
============================
 value (abs X Ty1 E1) \/ (exists E', evalStep (abs X Ty1 E1) E')

 < search.

Subgoal 2:

Variables: Ty Ty1 E2 E1
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
IsE : is_e (app E1 E2)
Ty : typeOf [] (app E1 E2) Ty @
Ty1 : typeOf [] E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
============================
 value (app E1 E2) \/ (exists E', evalStep (app E1 E2) E')

 < Is: case IsE.

Subgoal 2:

Variables: Ty Ty1 E2 E1
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (app E1 E2) Ty @
Ty1 : typeOf [] E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
============================
 value (app E1 E2) \/ (exists E', evalStep (app E1 E2) E')

 < Or1: apply IH to _ Ty1.

Subgoal 2:

Variables: Ty Ty1 E2 E1
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (app E1 E2) Ty @
Ty1 : typeOf [] E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
Or1 : value E1 \/ (exists E', evalStep E1 E')
============================
 value (app E1 E2) \/ (exists E', evalStep (app E1 E2) E')

 < Or2: apply IH to _ Ty2.

Subgoal 2:

Variables: Ty Ty1 E2 E1
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (app E1 E2) Ty @
Ty1 : typeOf [] E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
Or1 : value E1 \/ (exists E', evalStep E1 E')
Or2 : value E2 \/ (exists E', evalStep E2 E')
============================
 value (app E1 E2) \/ (exists E', evalStep (app E1 E2) E')

 < Ev1: case Or1.

Subgoal 2.1:

Variables: Ty Ty1 E2 E1
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (app E1 E2) Ty @
Ty1 : typeOf [] E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
Or2 : value E2 \/ (exists E', evalStep E2 E')
Ev1 : value E1
============================
 value (app E1 E2) \/ (exists E', evalStep (app E1 E2) E')

 < Ev2: case Or2.

Subgoal 2.1.1:

Variables: Ty Ty1 E2 E1
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (app E1 E2) Ty @
Ty1 : typeOf [] E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
Ev1 : value E1
Ev2 : value E2
============================
 value (app E1 E2) \/ (exists E', evalStep (app E1 E2) E')

 < C: apply canonical_form to Ev1 Ty1.

Subgoal 2.1.1:

Variables: Ty Ty1 E2 E1
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (app E1 E2) Ty @
Ty1 : typeOf [] E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
Ev1 : value E1
Ev2 : value E2
C : canon (arrowTy Ty1 Ty) E1
============================
 value (app E1 E2) \/ (exists E', evalStep (app E1 E2) E')

 < case C.

Subgoal 2.1.1:

Variables: Ty Ty1 E2 E3 X
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (app (abs X Ty1 E3) E2) Ty @
Ty1 : typeOf [] (abs X Ty1 E3) (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
Is : is_e (abs X Ty1 E3)
Is1 : is_e E2
Ev1 : value (abs X Ty1 E3)
Ev2 : value E2
============================
 value (app (abs X Ty1 E3) E2) \/
 (exists E', evalStep (app (abs X Ty1 E3) E2) E')

 < IsAbs: case Is.

Subgoal 2.1.1:

Variables: Ty Ty1 E2 E3 X
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (app (abs X Ty1 E3) E2) Ty @
Ty1 : typeOf [] (abs X Ty1 E3) (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
Is1 : is_e E2
Ev1 : value (abs X Ty1 E3)
Ev2 : value E2
IsAbs : is_string X
IsAbs1 : is_ty Ty1
IsAbs2 : is_e E3
============================
 value (app (abs X Ty1 E3) E2) \/
 (exists E', evalStep (app (abs X Ty1 E3) E2) E')

 < apply subst_total to IsAbs2 IsAbs Is1.

Subgoal 2.1.1:

Variables: Ty Ty1 E2 E3 X E'
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (app (abs X Ty1 E3) E2) Ty @
Ty1 : typeOf [] (abs X Ty1 E3) (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
Is1 : is_e E2
Ev1 : value (abs X Ty1 E3)
Ev2 : value E2
IsAbs : is_string X
IsAbs1 : is_ty Ty1
IsAbs2 : is_e E3
H1 : subst X E2 E3 E'
============================
 value (app (abs X Ty1 E3) E2) \/
 (exists E', evalStep (app (abs X Ty1 E3) E2) E')

 < search.

Subgoal 2.1.2:

Variables: Ty Ty1 E2 E1 E'
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (app E1 E2) Ty @
Ty1 : typeOf [] E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
Ev1 : value E1
Ev2 : evalStep E2 E'
============================
 value (app E1 E2) \/ (exists E', evalStep (app E1 E2) E')

 < search.

Subgoal 2.2:

Variables: Ty Ty1 E2 E1 E'
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (app E1 E2) Ty @
Ty1 : typeOf [] E1 (arrowTy Ty1 Ty) *
Ty2 : typeOf [] E2 Ty1 *
Is : is_e E1
Is1 : is_e E2
Or2 : value E2 \/ (exists E', evalStep E2 E')
Ev1 : evalStep E1 E'
============================
 value (app E1 E2) \/ (exists E', evalStep (app E1 E2) E')

 < search.

Subgoal 3:

Variables: Ty X
IH : forall E Ty,
       is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
IsE : is_e (var X)
Ty : typeOf [] (var X) Ty @
Ty1 : lookup [] X Ty
============================
 value (var X) \/ (exists E', evalStep (var X) E')

 < case Ty1.

Proof completed.

Back to example home