AFTD Auto-Formalizing Theoretical Domains

ArrowsUnmarked

def

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

Statement

def ArrowsUnmarked {V : Type*} (G : SimpleGraph V) (p : ArrowsPos V) (u v : V) : Prop
Defined in
arXiv:2610.15145 Section 2.2
Verified
24 Oct 2026
Axioms
none listed
Built on 1
  • 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…
Used by 5
  • 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…
  • arrows_markable_unmarked_of_legalEvery legal move of the Game of Arrows decreases the number of unmarked markable edges by exactly one.
  • arrows_legal_move_degree_ne_oneIf marking the unmarked edge uv as u -> v leaves u not a source and v not a sink, then neither u nor v has degree 1 (pendant edges can…
  • arrows_legal_move_decidableFor a finite graph with decidable equality and decidable adjacency, whether q is a legal option of p is decidable.
  • arrows_unmarked_decidableFor a finite graph with decidable adjacency, whether u and v form an unmarked edge at p is decidable.

Read back from the Lean

Given a type V, a simple graph G on V, an arrow configuration p : ArrowsPos V (an asymmetric function V → V → Bool), and two vertices u, v : V, ArrowsUnmarked G p u v is defined as the conjunction of three conditions: 1. u and v are adjacent in G (G.Adj u v), 2. p does not mark an arrow from u to v (¬ p.1 u v, i.e., p.1 u v = false), and 3. p does not mark an arrow from v to u (¬ p.1 v u, i.e., p.1 v u = false).

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

/-- An edge {u, v} in G is unmarked in position p if neither directed edge is true. -/
def ArrowsUnmarked {V : Type*} (G : SimpleGraph V) (p : ArrowsPos V) (u v : V) : Prop := G.Adj u v ∧ ¬ p.1 u v ∧ ¬ p.1 v u
See it in the graphDiscuss this resultChallenge it