AFTD Auto-Formalizing Theoretical Domains

order_graph_serves

def

An order graph G serves requirement (S, x) where S is a finite set of Fin d and x : Fin d 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 either the first edge of p or the last edge of p has label x.

Statement

def order_graph_serves {d : ℕ} (G : OrderGraph d) (S : Finset (Fin d)) (x : Fin d) : Prop
Defined in
arXiv:2610.39311 Definition 2
Verified
31 Oct 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 4

Read back from the Lean

For a natural number d, an order graph G on Fin d, a finite set S ⊆ Fin d, and an element x ∈ Fin d, order_graph_serves G S x asserts the existence of a non-empty list p of edges (each edge being a pair (π, a) of a permutation π of Fin d and a label a ∈ Fin d) such that: 1. Every edge in p belongs to G.E; 2. p forms a directed path/walk: for any two consecutive edges e₁, e₂ in p, the source permutation of e₂ is obtained from the source permutation of e₁ by moving the label of e₁ to the front (e₂.1 = order_move_to_front e₁.2 e₁.1); 3. The number of edges in p is |S| + 1; 4. The set of edge labels appearing in p is equal to {x} ∪ S; 5. The label of either the first edge in p or 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

/-- G serves requirement (S, x) in the bidirectional model. -/
def order_graph_serves {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.head hp).2 = x ∨ (p.getLast hp).2 = x)
See it in the graphDiscuss this resultChallenge it