---

Step * 1 2 of Lemma list_ind_reverse_wf_dependent


1. [A] : Type
2. [B] : Type
3. nilcase : B
4. F : B ⟶ (A List) ⟶ A ⟶ B
5. P : (A List) ⟶ B ⟶ ℙ
6. P [] nilcase
7. ∀L:A List. ∀x:A. ∀b:B.  ((b = list_ind_reverse(L;nilcase;F) ∈ B) ⇒ (P L b) ⇒ (P (L @ [x]) (F b L x)))
8. L : A List
9. n : ℤ
10. [%3] : 0 < n
11. ∀LL:A List. ((||LL|| = (n - 1) ∈ ℕ) ⇒ (P LL list_ind_reverse(LL;nilcase;F)))
12. LL : A List
13. ||LL|| ≠ 0
14. ||LL|| = n ∈ ℕ
⊢ P LL 
  (F 
   (fix((λF@0,l. if (||l|| =z 0) then nilcase else F (F@0 firstn(||l|| - 1;l)) firstn(||l|| - 1;l) last(l) fi )) 
    firstn(||LL|| - 1;LL)) 
   firstn(||LL|| - 1;LL) 
   last(LL))
BY
{ (InstHyp [⌜firstn(||LL|| - 1;LL)⌝] 11⋅ THENA (Auto THEN RWO "length_firstn" 0 THEN Auto))⋅ }

1
1. [A] : Type
2. [B] : Type
3. nilcase : B
4. F : B ⟶ (A List) ⟶ A ⟶ B
5. P : (A List) ⟶ B ⟶ ℙ
6. P [] nilcase
7. ∀L:A List. ∀x:A. ∀b:B.  ((b = list_ind_reverse(L;nilcase;F) ∈ B) ⇒ (P L b) ⇒ (P (L @ [x]) (F b L x)))
8. L : A List
9. n : ℤ
10. [%3] : 0 < n
11. ∀LL:A List. ((||LL|| = (n - 1) ∈ ℕ) ⇒ (P LL list_ind_reverse(LL;nilcase;F)))
12. LL : A List
13. ||LL|| ≠ 0
14. ||LL|| = n ∈ ℕ
15. P firstn(||LL|| - 1;LL) list_ind_reverse(firstn(||LL|| - 1;LL);nilcase;F)
⊢ P LL 
  (F 
   (fix((λF@0,l. if (||l|| =z 0) then nilcase else F (F@0 firstn(||l|| - 1;l)) firstn(||l|| - 1;l) last(l) fi )) 
    firstn(||LL|| - 1;LL)) 
   firstn(||LL|| - 1;LL) 
   last(LL))

---

Latex:

---

Latex:

1.  [A]  :  Type
2.  [B]  :  Type
3.  nilcase  :  B
4.  F  :  B  {}\mrightarrow{}  (A  List)  {}\mrightarrow{}  A  {}\mrightarrow{}  B
5.  P  :  (A  List)  {}\mrightarrow{}  B  {}\mrightarrow{}  \mBbbP{}
6.  P  []  nilcase
7.  \mforall{}L:A  List.  \mforall{}x:A.  \mforall{}b:B.
          ((b  =  list\_ind\_reverse(L;nilcase;F))  {}\mRightarrow{}  (P  L  b)  {}\mRightarrow{}  (P  (L  @  [x])  (F  b  L  x)))
8.  L  :  A  List
9.  n  :  \mBbbZ{}
10.  [\%3]  :  0  <  n
11.  \mforall{}LL:A  List.  ((||LL||  =  (n  -  1))  {}\mRightarrow{}  (P  LL  list\_ind\_reverse(LL;nilcase;F)))
12.  LL  :  A  List
13.  ||LL||  \mneq{}  0
14.  ||LL||  =  n
\mvdash{}  P  LL 
    (F 
      (fix((\mlambda{}F@0,l.  if  (||l||  =\msubz{}  0)
                                then  nilcase
                                else  F  (F@0  firstn(||l||  -  1;l))  firstn(||l||  -  1;l)  last(l)
                                fi  )) 
        firstn(||LL||  -  1;LL)) 
      firstn(||LL||  -  1;LL) 
      last(LL))


By

---

Latex:
(InstHyp  [\mkleeneopen{}firstn(||LL||  -  1;LL)\mkleeneclose{}]  11\mcdot{}  THENA  (Auto  THEN  RWO  "length\_firstn"  0  THEN  Auto))\mcdot{}

---

Home Index