AFTD Auto-Formalizing Theoretical Domains

pmFam

def

The poset that is a disjoint union of (at most) two chains: elements of the same colour c are ordered by the rank ρ, elements of different colours are incomparable.

Statement

def pmFam {n : ℕ} (c : Fin n → Bool) (ρ : Fin n → ℤ) : PMPoset n where
  lt a b
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
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 12
  • pm_rerankChanging an alive element's rank to anything below n + #alive does not change any recorded answer (used both for the adversary's "kill"…
  • 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.
  • pm_fam_width2Two-chain posets with injective rank have width at most 2.
  • PMState.InvThe adversary invariant.
  • pm_inv_mergeAdversary case: two different components are merged (answer ∥); the second component is recoloured if necessary. The number of components…
  • 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_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…
  • pm_inv_deadAdversary case: same component and colour, not both alive (answer read off the current two-chain realisation).
  • pm_leafAt a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can…
  • pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.

Lean source view module on GitHub

/-- The poset that is a disjoint union of (at most) two chains: elements of the same colour `c` are ordered by the rank `ρ`, elements of different colours are incomparable. -/
def pmFam {n : ℕ} (c : Fin n → Bool) (ρ : Fin n → ℤ) : PMPoset n where
  lt a b := decide (c a = c b ∧ ρ a < ρ b)
  irrefl a := by simp
  trans a b d h1 h2 := by
    simp only [decide_eq_true_eq] at h1 h2 ⊢
    exact ⟨h1.1.trans h2.1, h1.2.trans h2.2⟩
See it in the graphDiscuss this resultChallenge it