---

Step * 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) ∈ ℤ
⊢ a ∈ {x:{a..b-}| (¬↑(f x)) ∧ (↑(f (x + 1)))} 
BY
{ (SqExRepD THEN MemTypeCD THEN Auto) }

---

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.  b  =  (a  +  1)
\mvdash{}  a  \mmember{}  \{x:\{a..b\msupminus{}\}|  (\mneg{}\muparrow{}(f  x))  \mwedge{}  (\muparrow{}(f  (x  +  1)))\} 


By

---

Latex:
(SqExRepD  THEN  MemTypeCD  THEN  Auto)

---

Home Index