Halving.target_mem_update
theoremverifiedimported Lean
Target survives its own update. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let $V \subseteq \mathit{Hyp}$ be a version space, fix an input $x \in X$, and let $\mathtt{target} \in V$ be a hypothesis. Then $\mathtt{target}$ remains in the version space obtained by updating $V$ on $x$ with the label that $\mathtt{target}$ itself assigns, that is, $\mathtt{target} \in \mathtt{update}(\mathtt{eval}, V, x, \mathtt{eval}\,\mathtt{target}\,x)$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {Hyp X : Type*} in lemma Halving.target_mem_update (eval : Hyp → X → Bool) (target : Hyp) (V : Finset Hyp) (x : X) (htarget : target ∈ V) : target ∈ update eval V x (eval target x)
- Source
- TCSlib, `Halving.target_mem_update`
- 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.target_mem_update← Halving.target_mem_update (TCSlib/LearningTheory/MistakeBounds/Halving.lean:112): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- Halving.updateAfter observing that the correct label for input $x$ is $y$, the version space is updated to…
- 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.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/-- In the realizable setting the target hypothesis survives every update: if `target` lies in `V`, then it lies in the version space obtained by updating `V` on `x` with the label that `target` itself assigns to `x`. -/lemma Halving.target_mem_update (eval : Hyp → X → Bool) (target : Hyp) (V : Finset Hyp) (x : X) (htarget : target ∈ V) : target ∈ update eval V x (eval target x) := by simp [update, voteFor, htarget]