AFTD Auto-Formalizing Theoretical Domains

arrows_legal_move_decidable

instance

For a finite graph with decidable equality and decidable adjacency, whether q is a legal option of p is decidable.

Statement

instance arrows_legal_move_decidable {V : Type*} [DecidableEq V] [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (p q : ArrowsPos V) : Decidable (ArrowsLegalMove G p q)
Source
step towards arrows_op602_refutation_tree_grundy_gt_three
Verified
28 Oct 2026
Axioms
none listed
Built on 5
  • ArrowsIsSinkIn a simple graph G and position p : ArrowsPos V, vertex u is a sink if G.degree u ≥ 1 and for every neighbor v adjacent to u in G, p.1 v…
  • ArrowsLegalMoveIn a simple graph G, a transition from position p to q in ArrowsPos V is a legal move if there exist u, v with ArrowsUnmarked G p u v such…
  • ArrowsPosGiven a type V, ArrowsPos V is the subtype of boolean-valued binary relations p : V → V → Bool that are asymmetric, meaning that for all…
  • ArrowsUnmarkedIn a simple graph G and position p : ArrowsPos V, vertices u and v form an unmarked edge if G.Adj u v and both p.1 u v and p.1 v u are…
  • ArrowsIsSourceIn a simple graph G and position p : ArrowsPos V, vertex u is a source if G.degree u ≥ 1 and for every neighbor v adjacent to u in G, p.1…

Lean source view module on GitHub

/-- Decidability of the legal-move relation, so that concrete legality instances can be closed by kernel `decide`. -/
instance arrows_legal_move_decidable {V : Type*} [DecidableEq V] [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (p q : ArrowsPos V) : Decidable (ArrowsLegalMove G p q) := by unfold ArrowsLegalMove ArrowsUnmarked ArrowsIsSink ArrowsIsSource; infer_instance
See it in the graphDiscuss this resultChallenge it