AFTD Auto-Formalizing Theoretical Domains

poset_sorting_map_classification

theoremverifiedformalization

Let 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 satisfies the braid equation R12∘R23∘R12 = R23∘R12∘R23 and is idempotent; (2) a permutation of P commutes with R_P (i.e. lies in Aut(P,R_P)) iff it is an order automorphism of P; (3) there is a bijection P → Q intertwining R_P and R_Q iff P and Q are order isomorphic; (4) for every map R : X×X → X×X with R(x,y) ∈ {(x,y),(y,x)} for all x,y, R is an idempotent solution of the braid equation iff R = R_P for exactly one partial order on X.

Statement

theorem poset_sorting_map_classification (P Q X : Type*) [PartialOrder P] [PartialOrder Q] :
    (is_braid_solution (poset_sorting_map P) ∧
        poset_sorting_map P ∘ poset_sorting_map P = poset_sorting_map P) ∧
      (∀ σ : Equiv.Perm P, σ ∈ braid_aut (poset_sorting_map P) ↔ ∃ f : P ≃o P, f.toEquiv = σ) ∧
      (is_braid_iso (poset_sorting_map P) (poset_sorting_map Q) ↔ Nonempty (P ≃o Q)) ∧
      (∀ R : X × X → X × X, (∀ x y : X, R (x, y) = (x, y) ∨ R (x, y) = (y, x)) →
        ((is_braid_solution R ∧ R ∘ R = R) ↔ ∃! o : PartialOrder X, R = @poset_sorting_map X o))
Formalizes
arXiv:2611.15540, Theorem A (Theorem 2.1 and Corollary 2.2); Aut(P,R_P)=Aut(P) stated as: a permutation commutes with R_P iff it is an order automorphism
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • poset_sorting_map_idempotent_braidFor every partially ordered set P, the sorting map R_P (swapping (x,y) to (y,x) when y<x, fixing it otherwise) satisfies the braid…
  • braid_aut_poset_sorting_mapA permutation σ of a partially ordered set P lies in Aut(P,R_P) iff σ is (the underlying permutation of) an order automorphism of P.
  • poset_sorting_map_braid_iso_iffFor partially ordered sets P and Q, the solutions (P,R_P) and (Q,R_Q) are isomorphic iff P and Q are order isomorphic.
  • swap_idempotent_braid_iff_poset_sorting_mapIf R : X×X → X×X satisfies R(x,y) ∈ {(x,y),(y,x)} for all x,y, then R is an idempotent solution of the braid equation iff R = R_P for a…
  • 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 ×…
  • 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 (σ ×…
  • is_braid_solutionA map R : X × X → X × X on a type X is a solution of the braid equation if (R × id) ∘ (id × R) ∘ (R × id) = (id × R) ∘ (R × id) ∘ (id × R)…
  • 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.

Read back from the Lean

For all types $P$, $Q$, and $X$, where $P$ and $Q$ are equipped with partial orders: 1. The poset sorting map on $P$ (which maps $(x, y) \mapsto (y, x)$ if $y < x$, and $(x, y)$ otherwise) satisfies the set-theoretic braid relation and is idempotent under composition (poset_sorting_map P ∘ poset_sorting_map P = poset_sorting_map P). 2. For every permutation $\sigma$ of $P$, $\sigma$ is an automorphism of the sorting map on $P$ (i.e., $\sigma \in \text{braid\_aut}(\text{poset\_sorting\_map } P)$) if and only if there exists an order automorphism $f : P \simeqo P$ whose underlying equivalence is $\sigma$. 3. The sorting map of $P$ is braid-isomorphic to the sorting map of $Q$ if and only if $P$ and $Q$ are order-isomorphic (i.e., there exists an order isomorphism $P \simeqo Q$). 4. For every map $R : X \times X \to X \times X$ such that for all $x, y \in X$, either $R(x, y) = (x, y)$ or $R(x, y) = (y, x)$: $R$ satisfies the braid relation and is idempotent ($R \circ R = R$) if and only if there exists a unique partial order structure $o$ on $X$ such that $R$ is the sorting map on $X$ determined by $o$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem compiles four main results into a master classification of poset sorting maps. The proof packages the four individual theorems—idempotence and the braid relation, characterization of the automorphism group, classification of braid isomorphisms via order isomorphisms, and the one-to-one correspondence between partial orders and idempotent braid swap maps—into a single conjunction.

  1. The four parts of the classification theorem hold for partially ordered sets P, Q and the set X.

    The goal is a conjunction of four claims. The proof constructs the conjunction directly by providing the proof of each component: (1) `poset_sorting_map_idempotent_braid` establishes that the sorting map R_P is idempotent and satisfies the braid equation; (2) `braid_aut_poset_sorting_map` characterizes the permutations commuting with R_P as the order automorphisms of P; (3) `poset_sorting_map_braid_iso_iff` shows that R_P and R_Q are braid isomorphic if and only if P and Q are order isomorphic; and (4) `swap_idempotent_braid_iff_poset_sorting_map`, applied to an arbitrary swap map R, shows that R is an idempotent braid solution if and only if it is the sorting map of a uniquely determined partial order on X.

    lines 8–9

    uses poset_sorting_map_idempotent_braid, braid_aut_poset_sorting_map, poset_sorting_map_braid_iso_iff, swap_idempotent_braid_iff_poset_sorting_map

      exact ⟨poset_sorting_map_idempotent_braid P, braid_aut_poset_sorting_map P,
        poset_sorting_map_braid_iso_iff P Q, fun R hR => swap_idempotent_braid_iff_poset_sorting_map R hR⟩
poset_sorting_map_idempotent_braid
The sorting map associated with a partially ordered set satisfies the braid relation and is idempotent.
braid_aut_poset_sorting_map
A permutation of a poset commutes with its sorting map if and only if it is an order automorphism.
poset_sorting_map_braid_iso_iff
The sorting maps of two posets are braid isomorphic if and only if the posets are order isomorphic.
swap_idempotent_braid_iff_poset_sorting_map
For any map that either preserves or transposes each pair of elements, it is an idempotent solution to the braid equation if and only if it equals the sorting map of a unique partial order.

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_classification (P Q X : Type*) [PartialOrder P] [PartialOrder Q] :    (is_braid_solution (poset_sorting_map P) ∧        poset_sorting_map P ∘ poset_sorting_map P = poset_sorting_map P) ∧      (∀ σ : Equiv.Perm P, σ ∈ braid_aut (poset_sorting_map P) ↔ ∃ f : P ≃o P, f.toEquiv = σ) ∧      (is_braid_iso (poset_sorting_map P) (poset_sorting_map Q) ↔ Nonempty (P ≃o Q)) ∧      (∀ R : X × X → X × X, (∀ x y : X, R (x, y) = (x, y) ∨ R (x, y) = (y, x)) →        ((is_braid_solution R ∧ R ∘ R = R) ↔ ∃! o : PartialOrder X, R = @poset_sorting_map X o)) := by  exact ⟨poset_sorting_map_idempotent_braid P, braid_aut_poset_sorting_map P,    poset_sorting_map_braid_iso_iff P Q, fun R hR => swap_idempotent_braid_iff_poset_sorting_map R hR⟩
See it in the graphDiscuss this resultChallenge it