poset_sorting_map_braid_iso_iff
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.
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.
uses
poset_sorting_map_intertwine_iff,le_iff_lt_or_eqconstructor · 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]
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.
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
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 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⟩