AFTD Auto-Formalizing Theoretical Domains

braid_aut_poset_sorting_map

theoremverified

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.

  1. 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.

    lines 3–4

    uses poset_sorting_map_intertwine_iff

      change Prod.map σ σ ∘ _ = _ ↔ _
      rw [poset_sorting_map_intertwine_iff]
  2. 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).

    lines 5–8

    uses le_iff_lt_or_eq, σ.injective.eq_iff

      constructor
      · intro hlt
        refine ⟨⟨σ, fun {a b} => ?_⟩, rfl⟩
        simp only [le_iff_lt_or_eq, hlt, σ.injective.eq_iff]
  3. 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.

    lines 9–10

    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

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
See it in the graphDiscuss this resultChallenge it