order_graph_is_complete_uni
An 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 ∉ S, G serves requirement (S, x) in the unidirectional model.
Statement
def order_graph_is_complete_uni {d : ℕ} (G : OrderGraph d) : Prop
- Defined in
- arXiv:2610.39311 Definition 3
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Built on 2
- 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_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…
- Used by 1
- 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 natural number d and an OrderGraph d G, order_graph_is_complete_uni G asserts that for every subset S of Fin d and every element x : Fin d such that x ∉ S, G serves the pair (S, x). That is, there exists a non-empty list of edges p : List (Order d × Fin d) such that:
1. Every edge e in p belongs to G.E;
2. Consecutive edges in p are chained such that the source permutation of each step e2 is obtained by moving the label (the second component) of the previous step e1 to the front of e1's permutation;
3. The length of p is S.card + 1;
4. The set of labels (second components) of the edges in p is equal to insert x S (meaning every element of S ∪ {x} appears exactly once as an edge label along p);
5. The label of the final 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 is complete in the unidirectional model if it serves every requirement (S, x) with x ∉ S in the unidirectional model. -/ def order_graph_is_complete_uni {d : ℕ} (G : OrderGraph d) : Prop := ∀ (S : Finset (Fin d)) (x : Fin d), x ∉ S → order_graph_serves_uni G S x