AFTD Auto-Formalizing Theoretical Domains

order_graph_serves_uni

def

An order graph G of dimension d serves requirement (S, x) where S is a finite set of Fin d and x : Fin d in the unidirectional model if there exists a nonempty list of edges p all in G.E, chaining by e2.1 = order_move_to_front e1.2 e1.1, such that p has length |S| + 1, the set of edge labels in p is insert x S, and the last edge of p has label x.

Statement

def order_graph_serves_uni {d : ℕ} (G : OrderGraph d) (S : Finset (Fin d)) (x : Fin d) : Prop
Defined in
arXiv:2610.39311 Definition 2
Verified
07 Nov 2026
Axioms
none listed
Built on 3
  • OrderGraphAn order graph of dimension d is a structure consisting of a finite set V of orders of Fin d and a finite set E of edges (π, a) where π :…
  • order_move_to_frontThe order obtained by moving attribute a to the front of order π, preserving the relative order of the remaining attributes.
  • OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
Used by 2
  • order_graph_is_complete_uniAn order graph G of dimension d is complete in the unidirectional model if for every subset S ⊆ Fin d and every element x : Fin d with x ∉…
  • order_graph_is_complete_of_complete_uniIf an order graph G of dimension d is complete in the unidirectional model, then G is complete in the bidirectional model.

Read back from the Lean

Given a dimension d : ℕ, an OrderGraph d G, a subset S : Finset (Fin d), and an element x : Fin d, the proposition order_graph_serves_uni G S x asserts that there exists a non-empty list p : List (Order d × Fin d) (with non-emptiness witnessed by hp : p ≠ []) such that: 1. Every element e of p is an edge of G (e ∈ G.E). 2. Consecutive edges in p connect head-to-tail according to the move-to-front transition: for every consecutive pair (e1, e2) in p, the source order of e2 is obtained by moving the element e1.2 to the front of the order e1.1 (e2.1 = order_move_to_front e1.2 e1.1). 3. The length of p is S.card + 1. 4. The set of labels (the second components) of all edges in p is exactly insert x S (i.e., S ∪ {x}). 5. The label (second component) of the last edge in p is x.

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 order graph G serves requirement (S, x) in the unidirectional model if there is a witness path whose last edge has label x. -/
def order_graph_serves_uni {d : ℕ} (G : OrderGraph d) (S : Finset (Fin d)) (x : Fin d) : Prop := ∃ (p : List (Order d × Fin d)) (hp : p ≠ []),
    (∀ e ∈ p, e ∈ G.E) ∧
    p.IsChain (fun e1 e2 => e2.1 = order_move_to_front e1.2 e1.1) ∧
    p.length = S.card + 1 ∧
    (p.map Prod.snd).toFinset = insert x S ∧
    (p.getLast hp).2 = x
See it in the graphDiscuss this resultChallenge it