pm_ans_gt
theoremverified
If the oracle answers b < a then b < a holds and a < b does not.
Statement
theorem pm_ans_gt {n : ℕ} (P : PMPoset n) (a b : Fin n) (h : P.ans a b = PMAns.gt) :
P.lt a b = false ∧ P.lt b a = true- 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
propext- 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 1
- pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem pm_ans_gt {n : ℕ} (P : PMPoset n) (a b : Fin n) (h : P.ans a b = PMAns.gt) : P.lt a b = false ∧ P.lt b a = true := by unfold PMPoset.ans at h cases h1 : P.lt a b <;> cases h2 : P.lt b a <;> simp_all