AFTD Auto-Formalizing Theoretical Domains

swap_idempotent_braid_iff_poset_sorting_map

theoremverified

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.

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

    lines 1–4

    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
  2. 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).

    lines 9–11

    uses congrFun

      constructor
      · rintro ⟨hb, hi⟩
        have idem : ∀ p, R (R p) = R p := fun p => congrFun hi p
  3. 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.

    lines 12–16

    uses Prod.ext_iff.1

        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
  4. 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).

    lines 17–31

    uses Function.comp_apply, Prod.ext_iff.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
  5. 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.

    lines 32–57

    uses Or.inl, Or.inr

        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) }, ?_, ?_⟩
  6. 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.

    lines 58–66

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

    lines 67–81

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

    lines 82–83

    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.

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

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