< Module mtc:natCase.
< Prove mtc:arith:fix_nat.
Proof completed.
< Prove mtc:shared_declarations:type_preservation.
Subgoal 3:
Variables: TG Ty EG V S X Z 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 (natCase E1 Z X S) Ty
Ev : eval EG (natCase E1 Z X S) V @
Ev1 : eval EG E1 (numVal z) *
Ev2 : eval EG Z V *
============================
valueType V Ty
< Ty: case Ty.
Subgoal 3:
Variables: TG Ty EG V S X Z 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
Ev : eval EG (natCase E1 Z X S) V @
Ev1 : eval EG E1 (numVal z) *
Ev2 : eval EG Z V *
Ty : typeOf TG E1 natTy
Ty1 : typeOf TG Z Ty
Ty2 : typeOf ((X, natTy)::TG) S Ty
============================
valueType V Ty
< apply IH to _ Ty1 Ev2.
Subgoal 3:
Variables: TG Ty EG V S X Z 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
Ev : eval EG (natCase E1 Z X S) V @
Ev1 : eval EG E1 (numVal z) *
Ev2 : eval EG Z V *
Ty : typeOf TG E1 natTy
Ty1 : typeOf TG Z Ty
Ty2 : typeOf ((X, natTy)::TG) S Ty
H1 : valueType V Ty
============================
valueType V Ty
< search.
Subgoal 4:
Variables: TG Ty EG V N S X Z 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 (natCase E1 Z X S) Ty
Ev : eval EG (natCase E1 Z X S) V @
Ev1 : eval EG E1 (numVal (s N)) *
Ev2 : eval ((X, numVal N)::EG) S V *
============================
valueType V Ty
< Ty: case Ty.
Subgoal 4:
Variables: TG Ty EG V N S X Z 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
Ev : eval EG (natCase E1 Z X S) V @
Ev1 : eval EG E1 (numVal (s N)) *
Ev2 : eval ((X, numVal N)::EG) S V *
Ty : typeOf TG E1 natTy
Ty1 : typeOf TG Z Ty
Ty2 : typeOf ((X, natTy)::TG) S Ty
============================
valueType V Ty
< apply IH to _ Ty2 Ev2.
Subgoal 4:
Variables: TG Ty EG V N S X Z 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
Ev : eval EG (natCase E1 Z X S) V @
Ev1 : eval EG E1 (numVal (s N)) *
Ev2 : eval ((X, numVal N)::EG) S V *
Ty : typeOf TG E1 natTy
Ty1 : typeOf TG Z Ty
Ty2 : typeOf ((X, natTy)::TG) S Ty
H1 : valueType V Ty
============================
valueType V Ty
< search.
Proof completed.
< Prove mtc:shared_declarations:value_evalStep_false.
Proof completed.
< Prove mtc:shared_declarations:subst_unique.
Subgoal 3:
Variables: X R EB S Z1 E2 Z E1
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (natCase E1 Z X S) (natCase E2 Z1 X S) @
SB : subst X R (natCase E1 Z X S) EB
SA1 : subst X R E1 E2 *
SA2 : subst X R Z Z1 *
============================
natCase E2 Z1 X S = EB
< SB: case SB.
Subgoal 3.1:
Variables: X R S Z1 E2 Z E1 Z3 E4
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (natCase E1 Z X S) (natCase E2 Z1 X S) @
SA1 : subst X R E1 E2 *
SA2 : subst X R Z Z1 *
SB : subst X R E1 E4
SB1 : subst X R Z Z3
============================
natCase E2 Z1 X S = natCase E4 Z3 X S
< apply IH to SA1 SB.
Subgoal 3.1:
Variables: X R S Z1 Z E1 Z3 E4
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (natCase E1 Z X S) (natCase E4 Z1 X S) @
SA1 : subst X R E1 E4 *
SA2 : subst X R Z Z1 *
SB : subst X R E1 E4
SB1 : subst X R Z Z3
============================
natCase E4 Z1 X S = natCase E4 Z3 X S
< apply IH to SA2 SB1.
Subgoal 3.1:
Variables: X R S Z E1 Z3 E4
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (natCase E1 Z X S) (natCase E4 Z3 X S) @
SA1 : subst X R E1 E4 *
SA2 : subst X R Z Z3 *
SB : subst X R E1 E4
SB1 : subst X R Z Z3
============================
natCase E4 Z3 X S = natCase E4 Z3 X S
< search.
Subgoal 3.2:
Variables: X R S Z1 E2 Z E1 S2 Z3 E4
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (natCase E1 Z X S) (natCase E2 Z1 X S) @
SA1 : subst X R E1 E2 *
SA2 : subst X R Z Z1 *
SB : X = X -> false
SB1 : subst X R E1 E4
SB2 : subst X R Z Z3
SB3 : subst X R S S2
============================
natCase E2 Z1 X S = natCase E4 Z3 X S2
< apply SB to _.
Subgoal 4:
Variables: X R EB S1 Y Z1 E2 S Z E1
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
SB : subst X R (natCase E1 Z Y S) EB
SA1 : X = Y -> false
SA2 : subst X R E1 E2 *
SA3 : subst X R Z Z1 *
SA4 : subst X R S S1 *
============================
natCase E2 Z1 Y S1 = EB
< SB: case SB.
Subgoal 4.1:
Variables: R S1 Y Z1 E2 S Z E1 Z3 E4
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst Y R (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
SA1 : Y = Y -> false
SA2 : subst Y R E1 E2 *
SA3 : subst Y R Z Z1 *
SA4 : subst Y R S S1 *
SB : subst Y R E1 E4
SB1 : subst Y R Z Z3
============================
natCase E2 Z1 Y S1 = natCase E4 Z3 Y S
< apply SA1 to _.
Subgoal 4.2:
Variables: X R S1 Y Z1 E2 S Z E1 S3 Z3 E4
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
SA1 : X = Y -> false
SA2 : subst X R E1 E2 *
SA3 : subst X R Z Z1 *
SA4 : subst X R S S1 *
SB : X = Y -> false
SB1 : subst X R E1 E4
SB2 : subst X R Z Z3
SB3 : subst X R S S3
============================
natCase E2 Z1 Y S1 = natCase E4 Z3 Y S3
< apply IH to SA2 SB1.
Subgoal 4.2:
Variables: X R S1 Y Z1 S Z E1 S3 Z3 E4
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (natCase E1 Z Y S) (natCase E4 Z1 Y S1) @
SA1 : X = Y -> false
SA2 : subst X R E1 E4 *
SA3 : subst X R Z Z1 *
SA4 : subst X R S S1 *
SB : X = Y -> false
SB1 : subst X R E1 E4
SB2 : subst X R Z Z3
SB3 : subst X R S S3
============================
natCase E4 Z1 Y S1 = natCase E4 Z3 Y S3
< apply IH to SA3 SB2.
Subgoal 4.2:
Variables: X R S1 Y S Z E1 S3 Z3 E4
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (natCase E1 Z Y S) (natCase E4 Z3 Y S1) @
SA1 : X = Y -> false
SA2 : subst X R E1 E4 *
SA3 : subst X R Z Z3 *
SA4 : subst X R S S1 *
SB : X = Y -> false
SB1 : subst X R E1 E4
SB2 : subst X R Z Z3
SB3 : subst X R S S3
============================
natCase E4 Z3 Y S1 = natCase E4 Z3 Y S3
< apply IH to SA4 SB3.
Subgoal 4.2:
Variables: X R Y S Z E1 S3 Z3 E4
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (natCase E1 Z Y S) (natCase E4 Z3 Y S3) @
SA1 : X = Y -> false
SA2 : subst X R E1 E4 *
SA3 : subst X R Z Z3 *
SA4 : subst X R S S3 *
SB : X = Y -> false
SB1 : subst X R E1 E4
SB2 : subst X R Z Z3
SB3 : subst X R S S3
============================
natCase E4 Z3 Y S3 = natCase E4 Z3 Y S3
< search.
Proof completed.
< Prove mtc:shared_declarations:evalStep_unique.
Subgoal 4:
Variables: EB S X Z E2 E1
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase E1 Z X S) (natCase E2 Z X S) @
EvB : evalStep (natCase E1 Z X S) EB
EvA1 : evalStep E1 E2 *
============================
natCase E2 Z X S = EB
< EvB: case EvB.
Subgoal 4.1:
Variables: S X Z E2 E1 E4
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase E1 Z X S) (natCase E2 Z X S) @
EvA1 : evalStep E1 E2 *
EvB : evalStep E1 E4
============================
natCase E2 Z X S = natCase E4 Z X S
< apply IH to EvA1 EvB.
Subgoal 4.1:
Variables: S X Z E1 E4
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase E1 Z X S) (natCase E4 Z X S) @
EvA1 : evalStep E1 E4 *
EvB : evalStep E1 E4
============================
natCase E4 Z X S = natCase E4 Z X S
< search.
Subgoal 4.2:
Variables: EB S X E2
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase (num z) EB X S) (natCase E2 EB X S) @
EvA1 : evalStep (num z) E2 *
============================
natCase E2 EB X S = EB
< case EvA1.
Subgoal 4.3:
Variables: EB S X Z E2 N
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase (num (s N)) Z X S) (natCase E2 Z X S) @
EvA1 : evalStep (num (s N)) E2 *
EvB : subst X (num N) S EB
============================
natCase E2 Z X S = EB
< case EvA1.
Subgoal 5:
Variables: EA EB S X
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase (num z) EA X S) EA @
EvB : evalStep (natCase (num z) EA X S) EB
============================
EA = EB
< EvB: case EvB.
Subgoal 5.1:
Variables: EA S X E2
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase (num z) EA X S) EA @
EvB : evalStep (num z) E2
============================
EA = natCase E2 EA X S
< case EvB.
Subgoal 5.2:
Variables: EB S X
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase (num z) EB X S) EB @
============================
EB = EB
< search.
Subgoal 6:
Variables: EA EB S X Z N
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase (num (s N)) Z X S) EA @
EvB : evalStep (natCase (num (s N)) Z X S) EB
EvA1 : subst X (num N) S EA
============================
EA = EB
< EvB: case EvB.
Subgoal 6.1:
Variables: EA S X Z N E2
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase (num (s N)) Z X S) EA @
EvA1 : subst X (num N) S EA
EvB : evalStep (num (s N)) E2
============================
EA = natCase E2 Z X S
< case EvB.
Subgoal 6.2:
Variables: EA EB S X Z N
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase (num (s N)) Z X S) EA @
EvA1 : subst X (num N) S EA
EvB : subst X (num N) S EB
============================
EA = EB
< apply subst_unique to EvA1 EvB.
Subgoal 6.2:
Variables: EB S X Z N
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (natCase (num (s N)) Z X S) EB @
EvA1 : subst X (num N) S EB
EvB : subst X (num N) S EB
============================
EB = EB
< search.
Proof completed.
< Prove mtc:shared_declarations:ty_lookup.
Subgoal 3:
Variables: G1 G2 Ty S X Z 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 (natCase E1 Z X S) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 Z Ty *
Ty3 : typeOf ((X, natTy)::G1) S Ty *
============================
typeOf G2 (natCase E1 Z X S) Ty
< apply IH to Ty1 L.
Subgoal 3:
Variables: G1 G2 Ty S X Z 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 (natCase E1 Z X S) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 Z Ty *
Ty3 : typeOf ((X, natTy)::G1) S Ty *
H1 : typeOf G2 E1 natTy
============================
typeOf G2 (natCase E1 Z X S) Ty
< apply IH to Ty2 L.
Subgoal 3:
Variables: G1 G2 Ty S X Z 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 (natCase E1 Z X S) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 Z Ty *
Ty3 : typeOf ((X, natTy)::G1) S Ty *
H1 : typeOf G2 E1 natTy
H2 : typeOf G2 Z Ty
============================
typeOf G2 (natCase E1 Z X S) Ty
< apply IH to Ty3 _ with
G2 = (X, natTy)::G2.
Subgoal 3.1:
Variables: G1 G2 Ty S X Z 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 (natCase E1 Z X S) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 Z Ty *
Ty3 : typeOf ((X, natTy)::G1) S Ty *
H1 : typeOf G2 E1 natTy
H2 : typeOf G2 Z Ty
============================
forall X1 XTy, lookup ((X, natTy)::G1) X1 XTy -> lookup ((X, natTy)::G2) X1 XTy
< intros L'.
Subgoal 3.1:
Variables: G1 G2 Ty S X Z 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 (natCase E1 Z X S) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 Z Ty *
Ty3 : typeOf ((X, natTy)::G1) S Ty *
H1 : typeOf G2 E1 natTy
H2 : typeOf G2 Z Ty
L' : lookup ((X, natTy)::G1) X1 XTy
============================
lookup ((X, natTy)::G2) X1 XTy
< L': case L'.
Subgoal 3.1.1:
Variables: G1 G2 Ty S Z E1 X1
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 (natCase E1 Z X1 S) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 Z Ty *
Ty3 : typeOf ((X1, natTy)::G1) S Ty *
H1 : typeOf G2 E1 natTy
H2 : typeOf G2 Z Ty
============================
lookup ((X1, natTy)::G2) X1 natTy
< search.
Subgoal 3.1.2:
Variables: G1 G2 Ty S X Z 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 (natCase E1 Z X S) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 Z Ty *
Ty3 : typeOf ((X, natTy)::G1) S Ty *
H1 : typeOf G2 E1 natTy
H2 : typeOf G2 Z Ty
L' : X = X1 -> false
L'1 : lookup G1 X1 XTy
============================
lookup ((X, natTy)::G2) X1 XTy
< apply L to L'1.
Subgoal 3.1.2:
Variables: G1 G2 Ty S X Z 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 (natCase E1 Z X S) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 Z Ty *
Ty3 : typeOf ((X, natTy)::G1) S Ty *
H1 : typeOf G2 E1 natTy
H2 : typeOf G2 Z Ty
L' : X = X1 -> false
L'1 : lookup G1 X1 XTy
H3 : lookup G2 X1 XTy
============================
lookup ((X, natTy)::G2) X1 XTy
< search.
Subgoal 3:
Variables: G1 G2 Ty S X Z 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 (natCase E1 Z X S) Ty @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 Z Ty *
Ty3 : typeOf ((X, natTy)::G1) S Ty *
H1 : typeOf G2 E1 natTy
H2 : typeOf G2 Z Ty
H3 : typeOf ((X, natTy)::G2) S Ty
============================
typeOf G2 (natCase E1 Z X S) Ty
< search.
Proof completed.
< Prove mtc:shared_declarations:subst_preservation.
Subgoal 3:
Variables: X XTy TG Ty R S Z1 E2 Z 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) (natCase E1 Z X S) Ty
S : subst X R (natCase E1 Z X S) (natCase E2 Z1 X S) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
============================
typeOf TG (natCase E2 Z1 X S) Ty
< Ty: case Ty.
Subgoal 3:
Variables: X XTy TG Ty R S Z1 E2 Z 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
S : subst X R (natCase E1 Z X S) (natCase E2 Z1 X S) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((X, natTy)::((X, XTy)::TG)) S Ty
============================
typeOf TG (natCase E2 Z1 X S) Ty
< apply IH to Ty S1 RTy.
Subgoal 3:
Variables: X XTy TG Ty R S Z1 E2 Z 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
S : subst X R (natCase E1 Z X S) (natCase E2 Z1 X S) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((X, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
============================
typeOf TG (natCase E2 Z1 X S) Ty
< apply IH to Ty1 S2 RTy.
Subgoal 3:
Variables: X XTy TG Ty R S Z1 E2 Z 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
S : subst X R (natCase E1 Z X S) (natCase E2 Z1 X S) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((X, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
============================
typeOf TG (natCase E2 Z1 X S) Ty
< apply ty_lookup to Ty2 _ with
G2 = (X, natTy)::TG.
Subgoal 3.1:
Variables: X XTy TG Ty R S Z1 E2 Z 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
S : subst X R (natCase E1 Z X S) (natCase E2 Z1 X S) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((X, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
============================
forall X1 XTy1,
lookup ((X, natTy)::((X, XTy)::TG)) X1 XTy1 -> lookup ((X, natTy)::TG) X1 XTy1
< intros L.
Subgoal 3.1:
Variables: X XTy TG Ty R S Z1 E2 Z E1 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 (natCase E1 Z X S) (natCase E2 Z1 X S) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((X, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
L : lookup ((X, natTy)::((X, XTy)::TG)) X1 XTy1
============================
lookup ((X, natTy)::TG) X1 XTy1
< L: case L.
Subgoal 3.1.1:
Variables: XTy TG Ty R S Z1 E2 Z E1 X1
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 (natCase E1 Z X1 S) (natCase E2 Z1 X1 S) @
RTy : typeOf [] R XTy
S1 : subst X1 R E1 E2 *
S2 : subst X1 R Z Z1 *
Ty : typeOf ((X1, XTy)::TG) E1 natTy
Ty1 : typeOf ((X1, XTy)::TG) Z Ty
Ty2 : typeOf ((X1, natTy)::((X1, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
============================
lookup ((X1, natTy)::TG) X1 natTy
< search.
Subgoal 3.1.2:
Variables: X XTy TG Ty R S Z1 E2 Z E1 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 (natCase E1 Z X S) (natCase E2 Z1 X S) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((X, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
L : X = X1 -> false
L1 : lookup ((X, XTy)::TG) X1 XTy1
============================
lookup ((X, natTy)::TG) X1 XTy1
< L': case L1.
Subgoal 3.1.2.1:
Variables: TG Ty R S Z1 E2 Z E1 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 (natCase E1 Z X1 S) (natCase E2 Z1 X1 S) @
RTy : typeOf [] R XTy1
S1 : subst X1 R E1 E2 *
S2 : subst X1 R Z Z1 *
Ty : typeOf ((X1, XTy1)::TG) E1 natTy
Ty1 : typeOf ((X1, XTy1)::TG) Z Ty
Ty2 : typeOf ((X1, natTy)::((X1, XTy1)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
L : X1 = X1 -> false
============================
lookup ((X1, natTy)::TG) X1 XTy1
< apply L to _.
Subgoal 3.1.2.2:
Variables: X XTy TG Ty R S Z1 E2 Z E1 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 (natCase E1 Z X S) (natCase E2 Z1 X S) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((X, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
L : X = X1 -> false
L' : X = X1 -> false
L'1 : lookup TG X1 XTy1
============================
lookup ((X, natTy)::TG) X1 XTy1
< search.
Subgoal 3:
Variables: X XTy TG Ty R S Z1 E2 Z 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
S : subst X R (natCase E1 Z X S) (natCase E2 Z1 X S) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((X, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
H3 : typeOf ((X, natTy)::TG) S Ty
============================
typeOf TG (natCase E2 Z1 X S) Ty
< search.
Subgoal 4:
Variables: X XTy TG Ty R S1 Y Z1 E2 S Z 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) (natCase E1 Z Y S) Ty
S : subst X R (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
============================
typeOf TG (natCase E2 Z1 Y S1) Ty
< Ty: case Ty.
Subgoal 4:
Variables: X XTy TG Ty R S1 Y Z1 E2 S Z 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
S : subst X R (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((Y, natTy)::((X, XTy)::TG)) S Ty
============================
typeOf TG (natCase E2 Z1 Y S1) Ty
< apply IH to Ty S2 RTy.
Subgoal 4:
Variables: X XTy TG Ty R S1 Y Z1 E2 S Z 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
S : subst X R (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((Y, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
============================
typeOf TG (natCase E2 Z1 Y S1) Ty
< apply IH to Ty1 S3 RTy.
Subgoal 4:
Variables: X XTy TG Ty R S1 Y Z1 E2 S Z 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
S : subst X R (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((Y, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
============================
typeOf TG (natCase E2 Z1 Y S1) Ty
< Ty': apply ty_lookup to Ty2 _ with
G2 = (X, XTy)::((Y, natTy)::TG).
Subgoal 4.1:
Variables: X XTy TG Ty R S1 Y Z1 E2 S Z 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
S : subst X R (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((Y, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
============================
forall X1 XTy1,
lookup ((Y, natTy)::((X, XTy)::TG)) X1 XTy1 -> lookup ((X, XTy)::((Y, natTy)::TG)) X1 XTy1
< intros L.
Subgoal 4.1:
Variables: X XTy TG Ty R S1 Y Z1 E2 S Z E1 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 (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((Y, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
L : lookup ((Y, natTy)::((X, XTy)::TG)) X1 XTy1
============================
lookup ((X, XTy)::((Y, natTy)::TG)) X1 XTy1
< L: case L.
Subgoal 4.1.1:
Variables: X XTy TG Ty R S1 Z1 E2 S Z E1 X1
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 (natCase E1 Z X1 S) (natCase E2 Z1 X1 S1) @
RTy : typeOf [] R XTy
S1 : X = X1 -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((X1, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
============================
lookup ((X, XTy)::((X1, natTy)::TG)) X1 natTy
< search.
Subgoal 4.1.2:
Variables: X XTy TG Ty R S1 Y Z1 E2 S Z E1 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 (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((Y, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
L : Y = X1 -> false
L1 : lookup ((X, XTy)::TG) X1 XTy1
============================
lookup ((X, XTy)::((Y, natTy)::TG)) X1 XTy1
< L': case L1.
Subgoal 4.1.2.1:
Variables: TG Ty R S1 Y Z1 E2 S Z E1 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 (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
RTy : typeOf [] R XTy1
S1 : X1 = Y -> false
S2 : subst X1 R E1 E2 *
S3 : subst X1 R Z Z1 *
S4 : subst X1 R S S1 *
Ty : typeOf ((X1, XTy1)::TG) E1 natTy
Ty1 : typeOf ((X1, XTy1)::TG) Z Ty
Ty2 : typeOf ((Y, natTy)::((X1, XTy1)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
L : Y = X1 -> false
============================
lookup ((X1, XTy1)::((Y, natTy)::TG)) X1 XTy1
< search.
Subgoal 4.1.2.2:
Variables: X XTy TG Ty R S1 Y Z1 E2 S Z E1 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 (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((Y, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
L : Y = X1 -> false
L' : X = X1 -> false
L'1 : lookup TG X1 XTy1
============================
lookup ((X, XTy)::((Y, natTy)::TG)) X1 XTy1
< search.
Subgoal 4:
Variables: X XTy TG Ty R S1 Y Z1 E2 S Z 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
S : subst X R (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((Y, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
Ty' : typeOf ((X, XTy)::((Y, natTy)::TG)) S Ty
============================
typeOf TG (natCase E2 Z1 Y S1) Ty
< apply IH to Ty' S4 RTy.
Subgoal 4:
Variables: X XTy TG Ty R S1 Y Z1 E2 S Z 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
S : subst X R (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
RTy : typeOf [] R XTy
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) Z Ty
Ty2 : typeOf ((Y, natTy)::((X, XTy)::TG)) S Ty
H1 : typeOf TG E2 natTy
H2 : typeOf TG Z1 Ty
Ty' : typeOf ((X, XTy)::((Y, natTy)::TG)) S Ty
H3 : typeOf ((Y, natTy)::TG) S1 Ty
============================
typeOf TG (natCase E2 Z1 Y S1) Ty
< search.
Proof completed.
< Prove mtc:shared_declarations:evalStep_type_preservation.
Subgoal 4:
Variables: Ty S X Z E2 E1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ty : typeOf [] (natCase E1 Z X S) Ty
Ev : evalStep (natCase E1 Z X S) (natCase E2 Z X S) @
Ev1 : evalStep E1 E2 *
============================
typeOf [] (natCase E2 Z X S) Ty
< Ty: case Ty.
Subgoal 4:
Variables: Ty S X Z E2 E1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (natCase E1 Z X S) (natCase E2 Z X S) @
Ev1 : evalStep E1 E2 *
Ty : typeOf [] E1 natTy
Ty1 : typeOf [] Z Ty
Ty2 : typeOf [(X, natTy)] S Ty
============================
typeOf [] (natCase E2 Z X S) Ty
< apply IH to Ty Ev1.
Subgoal 4:
Variables: Ty S X Z E2 E1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (natCase E1 Z X S) (natCase E2 Z X S) @
Ev1 : evalStep E1 E2 *
Ty : typeOf [] E1 natTy
Ty1 : typeOf [] Z Ty
Ty2 : typeOf [(X, natTy)] S Ty
H1 : typeOf [] E2 natTy
============================
typeOf [] (natCase E2 Z X S) Ty
< search.
Subgoal 5:
Variables: Ty E' S X
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ty : typeOf [] (natCase (num z) E' X S) Ty
Ev : evalStep (natCase (num z) E' X S) E' @
============================
typeOf [] E' Ty
< Ty: case Ty.
Subgoal 5:
Variables: Ty E' S X
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (natCase (num z) E' X S) E' @
Ty : typeOf [] (num z) natTy
Ty1 : typeOf [] E' Ty
Ty2 : typeOf [(X, natTy)] S Ty
============================
typeOf [] E' Ty
< search.
Subgoal 6:
Variables: Ty E' S X Z N
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ty : typeOf [] (natCase (num (s N)) Z X S) Ty
Ev : evalStep (natCase (num (s N)) Z X S) E' @
Ev1 : subst X (num N) S E'
============================
typeOf [] E' Ty
< Ty: case Ty.
Subgoal 6:
Variables: Ty E' S X Z N
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (natCase (num (s N)) Z X S) E' @
Ev1 : subst X (num N) S E'
Ty : typeOf [] (num (s N)) natTy
Ty1 : typeOf [] Z Ty
Ty2 : typeOf [(X, natTy)] S Ty
============================
typeOf [] E' Ty
< apply subst_preservation to Ty2 Ev1 _.
Subgoal 6:
Variables: Ty E' S X Z N
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (natCase (num (s N)) Z X S) E' @
Ev1 : subst X (num N) S E'
Ty : typeOf [] (num (s N)) natTy
Ty1 : typeOf [] Z Ty
Ty2 : typeOf [(X, natTy)] S Ty
H1 : typeOf [] E' Ty
============================
typeOf [] E' Ty
< search.
Proof completed.
< Prove mtc:shared_declarations:canonical_form.
Proof completed.
< Prove mtc:shared_declarations:subst_is.
Subgoal 3:
Variables: X R S Z1 E2 Z E1
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsE : is_e (natCase E1 Z X S)
IsR : is_e R
S : subst X R (natCase E1 Z X S) (natCase E2 Z1 X S) @
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
============================
is_e (natCase E2 Z1 X S)
< case IsE.
Subgoal 3:
Variables: X R S Z1 E2 Z 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 (natCase E1 Z X S) (natCase E2 Z1 X S) @
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
H1 : is_e E1
H2 : is_e Z
H3 : is_string X
H4 : is_e S
============================
is_e (natCase E2 Z1 X S)
< apply IH to _ _ S1.
Subgoal 3:
Variables: X R S Z1 E2 Z 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 (natCase E1 Z X S) (natCase E2 Z1 X S) @
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
H1 : is_e E1
H2 : is_e Z
H3 : is_string X
H4 : is_e S
H5 : is_e E2
============================
is_e (natCase E2 Z1 X S)
< apply IH to _ _ S2.
Subgoal 3:
Variables: X R S Z1 E2 Z 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 (natCase E1 Z X S) (natCase E2 Z1 X S) @
S1 : subst X R E1 E2 *
S2 : subst X R Z Z1 *
H1 : is_e E1
H2 : is_e Z
H3 : is_string X
H4 : is_e S
H5 : is_e E2
H6 : is_e Z1
============================
is_e (natCase E2 Z1 X S)
< search.
Subgoal 4:
Variables: X R S1 Y Z1 E2 S Z E1
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsE : is_e (natCase E1 Z Y S)
IsR : is_e R
S : subst X R (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
============================
is_e (natCase E2 Z1 Y S1)
< case IsE.
Subgoal 4:
Variables: X R S1 Y Z1 E2 S Z 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 (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
H1 : is_e E1
H2 : is_e Z
H3 : is_string Y
H4 : is_e S
============================
is_e (natCase E2 Z1 Y S1)
< apply IH to _ _ S2.
Subgoal 4:
Variables: X R S1 Y Z1 E2 S Z 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 (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
H1 : is_e E1
H2 : is_e Z
H3 : is_string Y
H4 : is_e S
H5 : is_e E2
============================
is_e (natCase E2 Z1 Y S1)
< apply IH to _ _ S3.
Subgoal 4:
Variables: X R S1 Y Z1 E2 S Z 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 (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
H1 : is_e E1
H2 : is_e Z
H3 : is_string Y
H4 : is_e S
H5 : is_e E2
H6 : is_e Z1
============================
is_e (natCase E2 Z1 Y S1)
< apply IH to _ _ S4.
Subgoal 4:
Variables: X R S1 Y Z1 E2 S Z 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 (natCase E1 Z Y S) (natCase E2 Z1 Y S1) @
S1 : X = Y -> false
S2 : subst X R E1 E2 *
S3 : subst X R Z Z1 *
S4 : subst X R S S1 *
H1 : is_e E1
H2 : is_e Z
H3 : is_string Y
H4 : is_e S
H5 : is_e E2
H6 : is_e Z1
H7 : is_e S1
============================
is_e (natCase E2 Z1 Y S1)
< search.
Proof completed.
< Prove mtc:shared_declarations:evalStep_is.
Subgoal 4:
Variables: S X Z E2 E1
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
IsE : is_e (natCase E1 Z X S)
Ev : evalStep (natCase E1 Z X S) (natCase E2 Z X S) @
Ev1 : evalStep E1 E2 *
============================
is_e (natCase E2 Z X S)
< case IsE.
Subgoal 4:
Variables: S X Z E2 E1
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (natCase E1 Z X S) (natCase E2 Z X S) @
Ev1 : evalStep E1 E2 *
H1 : is_e E1
H2 : is_e Z
H3 : is_string X
H4 : is_e S
============================
is_e (natCase E2 Z X S)
< apply IH to _ Ev1.
Subgoal 4:
Variables: S X Z E2 E1
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (natCase E1 Z X S) (natCase E2 Z X S) @
Ev1 : evalStep E1 E2 *
H1 : is_e E1
H2 : is_e Z
H3 : is_string X
H4 : is_e S
H5 : is_e E2
============================
is_e (natCase E2 Z X S)
< search.
Subgoal 5:
Variables: E' S X
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
IsE : is_e (natCase (num z) E' X S)
Ev : evalStep (natCase (num z) E' X S) E' @
============================
is_e E'
< case IsE.
Subgoal 5:
Variables: E' S X
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (natCase (num z) E' X S) E' @
H1 : is_e (num z)
H2 : is_e E'
H3 : is_string X
H4 : is_e S
============================
is_e E'
< search.
Subgoal 6:
Variables: E' S X Z N
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
IsE : is_e (natCase (num (s N)) Z X S)
Ev : evalStep (natCase (num (s N)) Z X S) E' @
Ev1 : subst X (num N) S E'
============================
is_e E'
< Is: case IsE.
Subgoal 6:
Variables: E' S X Z N
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (natCase (num (s N)) Z X S) E' @
Ev1 : subst X (num N) S E'
Is : is_e (num (s N))
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
============================
is_e E'
< Is: case Is.
Subgoal 6:
Variables: E' S X Z N
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (natCase (num (s N)) Z X S) E' @
Ev1 : subst X (num N) S E'
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Is : is_nat (s N)
============================
is_e E'
< case Is.
Subgoal 6:
Variables: E' S X Z N
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (natCase (num (s N)) Z X S) E' @
Ev1 : subst X (num N) S E'
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
H1 : is_nat N
============================
is_e E'
< apply subst_is to _ _ Ev1.
Subgoal 6:
Variables: E' S X Z N
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (natCase (num (s N)) Z X S) E' @
Ev1 : subst X (num N) S E'
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
H1 : is_nat N
H2 : is_e E'
============================
is_e E'
< search.
Proof completed.
< Prove mtc:shared_declarations:subst_total.
Subgoal 4:
Variables: X R E3 S E1 E2
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (natCase E2 E1 S E3) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E2 *
IsE2 : is_e E1 *
IsE3 : is_string S
IsE4 : is_e E3 *
============================
exists E', subst X R (natCase E2 E1 S E3) E'
< apply IH to IsE1 IsX IsR.
Subgoal 4:
Variables: X R E3 S E1 E2 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 (natCase E2 E1 S E3) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E2 *
IsE2 : is_e E1 *
IsE3 : is_string S
IsE4 : is_e E3 *
H1 : subst X R E2 E'
============================
exists E', subst X R (natCase E2 E1 S E3) E'
< apply IH to IsE2 IsX IsR.
Subgoal 4:
Variables: X R E3 S E1 E2 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 (natCase E2 E1 S E3) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E2 *
IsE2 : is_e E1 *
IsE3 : is_string S
IsE4 : is_e E3 *
H1 : subst X R E2 E'
H2 : subst X R E1 E'1
============================
exists E', subst X R (natCase E2 E1 S E3) E'
< apply IH to IsE4 IsX IsR.
Subgoal 4:
Variables: X R E3 S E1 E2 E' E'1 E'2
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (natCase E2 E1 S E3) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E2 *
IsE2 : is_e E1 *
IsE3 : is_string S
IsE4 : is_e E3 *
H1 : subst X R E2 E'
H2 : subst X R E1 E'1
H3 : subst X R E3 E'2
============================
exists E', subst X R (natCase E2 E1 S E3) E'
< Or: apply is_string_eq_or_not to IsX IsE3.
Subgoal 4:
Variables: X R E3 S E1 E2 E' E'1 E'2
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (natCase E2 E1 S E3) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E2 *
IsE2 : is_e E1 *
IsE3 : is_string S
IsE4 : is_e E3 *
H1 : subst X R E2 E'
H2 : subst X R E1 E'1
H3 : subst X R E3 E'2
Or : X = S \/ (X = S -> false)
============================
exists E', subst X R (natCase E2 E1 S E3) E'
< case Or.
Subgoal 4.1:
Variables: R E3 S E1 E2 E' E'1 E'2
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (natCase E2 E1 S E3) @
IsX : is_string S
IsR : is_e R
IsE1 : is_e E2 *
IsE2 : is_e E1 *
IsE3 : is_string S
IsE4 : is_e E3 *
H1 : subst S R E2 E'
H2 : subst S R E1 E'1
H3 : subst S R E3 E'2
============================
exists E', subst S R (natCase E2 E1 S E3) E'
< search.
Subgoal 4.2:
Variables: X R E3 S E1 E2 E' E'1 E'2
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (natCase E2 E1 S E3) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E2 *
IsE2 : is_e E1 *
IsE3 : is_string S
IsE4 : is_e E3 *
H1 : subst X R E2 E'
H2 : subst X R E1 E'1
H3 : subst X R E3 E'2
H4 : X = S -> false
============================
exists E', subst X R (natCase E2 E1 S E3) E'
< search.
Proof completed.
< Prove mtc:shared_declarations:progress.
Subgoal 3:
Variables: Ty S X Z E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
IsE : is_e (natCase E1 Z X S)
Ty : typeOf [] (natCase E1 Z X S) Ty @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
============================
value (natCase E1 Z X S) \/ (exists E', evalStep (natCase E1 Z X S) E')
< Is: case IsE.
Subgoal 3:
Variables: Ty S X Z E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase E1 Z X S) Ty @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is : is_e E1
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
============================
value (natCase E1 Z X S) \/ (exists E', evalStep (natCase E1 Z X S) E')
< Or: apply IH to _ Ty1.
Subgoal 3:
Variables: Ty S X Z E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase E1 Z X S) Ty @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is : is_e E1
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Or : value E1 \/ (exists E', evalStep E1 E')
============================
value (natCase E1 Z X S) \/ (exists E', evalStep (natCase E1 Z X S) E')
< Ev: case Or.
Subgoal 3.1:
Variables: Ty S X Z E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase E1 Z X S) Ty @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is : is_e E1
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Ev : value E1
============================
value (natCase E1 Z X S) \/ (exists E', evalStep (natCase E1 Z X S) E')
< C: apply canonical_form to Ev Ty1.
Subgoal 3.1:
Variables: Ty S X Z E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase E1 Z X S) Ty @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is : is_e E1
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Ev : value E1
C : canon natTy E1
============================
value (natCase E1 Z X S) \/ (exists E', evalStep (natCase E1 Z X S) E')
< case C.
Subgoal 3.1:
Variables: Ty S X Z N
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase (num N) Z X S) Ty @
Ty1 : typeOf [] (num N) natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is : is_e (num N)
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Ev : value (num N)
============================
value (natCase (num N) Z X S) \/
(exists E', evalStep (natCase (num N) Z X S) E')
< IsN: case Is.
Subgoal 3.1:
Variables: Ty S X Z N
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase (num N) Z X S) Ty @
Ty1 : typeOf [] (num N) natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Ev : value (num N)
IsN : is_nat N
============================
value (natCase (num N) Z X S) \/
(exists E', evalStep (natCase (num N) Z X S) E')
< Or: apply fix_nat to IsN.
Subgoal 3.1:
Variables: Ty S X Z N
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase (num N) Z X S) Ty @
Ty1 : typeOf [] (num N) natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Ev : value (num N)
IsN : is_nat N
Or : N = z \/ (exists N', N = s N')
============================
value (natCase (num N) Z X S) \/
(exists E', evalStep (natCase (num N) Z X S) E')
< case Or.
Subgoal 3.1.1:
Variables: Ty S X Z
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase (num z) Z X S) Ty @
Ty1 : typeOf [] (num z) natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Ev : value (num z)
IsN : is_nat z
============================
value (natCase (num z) Z X S) \/
(exists E', evalStep (natCase (num z) Z X S) E')
< search.
Subgoal 3.1.2:
Variables: Ty S X Z N'
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase (num (s N')) Z X S) Ty @
Ty1 : typeOf [] (num (s N')) natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Ev : value (num (s N'))
IsN : is_nat (s N')
============================
value (natCase (num (s N')) Z X S) \/
(exists E', evalStep (natCase (num (s N')) Z X S) E')
< case IsN.
Subgoal 3.1.2:
Variables: Ty S X Z N'
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase (num (s N')) Z X S) Ty @
Ty1 : typeOf [] (num (s N')) natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Ev : value (num (s N'))
H1 : is_nat N'
============================
value (natCase (num (s N')) Z X S) \/
(exists E', evalStep (natCase (num (s N')) Z X S) E')
< apply subst_total to Is3 Is2 _ with
R = num N'.
Subgoal 3.1.2:
Variables: Ty S X Z N' E'
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase (num (s N')) Z X S) Ty @
Ty1 : typeOf [] (num (s N')) natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Ev : value (num (s N'))
H1 : is_nat N'
H2 : subst X (num N') S E'
============================
value (natCase (num (s N')) Z X S) \/
(exists E', evalStep (natCase (num (s N')) Z X S) E')
< search.
Subgoal 3.2:
Variables: Ty S X Z E1 E'
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (natCase E1 Z X S) Ty @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] Z Ty *
Ty3 : typeOf [(X, natTy)] S Ty *
Is : is_e E1
Is1 : is_e Z
Is2 : is_string X
Is3 : is_e S
Ev : evalStep E1 E'
============================
value (natCase E1 Z X S) \/ (exists E', evalStep (natCase E1 Z X S) E')
< search.
Proof completed.
