AFTD Auto-Formalizing Theoretical Domains

order_graph_is_complete_of_complete_uni

theoremverified

If an order graph G of dimension d is complete in the unidirectional model, then G is complete in the bidirectional model.

Statement

theorem order_graph_is_complete_of_complete_uni {d : ℕ} {G : OrderGraph d}
    (h : order_graph_is_complete_uni G) : order_graph_is_complete G
Source
arXiv:2610.39311 Definition 2
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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_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_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_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…
  • 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_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…

Read back from the Lean

For every natural number $d$ and every order graph $G$ of dimension $d$, if $G$ is unidirectionally complete (order_graph_is_complete_uni G), then $G$ is complete (order_graph_is_complete G).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that an order graph G complete in the unidirectional model is complete in the bidirectional model, fix any subset S and element x ∉ S. Unidirectional completeness provides a valid path of length |S| + 1 labeled by S ∪ {x} whose last edge is labeled by x. Because the bidirectional model only requires x to be either the first or the last label, this same path immediately witnesses bidirectional completeness.

  1. Given a subset S ⊆ Fin d and an element x ∉ S, there exists a path p that serves (S, x) in the unidirectional model.

    We fix an arbitrary subset S and an element x ∉ S. Applying the hypothesis h that G is complete in the unidirectional model provides a non-empty path p of edges in G forming a valid move-to-front chain of length |S| + 1, whose set of edge labels is S ∪ {x}, and whose final edge label is x.

    lines 4–5

      intro S x hx
      obtain ⟨p, hp, hE, hchain, hlen, hlabels, hlast⟩ := h S x hx
  2. The path p witnesses that G serves (S, x) in the bidirectional model.

    The bidirectional serving condition requires all the same structural properties of p as the unidirectional model, but weakens the requirement on x: it only requires x to be either the first or the last label of p. Since the final label of p is indeed x, the disjunction holds by Or.inr.

    line 6

    uses Or.inr

      exact ⟨p, hp, hE, hchain, hlen, hlabels, Or.inr hlast⟩
Or.inr
Given a proof of B, proves the disjunction A ∨ B.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Every order graph that is complete in the unidirectional model is complete in the bidirectional model. -/theorem order_graph_is_complete_of_complete_uni {d : ℕ} {G : OrderGraph d}    (h : order_graph_is_complete_uni G) : order_graph_is_complete G := by  intro S x hx  obtain ⟨p, hp, hE, hchain, hlen, hlabels, hlast⟩ := h S x hx  exact ⟨p, hp, hE, hchain, hlen, hlabels, Or.inr hlast⟩
See it in the graphDiscuss this resultChallenge it