AFTD Auto-Formalizing Theoretical Domains

PMPoset

structure

A strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).

Statement

structure PMPoset (n : ℕ)
Defined in
Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4: Theorem 11, Theorem 16 and the conjecture that the deterministic lower bound for k = 1 is tight; formalized by the operator (Claude), 2026-10-05
Verified
05 Oct 2026
Axioms
none listed
Used by 27
  • pm_minPre_succAn element is minimal in the prefix of length k+1 iff it was minimal in the prefix of length k and is not above element k, or it is…
  • pm_ans_incIf the oracle answers that a and b are incomparable, neither a < b nor b < a holds.
  • pm_asymma ≺ b excludes b ≺ a.
  • pm_ans_famExplicit form of the oracle on a two-chain poset.
  • pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
  • PMSatA list of query/answer facts is satisfied by P.
  • pm_exists_min_belowEvery element of a prefix lies above (or is) a minimal element of that prefix.
  • pm_mem_minPreEvery minimal element of the prefix of length k has index below k and no element of index below k lies below it.
  • pmMinPreMinimal elements of the prefix {0, …, k−1}.
  • PMTree.runThe output of the algorithm T on the poset P.
  • pm_ans_ltIf the oracle answers a < b then a < b holds and b < a does not.
  • pmFamThe poset that is a disjoint union of (at most) two chains: elements of the same colour c are ordered by the rank ρ, elements of different…
  • pm_conjecture_falseThe conjecture of arXiv 0707.1532 (Section 4) that the deterministic lower bound (w+1)n/2 − w for finding the minimal elements is tight…
  • PMPoset.minSetThe set of minimal elements of P (the output of the 1-selection problem).
  • PMPoset.Width2The poset has width at most 2: among any three distinct elements some two are comparable.
  • 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_ans_gtIf the oracle answers b < a then b < a holds and a < b does not.
  • pm_alg_cost_leThe algorithm makes at most 2n − 3 queries (for n ≥ 2).
  • PMTree.costThe number of queries the algorithm T makes on the poset P.
  • PMPoset.ansThe comparison oracle: the answer to query (a, b) on the poset P.
  • pm_alg_costCost bound: at most two queries per element, one for the second element, none for the first.
  • pm_minPre_nThe minimal elements of the full prefix of length n are the minimal elements of the poset.
  • pm_step_eqOne scanning step of the candidate algorithm maintains the invariant that its candidate list is exactly the set of minimal elements of the…
  • pm_leafAt a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can…
  • pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…
  • PMTree.Correct2T correctly finds the minimal elements of every poset of width at most 2 on Fin n.
  • pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.

Lean source view module on GitHub

/-- A strict partial order on the ground set `Fin n`, given by a Boolean relation `lt` (`lt a b = true` means `a ≺ b`). -/
structure PMPoset (n : ℕ) where
  lt : Fin n → Fin n → Bool
  irrefl : ∀ a, lt a a = false
  trans : ∀ a b c, lt a b = true → lt b c = true → lt a c = true
See it in the graphDiscuss this resultChallenge it