swap_idempotent_braid_iff_poset_sorting_map
If 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 unique partial order on X.
Statement
theorem swap_idempotent_braid_iff_poset_sorting_map {X : Type*} (R : X × X → X × X) (hR : ∀ 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
- 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_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_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…
- 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
To establish the equivalence, the backward direction is immediate because the sorting map of any poset is known to be an idempotent solution to the braid equation. In the forward direction, we define a strict order by declaring a < b whenever b ≠ a and R(b, a) = (a, b), with reflexive closure a ≤ b. Asymmetry of this relation follows from the idempotency of R, and transitivity is established by evaluating the braid equation on triples (c, b, a). We then show that R coincides with the sorting map of this partial order, and uniqueness follows because any partial order yielding R must have its strict order completely determined by the swapping action of R on distinct elements.
The poset sorting map swaps the components of a pair p to (p.2, p.1) whenever p.2 < p.1, and leaves p unchanged otherwise.
The private helper lemma psm_apply_sw unfolds the definition of poset_sorting_map on a pair p; this equality holds definitionally by rfl.
open Classical in private lemma psm_apply_sw {P : Type*} [PartialOrder P] (p : P × P) : poset_sorting_map P p = if p.2 < p.1 then (p.2, p.1) else p := by rfl
In the forward direction, R satisfies the braid equation and is idempotent, so R(R(p)) = R(p) for every pair p.
We split the bi-implication into two directions. In the forward direction, we assume R is a braid solution and R ∘ R = R. Evaluating the composition at an arbitrary pair p using congrFun yields pointwise idempotency R(R(p)) = R(p).
uses
congrFunconstructor · rintro ⟨hb, hi⟩ have idem : ∀ p, R (R p) = R p := fun p => congrFun hi p
The swapping relation is asymmetric: it is impossible to have both b ≠ a with R(b, a) = (a, b) and a ≠ b with R(a, b) = (b, a).
Assuming both conditions hold, pointwise idempotency gives R(R(b, a)) = R(b, a). Rewriting both occurrences using R(b, a) = (a, b) and R(a, b) = (b, a) yields (b, a) = (a, b). Equating the first components via Prod.ext_iff.1 gives b = a, which contradicts b ≠ a.
uses
Prod.ext_iff.1have asymm : ∀ a b : X, (b ≠ a ∧ R (b, a) = (a, b)) → ¬ (a ≠ b ∧ R (a, b) = (b, a)) := by rintro a b ⟨hne, h1⟩ ⟨-, h2⟩ have := idem (b, a) rw [h1, h2] at this exact hne (Prod.ext_iff.1 this).1
The swapping relation is transitive: if b ≠ a with R(b, a) = (a, b) and c ≠ b with R(c, b) = (b, c), then c ≠ a and R(c, a) = (a, c).
First, c ≠ a because if c = a, the assumptions would contradict asymmetry. To establish R(c, a) = (a, c), we examine the hypothesis that R(c, a) is either (c, a) or (a, c). If R(c, a) = (c, a), idempotence forces R(b, c) = (b, c) and R(a, b) = (a, b). Evaluating the braid equation on the triple (c, b, a) then simplifies using Function.comp_apply to (b, c, a) = (c, a, b). By Prod.ext_iff.1, this forces b = c, contradicting c ≠ b. Thus R(c, a) must equal (a, c).
uses
Function.comp_apply,Prod.ext_iff.1have trans : ∀ a b c : X, (b ≠ a ∧ R (b, a) = (a, b)) → (c ≠ b ∧ R (c, b) = (b, c)) → (c ≠ a ∧ R (c, a) = (a, c)) := by rintro a b c ⟨hba, h1⟩ ⟨hcb, h2⟩ have hca : c ≠ a := by rintro rfl exact asymm _ _ ⟨hba, h1⟩ ⟨hcb, h2⟩ refine ⟨hca, ?_⟩ rcases hR c a with h3 | h3 · exfalso have hbc : R (b, c) = (b, c) := by have := idem (c, b); rwa [h2] at this have hab : R (a, b) = (a, b) := by have := idem (b, a); rwa [h1] at this have := congrFun hb (c, b, a) simp only [Function.comp_apply, h1, h2, h3, hbc, hab] at this exact hcb (Prod.ext_iff.1 this).1.symm · exact h3
The relations a ≤ b ↔ a = b ∨ (b ≠ a ∧ R(b, a) = (a, b)) and a < b ↔ b ≠ a ∧ R(b, a) = (a, b) define a partial order on X.
Reflexivity holds by definition via Or.inl rfl. Transitivity of ≤ follows by considering whether each inequality is an equality or strict, applying transitivity of the strict relation when both are strict. Antisymmetry and the equivalence a < b ↔ a ≤ b ∧ ¬(b ≤ a) follow directly from the definitions and the asymmetry of the strict relation.
uses
Or.inl,Or.inrrefine ⟨{ le := fun a b => a = b ∨ (b ≠ a ∧ R (b, a) = (a, b)) lt := fun a b => b ≠ a ∧ R (b, a) = (a, b) le_refl := fun a => Or.inl rfl le_trans := by rintro a b c (rfl | hab) (rfl | hbc) · exact Or.inl rfl · exact Or.inr hbc · exact Or.inr hab · exact Or.inr (trans a b c hab hbc) lt_iff_le_not_ge := by intro a b constructor · intro h refine ⟨Or.inr h, ?_⟩ rintro (rfl | h') · exact h.1 rfl · exact asymm a b h h' · rintro ⟨rfl | h, h'⟩ · exact absurd (Or.inl rfl) h' · exact h le_antisymm := by rintro a b (rfl | hab) (h | hba) · rfl · rfl · exact h.symm · exact absurd hba (asymm a b hab) }, ?_, ?_⟩
The map R coincides with the poset sorting map for the constructed partial order.
By function extensionality, we compare R(x, y) with the poset sorting map. If y < x, the definition of < ensures R(x, y) = (y, x), matching the sorting map. If ¬(y < x), the sorting map produces (x, y). Since R(x, y) is either (x, y) or (y, x), in the latter case either x = y (giving (y, x) = (x, y)) or x ≠ y (which would mean y < x, a contradiction). Hence R(x, y) = (x, y) in all cases.
· funext ⟨x, y⟩ dsimp only [poset_sorting_map] split_ifs with h · exact h.2 · rcases hR x y with h' | h' · exact h' · by_cases hxy : x = y · subst hxy; exact h' · exact absurd ⟨hxy, h'⟩ h
The partial order on X whose sorting map equals R is unique.
Let o' be any partial order such that R = poset_sorting_map X. By PartialOrder.ext_lt, it suffices to show that strict inequality in o' matches the relation b ≠ a ∧ R(b, a) = (a, b). Rewriting R(b, a) via psm_apply_sw gives if a < b then (a, b) else (b, a). If a < b, if_pos yields R(b, a) = (a, b) with b ≠ a. Conversely, if b ≠ a and R(b, a) = (a, b), assuming ¬(a < b) would make R(b, a) = (b, a) via if_neg, equating (a, b) with (b, a) and forcing a = b via Prod.ext_iff.1, a contradiction.
uses
PartialOrder.ext_lt,psm_apply_sw,if_pos,if_neg,Prod.ext_iff.1· intro o' ho' apply PartialOrder.ext_lt intro a b show a < b ↔ (b ≠ a ∧ R (b, a) = (a, b)) have := congrFun ho' (b, a) rw [psm_apply_sw] at this dsimp only at this constructor · intro h rw [if_pos h] at this exact ⟨h.ne', this⟩ · rintro ⟨hne, h⟩ by_contra hlt rw [if_neg hlt, h] at this exact hne (Prod.ext_iff.1 this).2
Conversely, if R is the sorting map of some partial order, then R is an idempotent solution to the braid equation.
Given a partial order o with R = poset_sorting_map X, the theorem poset_sorting_map_idempotent_braid directly proves that R is an idempotent solution of the braid equation.
uses
poset_sorting_map_idempotent_braid· rintro ⟨o, rfl, -⟩ exact (@poset_sorting_map_idempotent_braid X o)
congrFun- Equal functions applied to the same argument yield equal values: if f = g, then f(a) = g(a).
Prod.ext_iff.1- If two pairs are equal, then their first and second components are equal: (x₁, x₂) = (y₁, y₂) implies x₁ = y₁ and x₂ = y₂.
Function.comp_apply- Definition of function composition: (f ∘ g)(x) = f(g(x)).
Or.inl- Left introduction rule for disjunction: A implies A ∨ B.
Or.inr- Right introduction rule for disjunction: B implies A ∨ B.
PartialOrder.ext_lt- Two partial orders on the same type are identical if their strict order relations (<) agree on all pairs.
psm_apply_sw- For a pair p in a poset, the sorting map evaluates to (p.2, p.1) if p.2 < p.1, and to p otherwise.
if_pos- An if-then-else expression evaluates to the then-branch when the condition is true: if c holds, then (if c then t else e) = t.
if_neg- An if-then-else expression evaluates to the else-branch when the condition is false: if ¬c holds, then (if c then t else e) = e.
poset_sorting_map_idempotent_braid- For any poset, its sorting map satisfies the braid equation and is idempotent.
- The helper lemma psm_apply_sw is a local formulation of the poset sorting map on pairs, used to avoid pattern matching during equational rewrites.
- Transitivity of the strict relation is derived via the braid equation on the triple (c, b, a): assuming transitivity fails leads, via idempotence, to the braid equation equating (b, c, a) and (c, a, b), which contradicts distinctness of the elements.
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.
open Classical inprivate lemma psm_apply_sw {P : Type*} [PartialOrder P] (p : P × P) : poset_sorting_map P p = if p.2 < p.1 then (p.2, p.1) else p := by rfltheorem swap_idempotent_braid_iff_poset_sorting_map {X : Type*} (R : X × X → X × X) (hR : ∀ 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 constructor · rintro ⟨hb, hi⟩ have idem : ∀ p, R (R p) = R p := fun p => congrFun hi p have asymm : ∀ a b : X, (b ≠ a ∧ R (b, a) = (a, b)) → ¬ (a ≠ b ∧ R (a, b) = (b, a)) := by rintro a b ⟨hne, h1⟩ ⟨-, h2⟩ have := idem (b, a) rw [h1, h2] at this exact hne (Prod.ext_iff.1 this).1 have trans : ∀ a b c : X, (b ≠ a ∧ R (b, a) = (a, b)) → (c ≠ b ∧ R (c, b) = (b, c)) → (c ≠ a ∧ R (c, a) = (a, c)) := by rintro a b c ⟨hba, h1⟩ ⟨hcb, h2⟩ have hca : c ≠ a := by rintro rfl exact asymm _ _ ⟨hba, h1⟩ ⟨hcb, h2⟩ refine ⟨hca, ?_⟩ rcases hR c a with h3 | h3 · exfalso have hbc : R (b, c) = (b, c) := by have := idem (c, b); rwa [h2] at this have hab : R (a, b) = (a, b) := by have := idem (b, a); rwa [h1] at this have := congrFun hb (c, b, a) simp only [Function.comp_apply, h1, h2, h3, hbc, hab] at this exact hcb (Prod.ext_iff.1 this).1.symm · exact h3 refine ⟨{ le := fun a b => a = b ∨ (b ≠ a ∧ R (b, a) = (a, b)) lt := fun a b => b ≠ a ∧ R (b, a) = (a, b) le_refl := fun a => Or.inl rfl le_trans := by rintro a b c (rfl | hab) (rfl | hbc) · exact Or.inl rfl · exact Or.inr hbc · exact Or.inr hab · exact Or.inr (trans a b c hab hbc) lt_iff_le_not_ge := by intro a b constructor · intro h refine ⟨Or.inr h, ?_⟩ rintro (rfl | h') · exact h.1 rfl · exact asymm a b h h' · rintro ⟨rfl | h, h'⟩ · exact absurd (Or.inl rfl) h' · exact h le_antisymm := by rintro a b (rfl | hab) (h | hba) · rfl · rfl · exact h.symm · exact absurd hba (asymm a b hab) }, ?_, ?_⟩ · funext ⟨x, y⟩ dsimp only [poset_sorting_map] split_ifs with h · exact h.2 · rcases hR x y with h' | h' · exact h' · by_cases hxy : x = y · subst hxy; exact h' · exact absurd ⟨hxy, h'⟩ h · intro o' ho' apply PartialOrder.ext_lt intro a b show a < b ↔ (b ≠ a ∧ R (b, a) = (a, b)) have := congrFun ho' (b, a) rw [psm_apply_sw] at this dsimp only at this constructor · intro h rw [if_pos h] at this exact ⟨h.ne', this⟩ · rintro ⟨hne, h⟩ by_contra hlt rw [if_neg hlt, h] at this exact hne (Prod.ext_iff.1 this).2 · rintro ⟨o, rfl, -⟩ exact (@poset_sorting_map_idempotent_braid X o)