---

Step * 1 of Lemma ml-insert-int-sq


1. u : ℤ
2. v : ℤ List
3. ∀[x:ℤ]
     (let y ⟵ v
      in let y ⟵ x
         in fix((λinsert_int,x,l. if null(l)
                                 then [x]
                                 else let a,as = l 
                                      in if x <z a + 1
                                         then [x / l]
                                         else [a / let y ⟵ as in let y ⟵ x in insert_int y y]
                                         fi 
                                 fi )) 
            y 
         y ~ insert-int(x;v))
4. [x] : ℤ
5. let y ⟵ v
   in fix((λinsert_int,x,l. if null(l)
                           then [x]
                           else let a,as = l 
                                in if x <z a + 1 then [x / l] else [a / let y ⟵ as in let y ⟵ x in insert_int y y] fi 
                           fi )) 
      x 
      y ~ insert-int(x;v)
⊢ if x <z u + 1 then [x; [u / v]] else [u / insert-int(x;v)] fi  ~ insert-int(x;[u / v])
BY
{ (RW (AddrC [2] UnfoldTopAbC) 0 THEN Reduce 0 THEN Fold `insert-int` 0 THEN (CallByValueReduce 0 THENA Auto)) }

1
1. u : ℤ
2. v : ℤ List
3. ∀[x:ℤ]
     (let y ⟵ v
      in let y ⟵ x
         in fix((λinsert_int,x,l. if null(l)
                                 then [x]
                                 else let a,as = l 
                                      in if x <z a + 1
                                         then [x / l]
                                         else [a / let y ⟵ as in let y ⟵ x in insert_int y y]
                                         fi 
                                 fi )) 
            y 
         y ~ insert-int(x;v))
4. [x] : ℤ
5. let y ⟵ v
   in fix((λinsert_int,x,l. if null(l)
                           then [x]
                           else let a,as = l 
                                in if x <z a + 1 then [x / l] else [a / let y ⟵ as in let y ⟵ x in insert_int y y] fi 
                           fi )) 
      x 
      y ~ insert-int(x;v)
⊢ if x <z u + 1 then [x; [u / v]] else [u / insert-int(x;v)] fi  ~ if (u) < (x)
                                                                      then [u / insert-int(x;v)]
                                                                      else [x; [u / v]]

---

Latex:

---

Latex:

1.  u  :  \mBbbZ{}
2.  v  :  \mBbbZ{}  List
3.  \mforall{}[x:\mBbbZ{}]
          (let  y  \mleftarrow{}{}  v
            in  let  y  \mleftarrow{}{}  x
                  in  fix((\mlambda{}insert$_{int}$,x,l.  if  null(l)
                                                                then  [x]
                                                                else  let  a,as  =  l 
                                                                          in  if  x  <z  a  +  1
                                                                                then  [x  /  l]
                                                                                else  [a  /  let  y  \mleftarrow{}{}  as  in  let  y  \mleftarrow{}{}  x  in  insert$_{\000Cint}$  y  y]
                                                                                fi 
                                                                fi  )) 
                        y 
                  y  \msim{}  insert-int(x;v))
4.  [x]  :  \mBbbZ{}
5.  let  y  \mleftarrow{}{}  v
      in  fix((\mlambda{}insert$_{int}$,x,l.  if  null(l)
                                                    then  [x]
                                                    else  let  a,as  =  l 
                                                              in  if  x  <z  a  +  1
                                                                    then  [x  /  l]
                                                                    else  [a  /  let  y  \mleftarrow{}{}  as  in  let  y  \mleftarrow{}{}  x  in  insert$_{int\mbackslash{}ff\000C7d$  y  y]
                                                                    fi 
                                                    fi  )) 
            x 
            y  \msim{}  insert-int(x;v)
\mvdash{}  if  x  <z  u  +  1  then  [x;  [u  /  v]]  else  [u  /  insert-int(x;v)]  fi    \msim{}  insert-int(x;[u  /  v])


By

---

Latex:
(RW  (AddrC  [2]  UnfoldTopAbC)  0
  THEN  Reduce  0
  THEN  Fold  `insert-int`  0
  THEN  (CallByValueReduce  0  THENA  Auto))

---

Home Index