AFTD Auto-Formalizing Theoretical Domains

PMSat

def

A list of query/answer facts is satisfied by P.

Statement

def PMSat {n : ℕ} (P : PMPoset n) (F : List (Fin n × Fin n × PMAns)) : Prop
Source
step towards pm_exact_complexity / pm_lower_bound (exact complexity 2n - 3 at width 2, refuting the tightness conjecture of Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4)
Verified
06 Oct 2026
Axioms
none listed
Built on 3
  • PMAnsThe three possible answers of a comparison query (a, b) on a poset: a ≺ b, b ≺ a, or a ∥ b (incomparable). Setting of arXiv 0707.1532…
  • PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
  • PMPoset.ansThe comparison oracle: the answer to query (a, b) on the poset P.
Used by 3
  • PMState.InvThe adversary invariant.
  • pm_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…
  • pm_leafAt a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can…

Lean source view module on GitHub

/-- A list of query/answer facts is satisfied by `P`. -/
def PMSat {n : ℕ} (P : PMPoset n) (F : List (Fin n × Fin n × PMAns)) : Prop :=
  ∀ f ∈ F, P.ans f.1 f.2.1 = f.2.2
See it in the graphDiscuss this resultChallenge it