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