---

Step * 2 2 1 1 1 1 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
13. v < b - a
14. ↑(f (a + v))
15. ((a + v) + 1) ≤ (b + 1)
⊢ ↓∃x:{a..a + v-}. ((∀y:{a..x + 1-}. (¬↑(f y))) ∧ (∀z:{x + 1..(a + v) + 1-}. (↑(f z))))
BY
{ TACTIC:(D 0 THEN ParallelOp 8) }

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 : ℤ
9. a ≤ x
10. x < b
11. ∀y:{a..x + 1-}. (¬↑(f y))
12. ∀z:{x + 1..b + 1-}. (↑(f z))
13. ¬(b = (a + 1) ∈ ℤ)
14. v : ℤ
15. ((b - a) ÷ 2) = v ∈ ℤ
16. 0 < v
17. v < b - a
18. ↑(f (a + v))
19. ((a + v) + 1) ≤ (b + 1)
⊢ x < a + v

2
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-}
9. (∀y:{a..x + 1-}. (¬↑(f y))) ∧ (∀z:{x + 1..b + 1-}. (↑(f z)))
10. ¬(b = (a + 1) ∈ ℤ)
11. v : ℤ
12. ((b - a) ÷ 2) = v ∈ ℤ
13. 0 < v
14. v < b - a
15. ↑(f (a + v))
16. ((a + v) + 1) ≤ (b + 1)
⊢ (∀y:{a..x + 1-}. (¬↑(f y))) ∧ (∀z:{x + 1..(a + v) + 1-}. (↑(f z)))

---

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.  \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
13.  v  <  b  -  a
14.  \muparrow{}(f  (a  +  v))
15.  ((a  +  v)  +  1)  \mleq{}  (b  +  1)
\mvdash{}  \mdownarrow{}\mexists{}x:\{a..a  +  v\msupminus{}\}.  ((\mforall{}y:\{a..x  +  1\msupminus{}\}.  (\mneg{}\muparrow{}(f  y)))  \mwedge{}  (\mforall{}z:\{x  +  1..(a  +  v)  +  1\msupminus{}\}.  (\muparrow{}(f  z))))


By

---

Latex:
TACTIC:(D  0  THEN  ParallelOp  8)

---

Home Index