< Module mtc:arith.
< Extensible_Theorem
fix_nat : forall N,
IsN : is_nat N ->
N = z \/
(exists N', N = s N')
on IsN.
Subgoal 1:
IH : forall N, is_nat N * -> N = z \/ (exists N', N = s N')
IsN : is_nat z @
============================
z = z \/ (exists N', z = s N')
< search.
Subgoal 2:
Variables: Nat
IH : forall N, is_nat N * -> N = z \/ (exists N', N = s N')
IsN : is_nat (s Nat) @
IsN1 : is_nat Nat *
============================
s Nat = z \/ (exists N', s Nat = s N')
< search.
Proof completed.
< Prove mtc:shared_declarations:type_preservation.
Subgoal 1:
Variables: TG Ty EG N
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 (num N) Ty
Ev : eval EG (num N) (numVal N) @
============================
valueType (numVal N) Ty
< case Ty.
Subgoal 1:
Variables: TG EG N
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 (num N) (numVal N) @
============================
valueType (numVal N) natTy
< search.
Subgoal 2:
Variables: TG Ty EG N1 N2 N 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 (plus E1 E2) Ty
Ev : eval EG (plus E1 E2) (numVal N) @
Ev1 : eval EG E1 (numVal N1) *
Ev2 : eval EG E2 (numVal N2) *
Ev3 : plusRel N1 N2 N
============================
valueType (numVal N) Ty
< case Ty.
Subgoal 2:
Variables: TG EG N1 N2 N 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
Ev : eval EG (plus E1 E2) (numVal N) @
Ev1 : eval EG E1 (numVal N1) *
Ev2 : eval EG E2 (numVal N2) *
Ev3 : plusRel N1 N2 N
H1 : typeOf TG E1 natTy
H2 : typeOf TG E2 natTy
============================
valueType (numVal N) natTy
< search.
Proof completed.
< Prove mtc:shared_declarations:value_evalStep_false.
Subgoal 1:
Variables: E' N
IH : forall E E', value E * -> evalStep E E' -> false
V : value (num N) @
Ev : evalStep (num N) E'
============================
false
< case Ev.
Proof completed.
< Theorem plusRel_unique :
forall N1 N2 A B, plusRel N1 N2 A -> plusRel N1 N2 B -> A = B.
============================
forall N1 N2 A B, plusRel N1 N2 A -> plusRel N1 N2 B -> A = B
< induction on 1.
IH : forall N1 N2 A B, plusRel N1 N2 A * -> plusRel N1 N2 B -> A = B
============================
forall N1 N2 A B, plusRel N1 N2 A @ -> plusRel N1 N2 B -> A = B
< intros PA PB.
Variables: N1 N2 A B
IH : forall N1 N2 A B, plusRel N1 N2 A * -> plusRel N1 N2 B -> A = B
PA : plusRel N1 N2 A @
PB : plusRel N1 N2 B
============================
A = B
< PA: case PA.
Subgoal 1:
Variables: A B
IH : forall N1 N2 A B, plusRel N1 N2 A * -> plusRel N1 N2 B -> A = B
PB : plusRel z A B
============================
A = B
< case PB.
Subgoal 1:
Variables: B
IH : forall N1 N2 A B, plusRel N1 N2 A * -> plusRel N1 N2 B -> A = B
============================
B = B
< search.
Subgoal 2:
Variables: N2 B N5 N3
IH : forall N1 N2 A B, plusRel N1 N2 A * -> plusRel N1 N2 B -> A = B
PB : plusRel (s N3) N2 B
PA : plusRel N3 N2 N5 *
============================
s N5 = B
< PB: case PB.
Subgoal 2:
Variables: N2 N5 N3 N7
IH : forall N1 N2 A B, plusRel N1 N2 A * -> plusRel N1 N2 B -> A = B
PA : plusRel N3 N2 N5 *
PB : plusRel N3 N2 N7
============================
s N5 = s N7
< apply IH to PA PB.
Subgoal 2:
Variables: N2 N3 N7
IH : forall N1 N2 A B, plusRel N1 N2 A * -> plusRel N1 N2 B -> A = B
PA : plusRel N3 N2 N7 *
PB : plusRel N3 N2 N7
============================
s N7 = s N7
< search.
Proof completed.
< Prove mtc:shared_declarations:subst_unique.
Subgoal 1:
Variables: X R EB N
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (num N) (num N) @
SB : subst X R (num N) EB
============================
num N = EB
< case SB.
Subgoal 1:
Variables: X R N
IH : forall X R E EA EB, subst X R E EA * -> subst X R E EB -> EA = EB
SA : subst X R (num N) (num N) @
============================
num N = num N
< search.
Subgoal 2:
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 (plus E1 E2) (plus E11 E21) @
SB : subst X R (plus E1 E2) EB
SA1 : subst X R E1 E11 *
SA2 : subst X R E2 E21 *
============================
plus E11 E21 = EB
< SB: case SB.
Subgoal 2:
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 (plus E1 E2) (plus 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
============================
plus E11 E21 = plus E5 E6
< apply IH to SA1 SB.
Subgoal 2:
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 (plus E1 E2) (plus 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
============================
plus E5 E21 = plus E5 E6
< apply IH to SA2 SB1.
Subgoal 2:
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 (plus E1 E2) (plus 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
============================
plus E5 E6 = plus E5 E6
< 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 (plus E1 E2) (plus E11 E2) @
EvB : evalStep (plus E1 E2) EB
EvA1 : evalStep E1 E11 *
============================
plus 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 (plus E1 E2) (plus E11 E2) @
EvA1 : evalStep E1 E11 *
EvB : evalStep E1 E5
============================
plus E11 E2 = plus 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 (plus E1 E2) (plus E5 E2) @
EvA1 : evalStep E1 E5 *
EvB : evalStep E1 E5
============================
plus E5 E2 = plus 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 (plus E1 E2) (plus E11 E2) @
EvA1 : evalStep E1 E11 *
EvB : value E1
EvB1 : evalStep E2 E21
============================
plus E11 E2 = plus E1 E21
< apply value_evalStep_false to EvB EvA1.
Subgoal 1.3:
Variables: E11 N N2 N1
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (plus (num N1) (num N2)) (plus E11 (num N2)) @
EvA1 : evalStep (num N1) E11 *
EvB : plusRel N1 N2 N
============================
plus E11 (num N2) = num N
< case EvA1.
Subgoal 2:
Variables: EB E21 E1 E2
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (plus E1 E2) (plus E1 E21) @
EvB : evalStep (plus E1 E2) EB
EvA1 : value E1
EvA2 : evalStep E2 E21 *
============================
plus 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 (plus E1 E2) (plus E1 E21) @
EvA1 : value E1
EvA2 : evalStep E2 E21 *
EvB : evalStep E1 E11
============================
plus E1 E21 = plus 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 (plus E1 E2) (plus E1 E21) @
EvA1 : value E1
EvA2 : evalStep E2 E21 *
EvB : value E1
EvB1 : evalStep E2 E5
============================
plus E1 E21 = plus 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 (plus E1 E2) (plus E1 E5) @
EvA1 : value E1
EvA2 : evalStep E2 E5 *
EvB : value E1
EvB1 : evalStep E2 E5
============================
plus E1 E5 = plus E1 E5
< search.
Subgoal 2.3:
Variables: E21 N N2 N1
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (plus (num N1) (num N2)) (plus (num N1) E21) @
EvA1 : value (num N1)
EvA2 : evalStep (num N2) E21 *
EvB : plusRel N1 N2 N
============================
plus (num N1) E21 = num N
< case EvA2.
Subgoal 3:
Variables: EB N N2 N1
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (plus (num N1) (num N2)) (num N) @
EvB : evalStep (plus (num N1) (num N2)) EB
EvA1 : plusRel N1 N2 N
============================
num N = EB
< EvB: case EvB.
Subgoal 3.1:
Variables: N N2 N1 E11
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (plus (num N1) (num N2)) (num N) @
EvA1 : plusRel N1 N2 N
EvB : evalStep (num N1) E11
============================
num N = plus E11 (num N2)
< case EvB.
Subgoal 3.2:
Variables: N N2 N1 E21
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (plus (num N1) (num N2)) (num N) @
EvA1 : plusRel N1 N2 N
EvB : value (num N1)
EvB1 : evalStep (num N2) E21
============================
num N = plus (num N1) E21
< case EvB1.
Subgoal 3.3:
Variables: N N2 N1 N5
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (plus (num N1) (num N2)) (num N) @
EvA1 : plusRel N1 N2 N
EvB : plusRel N1 N2 N5
============================
num N = num N5
< apply plusRel_unique to EvA1 EvB.
Subgoal 3.3:
Variables: N2 N1 N5
IH : forall E EA EB, evalStep E EA * -> evalStep E EB -> EA = EB
EvA : evalStep (plus (num N1) (num N2)) (num N5) @
EvA1 : plusRel N1 N2 N5
EvB : plusRel N1 N2 N5
============================
num N5 = num N5
< search.
Proof completed.
< Prove mtc:shared_declarations:ty_lookup.
Subgoal 1:
Variables: G1 G2 N
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 (num N) natTy @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
============================
typeOf G2 (num N) natTy
< search.
Subgoal 2:
Variables: G1 G2 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 (plus E1 E2) natTy @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 E2 natTy *
============================
typeOf G2 (plus E1 E2) natTy
< apply IH to Ty1 L.
Subgoal 2:
Variables: G1 G2 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 (plus E1 E2) natTy @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 E2 natTy *
H1 : typeOf G2 E1 natTy
============================
typeOf G2 (plus E1 E2) natTy
< apply IH to Ty2 L.
Subgoal 2:
Variables: G1 G2 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 (plus E1 E2) natTy @
L : forall X XTy, lookup G1 X XTy -> lookup G2 X XTy
Ty1 : typeOf G1 E1 natTy *
Ty2 : typeOf G1 E2 natTy *
H1 : typeOf G2 E1 natTy
H2 : typeOf G2 E2 natTy
============================
typeOf G2 (plus E1 E2) natTy
< search.
Proof completed.
< Prove mtc:shared_declarations:subst_preservation.
Subgoal 1:
Variables: X XTy TG Ty R N
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) (num N) Ty
S : subst X R (num N) (num N) @
RTy : typeOf [] R XTy
============================
typeOf TG (num N) Ty
< case Ty.
Subgoal 1:
Variables: X XTy TG R N
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 (num N) (num N) @
RTy : typeOf [] R XTy
============================
typeOf TG (num N) natTy
< search.
Subgoal 2:
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) (plus E1 E2) Ty
S : subst X R (plus E1 E2) (plus E11 E21) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
============================
typeOf TG (plus E11 E21) Ty
< Ty: case Ty.
Subgoal 2:
Variables: X XTy TG 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
S : subst X R (plus E1 E2) (plus E11 E21) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) E2 natTy
============================
typeOf TG (plus E11 E21) natTy
< apply IH to Ty S1 RTy.
Subgoal 2:
Variables: X XTy TG 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
S : subst X R (plus E1 E2) (plus E11 E21) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) E2 natTy
H1 : typeOf TG E11 natTy
============================
typeOf TG (plus E11 E21) natTy
< apply IH to Ty1 S2 RTy.
Subgoal 2:
Variables: X XTy TG 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
S : subst X R (plus E1 E2) (plus E11 E21) @
RTy : typeOf [] R XTy
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
Ty : typeOf ((X, XTy)::TG) E1 natTy
Ty1 : typeOf ((X, XTy)::TG) E2 natTy
H1 : typeOf TG E11 natTy
H2 : typeOf TG E21 natTy
============================
typeOf TG (plus E11 E21) natTy
< 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 [] (plus E1 E2) Ty
Ev : evalStep (plus E1 E2) (plus E11 E2) @
Ev1 : evalStep E1 E11 *
============================
typeOf [] (plus E11 E2) Ty
< Ty: case Ty.
Subgoal 1:
Variables: E2 E11 E1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (plus E1 E2) (plus E11 E2) @
Ev1 : evalStep E1 E11 *
Ty : typeOf [] E1 natTy
Ty1 : typeOf [] E2 natTy
============================
typeOf [] (plus E11 E2) natTy
< apply IH to Ty Ev1.
Subgoal 1:
Variables: E2 E11 E1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (plus E1 E2) (plus E11 E2) @
Ev1 : evalStep E1 E11 *
Ty : typeOf [] E1 natTy
Ty1 : typeOf [] E2 natTy
H1 : typeOf [] E11 natTy
============================
typeOf [] (plus E11 E2) natTy
< search.
Subgoal 2:
Variables: Ty E21 E1 E2
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ty : typeOf [] (plus E1 E2) Ty
Ev : evalStep (plus E1 E2) (plus E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
============================
typeOf [] (plus E1 E21) Ty
< Ty: case Ty.
Subgoal 2:
Variables: E21 E1 E2
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (plus E1 E2) (plus E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
Ty : typeOf [] E1 natTy
Ty1 : typeOf [] E2 natTy
============================
typeOf [] (plus E1 E21) natTy
< apply IH to Ty1 Ev2.
Subgoal 2:
Variables: E21 E1 E2
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (plus E1 E2) (plus E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
Ty : typeOf [] E1 natTy
Ty1 : typeOf [] E2 natTy
H1 : typeOf [] E21 natTy
============================
typeOf [] (plus E1 E21) natTy
< search.
Subgoal 3:
Variables: Ty N N2 N1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ty : typeOf [] (plus (num N1) (num N2)) Ty
Ev : evalStep (plus (num N1) (num N2)) (num N) @
Ev1 : plusRel N1 N2 N
============================
typeOf [] (num N) Ty
< case Ty.
Subgoal 3:
Variables: N N2 N1
IH : forall E Ty E', typeOf [] E Ty -> evalStep E E' * -> typeOf [] E' Ty
Ev : evalStep (plus (num N1) (num N2)) (num N) @
Ev1 : plusRel N1 N2 N
H1 : typeOf [] (num N1) natTy
H2 : typeOf [] (num N2) natTy
============================
typeOf [] (num N) natTy
< search.
Proof completed.
< Prove mtc:shared_declarations:canonical_form.
Subgoal 1:
Variables: Ty N
IH : forall V Ty, value V * -> typeOf [] V Ty -> canon Ty V
V : value (num N) @
Ty : typeOf [] (num N) Ty
============================
canon Ty (num N)
< case Ty.
Subgoal 1:
Variables: N
IH : forall V Ty, value V * -> typeOf [] V Ty -> canon Ty V
V : value (num N) @
============================
canon natTy (num N)
< search.
Proof completed.
< Prove mtc:shared_declarations:subst_is.
Subgoal 1:
Variables: X R N
IH : forall X R E E', is_e E -> is_e R -> subst X R E E' * -> is_e E'
IsE : is_e (num N)
IsR : is_e R
S : subst X R (num N) (num N) @
============================
is_e (num N)
< search.
Subgoal 2:
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 (plus E1 E2)
IsR : is_e R
S : subst X R (plus E1 E2) (plus E11 E21) @
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
============================
is_e (plus E11 E21)
< case IsE.
Subgoal 2:
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 (plus E1 E2) (plus E11 E21) @
S1 : subst X R E1 E11 *
S2 : subst X R E2 E21 *
H1 : is_e E1
H2 : is_e E2
============================
is_e (plus E11 E21)
< apply IH to _ _ S1.
Subgoal 2:
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 (plus E1 E2) (plus 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 (plus E11 E21)
< apply IH to _ _ S2.
Subgoal 2:
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 (plus E1 E2) (plus 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 (plus E11 E21)
< search.
Proof completed.
< Theorem plusRel_is :
forall A B C, is_nat A -> is_nat B -> plusRel A B C -> is_nat C.
============================
forall A B C, is_nat A -> is_nat B -> plusRel A B C -> is_nat C
< induction on 3.
IH : forall A B C, is_nat A -> is_nat B -> plusRel A B C * -> is_nat C
============================
forall A B C, is_nat A -> is_nat B -> plusRel A B C @ -> is_nat C
< intros IsA IsB P.
Variables: A B C
IH : forall A B C, is_nat A -> is_nat B -> plusRel A B C * -> is_nat C
IsA : is_nat A
IsB : is_nat B
P : plusRel A B C @
============================
is_nat C
< P: case P.
Subgoal 1:
Variables: C
IH : forall A B C, is_nat A -> is_nat B -> plusRel A B C * -> is_nat C
IsA : is_nat z
IsB : is_nat C
============================
is_nat C
< search.
Subgoal 2:
Variables: B N3 N1
IH : forall A B C, is_nat A -> is_nat B -> plusRel A B C * -> is_nat C
IsA : is_nat (s N1)
IsB : is_nat B
P : plusRel N1 B N3 *
============================
is_nat (s N3)
< case IsA.
Subgoal 2:
Variables: B N3 N1
IH : forall A B C, is_nat A -> is_nat B -> plusRel A B C * -> is_nat C
IsB : is_nat B
P : plusRel N1 B N3 *
H1 : is_nat N1
============================
is_nat (s N3)
< apply IH to _ _ P.
Subgoal 2:
Variables: B N3 N1
IH : forall A B C, is_nat A -> is_nat B -> plusRel A B C * -> is_nat C
IsB : is_nat B
P : plusRel N1 B N3 *
H1 : is_nat N1
H2 : is_nat N3
============================
is_nat (s N3)
< 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 (plus E1 E2)
Ev : evalStep (plus E1 E2) (plus E11 E2) @
Ev1 : evalStep E1 E11 *
============================
is_e (plus 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 (plus E1 E2) (plus E11 E2) @
Ev1 : evalStep E1 E11 *
H1 : is_e E1
H2 : is_e E2
============================
is_e (plus 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 (plus E1 E2) (plus E11 E2) @
Ev1 : evalStep E1 E11 *
H1 : is_e E1
H2 : is_e E2
H3 : is_e E11
============================
is_e (plus 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 (plus E1 E2)
Ev : evalStep (plus E1 E2) (plus E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
============================
is_e (plus 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 (plus E1 E2) (plus E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
H1 : is_e E1
H2 : is_e E2
============================
is_e (plus 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 (plus E1 E2) (plus E1 E21) @
Ev1 : value E1
Ev2 : evalStep E2 E21 *
H1 : is_e E1
H2 : is_e E2
H3 : is_e E21
============================
is_e (plus E1 E21)
< search.
Subgoal 3:
Variables: N N2 N1
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
IsE : is_e (plus (num N1) (num N2))
Ev : evalStep (plus (num N1) (num N2)) (num N) @
Ev1 : plusRel N1 N2 N
============================
is_e (num N)
< Is: case IsE.
Subgoal 3:
Variables: N N2 N1
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (plus (num N1) (num N2)) (num N) @
Ev1 : plusRel N1 N2 N
Is : is_e (num N1)
Is1 : is_e (num N2)
============================
is_e (num N)
< case Is.
Subgoal 3:
Variables: N N2 N1
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (plus (num N1) (num N2)) (num N) @
Ev1 : plusRel N1 N2 N
Is1 : is_e (num N2)
H1 : is_nat N1
============================
is_e (num N)
< case Is1.
Subgoal 3:
Variables: N N2 N1
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (plus (num N1) (num N2)) (num N) @
Ev1 : plusRel N1 N2 N
H1 : is_nat N1
H2 : is_nat N2
============================
is_e (num N)
< apply plusRel_is to _ _ Ev1.
Subgoal 3:
Variables: N N2 N1
IH : forall E E', is_e E -> evalStep E E' * -> is_e E'
Ev : evalStep (plus (num N1) (num N2)) (num N) @
Ev1 : plusRel N1 N2 N
H1 : is_nat N1
H2 : is_nat N2
H3 : is_nat N
============================
is_e (num N)
< search.
Proof completed.
< Prove mtc:shared_declarations:subst_total.
Subgoal 2:
Variables: X R Nat
IH : forall X R E,
is_e E * -> is_string X -> is_e R -> exists E', subst X R E E'
IsE : is_e (num Nat) @
IsX : is_string X
IsR : is_e R
IsE1 : is_nat Nat
============================
exists E', subst X R (num Nat) 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 (plus E1 E2) @
IsX : is_string X
IsR : is_e R
IsE1 : is_e E1 *
IsE2 : is_e E2 *
============================
exists E', subst X R (plus 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 (plus 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 (plus 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 (plus 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 (plus E1 E2) E'
< search.
Proof completed.
< Theorem plusRel_total :
forall N1 N2, is_nat N1 -> exists N, plusRel N1 N2 N.
============================
forall N1 N2, is_nat N1 -> exists N, plusRel N1 N2 N
< induction on 1.
IH : forall N1 N2, is_nat N1 * -> exists N, plusRel N1 N2 N
============================
forall N1 N2, is_nat N1 @ -> exists N, plusRel N1 N2 N
< intros Is.
Variables: N1 N2
IH : forall N1 N2, is_nat N1 * -> exists N, plusRel N1 N2 N
Is : is_nat N1 @
============================
exists N, plusRel N1 N2 N
< Or: apply fix_nat to Is.
Variables: N1 N2
IH : forall N1 N2, is_nat N1 * -> exists N, plusRel N1 N2 N
Is : is_nat N1 @
Or : N1 = z \/ (exists N', N1 = s N')
============================
exists N, plusRel N1 N2 N
< case Or.
Subgoal 1:
Variables: N2
IH : forall N1 N2, is_nat N1 * -> exists N, plusRel N1 N2 N
Is : is_nat z @
============================
exists N, plusRel z N2 N
< search.
Subgoal 2:
Variables: N2 N'
IH : forall N1 N2, is_nat N1 * -> exists N, plusRel N1 N2 N
Is : is_nat (s N') @
============================
exists N, plusRel (s N') N2 N
< Is: case Is.
Subgoal 2:
Variables: N2 N'
IH : forall N1 N2, is_nat N1 * -> exists N, plusRel N1 N2 N
Is : is_nat N' *
============================
exists N, plusRel (s N') N2 N
< apply IH to Is with
N2 = N2.
Subgoal 2:
Variables: N2 N' N
IH : forall N1 N2, is_nat N1 * -> exists N, plusRel N1 N2 N
Is : is_nat N' *
H1 : plusRel N' N2 N
============================
exists N, plusRel (s N') N2 N
< search.
Proof completed.
< Prove mtc:shared_declarations:progress.
Subgoal 1:
Variables: N
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
IsE : is_e (num N)
Ty : typeOf [] (num N) natTy @
============================
value (num N) \/ (exists E', evalStep (num N) E')
< search.
Subgoal 2:
Variables: E2 E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
IsE : is_e (plus E1 E2)
Ty : typeOf [] (plus E1 E2) natTy @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] E2 natTy *
============================
value (plus E1 E2) \/ (exists E', evalStep (plus E1 E2) E')
< Is: case IsE.
Subgoal 2:
Variables: E2 E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus E1 E2) natTy @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] E2 natTy *
Is : is_e E1
Is1 : is_e E2
============================
value (plus E1 E2) \/ (exists E', evalStep (plus E1 E2) E')
< Or1: apply IH to _ Ty1.
Subgoal 2:
Variables: E2 E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus E1 E2) natTy @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] E2 natTy *
Is : is_e E1
Is1 : is_e E2
Or1 : value E1 \/ (exists E', evalStep E1 E')
============================
value (plus E1 E2) \/ (exists E', evalStep (plus E1 E2) E')
< Or2: apply IH to _ Ty2.
Subgoal 2:
Variables: E2 E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus E1 E2) natTy @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] E2 natTy *
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 (plus E1 E2) \/ (exists E', evalStep (plus E1 E2) E')
< Ev1: case Or1.
Subgoal 2.1:
Variables: E2 E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus E1 E2) natTy @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] E2 natTy *
Is : is_e E1
Is1 : is_e E2
Or2 : value E2 \/ (exists E', evalStep E2 E')
Ev1 : value E1
============================
value (plus E1 E2) \/ (exists E', evalStep (plus E1 E2) E')
< Ev2: case Or2.
Subgoal 2.1.1:
Variables: E2 E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus E1 E2) natTy @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] E2 natTy *
Is : is_e E1
Is1 : is_e E2
Ev1 : value E1
Ev2 : value E2
============================
value (plus E1 E2) \/ (exists E', evalStep (plus E1 E2) E')
< C1: apply canonical_form to Ev1 Ty1.
Subgoal 2.1.1:
Variables: E2 E1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus E1 E2) natTy @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] E2 natTy *
Is : is_e E1
Is1 : is_e E2
Ev1 : value E1
Ev2 : value E2
C1 : canon natTy E1
============================
value (plus E1 E2) \/ (exists E', evalStep (plus E1 E2) E')
< case C1.
Subgoal 2.1.1:
Variables: E2 N
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus (num N) E2) natTy @
Ty1 : typeOf [] (num N) natTy *
Ty2 : typeOf [] E2 natTy *
Is : is_e (num N)
Is1 : is_e E2
Ev1 : value (num N)
Ev2 : value E2
============================
value (plus (num N) E2) \/ (exists E', evalStep (plus (num N) E2) E')
< C2: apply canonical_form to Ev2 Ty2.
Subgoal 2.1.1:
Variables: E2 N
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus (num N) E2) natTy @
Ty1 : typeOf [] (num N) natTy *
Ty2 : typeOf [] E2 natTy *
Is : is_e (num N)
Is1 : is_e E2
Ev1 : value (num N)
Ev2 : value E2
C2 : canon natTy E2
============================
value (plus (num N) E2) \/ (exists E', evalStep (plus (num N) E2) E')
< case C2.
Subgoal 2.1.1:
Variables: N N1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus (num N) (num N1)) natTy @
Ty1 : typeOf [] (num N) natTy *
Ty2 : typeOf [] (num N1) natTy *
Is : is_e (num N)
Is1 : is_e (num N1)
Ev1 : value (num N)
Ev2 : value (num N1)
============================
value (plus (num N) (num N1)) \/
(exists E', evalStep (plus (num N) (num N1)) E')
< Is: case Is.
Subgoal 2.1.1:
Variables: N N1
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus (num N) (num N1)) natTy @
Ty1 : typeOf [] (num N) natTy *
Ty2 : typeOf [] (num N1) natTy *
Is1 : is_e (num N1)
Ev1 : value (num N)
Ev2 : value (num N1)
Is : is_nat N
============================
value (plus (num N) (num N1)) \/
(exists E', evalStep (plus (num N) (num N1)) E')
< apply plusRel_total to Is with
N2 = N1.
Subgoal 2.1.1:
Variables: N N1 N2
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus (num N) (num N1)) natTy @
Ty1 : typeOf [] (num N) natTy *
Ty2 : typeOf [] (num N1) natTy *
Is1 : is_e (num N1)
Ev1 : value (num N)
Ev2 : value (num N1)
Is : is_nat N
H1 : plusRel N N1 N2
============================
value (plus (num N) (num N1)) \/
(exists E', evalStep (plus (num N) (num N1)) E')
< search.
Subgoal 2.1.2:
Variables: E2 E1 E'
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus E1 E2) natTy @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] E2 natTy *
Is : is_e E1
Is1 : is_e E2
Ev1 : value E1
Ev2 : evalStep E2 E'
============================
value (plus E1 E2) \/ (exists E', evalStep (plus E1 E2) E')
< search.
Subgoal 2.2:
Variables: E2 E1 E'
IH : forall E Ty,
is_e E -> typeOf [] E Ty * -> value E \/ (exists E', evalStep E E')
Ty : typeOf [] (plus E1 E2) natTy @
Ty1 : typeOf [] E1 natTy *
Ty2 : typeOf [] E2 natTy *
Is : is_e E1
Is1 : is_e E2
Or2 : value E2 \/ (exists E', evalStep E2 E')
Ev1 : evalStep E1 E'
============================
value (plus E1 E2) \/ (exists E', evalStep (plus E1 E2) E')
< search.
Proof completed.
