moving_target_strategy_stop_successful
For any finite type V with decidable equality and simple graph G on V with decidable adjacency, the immediate stopping strategy MovingTargetStrategy.stop is successful with accuracy Fintype.card V starting from Finset.univ: moving_target_strategy_successful G (Fintype.card V) MovingTargetStrategy.stop Finset.univ.
Statement
theorem moving_target_strategy_stop_successful {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : moving_target_strategy_successful G (Fintype.card V) MovingTargetStrategy.stop Finset.univ
- Source
- arXiv:2611.01281 Definition 2.1
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- MovingTargetStrategyAn inductive datatype
MovingTargetStrategyparameterized by a typeV : Type*, with two constructors:stop : MovingTargetStrategy V… - closed_neighborhoodGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset A : Finset V,…
- moving_target_strategy_successfulGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, an accuracy threshold s : ℕ, a strategy…
- MovingTargetStrategyAn inductive datatype
Read back from the Lean
For any finite type V with decidable equality and any simple graph G on V with decidable adjacency, the immediate-stop strategy MovingTargetStrategy.stop is a successful moving-target strategy on G with target bound Fintype.card V when starting from the universal set Finset.univ.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof unfolds the definition of `moving_target_strategy_successful` for the immediate stopping strategy `MovingTargetStrategy.stop`. On the initial candidate set of all vertices `Finset.univ`, stopping requires that the size of the set does not exceed the target accuracy, which holds trivially since |Finset.univ| = |V| ≤ |V|.
The immediate stopping strategy succeeds with accuracy |V| on the entire vertex set.
By definition of `moving_target_strategy_successful`, the stopping strategy `MovingTargetStrategy.stop` is successful on a set of candidates `D` with bound `s` if and only if |D| ≤ s. For D = Finset.univ and s = |V|, this condition is |Finset.univ| ≤ |V|, which is |V| ≤ |V| and holds by reflexivity. Simplification with the definition of `moving_target_strategy_successful` unfolds this definition and automatically closes the resulting inequality.
uses
moving_target_strategy_successfulsimp [moving_target_strategy_successful]
moving_target_strategy_successful- Inductive predicate asserting that a strategy guarantees locating the moving target within a set of size at most s, which for the stopping strategy requires the candidate set D to satisfy |D| ≤ s.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
/-- The immediate stopping strategy is successful with accuracy equal to the vertex count. -/theorem moving_target_strategy_stop_successful {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : moving_target_strategy_successful G (Fintype.card V) MovingTargetStrategy.stop Finset.univ := by simp [moving_target_strategy_successful]