---

Step * 2 2 1 of Lemma binary-search_wf


1. d : ℤ
2. 0 < d
3. ∀a:ℤ. ∀b:{a + 1...}.
     (((b - a) ≤ (d - 1))
     ⇒ (∀f:{a..b + 1-} ⟶ 𝔹
           binary-search(f;a;b) ∈ {x:{a..b-}| (¬↑(f x)) ∧ (↑(f (x + 1)))}  
           supposing ↓∃x:{a..b-}. ((∀y:{a..x + 1-}. (¬↑(f y))) ∧ (∀z:{x + 1..b + 1-}. (↑(f z))))))
4. a : ℤ
5. b : {a + 1...}
6. (b - a) ≤ d
7. f : {a..b + 1-} ⟶ 𝔹
8. ↓∃x:{a..b-}. ((∀y:{a..x + 1-}. (¬↑(f y))) ∧ (∀z:{x + 1..b + 1-}. (↑(f z))))
9. ¬(b = (a + 1) ∈ ℤ)
10. v : ℤ
11. ((b - a) ÷ 2) = v ∈ ℤ
12. 0 < v ∧ v < b - a
⊢ eval c = a + v in
  if f c then binary-search(f;a;c) else binary-search(f;c;b) fi  ∈ {x:{a..b-}| (¬↑(f x)) ∧ (↑(f (x + 1)))} 
BY
{ TACTIC:(CallByValueReduce 0 THENA Auto) }

1
1. d : ℤ
2. 0 < d
3. ∀a:ℤ. ∀b:{a + 1...}.
     (((b - a) ≤ (d - 1))
     ⇒ (∀f:{a..b + 1-} ⟶ 𝔹
           binary-search(f;a;b) ∈ {x:{a..b-}| (¬↑(f x)) ∧ (↑(f (x + 1)))}  
           supposing ↓∃x:{a..b-}. ((∀y:{a..x + 1-}. (¬↑(f y))) ∧ (∀z:{x + 1..b + 1-}. (↑(f z))))))
4. a : ℤ
5. b : {a + 1...}
6. (b - a) ≤ d
7. f : {a..b + 1-} ⟶ 𝔹
8. ↓∃x:{a..b-}. ((∀y:{a..x + 1-}. (¬↑(f y))) ∧ (∀z:{x + 1..b + 1-}. (↑(f z))))
9. ¬(b = (a + 1) ∈ ℤ)
10. v : ℤ
11. ((b - a) ÷ 2) = v ∈ ℤ
12. 0 < v ∧ v < b - a
⊢ if f (a + v) then binary-search(f;a;a + v) else binary-search(f;a + v;b) fi  ∈ {x:{a..b-}| 
                                                                                  (¬↑(f x)) ∧ (↑(f (x + 1)))} 

---

Latex:

---

Latex:

1.  d  :  \mBbbZ{}
2.  0  <  d
3.  \mforall{}a:\mBbbZ{}.  \mforall{}b:\{a  +  1...\}.
          (((b  -  a)  \mleq{}  (d  -  1))
          {}\mRightarrow{}  (\mforall{}f:\{a..b  +  1\msupminus{}\}  {}\mrightarrow{}  \mBbbB{}
                      binary-search(f;a;b)  \mmember{}  \{x:\{a..b\msupminus{}\}|  (\mneg{}\muparrow{}(f  x))  \mwedge{}  (\muparrow{}(f  (x  +  1)))\}   
                      supposing  \mdownarrow{}\mexists{}x:\{a..b\msupminus{}\}.  ((\mforall{}y:\{a..x  +  1\msupminus{}\}.  (\mneg{}\muparrow{}(f  y)))  \mwedge{}  (\mforall{}z:\{x  +  1..b  +  1\msupminus{}\}.  (\muparrow{}(f  z))))))
4.  a  :  \mBbbZ{}
5.  b  :  \{a  +  1...\}
6.  (b  -  a)  \mleq{}  d
7.  f  :  \{a..b  +  1\msupminus{}\}  {}\mrightarrow{}  \mBbbB{}
8.  \mdownarrow{}\mexists{}x:\{a..b\msupminus{}\}.  ((\mforall{}y:\{a..x  +  1\msupminus{}\}.  (\mneg{}\muparrow{}(f  y)))  \mwedge{}  (\mforall{}z:\{x  +  1..b  +  1\msupminus{}\}.  (\muparrow{}(f  z))))
9.  \mneg{}(b  =  (a  +  1))
10.  v  :  \mBbbZ{}
11.  ((b  -  a)  \mdiv{}  2)  =  v
12.  0  <  v  \mwedge{}  v  <  b  -  a
\mvdash{}  eval  c  =  a  +  v  in
    if  f  c  then  binary-search(f;a;c)  else  binary-search(f;c;b)  fi    \mmember{}  \{x:\{a..b\msupminus{}\}| 
                                                                                                                                        (\mneg{}\muparrow{}(f  x))  \mwedge{}  (\muparrow{}(f  (x  +  1)))\} 


By

---

Latex:
TACTIC:(CallByValueReduce  0  THENA  Auto)

---

Home Index