Halving.update_subset
theoremverifiedimported Lean
The updated version space is a subset. Fix an evaluation map $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$, a finite version space $V \subseteq \mathit{Hyp}$, an input $x \in X$, and a label $y \in \mathsf{Bool}$. Then the updated version space is contained in the original one: $\mathtt{update}(\mathtt{eval}, V, x, y) \subseteq V$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {Hyp X : Type*} in lemma Halving.update_subset (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) (y : Bool) : update eval V x y ⊆ V
- Source
- TCSlib, `Halving.update_subset`
- 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.Halving.update_subset← Halving.update_subset (TCSlib/LearningTheory/MistakeBounds/Halving.lean:101): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- Halving.updateAfter observing that the correct label for input $x$ is $y$, the version space is updated to…
- Used by 1
- 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…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false invariable {Hyp X : Type*} in/-- Updating the version space on a labelled example only removes hypotheses: the updated version space `update eval V x y` is a subset of the old version space `V`. -/lemma Halving.update_subset (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) (y : Bool) : update eval V x y ⊆ V := by intro h hh have hh' : h ∈ V ∧ eval h x = y := by simpa [update, voteFor] using hh exact hh'.1