---

Step * 1 of Lemma dependent-choice


1. [T] : ℕ ⟶ Type
2. [R] : n:ℕ ⟶ T[n] ⟶ T[n + 1] ⟶ ℙ
3. ∀n:ℕ. ∀x:T[n].  ∃y:T[n + 1]. R[n;x;y]
4. x0 : T[0]
5. F : n:ℕ ⟶ x:T[n] ⟶ T[n + 1]
6. ∀n:ℕ. ∀x:T[n].  R[n;x;F n x]
⊢ ∃f:n:ℕ ⟶ T[n]. (((f 0) = x0 ∈ T[0]) ∧ (∀n:ℕ. R[n;f n;f (n + 1)]))
BY
{ (Assert ∀n:ℕ. (primrec(n;x0;λi,r. (F i r)) ∈ T[n]) BY
         (InductionOnNat
          THEN Reduce 0
          THEN Try (Trivial)
          THEN (RWO "primrec-unroll" 0 THENA Auto)
          THEN Reduce 0
          THEN Auto)) }

1
1. [T] : ℕ ⟶ Type
2. [R] : n:ℕ ⟶ T[n] ⟶ T[n + 1] ⟶ ℙ
3. ∀n:ℕ. ∀x:T[n].  ∃y:T[n + 1]. R[n;x;y]
4. x0 : T[0]
5. F : n:ℕ ⟶ x:T[n] ⟶ T[n + 1]
6. ∀n:ℕ. ∀x:T[n].  R[n;x;F n x]
7. ∀n:ℕ. (primrec(n;x0;λi,r. (F i r)) ∈ T[n])
⊢ ∃f:n:ℕ ⟶ T[n]. (((f 0) = x0 ∈ T[0]) ∧ (∀n:ℕ. R[n;f n;f (n + 1)]))

---

Latex:

---

Latex:

1.  [T]  :  \mBbbN{}  {}\mrightarrow{}  Type
2.  [R]  :  n:\mBbbN{}  {}\mrightarrow{}  T[n]  {}\mrightarrow{}  T[n  +  1]  {}\mrightarrow{}  \mBbbP{}
3.  \mforall{}n:\mBbbN{}.  \mforall{}x:T[n].    \mexists{}y:T[n  +  1].  R[n;x;y]
4.  x0  :  T[0]
5.  F  :  n:\mBbbN{}  {}\mrightarrow{}  x:T[n]  {}\mrightarrow{}  T[n  +  1]
6.  \mforall{}n:\mBbbN{}.  \mforall{}x:T[n].    R[n;x;F  n  x]
\mvdash{}  \mexists{}f:n:\mBbbN{}  {}\mrightarrow{}  T[n].  (((f  0)  =  x0)  \mwedge{}  (\mforall{}n:\mBbbN{}.  R[n;f  n;f  (n  +  1)]))


By

---

Latex:
(Assert  \mforall{}n:\mBbbN{}.  (primrec(n;x0;\mlambda{}i,r.  (F  i  r))  \mmember{}  T[n])  BY
              (InductionOnNat
                THEN  Reduce  0
                THEN  Try  (Trivial)
                THEN  (RWO  "primrec-unroll"  0  THENA  Auto)
                THEN  Reduce  0
                THEN  Auto))

---

Home Index