is_compatible_solution
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)