---

Step * 1 of Lemma lg-label-remove


1. T : Type
2. g : LabeledGraph(T)
3. lg-size(g) ∈ ℕ
4. g ∈ Top List
5. g ∈ (T × ℕlg-size(g) List × (ℕlg-size(g) List)) List
6. k : ℕlg-size(g)
7. x : ℕlg-size(g) - 1
⊢ fst(map(λtr.let lbl,in,out = tr in 
              <lbl
              , map(λx.if x ≤z k then x else x - 1 fi ;filter(λx.(¬b(x =z k));in))
              , map(λx.if x ≤z k then x else x - 1 fi ;filter(λx.(¬b(x =z k));out))>;firstn(k;g) @ nth_tl(k + 1;g))[x]) 
~ if x <z k then fst(g[x]) else fst(g[x + 1]) fi 
BY
{ (RWW "select-map select-append" 0 THENA Auto) }

1
1. T : Type
2. g : LabeledGraph(T)
3. lg-size(g) ∈ ℕ
4. g ∈ Top List
5. g ∈ (T × ℕlg-size(g) List × (ℕlg-size(g) List)) List
6. k : ℕlg-size(g)
7. x : ℤ
8. 0 ≤ x
9. x < lg-size(g) - 1
⊢ x < ||firstn(k;g)|| + ||nth_tl(k + 1;g)||

2
1. T : Type
2. g : LabeledGraph(T)
3. lg-size(g) ∈ ℕ
4. g ∈ Top List
5. g ∈ (T × ℕlg-size(g) List × (ℕlg-size(g) List)) List
6. k : ℕlg-size(g)
7. x : ℕlg-size(g) - 1
⊢ fst(((λtr.let lbl,in,out = tr in 
            <lbl
            , map(λx.if x ≤z k then x else x - 1 fi ;filter(λx.(¬b(x =z k));in))
            , map(λx.if x ≤z k then x else x - 1 fi ;filter(λx.(¬b(x =z k));out))>) 
       if x <z ||firstn(k;g)|| then firstn(k;g)[x] else nth_tl(k + 1;g)[x - ||firstn(k;g)||] fi )) ~ if x <z k
then fst(g[x])
else fst(g[x + 1])
fi 

---

Latex:

---

Latex:

1.  T  :  Type
2.  g  :  LabeledGraph(T)
3.  lg-size(g)  \mmember{}  \mBbbN{}
4.  g  \mmember{}  Top  List
5.  g  \mmember{}  (T  \mtimes{}  \mBbbN{}lg-size(g)  List  \mtimes{}  (\mBbbN{}lg-size(g)  List))  List
6.  k  :  \mBbbN{}lg-size(g)
7.  x  :  \mBbbN{}lg-size(g)  -  1
\mvdash{}  fst(map(\mlambda{}tr.let  lbl,in,out  =  tr  in 
                            <lbl
                            ,  map(\mlambda{}x.if  x  \mleq{}z  k  then  x  else  x  -  1  fi  ;filter(\mlambda{}x.(\mneg{}\msubb{}(x  =\msubz{}  k));in))
                            ,  map(\mlambda{}x.if  x  \mleq{}z  k  then  x  else  x  -  1  fi  ;filter(\mlambda{}x.(\mneg{}\msubb{}(x  =\msubz{}  k));out))>firstn(k;g)
                    @  nth\_tl(k  +  1;g))[x])  \msim{}  if  x  <z  k  then  fst(g[x])  else  fst(g[x  +  1])  fi 


By

---

Latex:
(RWW  "select-map  select-append"  0  THENA  Auto)

---

Home Index