AFTD Auto-Formalizing Theoretical Domains

Halving.voteFor

defimported Lean

Given an evaluation map $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$, a version space $V \subseteq \mathit{Hyp}$, an input $x \in X$, and a label $y \in \mathsf{Bool}$, $\mathtt{voteFor}(\mathtt{eval}, V, x, y)$ is the subset of $V$ consisting of all hypotheses that predict label $y$ on input $x$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {Hyp X : Type*} in
def Halving.voteFor (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) (y : Bool) :
    Finset Hyp
Defined in
TCSlib, `Halving.voteFor`
Lean proof
By Arhaan Aggarwal, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Arhaan Aggarwal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
none listed
Used by 5
  • Halving.mistake_halvesMistake bound for the Halving algorithm. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let…
  • Halving.target_mem_updateTarget survives its own update. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let…
  • Halving.voteFor_false_add_trueVote counts partition the version space. Let $\mathrm{eval}$ be a Boolean evaluation map assigning to each hypothesis and each input a…
  • Halving.updateAfter observing that the correct label for input $x$ is $y$, the version space is updated to…
  • Halving.predictThe Halving Algorithm predicts on input $x$ by taking a majority vote of the current version space $V$: it returns $\mathsf{true}$…

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {Hyp X : Type*} in
/-- The set of hypotheses in the version space `V` whose evaluation on the input `x` equals the label `y`, i.e. the hypotheses that vote for `y` on `x`. [MRT18, §8.2.1 (Halving algorithm)]; origin [Lit88, §3]. -/
def Halving.voteFor (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) (y : Bool) :
    Finset Hyp :=
  V.filter (fun h => eval h x = y)
See it in the graphDiscuss this resultChallenge it