AFTD Auto-Formalizing Theoretical Domains

is_compatible_solution

def

A triple (L, e, U) is a compatible solution for a partial order P on Fin n and rank i if L, {e}, and U partition Fin n with |L| = i - 1, and there exists a linear extension T of P that places all elements of L below e and e below all elements of U.

Statement

def is_compatible_solution {n : ℕ} (P : PartialOrder (Fin n)) (i : ℕ)
    (L : Finset (Fin n)) (e : Fin n) (U : Finset (Fin n)) : Prop
Defined in
arXiv:2610.18740 Section 5
Verified
23 Oct 2026
Axioms
none listed
Built on 1
  • is_linear_extensionGiven a natural number n, a partial order P on Fin n, and a linear order L on Fin n, L is a linear extension of P if for all x y in Fin n,…
Used by 1
  • poset_key_boundFor a partial order P on Fin n and rank i, KEY(P) is the supremum over all compatible solutions s = (L, e, U) of the crucial comparisons…

Read back from the Lean

Given a partial order P on Fin n, a natural number i, finite sets L, U : Finset (Fin n), and an element e : Fin n, is_compatible_solution P i L e U asserts that: 1. The cardinality of L equals i - 1 (using natural number subtraction); 2. e ∉ L; 3. e ∉ U; 4. L and U are disjoint; 5. The union L ∪ {e} ∪ U equals Finset.univ (i.e., L, {e}, and U partition Fin n); 6. There exists a linear order T on Fin n such that: - T is a linear extension of P (for all x, y : Fin n, if x ≤ y under P, then x ≤ y under T), - for all x ∈ L, x < e under T, and - for all y ∈ U, e < y under T.

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

/-- A compatible solution s = (L, e, U) for a partial order P on Fin n at rank i. -/
def is_compatible_solution {n : ℕ} (P : PartialOrder (Fin n)) (i : ℕ)
    (L : Finset (Fin n)) (e : Fin n) (U : Finset (Fin n)) : Prop := open scoped Classical in
  L.card = i - 1 ∧
  e ∉ L ∧ e ∉ U ∧ Disjoint L U ∧
  L ∪ {e} ∪ U = Finset.univ ∧
  ∃ (T : LinearOrder (Fin n)), is_linear_extension P T ∧
    (∀ x ∈ L, @LT.lt (Fin n) T.toLT x e) ∧
    (∀ y ∈ U, @LT.lt (Fin n) T.toLT e y)
See it in the graphDiscuss this resultChallenge it