---

Step * 1 of Lemma bar_recursion_wf


1. T : Type
2. R : n:ℕ ⟶ (ℕn ⟶ T) ⟶ ℙ
3. A : n:ℕ ⟶ (ℕn ⟶ T) ⟶ ℙ
4. d : ∀n:ℕ. ∀s:ℕn ⟶ T.  Dec(R[n;s])
5. b : ∀n:ℕ. ∀s:ℕn ⟶ T.  (R[n;s] ⇒ A[n;s])
6. i : ∀n:ℕ. ∀s:ℕn ⟶ T.  ((∀t:T. A[n + 1;seq-append(n;1;s;λi.t)]) ⇒ A[n;s])
7. n : ℕ
8. s : ℕn ⟶ T
9. ∀alpha:ℕ ⟶ T. (↓∃m:ℕ. R[n + m;seq-append(n;m;s;alpha)])
⊢ (λk,u. bar_recursion(d;b;i;n + k;seq-normalize(n + k;seq-append(n;k;s;u)))) 0 ⊥
  ∈ (λk,u. A[n + k;seq-normalize(n + k;seq-append(n;k;s;u))]) 0 ⊥
BY
{ TACTIC:(All (Unfold `so_apply`)⋅
          THEN Bar_Induction ⌜T⌝ ⌜λk,u. (R (n + k) seq-normalize(n + k;seq-append(n;k;s;u)))⌝⋅⋅
          THEN Reduce 0
          THEN Try (BackThruSomeHyp')
          THEN All Reduce
          THEN Auto
          THEN Try (((InstHyp [⌜alpha⌝] (-2)⋅ THENA Auto)
                     THEN RepeatFor 2 (ParallelLast)
                     THEN RWO "seq-normalize-append" 0
                     THEN Auto))
          THEN RecUnfold `bar_recursion` 0
          THEN Auto
          THEN All (\h. (RWO "seq-normalize-append" h THEN Auto))⋅)⋅ }

1
1. T : Type
2. R : n:ℕ ⟶ (ℕn ⟶ T) ⟶ ℙ
3. A : n:ℕ ⟶ (ℕn ⟶ T) ⟶ ℙ
4. d : ∀n:ℕ. ∀s:ℕn ⟶ T.  Dec(R n s)
5. b : ∀n:ℕ. ∀s:ℕn ⟶ T.  ((R n s) ⇒ (A n s))
6. i : ∀n:ℕ. ∀s:ℕn ⟶ T.  ((∀t:T. (A (n + 1) seq-append(n;1;s;λi.t))) ⇒ (A n s))
7. n : ℕ
8. s : ℕn ⟶ T
9. ∀alpha:ℕ ⟶ T. (↓∃m:ℕ. (R (n + m) seq-append(n;m;s;alpha)))
10. n1 : ℕ
11. s1 : ℕn1 ⟶ T
12. ∀t:T
      (bar_recursion(d;
                     b;
                     i;
                     n + n1 + 1;seq-append(n;n1 + 1;s;λm.if m=n1 then t else (s1 m))) ∈ A (n + n1 + 1) 
                                                                          seq-append(n;n1 + 1;s;λm.if m=n1
                                                                                                   then t
                                                                                                   else (s1 m)))
⊢ case d (n + n1) seq-append(n;n1;s;s1)
   of inl(r) =>
   b (n + n1) seq-append(n;n1;s;s1) r
   | inr(r) =>
   i (n + n1) seq-append(n;n1;s;s1) 
   (λt.bar_recursion(d;
                     b;
                     i;
                     (n + n1) + 1;λm.if m=n + n1 then t else (seq-append(n;n1;s;s1) m))) ∈ A (n + n1) seq-append(n;n1;s;\000Cs1)

---

Latex:

---

Latex:

1.  T  :  Type
2.  R  :  n:\mBbbN{}  {}\mrightarrow{}  (\mBbbN{}n  {}\mrightarrow{}  T)  {}\mrightarrow{}  \mBbbP{}
3.  A  :  n:\mBbbN{}  {}\mrightarrow{}  (\mBbbN{}n  {}\mrightarrow{}  T)  {}\mrightarrow{}  \mBbbP{}
4.  d  :  \mforall{}n:\mBbbN{}.  \mforall{}s:\mBbbN{}n  {}\mrightarrow{}  T.    Dec(R[n;s])
5.  b  :  \mforall{}n:\mBbbN{}.  \mforall{}s:\mBbbN{}n  {}\mrightarrow{}  T.    (R[n;s]  {}\mRightarrow{}  A[n;s])
6.  i  :  \mforall{}n:\mBbbN{}.  \mforall{}s:\mBbbN{}n  {}\mrightarrow{}  T.    ((\mforall{}t:T.  A[n  +  1;seq-append(n;1;s;\mlambda{}i.t)])  {}\mRightarrow{}  A[n;s])
7.  n  :  \mBbbN{}
8.  s  :  \mBbbN{}n  {}\mrightarrow{}  T
9.  \mforall{}alpha:\mBbbN{}  {}\mrightarrow{}  T.  (\mdownarrow{}\mexists{}m:\mBbbN{}.  R[n  +  m;seq-append(n;m;s;alpha)])
\mvdash{}  (\mlambda{}k,u.  bar\_recursion(d;b;i;n  +  k;seq-normalize(n  +  k;seq-append(n;k;s;u))))  0  \mbot{}
    \mmember{}  (\mlambda{}k,u.  A[n  +  k;seq-normalize(n  +  k;seq-append(n;k;s;u))])  0  \mbot{}


By

---

Latex:
TACTIC:(All  (Unfold  `so\_apply`)\mcdot{}
                THEN  Bar\_Induction  \mkleeneopen{}T\mkleeneclose{}  \mkleeneopen{}\mlambda{}k,u.  (R  (n  +  k)  seq-normalize(n  +  k;seq-append(n;k;s;u)))\mkleeneclose{}\mcdot{}\mcdot{}
                THEN  Reduce  0
                THEN  Try  (BackThruSomeHyp')
                THEN  All  Reduce
                THEN  Auto
                THEN  Try  (((InstHyp  [\mkleeneopen{}alpha\mkleeneclose{}]  (-2)\mcdot{}  THENA  Auto)
                                      THEN  RepeatFor  2  (ParallelLast)
                                      THEN  RWO  "seq-normalize-append"  0
                                      THEN  Auto))
                THEN  RecUnfold  `bar\_recursion`  0
                THEN  Auto
                THEN  All  (\mbackslash{}h.  (RWO  "seq-normalize-append"  h  THEN  Auto))\mcdot{})\mcdot{}

---

Home Index