poset_edge_braid_iso_of_order_iso
If two partially ordered sets P and Q with decidable equality are order isomorphic, then their associated poset braid solutions poset_edge_braid_map are isomorphic.
Statement
theorem poset_edge_braid_iso_of_order_iso {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 types P and Q equipped with partial orders and decidable equality, and any order isomorphism e : P ≃o Q, the map poset_edge_braid_map on P is braid-isomorphic (in the sense of is_braid_iso) to the map poset_edge_braid_map on Q.
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 shows that an order isomorphism e : P ≃o Q induces an isomorphism between the associated poset braid solutions. An equivalence between the state spaces is constructed by mapping edges (comparable pairs) via (e, e) and vertices via e × id. Verifying that this equivalence intertwines the braid maps reduces by extensionality to four cases on the input pair: the edge-edge and vertex-vertex cases are trivial identities, while the mixed cases swap the components and update the vertex. Since e is injective, the conditions triggering vertex updates are preserved, so both sides agree across all cases.
An order isomorphism induces an equivalence between the sets of comparable pairs and an equivalence between the braid state spaces.
Because an order isomorphism e : P ≃o Q preserves and reflects the partial order (x ≤ y ↔ e x ≤ e y), its product map restricts to a bijection between the sets of comparable pairs {p : P × P // p.1 ≤ p.2} ≃ {q : Q × Q // q.1 ≤ q.2} via Equiv.subtypeEquiv and Equiv.prodCongr. Taking the disjoint sum with the vertex equivalence e × id on P × ZMod 2 yields the full state space equivalence poset_edge_braid_iso_of_order_iso_equiv e.
uses
Equiv.subtypeEquiv,Equiv.prodCongr,Equiv.sumCongr,Equiv.refl,poset_edge_braid_iso_of_order_iso_edge_equivdef poset_edge_braid_iso_of_order_iso_edge_equiv {P Q : Type*} [PartialOrder P] [PartialOrder Q] (e : P ≃o Q) : {p : P × P // p.1 ≤ p.2} ≃ {q : Q × Q // q.1 ≤ q.2} := Equiv.subtypeEquiv (Equiv.prodCongr e.toEquiv e.toEquiv) (fun ⟨x, y⟩ => by dsimp; exact (e.le_iff_le : e x ≤ e y ↔ x ≤ y).symm) def poset_edge_braid_iso_of_order_iso_equiv {P Q : Type*} [PartialOrder P] [PartialOrder Q] (e : P ≃o Q) : ({p : P × P // p.1 ≤ p.2} ⊕ (P × ZMod 2)) ≃ ({p : Q × Q // p.1 ≤ p.2} ⊕ (Q × ZMod 2)) := Equiv.sumCongr (poset_edge_braid_iso_of_order_iso_edge_equiv e) (Equiv.prodCongr e.toEquiv (Equiv.refl (ZMod 2)))
The state space equivalence witnesses the braid isomorphism, reducing the claim to checking equality on all four combinations of inputs.
We provide the constructed equivalence poset_edge_braid_iso_of_order_iso_equiv e as the witness for is_braid_iso. By function extensionality, it suffices to show that the braid maps commute when evaluated on an arbitrary pair (a, b). Since each element is either an edge (Sum.inl) or a vertex (Sum.inr), the problem splits into four cases.
uses
poset_edge_braid_iso_of_order_iso_equiv/-- An order isomorphism between posets P and Q induces an isomorphism between their bipartite braid solutions. -/ theorem poset_edge_braid_iso_of_order_iso {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 use poset_edge_braid_iso_of_order_iso_equiv e funext ⟨a, b⟩ rcases a with l | ⟨y, ε⟩ <;> rcases b with l' | ⟨y', ε'⟩
The braid maps commute when both inputs are edges.
When both inputs are edges (l, l'), the braid map acts as the identity on both posets. Both sides evaluate definitionally to (E(l), E(l')), closing the goal by reflexivity.
· rflThe braid maps commute when the first input is an edge and the second is a vertex. automation
For an edge l and a vertex (y', ε'), both braid maps swap the two elements and update the vertex according to whether it equals (l.1, 0) or (l.2, 1). Simplifying with the definitions matches the edge components directly. For the vertex update, because e is injective, (e y', ε') matches an endpoint of e(l) if and only if (y', ε') matches the corresponding endpoint of l (lemmas h1 and h2 via Prod.ext_iff). Splitting into cases on these conditions (split_ifs) leaves branches that either trivially match or have contradictory hypotheses, which aesop discharges automatically.
uses
poset_edge_braid_iso_of_order_iso_equiv,Function.comp_apply,Prod.map_apply,poset_edge_braid_map,Equiv.sumCongr_apply,Sum.map_inl,Sum.map_inr,Equiv.prodCongr_apply,Equiv.refl_apply,OrderIso.coe_toEquiv,Prod.ext_iff· simp only [poset_edge_braid_iso_of_order_iso_equiv, Function.comp_apply, Prod.map_apply, poset_edge_braid_map, Equiv.sumCongr_apply, Sum.map_inl, Sum.map_inr, Equiv.prodCongr_apply, Equiv.refl_apply, OrderIso.coe_toEquiv] congr 1 congr 1 change Prod.map (⇑e) id (if (y', ε') = (l.val.1, 0) then (l.val.2, 1) else if (y', ε') = (l.val.2, 1) then (l.val.1, 0) else (y', ε')) = if (e y', ε') = (e l.val.1, 0) then (e l.val.2, 1) else if (e y', ε') = (e l.val.2, 1) then (e l.val.1, 0) else (e y', ε') have h1 : (e y', ε') = (e l.val.1, 0) ↔ (y', ε') = (l.val.1, 0) := by simp [Prod.ext_iff, e.injective.eq_iff] have h2 : (e y', ε') = (e l.val.2, 1) ↔ (y', ε') = (l.val.2, 1) := by simp [Prod.ext_iff, e.injective.eq_iff] split_ifs with ha hb hc <;> aesop
The braid maps commute when the first input is a vertex and the second is an edge. automation
Symmetrically, when the first input is a vertex (y, ε) and the second is an edge l', both maps place the edge in the first component and the updated vertex in the second component. The edge components agree directly, and the injectivity of e ensures that the conditional updates coincide (lemmas h1 and h2 via Prod.ext_iff). Case splitting on the if-then-else conditions followed by automated search (aesop) proves that all branches agree.
uses
poset_edge_braid_iso_of_order_iso_equiv,Function.comp_apply,Prod.map_apply,poset_edge_braid_map,Equiv.sumCongr_apply,Sum.map_inl,Sum.map_inr,Equiv.prodCongr_apply,Equiv.refl_apply,OrderIso.coe_toEquiv,Prod.ext_iff· simp only [poset_edge_braid_iso_of_order_iso_equiv, Function.comp_apply, Prod.map_apply, poset_edge_braid_map, Equiv.sumCongr_apply, Sum.map_inl, Sum.map_inr, Equiv.prodCongr_apply, Equiv.refl_apply, OrderIso.coe_toEquiv] congr 1 congr 1 change Prod.map (⇑e) id (if (y, ε) = (l'.val.1, 0) then (l'.val.2, 1) else if (y, ε) = (l'.val.2, 1) then (l'.val.1, 0) else (y, ε)) = if (e y, ε) = (e l'.val.1, 0) then (e l'.val.2, 1) else if (e y, ε) = (e l'.val.2, 1) then (e l'.val.1, 0) else (e y, ε) have h1 : (e y, ε) = (e l'.val.1, 0) ↔ (y, ε) = (l'.val.1, 0) := by simp [Prod.ext_iff, e.injective.eq_iff] have h2 : (e y, ε) = (e l'.val.2, 1) ↔ (y, ε) = (l'.val.2, 1) := by simp [Prod.ext_iff, e.injective.eq_iff] split_ifs with ha hb hc <;> aesop
The braid maps commute when both inputs are vertices.
When both inputs are vertices, the braid map acts as the identity on both sides, so both expressions evaluate definitionally to the mapped pair of vertices, closing the case by reflexivity.
· rfl
Equiv.subtypeEquiv- An equivalence between types restricts to an equivalence between subtypes whose predicates correspond under the equivalence.
Equiv.prodCongr- Given equivalences between types, their Cartesian product forms an equivalence between the product types.
Equiv.sumCongr- Given equivalences between types, their disjoint sum forms an equivalence between the sum types.
Equiv.refl- The identity equivalence on any type.
poset_edge_braid_iso_of_order_iso_edge_equiv- An order isomorphism between two posets induces an equivalence between their sets of comparable pairs (edges).
poset_edge_braid_iso_of_order_iso_equiv- An order isomorphism between posets induces an equivalence between their braid state spaces (edges and labeled vertices).
poset_edge_braid_map- The braid map associated to a poset, which swaps components and conditionally updates vertices matching edge endpoints.
Function.comp_apply- The evaluation of a composite function (f ∘ g)(x) is f(g(x)).
Prod.map_apply- Applying a product map Prod.map f g to a pair (x, y) yields (f(x), g(y)).
Equiv.sumCongr_apply- Evaluating a sum equivalence ea.sumCongr eb on an element coincides with applying the sum map Sum.map ea eb.
Sum.map_inl- The sum map on a left injection Sum.inl x applies the first function and remains in the left summand.
Sum.map_inr- The sum map on a right injection Sum.inr x applies the second function and remains in the right summand.
Equiv.prodCongr_apply- The equivalence of products acts coordinatewise as the product map.
Equiv.refl_apply- The identity equivalence leaves every element unchanged.
OrderIso.coe_toEquiv- The underlying function of an order isomorphism viewed as an equivalence is the order isomorphism itself.
Prod.ext_iff- Two ordered pairs are equal if and only if their first and second components are respectively equal.
- In steps 4 and 5 (lines 18–31 and 32–45), after `split_ifs` branches on whether the vertex matches either endpoint of the edge, `aesop` automatically discharges all 9 generated subgoals: it checks that the equality holds on consistent branches and derives contradictions via the injectivity equivalences $h_1$ and $h_2$ on impossible branches.
- The proof treats the mixed edge-vertex and vertex-edge cases separately (lines 18–31 and 32–45), even though mathematically they are symmetric mirror images.
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.
def poset_edge_braid_iso_of_order_iso_edge_equiv {P Q : Type*} [PartialOrder P] [PartialOrder Q] (e : P ≃o Q) : {p : P × P // p.1 ≤ p.2} ≃ {q : Q × Q // q.1 ≤ q.2} := Equiv.subtypeEquiv (Equiv.prodCongr e.toEquiv e.toEquiv) (fun ⟨x, y⟩ => by dsimp; exact (e.le_iff_le : e x ≤ e y ↔ x ≤ y).symm)def poset_edge_braid_iso_of_order_iso_equiv {P Q : Type*} [PartialOrder P] [PartialOrder Q] (e : P ≃o Q) : ({p : P × P // p.1 ≤ p.2} ⊕ (P × ZMod 2)) ≃ ({p : Q × Q // p.1 ≤ p.2} ⊕ (Q × ZMod 2)) := Equiv.sumCongr (poset_edge_braid_iso_of_order_iso_edge_equiv e) (Equiv.prodCongr e.toEquiv (Equiv.refl (ZMod 2)))/-- An order isomorphism between posets P and Q induces an isomorphism between their bipartite braid solutions. -/theorem poset_edge_braid_iso_of_order_iso {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 use poset_edge_braid_iso_of_order_iso_equiv e funext ⟨a, b⟩ rcases a with l | ⟨y, ε⟩ <;> rcases b with l' | ⟨y', ε'⟩ · rfl · simp only [poset_edge_braid_iso_of_order_iso_equiv, Function.comp_apply, Prod.map_apply, poset_edge_braid_map, Equiv.sumCongr_apply, Sum.map_inl, Sum.map_inr, Equiv.prodCongr_apply, Equiv.refl_apply, OrderIso.coe_toEquiv] congr 1 congr 1 change Prod.map (⇑e) id (if (y', ε') = (l.val.1, 0) then (l.val.2, 1) else if (y', ε') = (l.val.2, 1) then (l.val.1, 0) else (y', ε')) = if (e y', ε') = (e l.val.1, 0) then (e l.val.2, 1) else if (e y', ε') = (e l.val.2, 1) then (e l.val.1, 0) else (e y', ε') have h1 : (e y', ε') = (e l.val.1, 0) ↔ (y', ε') = (l.val.1, 0) := by simp [Prod.ext_iff, e.injective.eq_iff] have h2 : (e y', ε') = (e l.val.2, 1) ↔ (y', ε') = (l.val.2, 1) := by simp [Prod.ext_iff, e.injective.eq_iff] split_ifs with ha hb hc <;> aesop · simp only [poset_edge_braid_iso_of_order_iso_equiv, Function.comp_apply, Prod.map_apply, poset_edge_braid_map, Equiv.sumCongr_apply, Sum.map_inl, Sum.map_inr, Equiv.prodCongr_apply, Equiv.refl_apply, OrderIso.coe_toEquiv] congr 1 congr 1 change Prod.map (⇑e) id (if (y, ε) = (l'.val.1, 0) then (l'.val.2, 1) else if (y, ε) = (l'.val.2, 1) then (l'.val.1, 0) else (y, ε)) = if (e y, ε) = (e l'.val.1, 0) then (e l'.val.2, 1) else if (e y, ε) = (e l'.val.2, 1) then (e l'.val.1, 0) else (e y, ε) have h1 : (e y, ε) = (e l'.val.1, 0) ↔ (y, ε) = (l'.val.1, 0) := by simp [Prod.ext_iff, e.injective.eq_iff] have h2 : (e y, ε) = (e l'.val.2, 1) ↔ (y, ε) = (l'.val.2, 1) := by simp [Prod.ext_iff, e.injective.eq_iff] split_ifs with ha hb hc <;> aesop · rfl