AFTD Auto-Formalizing Theoretical Domains

poset_sorting_map_intertwine_iff

theoremverified

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.

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

    line 4

      rfl
  2. In 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.

    lines 10–13

    uses congrFun, Function.comp_apply, psm_apply_it, Prod.map

      constructor
      · intro h x y
        have hxy := congrFun h (x, y)
        simp only [Function.comp_apply, psm_apply_it, Prod.map] at hxy
  3. 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.

    lines 14–16

        by_cases hq : x = y
        · subst hq; simp
        have hne : e x ≠ e y := fun h' => hq (e.injective h')
  4. 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.

    lines 17–23

    uses iff_of_true, if_pos, if_neg, Prod.ext_iff.1, absurd, iff_of_false

        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
  5. 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).

    lines 24–25

      · intro h
        funext ⟨x, y⟩
  6. 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.

    lines 26–27

    uses Function.comp_apply, psm_apply_it, Prod.map

        simp 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

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