poset_edge_braid_iso_of_order_iso_dual
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.
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.
uses
Equiv.subtypeEquiv,Equiv.prodComm,Equiv.addRight,Equiv.sumCongrclassical 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
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`).
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
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`).
uses
add_right_cancelhave 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
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.
uses
congrArg,Prod.fst,Prod.snd,Prod.ext_iffhave 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]
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.
refine ⟨E, ?_⟩ funext p obtain ⟨a, b⟩ := p rcases a with l | z <;> rcases b with l' | w
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.
uses
Function.comp,Prod.map· simp [Function.comp, Prod.map, poset_edge_braid_map, E]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.
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
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`.
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))
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.
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).
- The tactic `decide` is used to establish basic algebraic identities and inequalities in `ZMod 2` by exhaustive finite evaluation.
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.
/-- 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]