poset_sorting_map_intertwine_iff
An equivalence e : P ≃ Q between partially ordered sets intertwines R_P and R_Q, (e×e)∘R_P = R_Q∘(e×e), iff e preserves and reflects the strict order.
Statement
theorem poset_sorting_map_intertwine_iff {P Q : Type*} [PartialOrder P] [PartialOrder Q] (e : P ≃ Q) : Prod.map e e ∘ poset_sorting_map P = poset_sorting_map Q ∘ Prod.map e e ↔ ∀ x y : P, e y < e x ↔ y < x
- Source
- Step of arXiv:2611.15540, Theorem A (Theorem 2.1 and Corollary 2.2)
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- poset_sorting_mapFor a partially ordered set P, the map R_P on P × P swaps (x, y) to (y, x) if y < x and leaves (x, y) fixed otherwise.
- Used by 2
- braid_aut_poset_sorting_mapA permutation σ of a partially ordered set P lies in Aut(P,R_P) iff σ is (the underlying permutation of) an order automorphism of P.
- poset_sorting_map_braid_iso_iffFor partially ordered sets P and Q, the solutions (P,R_P) and (Q,R_Q) are isomorphic iff P and Q are order isomorphic.
The proof, explained
The theorem is proven in two directions. For the forward direction, assuming intertwining, we evaluate the functions at an arbitrary pair (x, y): if x = y both sides are false by irreflexivity; if x ≠ y, injectivity of e forces the sorting conditions y < x and e y < e x to agree, because a mismatch would equate (e y, e x) and (e x, e y), contradicting e x ≠ e y. For the reverse direction, assuming e preserves and reflects the strict order, function extensionality reduces the claim to pairs (x, y), where case-splitting on y < x matches the sorting behavior on both sides.
The sorting map poset_sorting_map P on a pair p evaluates by definition to (p.2, p.1) if p.2 < p.1, and to p otherwise.
The private lemma psm_apply_it records the evaluation rule for poset_sorting_map on a pair, which holds by definition (rfl).
rflIn the forward direction, assuming intertwining and fixing x, y ∈ P, evaluating both sides at (x, y) equates the sorted image of (x, y) under e with the sorting of (e x, e y).
We split the equivalence into two directions. In the forward direction, we assume that Prod.map e e intertwines poset_sorting_map P and poset_sorting_map Q, fix x and y in P, apply the equality of functions to (x, y) using congrFun, and simplify using Function.comp_apply, psm_apply_it, and Prod.map.
uses
congrFun,Function.comp_apply,psm_apply_it,Prod.mapconstructor · intro h x y have hxy := congrFun h (x, y) simp only [Function.comp_apply, psm_apply_it, Prod.map] at hxy
If x = y, the equivalence e y < e x ↔ y < x holds trivially; if x ≠ y, then e x ≠ e y.
When x = y, both x < x and e x < e x are false by irreflexivity of strict partial orders, so both sides are false and the equivalence holds. When x ≠ y, injectivity of the equivalence e guarantees e x ≠ e y.
by_cases hq : x = y · subst hq; simp have hne : e x ≠ e y := fun h' => hq (e.injective h')
When x ≠ y, the equivalence e y < e x ↔ y < x holds.
We perform case analysis on the four truth-value combinations of y < x and e y < e x. If both are true or both are false, the equivalence holds by iff_of_true or iff_of_false. If they disagree, rewriting the if-then-else expressions using if_pos and if_neg reduces the intertwining equality to (e y, e x) = (e x, e y); taking components via Prod.ext_iff.1 implies e x = e y, which contradicts e x ≠ e y via absurd.
uses
iff_of_true,if_pos,if_neg,Prod.ext_iff.1,absurd,iff_of_falseby_cases h1 : y < x <;> by_cases h2 : e y < e x · exact iff_of_true h2 h1 · rw [if_pos h1, if_neg h2] at hxy exact absurd (Prod.ext_iff.1 hxy).2 hne · rw [if_neg h1, if_pos h2] at hxy exact absurd (Prod.ext_iff.1 hxy).1 hne · exact iff_of_false h2 h1
In the reverse direction, assuming e preserves and reflects strict order, function extensionality reduces intertwining to equality on each pair (x, y).
We introduce the hypothesis that e preserves and reflects strict order (∀ x y, e y < e x ↔ y < x). By function extensionality (funext), it suffices to show that the intertwining equality holds on an arbitrary pair (x, y).
· intro h funext ⟨x, y⟩
The intertwining equation holds on (x, y), completing the proof.
We expand the definitions using Function.comp_apply, psm_apply_it, and Prod.map. Splitting on the conditions y < x and e y < e x produces four branches; because the hypothesis ensures y < x ↔ e y < e x, the mismatching branches are contradictory, while in the matching branches both sides simplify to the same pair.
uses
Function.comp_apply,psm_apply_it,Prod.mapsimp only [Function.comp_apply, psm_apply_it, Prod.map] split_ifs <;> simp_all
congrFun- Two functions that are equal take equal values at any argument.
Function.comp_apply- The value of a function composition (f ∘ g) at x is f (g x).
psm_apply_it- poset_sorting_map P p evaluates to (p.2, p.1) if p.2 < p.1, and to p otherwise.
Prod.map- Maps a pair by applying a function to each component.
iff_of_true- If propositions a and b are both true, then a ↔ b holds.
if_pos- If a condition c is true, the if-then-else expression evaluates to the then branch.
if_neg- If a condition c is false, the if-then-else expression evaluates to the else branch.
Prod.ext_iff.1- If two pairs are equal, their corresponding components are equal.
absurd- From a proposition and its negation, anything follows.
iff_of_false- If propositions a and b are both false, then a ↔ b holds.
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.
open Classical inprivate lemma psm_apply_it {P : Type*} [PartialOrder P] (p : P × P) : poset_sorting_map P p = if p.2 < p.1 then (p.2, p.1) else p := by rfltheorem poset_sorting_map_intertwine_iff {P Q : Type*} [PartialOrder P] [PartialOrder Q] (e : P ≃ Q) : Prod.map e e ∘ poset_sorting_map P = poset_sorting_map Q ∘ Prod.map e e ↔ ∀ x y : P, e y < e x ↔ y < x := by constructor · intro h x y have hxy := congrFun h (x, y) simp only [Function.comp_apply, psm_apply_it, Prod.map] at hxy by_cases hq : x = y · subst hq; simp have hne : e x ≠ e y := fun h' => hq (e.injective h') by_cases h1 : y < x <;> by_cases h2 : e y < e x · exact iff_of_true h2 h1 · rw [if_pos h1, if_neg h2] at hxy exact absurd (Prod.ext_iff.1 hxy).2 hne · rw [if_neg h1, if_pos h2] at hxy exact absurd (Prod.ext_iff.1 hxy).1 hne · exact iff_of_false h2 h1 · intro h funext ⟨x, y⟩ simp only [Function.comp_apply, psm_apply_it, Prod.map] split_ifs <;> simp_all