AFTD Auto-Formalizing Theoretical Domains

poset_sorting_map_braid_iso_iff

theoremverified

For partially ordered sets P and Q, the solutions (P,R_P) and (Q,R_Q) are isomorphic iff P and Q are order isomorphic.

Statement

theorem poset_sorting_map_braid_iso_iff (P Q : Type*) [PartialOrder P] [PartialOrder Q] :
    is_braid_iso (poset_sorting_map P) (poset_sorting_map Q) ↔ Nonempty (P ≃o Q)
Source
Step of arXiv:2611.15540, Theorem A (Theorem 2.1 and Corollary 2.2)
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • poset_sorting_mapFor a partially ordered set P, the map R_P on P × P swaps (x, y) to (y, x) if y < x and leaves (x, y) fixed otherwise.
  • is_braid_isoTwo maps R : X × X → X × X and S : Y × Y → Y × Y are isomorphic if there exists an equivalence e : X ≃ Y such that (e × e) ∘ R = S ∘ (e ×…
  • poset_sorting_map_intertwine_iffAn equivalence e : P ≃ Q between partially ordered sets intertwines R_P and R_Q, (e×e)∘R_P = R_Q∘(e×e), iff e preserves and reflects the…
Used by 1
  • poset_sorting_map_classificationLet P and Q be partially ordered sets and X a set, and let R_P : P×P → P×P map (x,y) to (y,x) if y<x and fix it otherwise. Then (1) R_P…

The proof, explained

The theorem is proved by establishing the two implications separately. The central bridge is `poset_sorting_map_intertwine_iff`, which shows that a bijection between two posets intertwines their sorting maps if and only if it preserves and reflects strict inequality. Because non-strict inequality in a poset is completely determined by strict inequality and equality (a ≤ b ↔ a < b ∨ a = b), any bijection preserving strict order is an order isomorphism, and conversely, any order isomorphism intertwines the sorting maps.

  1. If the sorting maps are isomorphic as braid solutions, then the posets P and Q are order isomorphic.

    We split the equivalence into two directions using `constructor`. For the forward implication, we assume a braid isomorphism between the sorting maps, which provides a bijection e : P ≃ Q intertwining them (`rintro ⟨e, he⟩`). By `poset_sorting_map_intertwine_iff`, intertwining the sorting maps means e preserves and reflects strict inequality: e y < e x ↔ y < x for all x, y in P (`hlt`). To promote e to an order isomorphism P ≃o Q (`refine ⟨⟨e, fun {a b} => ?_⟩⟩`), we must show that e a ≤ e b ↔ a ≤ b. Using `le_iff_lt_or_eq`, non-strict inequality decomposes into strict inequality or equality (a < b ∨ a = b). Because e preserves strict order (by `hlt`) and is injective, the non-strict order equivalence follows, establishing that P and Q are order isomorphic.

    lines 3–7

    uses poset_sorting_map_intertwine_iff, le_iff_lt_or_eq

      constructor
      · rintro ⟨e, he⟩
        have hlt := (poset_sorting_map_intertwine_iff e).1 he
        refine ⟨⟨e, fun {a b} => ?_⟩⟩
        simp only [le_iff_lt_or_eq, hlt, e.injective.eq_iff]
  2. Conversely, if P and Q are order isomorphic, then their sorting maps are isomorphic as braid solutions.

    For the reverse implication, we assume there exists an order isomorphism f : P ≃o Q (`rintro ⟨f⟩`). Because f preserves strict inequality (x < y ↔ f x < f y), the reverse direction of `poset_sorting_map_intertwine_iff` shows that the underlying bijection of f intertwines the sorting maps of P and Q. This exhibits an explicit braid isomorphism between the two sorting maps.

    lines 8–9

    uses poset_sorting_map_intertwine_iff

      · rintro ⟨f⟩
        exact ⟨f.toEquiv, (poset_sorting_map_intertwine_iff f.toEquiv).2 fun x y => f.lt_iff_lt⟩
le_iff_lt_or_eq
In a partial order, a non-strict inequality a ≤ b holds if and only if a < b or a = b.
poset_sorting_map_intertwine_iff
A bijection between two posets intertwines their sorting maps if and only if it preserves and reflects the strict partial order (e y < e x ↔ y < x for all x, y).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem poset_sorting_map_braid_iso_iff (P Q : Type*) [PartialOrder P] [PartialOrder Q] :    is_braid_iso (poset_sorting_map P) (poset_sorting_map Q) ↔ Nonempty (P ≃o Q) := by  constructor  · rintro ⟨e, he⟩    have hlt := (poset_sorting_map_intertwine_iff e).1 he    refine ⟨⟨e, fun {a b} => ?_⟩⟩    simp only [le_iff_lt_or_eq, hlt, e.injective.eq_iff]  · rintro ⟨f⟩    exact ⟨f.toEquiv, (poset_sorting_map_intertwine_iff f.toEquiv).2 fun x y => f.lt_iff_lt⟩
See it in the graphDiscuss this resultChallenge it