AFTD Auto-Formalizing Theoretical Domains

OrderGraph

structure

An 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 d and a : Fin d, such that for each edge e ∈ E, the source e.1 is in V and the target order_move_to_front e.2 e.1 is in V.

Statement

structure OrderGraph (d : ℕ)
Defined in
arXiv:2610.39311 Definition 1
Verified
31 Oct 2026
Axioms
none listed
Built on 2
  • OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
  • order_move_to_frontThe order obtained by moving attribute a to the front of order π, preserving the relative order of the remaining attributes.
Used by 9
  • complete_order_graph_dim_six_lower_boundEvery complete order graph of dimension 6 has at least 40 edges.
  • 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_serves_uniAn 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…
  • order_graph_edges_geGiven an order graph G of dimension d and a natural number m, order_graph_edges_ge G m is the subset of edges e ∈ G.E such that m ≤…
  • 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.
  • complete_order_graph_dim_six_upper_boundThere exists a complete order graph of dimension 6 with exactly 40 edges.
  • complete_order_graph_dim_six_min_sizeThe minimum size of a complete order graph of dimension 6 is exactly 40: every complete order graph of dimension 6 has at least 40 edges,…
  • order_graph_is_completeAn order graph G is complete in the bidirectional model if for every subset S ⊆ Fin d and every element x : Fin d with x ∉ S, G serves…
  • order_graph_servesAn 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…

Read back from the Lean

A structure OrderGraph parameterized by a natural number d : ℕ, representing a directed graph whose vertices are orderings of Fin d and whose edges correspond to move-to-front operations. It contains four fields: 1. V : Finset (Order d): a finite set of vertices, where each vertex is an Order d (a permutation of Fin d represented as a duplicate-free list of length d). 2. E : Finset (Order d × Fin d): a finite set of directed edges, each represented as a pair (π, a) consisting of a source order π and an element a : Fin d. 3. edge_src : ∀ e ∈ E, e.1 ∈ V: a hypothesis that for every edge e ∈ E, the source vertex e.1 belongs to V. 4. edge_tgt : ∀ e ∈ E, order_move_to_front e.2 e.1 ∈ V: a hypothesis that for every edge e ∈ E, the target vertex resulting from moving element e.2 to the front of e.1 belongs to 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

/-- An order graph of dimension d with finite vertex set V and edge set E. -/
structure OrderGraph (d : ℕ) where
  V : Finset (Order d)
  E : Finset (Order d × Fin d)
  edge_src : ∀ e ∈ E, e.1 ∈ V
  edge_tgt : ∀ e ∈ E, order_move_to_front e.2 e.1 ∈ V
See it in the graphDiscuss this resultChallenge it