AFTD Auto-Formalizing Theoretical Domains

PMPoset.minSet

def

The set of minimal elements of P (the output of the 1-selection problem).

Statement

open Finset in
def PMPoset.minSet {n : ℕ} (P : PMPoset n) : Finset (Fin 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
Built on 1
  • PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
Used by 4
  • 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_minPre_nThe minimal elements of the full prefix of length n are the minimal elements of the poset.
  • pm_leafAt a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can…
  • PMTree.Correct2T correctly finds the minimal elements of every poset of width at most 2 on Fin n.

Lean source view module on GitHub

open Finset in
/-- The set of minimal elements of `P` (the output of the 1-selection problem). -/
def PMPoset.minSet {n : ℕ} (P : PMPoset n) : Finset (Fin n) :=
  univ.filter (fun a => ∀ b, P.lt b a = false)
See it in the graphDiscuss this resultChallenge it