AFTD Auto-Formalizing Theoretical Domains

moving_target_strategy_successful

def

Given a finite type V with decidable equality, a simple graph G on V with decidable adjacency, an accuracy threshold s : ℕ, a strategy strat : MovingTargetStrategy V, and a candidate set D : Finset V, moving_target_strategy_successful G s strat D is a proposition defined by recursion on strat: if strat is stop, then D.card ≤ s; if strat is query Q on_false on_true, let C := closed_neighborhood G D in ((C \ Q).Nonempty → moving_target_strategy_successful G s on_false (C \ Q)) ∧ ((C ∩ Q).Nonempty → moving_target_strategy_successful G s on_true (C ∩ Q)).

Statement

def moving_target_strategy_successful {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (s : ℕ) :
    MovingTargetStrategy V → Finset V → Prop
Defined in
arXiv:2611.01281 Definition 2.1
Verified
04 Nov 2026
Axioms
none listed
Built on 2
  • 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,…
Used by 4

Read back from the Lean

Given a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a natural number s, moving_target_strategy_successful G s is a recursively defined predicate on a strategy tree (of type MovingTargetStrategy V) and a set of candidate vertices D : Finset V: - If the strategy is .stop, it asserts that the cardinality of D is at most s (D.card ≤ s). - If the strategy is .query Q on_false on_true for a query set Q : Finset V and sub-strategies on_false and on_true: Let C be the closed neighborhood of D in G. The predicate asserts the conjunction of: 1. If C \ Q is nonempty, then moving_target_strategy_successful G s on_false (C \ Q) holds. 2. If C ∩ Q is nonempty, then moving_target_strategy_successful G s on_true (C ∩ Q) holds.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Whether an adaptive search strategy is successful with accuracy s starting from a candidate set. -/
def moving_target_strategy_successful {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (s : ℕ) :
    MovingTargetStrategy V → Finset V → Prop
  | .stop, D => D.card ≤ s
  | .query Q on_false on_true, D =>
    let C := closed_neighborhood G D
    ((C \ Q).Nonempty → moving_target_strategy_successful G s on_false (C \ Q)) ∧
    ((C ∩ Q).Nonempty → moving_target_strategy_successful G s on_true (C ∩ Q))
See it in the graphDiscuss this resultChallenge it