AFTD Auto-Formalizing Theoretical Domains

Halving.predict

defimported Lean

The Halving Algorithm predicts on input $x$ by taking a majority vote of the current version space $V$: it returns $\mathsf{true}$ whenever the number of hypotheses in $V$ that predict $\mathsf{true}$ is at least as large as the number that predict $\mathsf{false}$ (ties are broken in favour of $\mathsf{true}$).

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {Hyp X : Type*} in
def Halving.predict (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) : Bool
Defined in
TCSlib, `Halving.predict`
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
Built on 1
  • Halving.voteForGiven an evaluation map $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$, a version space $V \subseteq \mathit{Hyp}$, an input…
Used by 3
  • Halving.mistakes_boundMistake bound for the Halving Algorithm. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let $V$ be a…
  • Halving.mistake_halvesMistake bound for the Halving algorithm. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let…
  • Halving.mistakes$\mathtt{mistakes}(\mathtt{eval}, \mathtt{target}, V, xs)$ is the total number of prediction errors made by the Halving Algorithm when it…

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {Hyp X : Type*} in
/-- The Halving prediction on the input `x`: the label that receives the majority of the votes of the version space `V`, with ties broken towards `true`. [MRT18, §8.2.1 (Halving algorithm)]; origin [Lit88, §3]. -/
def Halving.predict (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) : Bool :=
  if (voteFor eval V x true).card ≥ (voteFor eval V x false).card then
    true
  else
    false
See it in the graphDiscuss this resultChallenge it