---

Step * 1 of Lemma term-accum-induction


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)]
BY
{ (D -2 With ⌜accumulate (with value L and list item bt):
               let p' = Q[p;f;fst(bt);L] in
                   L @ [<snd(bt), p', g bt p'>]
              over list:
                bts
              with starting value:
               [])⌝ 
THENM Trivial
) }

1
.....wf..... 
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. g : ∀bt:{bt:varname() List × term(opr)| (bt ∈ bts)} . ∀p:P.  R[p;snd(bt)]
⊢ accumulate (with value L and list item bt):
   let p' = Q[p;f;fst(bt);L] in
       L @ [<snd(bt), p', g bt p'>]
  over list:
    bts
  with starting value:
   []) ∈ {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))} 

---

Latex:

---

Latex:

1.  [opr]  :  Type
2.  [P]  :  Type
3.  [R]  :  P  {}\mrightarrow{}  term(opr)  {}\mrightarrow{}  \mBbbP{}
4.  Q  :  P  {}\mrightarrow{}  opr  {}\mrightarrow{}  (varname()  List)  {}\mrightarrow{}  ((t:term(opr)  \mtimes{}  p:P  \mtimes{}  R[p;t])  List)  {}\mrightarrow{}  P
5.  \mforall{}p:P.  \mforall{}v:\{v:varname()|  \mneg{}(v  =  nullvar())\}  .    R[p;varterm(v)]
6.  \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)]
7.  [n]  :  \mBbbN{}
8.  \mforall{}[m:\mBbbN{}n].  \mforall{}a:\{a:term(opr)|  term-size(a)  \mleq{}  m\}  .  \mforall{}p:P.    R[p;a]
9.  term(opr)  \mequiv{}  coterm-fun(opr;term(opr))
10.  f  :  opr
11.  bts  :  (varname()  List  \mtimes{}  term(opr))  List
12.  inr  <f,  bts>    \mmember{}  term(opr)
13.  (1  +  \mSigma{}(term-size(snd(bt))  |  bt  \mmember{}  bts))  \mleq{}  n
14.  p  :  P
15.  1  \mleq{}  (1  +  \mSigma{}(term-size(snd(bt))  |  bt  \mmember{}  bts))
16.  \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)]
17.  g  :  \mforall{}bt:\{bt:varname()  List  \mtimes{}  term(opr)|  (bt  \mmember{}  bts)\}  .  \mforall{}p:P.    R[p;snd(bt)]
\mvdash{}  R[p;mkterm(f;bts)]


By

---

Latex:
(D  -2  With  \mkleeneopen{}accumulate  (with  value  L  and  list  item  bt):
                          let  p'  =  Q[p;f;fst(bt);L]  in
                                  L  @  [<snd(bt),  p',  g  bt  p'>]
                        over  list:
                            bts
                        with  starting  value:
                          [])\mkleeneclose{} 
THENM  Trivial
)

---

Home Index