AFTD Auto-Formalizing Theoretical Domains

PMAns

inductive

The 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 ("Sorting and Selection in Posets"), Section 4.

Statement

inductive PMAns
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 16
  • pm_ans_incIf the oracle answers that a and b are incomparable, neither a < b nor b < a holds.
  • pm_inv_killAdversary case: comparison of two alive elements of the same component and colour; the larger one (z) dies and is re-ranked just below all…
  • pm_ans_famExplicit form of the oracle on a two-chain poset.
  • PMSatA list of query/answer facts is satisfied by P.
  • pm_ans_ltIf the oracle answers a < b then a < b holds and b < a does not.
  • pm_inv_mergeAdversary case: two different components are merged (answer ∥); the second component is recoloured if necessary. The number of components…
  • PMTreeA deterministic adaptive comparison algorithm, as a decision tree: a leaf outputs a set, an internal node queries the pair (a, b) and…
  • pm_inv_sameAdversary case a = b: invariant kept, potential unchanged.
  • pmAlgThe candidate-list algorithm (Theorem 11 of arXiv 0707.1532, for width 2): scan the elements in order, keeping the (at most two) minimal…
  • PMState.stepThe adversary's move on query (a, b): the answer, and the new state.
  • pm_recolorRecolouring that preserves colour-equality on every fact preserves all answers.
  • pm_ans_gtIf the oracle answers b < a then b < a holds and a < b does not.
  • PMPoset.ansThe comparison oracle: the answer to query (a, b) on the poset P.
  • PMStateThe state of the adversary: a colouring (which of the two chains), ranks, a component label, the set of "alive" elements (not yet shown to…
  • pm_inv_diffcolAdversary case: same component, different colours (answer ∥, forced).
  • pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.

Lean source view module on GitHub

/-- The 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 ("Sorting and Selection in Posets"), Section 4. -/
inductive PMAns | lt
  | gt
  | inc
  deriving DecidableEq
See it in the graphDiscuss this resultChallenge it