AFTD Auto-Formalizing Theoretical Domains

ArrowsPos

def

Given a type V, ArrowsPos V is the subtype of boolean-valued binary relations p : V → V → Bool that are asymmetric, meaning that for all u, v : V, if p u v is true, then p v u is false.

Statement

def ArrowsPos (V : Type*) : Type _
Defined in
arXiv:2610.15145 Section 2.2
Verified
24 Oct 2026
Axioms
none listed
Used by 18
  • arrows_unmarked_countThe number of unmarked edges of G at the position p: edges of G on which neither orientation has been marked.
  • arrows_pos_grundy_eq_mod_two_of_classStrategy lemma for parity in the Game of Arrows: let e be a function on positions that drops by exactly one along every legal move, and S…
  • ArrowsEmptyPosThe empty starting position in ArrowsPos V whose boolean relation is everywhere false.
  • arrows_tree_grundyThe Grundy value of the Game of Arrows on a finite simple graph G is the Grundy value of the empty position ArrowsEmptyPos V at fuel…
  • 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_parity_of_strategy_classLet T be a finite tree and S a class of positions of the Game of Arrows on T that contains the empty position, such that from every…
  • 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…
  • 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_markable_unmarkedThe number of unmarked markable edges of a position p of the Game of Arrows on G: edges of G neither of whose endpoints has degree 1 and…
  • arrows_pos_grundy_options_finiteFor any fuel and position p of the Game of Arrows on a finite graph, the set of fuel-bounded Grundy values of the legal options of p is…
  • arrows_pos_grundyThe Grundy value of a position p : ArrowsPos V in the Game of Arrows on G at recursion depth fuel, defined as 0 when fuel = 0 and as the…
  • arrows_sum_posThe disjoint-sum position of a position p on G and a position q on H: the arrows of p are placed on the left copy, the arrows of q on the…
  • 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…
  • arrows_legal_move_decidableFor a finite graph with decidable equality and decidable adjacency, whether q is a legal option of p is decidable.
  • 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…
  • arrows_twin_invariantThe pairing invariant of the second player on the disjoint sum of T and T' in the twin-branch configuration: the marked edges of the two…
  • 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, ArrowsPos V is the type of boolean-valued binary relations p : V → V → Bool on V that are asymmetric: for all u, v : V, if p u v is true, then p v u is false (in particular, p u u is false for all u : V).

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

/-- The subtype of boolean-valued binary relations on V that are asymmetric. -/
def ArrowsPos (V : Type*) : Type _ := { p : V → V → Bool // ∀ u v, p u v → ¬ p v u }
See it in the graphDiscuss this resultChallenge it