---

Step * 1 2 1 1 1 of Lemma lexico_well_fnd


1. [T] : Type
2. [R] : T ⟶ T ⟶ ℙ
3. WellFnd{i}(T;a,b.R[a;b])
4. m : ℤ
5. [%2] : 0 < m
6. lexico(T; a,b.R[a;b]) ∈ (T List) ⟶ (T List) ⟶ ℙ
7. WellFnd{i}({L:T List| ||L|| = (m - 1) ∈ ℕ} ;as,bs.as lexico(T; a,b.R[a;b]) bs)
8. WellFnd{i}(T × {L:T List| ||L|| = (m - 1) ∈ ℕ} ;p1,p2.let a1,b1 = p1 
                                                        in let a2,b2 = p2 
                                                           in R[a1;a2]
                                                              ∨ ((a1 = a2 ∈ T) ∧ (b1 lexico(T; a,b.R[a;b]) b2)))
9. WellFnd{i}({L:T List| ||L|| = m ∈ ℕ} ;x,y.let a1,b1 = <hd(x), tl(x)> 
                              in let a2,b2 = <hd(y), tl(y)> 
                                 in R[a1;a2] ∨ ((a1 = a2 ∈ T) ∧ (b1 lexico(T; a,b.R[a;b]) b2)))
⊢ WellFnd{i}({L:T List| ||L|| = m ∈ ℕ} ;as,bs.as lexico(T; a,b.R[a;b]) bs)
BY
{ xxx(Reduce (-1) THEN RepeatFor 4 (ParallelLast) THEN Auto)xxx }

1
1. [T] : Type
2. [R] : T ⟶ T ⟶ ℙ
3. WellFnd{i}(T;a,b.R[a;b])
4. m : ℤ
5. [%2] : 0 < m
6. lexico(T; a,b.R[a;b]) ∈ (T List) ⟶ (T List) ⟶ ℙ
7. WellFnd{i}({L:T List| ||L|| = (m - 1) ∈ ℕ} ;as,bs.as lexico(T; a,b.R[a;b]) bs)
8. WellFnd{i}(T × {L:T List| ||L|| = (m - 1) ∈ ℕ} ;p1,p2.let a1,b1 = p1 
                                                        in let a2,b2 = p2 
                                                           in R[a1;a2]
                                                              ∨ ((a1 = a2 ∈ T) ∧ (b1 lexico(T; a,b.R[a;b]) b2)))
9. ∀[P:{L:T List| ||L|| = m ∈ ℕ}  ⟶ ℙ]
     ((∀j:{L:T List| ||L|| = m ∈ ℕ} 
         ((∀k:{L:T List| ||L|| = m ∈ ℕ} 
             ((R[hd(k);hd(j)] ∨ ((hd(k) = hd(j) ∈ T) ∧ (tl(k) lexico(T; a,b.R[a;b]) tl(j)))) ⇒ P[k]))
         ⇒ P[j]))
     ⇒ {∀n:{L:T List| ||L|| = m ∈ ℕ} . P[n]})
10. [P] : {L:T List| ||L|| = m ∈ ℕ}  ⟶ ℙ
11. ∀j:{L:T List| ||L|| = m ∈ ℕ} . ((∀k:{L:T List| ||L|| = m ∈ ℕ} . ((k lexico(T; a,b.R[a;b]) j) ⇒ P[k])) ⇒ P[j])
12. j : {L:T List| ||L|| = m ∈ ℕ} 
13. (∀k:{L:T List| ||L|| = m ∈ ℕ} . ((k lexico(T; a,b.R[a;b]) j) ⇒ P[k])) ⇒ P[j]
14. ∀k:{L:T List| ||L|| = m ∈ ℕ} 
      ((R[hd(k);hd(j)] ∨ ((hd(k) = hd(j) ∈ T) ∧ (tl(k) lexico(T; a,b.R[a;b]) tl(j)))) ⇒ P[k])
⊢ P[j]

---

Latex:

---

Latex:

1.  [T]  :  Type
2.  [R]  :  T  {}\mrightarrow{}  T  {}\mrightarrow{}  \mBbbP{}
3.  WellFnd\{i\}(T;a,b.R[a;b])
4.  m  :  \mBbbZ{}
5.  [\%2]  :  0  <  m
6.  lexico(T;  a,b.R[a;b])  \mmember{}  (T  List)  {}\mrightarrow{}  (T  List)  {}\mrightarrow{}  \mBbbP{}
7.  WellFnd\{i\}(\{L:T  List|  ||L||  =  (m  -  1)\}  ;as,bs.as  lexico(T;  a,b.R[a;b])  bs)
8.  WellFnd\{i\}(T  \mtimes{}  \{L:T  List|  ||L||  =  (m  -  1)\}  ;p1,p2.let  a1,b1  =  p1 
                                                                                                        in  let  a2,b2  =  p2 
                                                                                                              in  R[a1;a2]
                                                                                                                    \mvee{}  ((a1  =  a2)
                                                                                                                        \mwedge{}  (b1  lexico(T;  a,b.R[a;b])  b2)))
9.  WellFnd\{i\}(\{L:T  List|  ||L||  =  m\}  ;x,y.let  a1,b1  =  <hd(x),  tl(x)> 
                                                    in  let  a2,b2  =  <hd(y),  tl(y)> 
                                                          in  R[a1;a2]  \mvee{}  ((a1  =  a2)  \mwedge{}  (b1  lexico(T;  a,b.R[a;b])  b2)))
\mvdash{}  WellFnd\{i\}(\{L:T  List|  ||L||  =  m\}  ;as,bs.as  lexico(T;  a,b.R[a;b])  bs)


By

---

Latex:
xxx(Reduce  (-1)  THEN  RepeatFor  4  (ParallelLast)  THEN  Auto)xxx

---

Home Index