Proof of Nuprl Lemma : term-accum-induction

Step * of Lemma term-accum-induction

No Annotations
∀[opr,P:Type]. ∀[R:P ⟶ term(opr) ⟶ ℙ].
  ∀Q:P ⟶ opr ⟶ (varname() List) ⟶ ((t:term(opr) × p:P × R[p;t]) List) ⟶ P
    ((∀p:P. ∀v:{v:varname()| ¬(v = nullvar() ∈ varname())} .  R[p;varterm(v)])
    ⇒ (∀p:P. ∀f:opr. ∀bts:bound-term(opr) List. ∀L:{L:(t:term(opr) × p:P × R[p;t]) List|

                                                     (||L|| = ||bts|| ∈ ℤ)

                                                     ∧ (∀i:ℕ||L||. ((fst(L[i])) = (snd(bts[i])) ∈ term(opr)))

                                                     ∧ (∀i:ℕ||L||

                                                          ((fst(snd(L[i]))) = Q[p;f;fst(bts[i]);firstn(i;L)] ∈ P))} .

          R[p;mkterm(f;bts)])
    ⇒ {∀t:term(opr). ∀p:P.  R[p;t]})
BY
{ (Intros
   THEN Unfold `guard` 0
   THEN (Enough to prove ∀[n:ℕ]. ∀a:{a:term(opr)| term-size(a) ≤ n} . ∀p:P.  R[p;a]
          Because (Intro THEN InstHyp [⌜term-size(t)⌝;⌜t⌝] (-2)⋅ THEN Auto))
   THEN (UniformCompNatInd THENW Auto)
   THEN Intro
   THEN (InstLemma `term-ext` [⌜opr⌝]⋅ THENA Auto)
   THEN (Assert term-size(a) ≤ n BY
               Auto)
   THEN MoveToConcl (-1)
   THEN (GenConcl ⌜a = t ∈ coterm-fun(opr;term(opr))⌝⋅ THENA Auto)
   THEN ThinVar `a'
   THEN (Assert t ∈ term(opr) BY
               Auto)
   THEN RepeatFor 2 (D -2)
   THEN Folds  ``varterm mkterm`` 0
   THEN Reduce 0
   THEN Auto
   THEN RenameVar `f' (-5)
   THEN RenameVar `bts' (-4)
   THEN (Assert 1 ≤ term-size(mkterm(f;bts)) BY
               Auto)
   THEN Reduce -1
   THEN (InstHyp [⌜p⌝;⌜f⌝;⌜bts⌝] 6⋅ THENA Auto)
   THEN (Assert ∀bt:{bt:varname() List × term(opr)| (bt ∈ bts)} . ∀p:P.  R[p;snd(bt)] BY
               ((D 8 With ⌜n - 1⌝  THENA Auto)
                THEN Intros
                THEN BHyp -3
                THEN Auto

                THEN InstLemma `summand-le-lsum` [⌜varname() List × term(opr)⌝;⌜bts⌝;⌜λ₂bt.term-size(snd(bt))⌝;

                ⌜<b1, b2>⌝]⋅
                THEN Reduce -1
                THEN Auto))
   THEN RenameVar `g' (-1)) }

1
1. [opr] : Type
2. [P] : Type
3. [R] : P ⟶ term(opr) ⟶ ℙ
4. Q : P ⟶ opr ⟶ (varname() List) ⟶ ((t:term(opr) × p:P × R[p;t]) List) ⟶ P
5. ∀p:P. ∀v:{v:varname()| ¬(v = nullvar() ∈ varname())} .  R[p;varterm(v)]
6. ∀p:P. ∀f:opr. ∀bts:bound-term(opr) List. ∀L:{L:(t:term(opr) × p:P × R[p;t]) List|

                                                (||L|| = ||bts|| ∈ ℤ)

                                                ∧ (∀i:ℕ||L||. ((fst(L[i])) = (snd(bts[i])) ∈ term(opr)))

                                                ∧ (∀i:ℕ||L||. ((fst(snd(L[i]))) = Q[p;f;fst(bts[i]);firstn(i;L)] ∈ P))} \000C.

     R[p;mkterm(f;bts)]
7. [n] : ℕ
8. ∀[m:ℕn]. ∀a:{a:term(opr)| term-size(a) ≤ m} . ∀p:P.  R[p;a]
9. term(opr) ≡ coterm-fun(opr;term(opr))
10. f : opr
11. bts : (varname() List × term(opr)) List
12. inr <f, bts>  ∈ term(opr)
13. (1 + Σ(term-size(snd(bt)) | bt ∈ bts)) ≤ n
14. p : P
15. 1 ≤ (1 + Σ(term-size(snd(bt)) | bt ∈ bts))
16. ∀L:{L:(t:term(opr) × p:P × R[p;t]) List|
        (||L|| = ||bts|| ∈ ℤ)
        ∧ (∀i:ℕ||L||. ((fst(L[i])) = (snd(bts[i])) ∈ term(opr)))
        ∧ (∀i:ℕ||L||. ((fst(snd(L[i]))) = Q[p;f;fst(bts[i]);firstn(i;L)] ∈ P))}
      R[p;mkterm(f;bts)]
17. g : ∀bt:{bt:varname() List × term(opr)| (bt ∈ bts)} . ∀p:P.  R[p;snd(bt)]
⊢ R[p;mkterm(f;bts)]

Latex:

Latex:
No Annotations \mforall{}[opr,P:Type]. \mforall{}[R:P {}\mrightarrow{} term(opr) {}\mrightarrow{} \mBbbP{}]. \mforall{}Q:P {}\mrightarrow{} opr {}\mrightarrow{} (varname() List) {}\mrightarrow{} ((t:term(opr) \mtimes{} p:P \mtimes{} R[p;t]) List) {}\mrightarrow{} P ((\mforall{}p:P. \mforall{}v:\{v:varname()| \mneg{}(v = nullvar())\} . R[p;varterm(v)]) {}\mRightarrow{} (\mforall{}p:P. \mforall{}f:opr. \mforall{}bts:bound-term(opr) List. \mforall{}L:\{L:(t:term(opr) \mtimes{} p:P \mtimes{} R[p;t]) List| (||L|| = ||bts||) \mwedge{} (\mforall{}i:\mBbbN{}||L||. ((fst(L[i])) = (snd(bts[i])))) \mwedge{} (\mforall{}i:\mBbbN{}||L|| ((fst(snd(L[i]))) = Q[p;f;fst(bts[i]);firstn(i;L)]))\} . R[p;mkterm(f;bts)]) {}\mRightarrow{} \{\mforall{}t:term(opr). \mforall{}p:P. R[p;t]\}) By Latex: (Intros THEN Unfold `guard` 0 THEN (Enough to prove \mforall{}[n:\mBbbN{}]. \mforall{}a:\{a:term(opr)| term-size(a) \mleq{} n\} . \mforall{}p:P. R[p;a] Because (Intro THEN InstHyp [\mkleeneopen{}term-size(t)\mkleeneclose{};\mkleeneopen{}t\mkleeneclose{}] (-2)\mcdot{} THEN Auto)) THEN (UniformCompNatInd THENW Auto) THEN Intro THEN (InstLemma `term-ext` [\mkleeneopen{}opr\mkleeneclose{}]\mcdot{} THENA Auto) THEN (Assert term-size(a) \mleq{} n BY Auto) THEN MoveToConcl (-1) THEN (GenConcl \mkleeneopen{}a = t\mkleeneclose{}\mcdot{} THENA Auto) THEN ThinVar `a' THEN (Assert t \mmember{} term(opr) BY Auto) THEN RepeatFor 2 (D -2) THEN Folds ``varterm mkterm`` 0 THEN Reduce 0 THEN Auto THEN RenameVar `f' (-5) THEN RenameVar `bts' (-4) THEN (Assert 1 \mleq{} term-size(mkterm(f;bts)) BY Auto) THEN Reduce -1 THEN (InstHyp [\mkleeneopen{}p\mkleeneclose{};\mkleeneopen{}f\mkleeneclose{};\mkleeneopen{}bts\mkleeneclose{}] 6\mcdot{} THENA Auto) THEN (Assert \mforall{}bt:\{bt:varname() List \mtimes{} term(opr)| (bt \mmember{} bts)\} . \mforall{}p:P. R[p;snd(bt)] BY ((D 8 With \mkleeneopen{}n - 1\mkleeneclose{} THENA Auto) THEN Intros THEN BHyp -3 THEN Auto THEN InstLemma `summand-le-lsum` [\mkleeneopen{}varname() List \mtimes{} term(opr)\mkleeneclose{};\mkleeneopen{}bts\mkleeneclose{}; \mkleeneopen{}\mlambda{}\msubtwo{}bt.term-size(snd(bt))\mkleeneclose{};\mkleeneopen{}<b1, b2>\mkleeneclose{}]\mcdot{} THEN Reduce -1 THEN Auto)) THEN RenameVar `g' (-1)) Home Index