AFTD Auto-Formalizing Theoretical Domains

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.
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

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]
See it in the graphDiscuss this resultChallenge it