AFTD Auto-Formalizing Theoretical Domains

poset_rigidity_of_down_set_preserving_bijections

theoremverifiedformalization

Let P and Q be finite posets, and let α, β : P → Q be bijective maps such that for all x in P, the image under α of the principal down-set Set.Iic x equals the principal down-set Set.Iic (β x). Then α = β, and α is an order isomorphism (for all x, y in P, α x ≤ α y ↔ x ≤ y).

Statement

theorem poset_rigidity_of_down_set_preserving_bijections
    {P Q : Type*} [Fintype P] [Fintype Q] [PartialOrder P] [PartialOrder Q]
    (α β : P → Q) (hα : Function.Bijective α) (hβ : Function.Bijective β)
    (h_down : ∀ x : P, α '' Set.Iic x = Set.Iic (β x)) :
    α = β ∧ ∀ x y : P, α x ≤ α y ↔ x ≤ y
Formalizes
arXiv:2611.15540, Lemma 3.1: Solutions of the set-theoretic quantum Yang-Baxter equation arising from posets
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

Read back from the Lean

Let $P$ and $Q$ be finite types equipped with partial orders, and let $\alpha, \beta : P \to Q$ be functions. Assume that $\alpha$ is bijective, $\beta$ is bijective, and for every $x \in P$, the image under $\alpha$ of the principal down-set $\{y \in P \mid y \le x\}$ equals the principal down-set $\{z \in Q \mid z \le \beta(x)\}$. Then $\alpha = \beta$, and $\alpha$ is an order embedding (that is, for all $x, y \in P$, $\alpha(x) \le \alpha(y)$ if and only if $x \le y$).

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 proof establishes rigidity by first applying the theorem poset_down_set_preserving_bijective_eq to show that the two bijections α and β must be identical. Substituting α = β back into the down-set condition shows that α sends each principal down-set onto the down-set of its own image. Finally, applying order_reflecting_of_injective_down_set_preserving with the injectivity of α proves that α is an order isomorphism.

  1. α = β, leaving only the order-isomorphism property to be proved.

    By poset_down_set_preserving_bijective_eq, the hypothesis that α and β are bijections between finite posets whose down-sets match according to h_down guarantees that α = β. Supplying this equality discharges the first conjunct of the goal.

    lines 7–8

    uses poset_down_set_preserving_bijective_eq

      have hab : α = β := poset_down_set_preserving_bijective_eq α β hα hβ h_down
      refine ⟨hab, ?_⟩
  2. For every x in P, α maps the principal down-set of x onto the principal down-set of α x: α '' Set.Iic x = Set.Iic (α x).

    For an arbitrary element x in P, the down-set hypothesis gives α '' Set.Iic x = Set.Iic (β x). Since α = β from the previous step, substituting α for β produces the identity α '' Set.Iic x = Set.Iic (α x).

    lines 9–11

      have h_down' : ∀ x : P, α '' Set.Iic x = Set.Iic (α x) := by
        intro x
        rw [h_down x, hab]
  3. The map α is an order isomorphism: for all x and y in P, α x ≤ α y ↔ x ≤ y.

    Because α is injective (being bijective) and preserves down-sets with respect to itself, order_reflecting_of_injective_down_set_preserving immediately concludes that α reflects and preserves the order.

    line 12

    uses order_reflecting_of_injective_down_set_preserving

      exact order_reflecting_of_injective_down_set_preserving α hα.injective h_down'
poset_down_set_preserving_bijective_eq
If two bijections between finite posets satisfy the condition that the image of each principal down-set under the first equals the principal down-set of the image under the second, then the two maps are equal.
order_reflecting_of_injective_down_set_preserving
An injective map between preorders that sends each principal down-set onto the principal down-set of the image point preserves and reflects the order (i.e., α x ≤ α y ↔ x ≤ y).

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

/-- Poset rigidity: down-set preserving bijections are equal and define an order isomorphism. -/theorem poset_rigidity_of_down_set_preserving_bijections    {P Q : Type*} [Fintype P] [Fintype Q] [PartialOrder P] [PartialOrder Q]    (α β : P → Q) (hα : Function.Bijective α) (hβ : Function.Bijective β)    (h_down : ∀ x : P, α '' Set.Iic x = Set.Iic (β x)) :    α = β ∧ ∀ x y : P, α x ≤ α y ↔ x ≤ y := by  have hab : α = β := poset_down_set_preserving_bijective_eq α β hα hβ h_down  refine ⟨hab, ?_⟩  have h_down' : ∀ x : P, α '' Set.Iic x = Set.Iic (α x) := by    intro x    rw [h_down x, hab]  exact order_reflecting_of_injective_down_set_preserving α hα.injective h_down'
See it in the graphDiscuss this resultChallenge it