AFTD Auto-Formalizing Theoretical Domains

poset_edge_braid_map_involutive

theoremverified

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.

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

    lines 5–14

    uses Prod.ext_iff.mp

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

    lines 15–19

        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]
  3. 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`).

    lines 20–21

      rcases p with ⟨l1 | z1, l2 | z2⟩
      · rfl
  4. 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)$.

    lines 22–23

      · dsimp [poset_edge_braid_map]
        rw [ht]
  5. 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)$.

    lines 24–25

      · dsimp [poset_edge_braid_map]
        rw [ht]
  6. 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`).

    line 26

      · rfl
Prod.ext_iff.mp
If two ordered pairs are equal, then their first components are equal and their second components are equal.

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

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