AFTD Auto-Formalizing Theoretical Domains

Halving.voteFor_false_add_true

theoremverifiedimported Lean

Vote counts partition the version space. Let $\mathrm{eval}$ be a Boolean evaluation map assigning to each hypothesis and each input a truth value, let $V$ be a finite version space of hypotheses, and let $x$ be an input. Every hypothesis in $V$ predicts either $\mathsf{false}$ or $\mathsf{true}$ on $x$, so the number of hypotheses in $V$ predicting $\mathsf{false}$ on $x$ and the number predicting $\mathsf{true}$ on $x$ sum to the total number of hypotheses in $V$: \[ \abs{\{\,h \in V : \mathrm{eval}(h, x) = \mathsf{false}\,\}} + \abs{\{\,h \in V : \mathrm{eval}(h, x) = \mathsf{true}\,\}} = \abs{V}. \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {Hyp X : Type*} in
lemma Halving.voteFor_false_add_true
    (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) :
    (voteFor eval V x false).card + (voteFor eval V x true).card = V.card
Source
TCSlib, `Halving.voteFor_false_add_true`
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.
What was changed in Halving.voteFor_false_add_true
--- TCSlib/LearningTheory/MistakeBounds/Halving.lean:86 (Halving.voteFor_false_add_true)
+++ as compiled here
@@ -1,4 +1,5 @@
-/-- The number of hypotheses of `V` voting `false` on `x` plus the number voting `true` on
-`x` equals the size of `V`: the two vote sets partition the current version space. -/
-lemma voteFor_false_add_true
+set_option relaxedAutoImplicit false in
+set_option autoImplicit false in
+variable {Hyp X : Type*} in
+lemma Halving.voteFor_false_add_true
     (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) :
@@ -12,3 +13,3 @@
   rw [hfilter]
-  exact Finset.filter_card_add_filter_neg_card_eq_card
+  exact Finset.card_filter_add_card_filter_not
     (s := V) (p := fun h : Hyp => eval h x = false)
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
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 1
  • Halving.mistake_halvesMistake bound for the Halving algorithm. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {Hyp X : Type*} in/-- The number of hypotheses of `V` voting `false` on `x` plus the number voting `true` on `x` equals the size of `V`: the two vote sets partition the current version space. -/lemma Halving.voteFor_false_add_true    (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) :    (voteFor eval V x false).card + (voteFor eval V x true).card = V.card := by  unfold voteFor  have hfilter :      V.filter (fun h : Hyp => eval h x = true) =        V.filter (fun h : Hyp => ¬ eval h x = false) := by    ext h    cases eval h x <;> simp  rw [hfilter]  exact Finset.card_filter_add_card_filter_not    (s := V) (p := fun h : Hyp => eval h x = false)
See it in the graphDiscuss this resultChallenge it