AFTD Auto-Formalizing Theoretical Domains

poset_edge_braid_iso_of_order_iso_dual

theoremverified

If a partially ordered set P is order isomorphic to the dual poset Qᵒᵈ, then their associated poset braid solutions poset_edge_braid_map are isomorphic.

Statement

theorem poset_edge_braid_iso_of_order_iso_dual {P Q : Type*} [PartialOrder P] [PartialOrder Q]
    [DecidableEq P] [DecidableEq Q] (e : P ≃o Qᵒᵈ) :
    is_braid_iso (@poset_edge_braid_map P _ _) (@poset_edge_braid_map Q _ _)
Source
arXiv:2611.15540, after Theorem 3.3
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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 ×…
  • poset_edge_braid_mapFor a partially ordered set P with decidable equality, poset_edge_braid_map is the bipartite braid map on ({p : P × P // p.1 ≤ p.2} ⊕ (P ×…

Read back from the Lean

For any two types $P$ and $Q$ equipped with partial orders and decidable equality, if there exists an order isomorphism $e : P \simeqo Q^{\mathrm{od}}$ between $P$ and the order dual of $Q$, then there is an isomorphism between the braid maps poset_edge_braid_map associated to $P$ and $Q$ (in the sense of is_braid_iso).

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

An order isomorphism e : P ≃o Qᵒᵈ is an anti-isomorphism, reversing the orientation of edges: p₁ ≤ p₂ in P if and only if e(p₂) ≤ e(p₁) in Q. The state space of the associated braid solution is the disjoint union of edges and vertices labeled by ℤ/2ℤ. We construct an isomorphism of braid solutions by mapping each edge (p₁, p₂) to the dual edge (e(p₂), e(p₁)) and shifting the vertex label by 1 in ℤ/2ℤ, (p, b) ↦ (e(p), b + 1), which aligns the edge-vertex transpositions in P and Q. The proof verifies this commutation on vertices and then checks the braid equation by case analysis on whether the two inputs are edges or vertices.

  1. Construct a bijection E between the state spaces of the braid maps for P and Q.

    The state space for a poset's braid map is the disjoint union of its directed edges {p : P × P // p.1 ≤ p.2} and its labeled vertices P × ℤ/2ℤ. Since e is an order isomorphism from P to the dual Qᵒᵈ, we have p₁ ≤ p₂ ↔ e(p₂) ≤ e(p₁). Mapping each edge (p₁, p₂) to (e(p₂), e(p₁)) via Equiv.subtypeEquiv and Equiv.prodComm gives an edge bijection `edgeEquiv`. For vertices, mapping (p, b) to (e(p), b + 1) via Equiv.addRight gives a vertex bijection `pointEquiv`. Finally, Equiv.sumCongr combines these into an equivalence E on the full state space.

    lines 5–15

    uses Equiv.subtypeEquiv, Equiv.prodComm, Equiv.addRight, Equiv.sumCongr

      classical
      let edgeEquiv : {p : P × P // p.1 ≤ p.2} ≃ {q : Q × Q // q.1 ≤ q.2} :=
        Equiv.subtypeEquiv ((e.toEquiv.prodCongr e.toEquiv).trans (Equiv.prodComm Q Q))
          (fun a => by
            show a.1 ≤ a.2 ↔ OrderDual.ofDual (e a.2) ≤ OrderDual.ofDual (e a.1)
            exact (e.le_iff_le (x := a.1) (y := a.2)).symm)
      let pointEquiv : P × ZMod 2 ≃ Q × ZMod 2 :=
        e.toEquiv.prodCongr (Equiv.addRight (1 : ZMod 2))
      let E : ({p : P × P // p.1 ≤ p.2} ⊕ (P × ZMod 2)) ≃
          ({q : Q × Q // q.1 ≤ q.2} ⊕ (Q × ZMod 2)) :=
        Equiv.sumCongr edgeEquiv pointEquiv
  2. Characterize the explicit actions of `edgeEquiv` and `pointEquiv` on elements.

    Unfolding their definitions, `edgeEquiv` sends an edge (p₁, p₂) to (e(p₂), e(p₁)) and `pointEquiv` sends (w₁, w₂) to (e(w₁), w₂ + 1), both holding by definition (`rfl`).

    lines 16–21

      have hedge : ∀ l : {p : P × P // p.1 ≤ p.2},
          (edgeEquiv l : Q × Q) = (OrderDual.ofDual (e l.1.2), OrderDual.ofDual (e l.1.1)) := by
        intro l; rfl
      have hpoint : ∀ w : P × ZMod 2,
          pointEquiv w = (OrderDual.ofDual (e w.1), w.2 + 1) := by
        intro w; rfl
  3. Establish the basic arithmetic properties of addition by 1 in ℤ/2ℤ.

    In ℤ/2ℤ, b + 1 = 0 ↔ b = 1 and b + 1 = 1 ↔ b = 0, both proved using add_right_cancel and decidability, while 1 ≠ 0 and 1 + 1 = 0 are verified by direct finite computation (`decide`).

    lines 22–33

    uses add_right_cancel

      have hz1 : ∀ b : ZMod 2, b + 1 = 0 ↔ b = 1 := by
        intro b; constructor
        · intro h
          have h1 : (b + 1) = (1 + 1 : ZMod 2) := by rw [h]; decide
          exact add_right_cancel h1
        · intro h; rw [h]; decide
      have hz0 : ∀ b : ZMod 2, b + 1 = 1 ↔ b = 0 := by
        intro b; constructor
        · intro h; exact add_right_cancel h
        · intro h; rw [h]; decide
      have h10 : (1 : ZMod 2) ≠ 0 := by decide
      have h11 : (1 : ZMod 2) + 1 = 0 := by decide
  4. The transposition action along an edge commutes with the bijection on labeled vertices.

    For an edge l = (p₁ ≤ p₂) and a vertex w, the braid transposition in P swaps (p₁, 0) with (p₂, 1) and fixes all other vertices. We check that under `pointEquiv`, this matches the transposition in Q for the dual edge (e(p₂), e(p₁)): (p₁, 0) maps to (e(p₁), 1) and (p₂, 1) maps to (e(p₂), 0), precisely interchanging the two swapped vertices in Q. If w is neither endpoint, injectivity of e and the arithmetic of ℤ/2ℤ ensure that `pointEquiv w` is neither endpoint of the dual edge in Q, so both sides leave it unchanged.

    lines 34–65

    uses congrArg, Prod.fst, Prod.snd, Prod.ext_iff

      have hcomm : ∀ (l : {p : P × P // p.1 ≤ p.2}) (w : P × ZMod 2),
          (OrderDual.ofDual (e (if w = ((l : P × P).1, 0) then ((l : P × P).2, 1)
              else if w = ((l : P × P).2, 1) then ((l : P × P).1, 0) else w).1),
            (if w = ((l : P × P).1, 0) then ((l : P × P).2, 1)
              else if w = ((l : P × P).2, 1) then ((l : P × P).1, 0) else w).2 + 1) =
          (if (OrderDual.ofDual (e w.1), w.2 + 1) = (OrderDual.ofDual (e (l : P × P).2), 0) then
             (OrderDual.ofDual (e (l : P × P).1), 1)
           else if (OrderDual.ofDual (e w.1), w.2 + 1) = (OrderDual.ofDual (e (l : P × P).1), 1) then
             (OrderDual.ofDual (e (l : P × P).2), 0)
           else (OrderDual.ofDual (e w.1), w.2 + 1)) := by
        intro l w
        by_cases h1 : w = ((l : P × P).1, 0)
        · subst h1
          simp [h10, h11]
        · by_cases h2 : w = ((l : P × P).2, 1)
          · subst h2
            simp [h1, h11]
          · have hc1 : ¬ ((OrderDual.ofDual (e w.1), w.2 + 1) = (OrderDual.ofDual (e (l : P × P).2), 0)) := by
              intro h
              have h1' : OrderDual.ofDual (e w.1) = OrderDual.ofDual (e (l : P × P).2) := congrArg Prod.fst h
              have h2' : w.2 + 1 = 0 := congrArg Prod.snd h
              have hwe : w.1 = (l : P × P).2 := e.injective (by simpa using h1')
              have hw2 : w.2 = 1 := (hz1 w.2).mp h2'
              exact h2 (by rw [Prod.ext_iff]; exact ⟨hwe, hw2⟩)
            have hc0 : ¬ ((OrderDual.ofDual (e w.1), w.2 + 1) = (OrderDual.ofDual (e (l : P × P).1), 1)) := by
              intro h
              have h1' : OrderDual.ofDual (e w.1) = OrderDual.ofDual (e (l : P × P).1) := congrArg Prod.fst h
              have h2' : w.2 + 1 = 1 := congrArg Prod.snd h
              have hwe : w.1 = (l : P × P).1 := e.injective (by simpa using h1')
              have hw2 : w.2 = 0 := (hz0 w.2).mp h2'
              exact h1 (by rw [Prod.ext_iff]; exact ⟨hwe, hw2⟩)
            simp [h1, h2, hc1, hc0]
  5. Provide E as the isomorphism witness and decompose the goal into four cases.

    To establish `is_braid_iso`, we provide E as the witness. By function extensionality, we evaluate both sides on an arbitrary pair of state-space elements (a, b). Decomposing a and b as either edges (`inl`) or vertices (`inr`) yields four cases: edge-edge, edge-vertex, vertex-edge, and vertex-vertex.

    lines 66–69

      refine ⟨E, ?_⟩
      funext p
      obtain ⟨a, b⟩ := p
      rcases a with l | z <;> rcases b with l' | w
  6. The braid isomorphism condition holds on a pair of edges.

    When both inputs are edges, the braid map acts as the identity on both sides, so the equality reduces to definitions by simplification.

    line 70

    uses Function.comp, Prod.map

      · simp [Function.comp, Prod.map, poset_edge_braid_map, E]
  7. The braid isomorphism condition holds on an edge-vertex pair.

    The braid map swaps the edge and vertex and applies the transposition `t` to the vertex. Unfolding the definitions and applying `hcomm` together with componentwise equality `Prod.ext` verifies that both sides agree.

    lines 71–74

    uses Function.comp_apply, Prod.map, Equiv.sumCongr_apply, Sum.map_inl, Sum.map_inr, Prod.ext, congrArg, Sum.inr

      · simp only [Function.comp_apply, Prod.map, poset_edge_braid_map, E, Equiv.sumCongr_apply,
          Sum.map_inl, Sum.map_inr]
        simp only [hpoint, hedge]
        exact Prod.ext (congrArg Sum.inr (hcomm l w)) rfl
  8. The braid isomorphism condition holds on a vertex-edge pair.

    Symmetrically to the edge-vertex case, the braid map swaps the components and applies `t` to the vertex, which matches by `hcomm` and `Prod.ext`.

    lines 75–78

    uses Function.comp_apply, Prod.map, Equiv.sumCongr_apply, Sum.map_inl, Sum.map_inr, Prod.ext, congrArg, Sum.inr

      · simp only [Function.comp_apply, Prod.map, poset_edge_braid_map, E, Equiv.sumCongr_apply,
          Sum.map_inl, Sum.map_inr]
        simp only [hpoint, hedge]
        exact Prod.ext rfl (congrArg Sum.inr (hcomm l' z))
  9. The braid isomorphism condition holds on a pair of vertices.

    When both inputs are vertices, the braid map acts as the identity on both sides, so the equality holds by simplification.

    line 79

    uses Function.comp, Prod.map

      · simp [Function.comp, Prod.map, poset_edge_braid_map, E]
add_right_cancel
In an additive structure with right cancellation, a + b = c + b implies a = c.
congrArg
Functions respect equality: if a₁ = a₂, then f(a₁) = f(a₂).
Equiv.addRight
The equivalence (permutation) of an additive group given by right addition: x ↦ x + g.
Equiv.prodComm
The canonical equivalence swapping the coordinates of a product: α × β ≃ β × α.
Equiv.subtypeEquiv
Given an equivalence e : α ≃ β and predicates p, q such that p(a) ↔ q(e(a)), produces an equivalence between the subtypes {a // p(a)} and {b // q(b)}.
Equiv.sumCongr
Combines equivalences α₁ ≃ α₂ and β₁ ≃ β₂ into an equivalence between disjoint unions α₁ ⊕ β₁ ≃ α₂ ⊕ β₂.
Equiv.sumCongr_apply
Evaluating the direct sum equivalence `ea.sumCongr eb` on an element applies `ea` to left injections and `eb` to right injections.
Function.comp
Function composition: (f ∘ g)(x) = f(g(x)).
Function.comp_apply
The evaluation of a composite function at an argument: (f ∘ g)(x) = f(g(x)).
Prod.fst
The first coordinate projection of an ordered pair: (x, y) ↦ x.
Prod.snd
The second coordinate projection of an ordered pair: (x, y) ↦ y.
Prod.ext
Two pairs are equal if their corresponding components are equal: x.1 = y.1 and x.2 = y.2 imply x = y.
Prod.ext_iff
Two pairs are equal if and only if both coordinates are equal: x = y ↔ x.1 = y.1 ∧ x.2 = y.2.
Prod.map
The product of two maps: (f × g)(x, y) = (f(x), g(y)).
Sum.inr
The canonical right inclusion map into a direct sum: x ↦ Sum.inr x.
Sum.map_inl
Applying a direct sum map Sum.map f g to a left injection yields Sum.inl (f x).
Sum.map_inr
Applying a direct sum map Sum.map f g to a right injection yields Sum.inr (g 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

/-- An anti-isomorphism between posets P and Q induces an isomorphism between their bipartite braid solutions. -/theorem poset_edge_braid_iso_of_order_iso_dual {P Q : Type*} [PartialOrder P] [PartialOrder Q]    [DecidableEq P] [DecidableEq Q] (e : P ≃o Qᵒᵈ) :    is_braid_iso (@poset_edge_braid_map P _ _) (@poset_edge_braid_map Q _ _) := by  classical  let edgeEquiv : {p : P × P // p.1 ≤ p.2} ≃ {q : Q × Q // q.1 ≤ q.2} :=    Equiv.subtypeEquiv ((e.toEquiv.prodCongr e.toEquiv).trans (Equiv.prodComm Q Q))      (fun a => by        show a.1 ≤ a.2 ↔ OrderDual.ofDual (e a.2) ≤ OrderDual.ofDual (e a.1)        exact (e.le_iff_le (x := a.1) (y := a.2)).symm)  let pointEquiv : P × ZMod 2 ≃ Q × ZMod 2 :=    e.toEquiv.prodCongr (Equiv.addRight (1 : ZMod 2))  let E : ({p : P × P // p.1 ≤ p.2} ⊕ (P × ZMod 2)) ≃      ({q : Q × Q // q.1 ≤ q.2} ⊕ (Q × ZMod 2)) :=    Equiv.sumCongr edgeEquiv pointEquiv  have hedge : ∀ l : {p : P × P // p.1 ≤ p.2},      (edgeEquiv l : Q × Q) = (OrderDual.ofDual (e l.1.2), OrderDual.ofDual (e l.1.1)) := by    intro l; rfl  have hpoint : ∀ w : P × ZMod 2,      pointEquiv w = (OrderDual.ofDual (e w.1), w.2 + 1) := by    intro w; rfl  have hz1 : ∀ b : ZMod 2, b + 1 = 0 ↔ b = 1 := by    intro b; constructor    · intro h      have h1 : (b + 1) = (1 + 1 : ZMod 2) := by rw [h]; decide      exact add_right_cancel h1    · intro h; rw [h]; decide  have hz0 : ∀ b : ZMod 2, b + 1 = 1 ↔ b = 0 := by    intro b; constructor    · intro h; exact add_right_cancel h    · intro h; rw [h]; decide  have h10 : (1 : ZMod 2) ≠ 0 := by decide  have h11 : (1 : ZMod 2) + 1 = 0 := by decide  have hcomm : ∀ (l : {p : P × P // p.1 ≤ p.2}) (w : P × ZMod 2),      (OrderDual.ofDual (e (if w = ((l : P × P).1, 0) then ((l : P × P).2, 1)          else if w = ((l : P × P).2, 1) then ((l : P × P).1, 0) else w).1),        (if w = ((l : P × P).1, 0) then ((l : P × P).2, 1)          else if w = ((l : P × P).2, 1) then ((l : P × P).1, 0) else w).2 + 1) =      (if (OrderDual.ofDual (e w.1), w.2 + 1) = (OrderDual.ofDual (e (l : P × P).2), 0) then         (OrderDual.ofDual (e (l : P × P).1), 1)       else if (OrderDual.ofDual (e w.1), w.2 + 1) = (OrderDual.ofDual (e (l : P × P).1), 1) then         (OrderDual.ofDual (e (l : P × P).2), 0)       else (OrderDual.ofDual (e w.1), w.2 + 1)) := by    intro l w    by_cases h1 : w = ((l : P × P).1, 0)    · subst h1      simp [h10, h11]    · by_cases h2 : w = ((l : P × P).2, 1)      · subst h2        simp [h1, h11]      · have hc1 : ¬ ((OrderDual.ofDual (e w.1), w.2 + 1) = (OrderDual.ofDual (e (l : P × P).2), 0)) := by          intro h          have h1' : OrderDual.ofDual (e w.1) = OrderDual.ofDual (e (l : P × P).2) := congrArg Prod.fst h          have h2' : w.2 + 1 = 0 := congrArg Prod.snd h          have hwe : w.1 = (l : P × P).2 := e.injective (by simpa using h1')          have hw2 : w.2 = 1 := (hz1 w.2).mp h2'          exact h2 (by rw [Prod.ext_iff]; exact ⟨hwe, hw2⟩)        have hc0 : ¬ ((OrderDual.ofDual (e w.1), w.2 + 1) = (OrderDual.ofDual (e (l : P × P).1), 1)) := by          intro h          have h1' : OrderDual.ofDual (e w.1) = OrderDual.ofDual (e (l : P × P).1) := congrArg Prod.fst h          have h2' : w.2 + 1 = 1 := congrArg Prod.snd h          have hwe : w.1 = (l : P × P).1 := e.injective (by simpa using h1')          have hw2 : w.2 = 0 := (hz0 w.2).mp h2'          exact h1 (by rw [Prod.ext_iff]; exact ⟨hwe, hw2⟩)        simp [h1, h2, hc1, hc0]  refine ⟨E, ?_⟩  funext p  obtain ⟨a, b⟩ := p  rcases a with l | z <;> rcases b with l' | w  · simp [Function.comp, Prod.map, poset_edge_braid_map, E]  · simp only [Function.comp_apply, Prod.map, poset_edge_braid_map, E, Equiv.sumCongr_apply,      Sum.map_inl, Sum.map_inr]    simp only [hpoint, hedge]    exact Prod.ext (congrArg Sum.inr (hcomm l w)) rfl  · simp only [Function.comp_apply, Prod.map, poset_edge_braid_map, E, Equiv.sumCongr_apply,      Sum.map_inl, Sum.map_inr]    simp only [hpoint, hedge]    exact Prod.ext rfl (congrArg Sum.inr (hcomm l' z))  · simp [Function.comp, Prod.map, poset_edge_braid_map, E]
See it in the graphDiscuss this resultChallenge it