---

Step * 1 1 1 1 1 3 of Lemma lg-acyclic-well-founded


1. [T] : Type
2. n : ℤ@i
3. [%1] : 0 < n@i
4. ∀g:LabeledGraph(T). (lg-size(g) < n - 1 ⇒ lg-acyclic(g) ⇒ SWellFounded(lg-edge(g;a;b)))@i
5. g : LabeledGraph(T)@i
6. lg-size(g) < n@i
7. lg-acyclic(g)@i
8. 0 < lg-size(g)
9. i : ℕlg-size(g)
10. ∀[j:ℕlg-size(g)]. (¬lg-edge(g;j;i))
11. SWellFounded(lg-edge(lg-remove(g;i);a;b))
⊢ SWellFounded(lg-edge(g;a;b))
BY
{ (D (-1) THEN With ⌜λx.if x <z i then (f x) + 1 if (x =z i) then 0 else (f (x - 1)) + 1 fi ⌝ (D 0)⋅) }

1
.....wf..... 
1. T : Type
2. n : ℤ@i
3. 0 < n@i
4. ∀g:LabeledGraph(T). (lg-size(g) < n - 1 ⇒ lg-acyclic(g) ⇒ SWellFounded(lg-edge(g;a;b)))@i
5. g : LabeledGraph(T)@i
6. lg-size(g) < n@i
7. lg-acyclic(g)@i
8. 0 < lg-size(g)
9. i : ℕlg-size(g)
10. ∀[j:ℕlg-size(g)]. (¬lg-edge(g;j;i))
11. f : ℕlg-size(lg-remove(g;i)) ⟶ ℕ
12. ∀a,b:ℕlg-size(lg-remove(g;i)).  (lg-edge(lg-remove(g;i);a;b) ⇒ f a < f b)
⊢ λx.if x <z i then (f x) + 1
     if (x =z i) then 0
     else (f (x - 1)) + 1
     fi  ∈ ℕlg-size(g) ⟶ ℕ

2
1. [T] : Type
2. n : ℤ@i
3. [%1] : 0 < n@i
4. ∀g:LabeledGraph(T). (lg-size(g) < n - 1 ⇒ lg-acyclic(g) ⇒ SWellFounded(lg-edge(g;a;b)))@i
5. g : LabeledGraph(T)@i
6. lg-size(g) < n@i
7. lg-acyclic(g)@i
8. 0 < lg-size(g)
9. i : ℕlg-size(g)
10. ∀[j:ℕlg-size(g)]. (¬lg-edge(g;j;i))
11. f : ℕlg-size(lg-remove(g;i)) ⟶ ℕ
12. ∀a,b:ℕlg-size(lg-remove(g;i)).  (lg-edge(lg-remove(g;i);a;b) ⇒ f a < f b)
⊢ ∀a,b:ℕlg-size(g).
    (lg-edge(g;a;b)
    ⇒ (λx.if x <z i then (f x) + 1 if (x =z i) then 0 else (f (x - 1)) + 1 fi ) a < (λx.if x <z i then (f x) + 1
                                                                                         if (x =z i) then 0
                                                                                         else (f (x - 1)) + 1
                                                                                         fi ) 
                                                                                     b)

3
.....wf..... 
1. T : Type
2. n : ℤ@i
3. 0 < n@i
4. ∀g:LabeledGraph(T). (lg-size(g) < n - 1 ⇒ lg-acyclic(g) ⇒ SWellFounded(lg-edge(g;a;b)))@i
5. g : LabeledGraph(T)@i
6. lg-size(g) < n@i
7. lg-acyclic(g)@i
8. 0 < lg-size(g)
9. i : ℕlg-size(g)
10. ∀[j:ℕlg-size(g)]. (¬lg-edge(g;j;i))
11. f : ℕlg-size(lg-remove(g;i)) ⟶ ℕ
12. ∀a,b:ℕlg-size(lg-remove(g;i)).  (lg-edge(lg-remove(g;i);a;b) ⇒ f a < f b)
13. f1 : ℕlg-size(g) ⟶ ℕ
⊢ ∀a,b:ℕlg-size(g).  (lg-edge(g;a;b) ⇒ f1 a < f1 b) ∈ ℙ

---

Latex:

---

Latex:

1.  [T]  :  Type
2.  n  :  \mBbbZ{}@i
3.  [\%1]  :  0  <  n@i
4.  \mforall{}g:LabeledGraph(T).  (lg-size(g)  <  n  -  1  {}\mRightarrow{}  lg-acyclic(g)  {}\mRightarrow{}  SWellFounded(lg-edge(g;a;b)))@i
5.  g  :  LabeledGraph(T)@i
6.  lg-size(g)  <  n@i
7.  lg-acyclic(g)@i
8.  0  <  lg-size(g)
9.  i  :  \mBbbN{}lg-size(g)
10.  \mforall{}[j:\mBbbN{}lg-size(g)].  (\mneg{}lg-edge(g;j;i))
11.  SWellFounded(lg-edge(lg-remove(g;i);a;b))
\mvdash{}  SWellFounded(lg-edge(g;a;b))


By

---

Latex:
(D  (-1)  THEN  With  \mkleeneopen{}\mlambda{}x.if  x  <z  i  then  (f  x)  +  1  if  (x  =\msubz{}  i)  then  0  else  (f  (x  -  1))  +  1  fi  \mkleeneclose{}  (D  0)\mcdot{})

---

Home Index