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