Finite-pool version-space invariant and query bound

Initially $V=\mathcal{H}$, so [F1] gives $h^{\ast }\in V$. If a query is made at $u_i$, [F1] gives its answer $y=h^{\ast }(u_i)$, and [F2] replaces $V$ by $\{h\in V:h(u_i)=y\}$, which still contains $h^{\ast }$. If no query is made, $V$ is unchanged. Induction over the scan therefore keeps $h^{\ast }$ in every current $V$, so $V$ is never empty. The finite filters make no arbitrary selections, as recorded in [A1].

At each loop pass the algorithm either advances from index $i$ to $i+1$ or returns. Since $U$ has $m$ indices, after at most $m$ such advances it returns, including when $m=0$. It queries at most once per visited index, hence $q\le m$.

Initially $q=0\le b$. The only update that increases $q$ is made in the branch $q<b$, so it preserves $q\le b$; when $q=b$, the algorithm does not query and either records a unanimous label or returns at a disagreement. Induction over the scan gives $q\le b$, in particular no queries when $b=0$.

When [F2] records a unanimous label at $u_i$, every $h\in V$ has that value there. Since $h^{\ast }\in V$ by step 1.1, the recorded value equals $h^{\ast }(u_i)$.

At every query, [F2] says the current classifiers disagree at the queried point. One of them is $h^{\ast }$ by step 1.1, so at least one current classifier has label different from the exact answer and is removed. Version spaces only shrink; consequently each query removes at least one distinct member of $\mathcal{H}\setminus \{h^{\ast }\}$. After $q$ queries at least $q$ such members have been removed, while $h^{\ast }$ remains, giving $q\le \mathrm{\mid }\mathcal{H}\mathrm{\mid }-1$.

Combining the pool-index bound in step 1.2 with step 2.2 gives $q\le \min \{m,\mathrm{\mid }\mathcal{H}\mathrm{\mid }-1\}$.

Under the additional branch-size hypothesis, after $r$ queries induction gives $\mathrm{\mid }{V}_r\mathrm{\mid }\le {\rho }^r\mathrm{\mid }\mathcal{H}\mathrm{\mid }$. Step 1.1 gives $\mathrm{\mid }{V}_q\mathrm{\mid }\ge 1$, so $1\le {\rho }^q\mathrm{\mid }\mathcal{H}\mathrm{\mid }$. Since ${\rho }^q\mathrm{\mid }\mathcal{H}\mathrm{\mid }>0$, [F4] gives $0=\log 1\le \log ({\rho }^q\mathrm{\mid }\mathcal{H}\mathrm{\mid })=q\log \rho +\log \mathrm{\mid }\mathcal{H}\mathrm{\mid }$, where the product law is applied repeatedly to the integer power ${\rho }^q$. Also $1\mathrm{/}\rho >1$, so [F4] gives $\log (1\mathrm{/}\rho )>0$ and, by applying its product law to $\rho (1\mathrm{/}\rho )=1$, $\log \rho =-\log (1\mathrm{/}\rho )$. Rearranging yields $q\le \log \mathrm{\mid }\mathcal{H}\mathrm{\mid }\mathrm{/}\log (1\mathrm{/}\rho )$. For $q=0$ the same conclusion follows from $\mathrm{\mid }\mathcal{H}\mathrm{\mid }\ge 1$.