pm_asymm
theoremverified
a ≺ b excludes b ≺ a.
Statement
theorem pm_asymm {n : ℕ} (P : PMPoset n) (a b : Fin n) (h : P.lt a b = true) :
P.lt b a = false- 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 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 1
- pm_ans_ltIf the oracle answers a < b then a < b holds and b < a does not.
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.
/-- `a ≺ b` excludes `b ≺ a`. -/theorem pm_asymm {n : ℕ} (P : PMPoset n) (a b : Fin n) (h : P.lt a b = true) : P.lt b a = false := by cases h' : P.lt b a · rfl · have := P.trans a b a h h' rw [P.irrefl] at this exact absurd this (by simp)