poset_rigidity_of_down_set_preserving_bijections
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
- poset_down_set_preserving_bijective_eqLet P and Q be finite posets, and let α, β : P → Q be bijective maps. If for all x in P, the image under α of the principal down-set…
- order_reflecting_of_injective_down_set_preservingIf a map α : P → Q between preordered types is injective and preserves principal down-sets (that is, the image of Set.Iic x under α is…
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.
α = β, 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.
uses
poset_down_set_preserving_bijective_eqhave hab : α = β := poset_down_set_preserving_bijective_eq α β hα hβ h_down refine ⟨hab, ?_⟩
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).
have h_down' : ∀ x : P, α '' Set.Iic x = Set.Iic (α x) := by intro x rw [h_down x, hab]
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.
uses
order_reflecting_of_injective_down_set_preservingexact 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
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.
/-- 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'