braid_aut_poset_sorting_map
A permutation σ of a partially ordered set P lies in Aut(P,R_P) iff σ is (the underlying permutation of) an order automorphism of P.
Statement
theorem braid_aut_poset_sorting_map (P : Type*) [PartialOrder P] (σ : Equiv.Perm P) : σ ∈ braid_aut (poset_sorting_map P) ↔ ∃ f : P ≃o P, f.toEquiv = σ
- 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.
- braid_autFor any map R : X × X → X × X on a type X, braid_aut R is the subgroup of permutations σ of X that commute with R in the sense that (σ ×…
- 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 condition that σ lies in the braid automorphism group Aut(P, R_P) means that σ × σ commutes with the poset sorting map. By a previous characterization (poset_sorting_map_intertwine_iff), this commutation holds if and only if σ preserves strict inequality between all pairs of elements. The proof then reduces to showing that a permutation preserves strict inequality if and only if it is an order automorphism: the forward direction constructs the order automorphism by expanding ≤ into < or = and applying injectivity, while the reverse direction follows because order isomorphisms preserve strict inequality.
A permutation σ belongs to Aut(P, R_P) if and only if σ preserves strict inequality between all pairs of elements.
By definition of braid_aut, σ belongs to Aut(P, R_P) if and only if σ × σ commutes with the poset sorting map poset_sorting_map P. By poset_sorting_map_intertwine_iff, this commutation is equivalent to σ y < σ x ↔ y < x for all x, y ∈ P.
uses
poset_sorting_map_intertwine_iffchange Prod.map σ σ ∘ _ = _ ↔ _ rw [poset_sorting_map_intertwine_iff]
If σ preserves strict inequality, then σ is the underlying permutation of an order automorphism of P.
We split the bi-implication into two directions. For the forward direction, assume σ preserves strict inequality (hlt). We construct an order automorphism whose underlying bijection is σ. To verify that σ preserves the non-strict order (σ a ≤ σ b ↔ a ≤ b), we rewrite ≤ in terms of < and = using le_iff_lt_or_eq. The equivalence then follows because σ preserves strict inequality by hlt and preserves equality by injectivity (σ.injective.eq_iff).
uses
le_iff_lt_or_eq,σ.injective.eq_iffconstructor · intro hlt refine ⟨⟨σ, fun {a b} => ?_⟩, rfl⟩ simp only [le_iff_lt_or_eq, hlt, σ.injective.eq_iff]
Conversely, any order automorphism of P preserves strict inequality.
Given an order automorphism f whose underlying permutation is σ, the order isomorphism f preserves strict inequality directly by f.lt_iff_lt, yielding f y < f x ↔ y < x.
uses
f.lt_iff_lt· rintro ⟨f, rfl⟩ x y exact f.lt_iff_lt
poset_sorting_map_intertwine_iff- A bijection between posets intertwines their sorting maps under the product action if and only if it preserves strict inequality: e y < e x ↔ y < x for all x, y.
le_iff_lt_or_eq- In any partial order, a ≤ b if and only if a < b or a = b.
σ.injective.eq_iff- An injective map reflects and preserves equality: σ a = σ b ↔ a = b.
f.lt_iff_lt- An order isomorphism preserves and reflects strict inequality: f y < f x ↔ y < x.
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 braid_aut_poset_sorting_map (P : Type*) [PartialOrder P] (σ : Equiv.Perm P) : σ ∈ braid_aut (poset_sorting_map P) ↔ ∃ f : P ≃o P, f.toEquiv = σ := by change Prod.map σ σ ∘ _ = _ ↔ _ rw [poset_sorting_map_intertwine_iff] constructor · intro hlt refine ⟨⟨σ, fun {a b} => ?_⟩, rfl⟩ simp only [le_iff_lt_or_eq, hlt, σ.injective.eq_iff] · rintro ⟨f, rfl⟩ x y exact f.lt_iff_lt