AFTD Auto-Formalizing Theoretical Domains

moving_target_strategy_stop_successful

theoremverified

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 MovingTargetStrategy parameterized by a type V : 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…

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

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

    line 5

    uses moving_target_strategy_successful

      simp [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

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