poset_edge_braid_map_involutive
For any partially ordered set P with decidable equality, the map poset_edge_braid_map is an involution on pairs: poset_edge_braid_map (poset_edge_braid_map p) = p.
Statement
theorem poset_edge_braid_map_involutive {P : Type*} [PartialOrder P] [DecidableEq P] (p : ({p : P × P // p.1 ≤ p.2} ⊕ (P × ZMod 2)) × ({p : P × P // p.1 ≤ p.2} ⊕ (P × ZMod 2))) : poset_edge_braid_map (poset_edge_braid_map p) = p
- Source
- arXiv:2611.15540, Section 3
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 type P equipped with a partial order and decidable equality, and for every element p of (E ⊕ (P × ZMod 2)) × (E ⊕ (P × ZMod 2)) (where E = {p : P × P // p.1 ≤ p.2} is the type of comparable pairs in P), applying poset_edge_braid_map twice to p equals p (i.e., poset_edge_braid_map is an involution).
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 map `poset_edge_braid_map` is shown to be an involution by first proving an auxiliary lemma: for any edge $l = (l_1 \le l_2)$, the operation $t(l, \cdot)$ that transposes $(l_1, 0)$ and $(l_2, 1)$ while fixing all other elements of $P \times \mathbb{Z}/2\mathbb{Z}$ is an involution. This transposition property holds because the two swapped points have distinct second components ($0 \ne 1$ in $\mathbb{Z}/2\mathbb{Z}$), so applying $t(l, \cdot)$ twice is always the identity. Finally, case analysis on the pair $p \in (L \oplus Z) \times (L \oplus Z)$ shows that the bipartite braid map either acts as the identity (when both components are of the same type) or swaps the components while applying $t(l, \cdot)$ (when components are of mixed types), both of which return the original pair after two applications.
For any edge $l = (l_1 \le l_2)$, the points $(l_2, 1)$ and $(l_1, 0)$ in $P \times \mathbb{Z}/2\mathbb{Z}$ are distinct.
To prepare for showing that the swap operation $t(l, \cdot)$ is an involution, we prove the sub-lemma `hne` stating that the two points being transposed are distinct. Assuming for contradiction that $(l_2, 1) = (l_1, 0)$, projecting onto the second coordinate via `Prod.ext_iff.mp` gives $1 = 0$ in $\mathbb{Z}/2\mathbb{Z}$, which is refuted by finite decidable equality (`decide`).
uses
Prod.ext_iff.mphave ht (l : {p : P × P // p.1 ≤ p.2}) (z : P × ZMod 2) : (if (if z = (l.val.1, 0) then (l.val.2, 1) else if z = (l.val.2, 1) then (l.val.1, 0) else z) = (l.val.1, 0) then (l.val.2, 1) else if (if z = (l.val.1, 0) then (l.val.2, 1) else if z = (l.val.2, 1) then (l.val.1, 0) else z) = (l.val.2, 1) then (l.val.1, 0) else if z = (l.val.1, 0) then (l.val.2, 1) else if z = (l.val.2, 1) then (l.val.1, 0) else z) = z := by have hne : (l.val.2, (1 : ZMod 2)) ≠ (l.val.1, (0 : ZMod 2)) := by intro h have : (1 : ZMod 2) = 0 := Prod.ext_iff.mp h |>.2 revert this; decide
For any edge $l$ and any $z \in P \times \mathbb{Z}/2\mathbb{Z}$, the conditional swap operation satisfies $t(l, t(l, z)) = z$.
We complete the helper lemma `ht` by case analysis on $z$. If $z = (l_1, 0)$, the first application produces $(l_2, 1)$, and because $(l_2, 1) \neq (l_1, 0)$ by `hne`, the second application maps it back to $(l_1, 0)$. If $z = (l_2, 1)$, it maps to $(l_1, 0)$ and then back to $(l_2, 1)$. If $z$ is neither point, both applications leave $z$ unchanged. In each branch, simplification confirms that $t(l, t(l, z)) = z$.
by_cases h1 : z = (l.val.1, 0) · subst h1; simp [hne] · by_cases h2 : z = (l.val.2, 1) · subst h2; simp · simp [h1, h2]
The map is an involution when both components of $p$ are edges.
We decompose the input pair $p \in (L \oplus Z) \times (L \oplus Z)$ into four cases according to the sum injections. When both components are edges $(l_1, l_2)$, `poset_edge_braid_map` acts as the identity on each application, so applying it twice returns $(l_1, l_2)$ definitionally (`rfl`).
rcases p with ⟨l1 | z1, l2 | z2⟩ · rfl
The map is an involution when the first component is an edge and the second is a vertex-bit pair.
When $p = (l_1, z_2)$, unfolding the definition shows that the first application maps it to $(t(l_1, z_2), l_1)$, and the second maps this to $(l_1, t(l_1, t(l_1, z_2)))$. Rewriting with the helper lemma `ht` reduces the second coordinate to $z_2$, recovering $(l_1, z_2)$.
· dsimp [poset_edge_braid_map] rw [ht]
The map is an involution when the first component is a vertex-bit pair and the second is an edge.
Symmetrically, when $p = (z_1, l_2)$, the first application yields $(l_2, t(l_2, z_1))$, and the second application yields $(t(l_2, t(l_2, z_1)), l_2)$. Rewriting with `ht` restores the first coordinate to $z_1$, recovering $(z_1, l_2)$.
· dsimp [poset_edge_braid_map] rw [ht]
The map is an involution when both components are vertex-bit pairs.
When both components are vertex-bit pairs $(z_1, z_2)$, `poset_edge_braid_map` acts as the identity on each application, so applying it twice returns $(z_1, z_2)$ definitionally (`rfl`).
· rfl
Prod.ext_iff.mp- If two ordered pairs are equal, then their first components are equal and their second components are equal.
- Because the local transposition function `t` is defined with a `let` binding inside `poset_edge_braid_map`, the helper lemma `ht` (lines 5–10) states its involutive property by writing out the nested `if-then-else` expressions explicitly rather than referencing `t` by name.
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.
/-- The poset bipartite braid map E_P is an involution. -/theorem poset_edge_braid_map_involutive {P : Type*} [PartialOrder P] [DecidableEq P] (p : ({p : P × P // p.1 ≤ p.2} ⊕ (P × ZMod 2)) × ({p : P × P // p.1 ≤ p.2} ⊕ (P × ZMod 2))) : poset_edge_braid_map (poset_edge_braid_map p) = p := by have ht (l : {p : P × P // p.1 ≤ p.2}) (z : P × ZMod 2) : (if (if z = (l.val.1, 0) then (l.val.2, 1) else if z = (l.val.2, 1) then (l.val.1, 0) else z) = (l.val.1, 0) then (l.val.2, 1) else if (if z = (l.val.1, 0) then (l.val.2, 1) else if z = (l.val.2, 1) then (l.val.1, 0) else z) = (l.val.2, 1) then (l.val.1, 0) else if z = (l.val.1, 0) then (l.val.2, 1) else if z = (l.val.2, 1) then (l.val.1, 0) else z) = z := by have hne : (l.val.2, (1 : ZMod 2)) ≠ (l.val.1, (0 : ZMod 2)) := by intro h have : (1 : ZMod 2) = 0 := Prod.ext_iff.mp h |>.2 revert this; decide by_cases h1 : z = (l.val.1, 0) · subst h1; simp [hne] · by_cases h2 : z = (l.val.2, 1) · subst h2; simp · simp [h1, h2] rcases p with ⟨l1 | z1, l2 | z2⟩ · rfl · dsimp [poset_edge_braid_map] rw [ht] · dsimp [poset_edge_braid_map] rw [ht] · rfl