order_reflecting_of_injective_down_set_preserving
If a map α : P → Q between preordered types is injective and preserves principal down-sets (that is, the image of Set.Iic x under α is Set.Iic (α x) for all x in P), then α preserves and reflects the order: α x ≤ α y ↔ x ≤ y for all x, y in P.
Statement
theorem order_reflecting_of_injective_down_set_preserving {P Q : Type*} [Preorder P] [Preorder Q] (α : P → Q) (hα : Function.Injective α) (h_down : ∀ x : P, α '' Set.Iic x = Set.Iic (α x)) (x y : P) : α x ≤ α y ↔ x ≤ y
- Source
- arXiv:2611.15540, Lemma 3.1: Solutions of the set-theoretic quantum Yang-Baxter equation arising from posets
- Verified
- 16 Nov 2026
- Axioms
propext- Used by 1
- poset_rigidity_of_down_set_preserving_bijectionsLet 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…
Read back from the Lean
Let $P$ and $Q$ be preordered types, and let $\alpha : P \to Q$ be a function. Assume that:
1. $\alpha$ is injective (Function.Injective α), and
2. for all $x \in P$, the image under $\alpha$ of the lower interval $\{z \in P \mid z \le x\}$ (Set.Iic x) equals the lower interval $\{w \in Q \mid w \le \alpha(x)\}$ (Set.Iic (α x)).
Then, 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 equivalence is proved in two directions. For the forward direction (order reflection), α x ≤ α y means that α x belongs to the principal down-set of α y, which equals the image under α of the down-set of y; by injectivity of α, x must equal the preimage element in that down-set, giving x ≤ y. For the reverse direction (order preservation), x ≤ y means x is in the down-set of y, so α x belongs to the image down-set, which is the down-set of α y, yielding α x ≤ α y.
It suffices to prove both directions of the equivalence: order reflection (α x ≤ α y → x ≤ y) and order preservation (x ≤ y → α x ≤ α y).
The equivalence α x ≤ α y ↔ x ≤ y is split into two separate implications to be proved independently.
constructorIf α x ≤ α y, then x ≤ y.
Assume α x ≤ α y. This inequality means that α x belongs to the principal down-set Set.Iic (α y). By the down-set preservation hypothesis h_down, Set.Iic (α y) = α '' Set.Iic y, so α x lies in the image under α of the down-set of y. Thus there exists some z ∈ Set.Iic y (that is, z ≤ y) with α z = α x. Since α is injective (hα), z = x. Substituting x for z in z ≤ y yields x ≤ y.
· intro h have hmem : α x ∈ α '' Set.Iic y := by rw [h_down y] exact h rcases hmem with ⟨z, hz, hzx⟩ have : z = x := hα hzx simpa [this] using hz
Conversely, if x ≤ y, then α x ≤ α y.
Assume x ≤ y, so x ∈ Set.Iic y. Applying α gives α x ∈ α '' Set.Iic y. Rewriting by the down-set preservation hypothesis h_down transforms this into α x ∈ Set.Iic (α y), which by definition means α x ≤ α y.
· intro h have hmem : x ∈ Set.Iic y := h have : α x ∈ α '' Set.Iic y := ⟨x, hmem, rfl⟩ rwa [h_down y] at this
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.
/-- An injective map between preordered types preserving principal down-sets is order-reflecting and order-preserving. -/theorem order_reflecting_of_injective_down_set_preserving {P Q : Type*} [Preorder P] [Preorder Q] (α : P → Q) (hα : Function.Injective α) (h_down : ∀ x : P, α '' Set.Iic x = Set.Iic (α x)) (x y : P) : α x ≤ α y ↔ x ≤ y := by constructor · intro h have hmem : α x ∈ α '' Set.Iic y := by rw [h_down y] exact h rcases hmem with ⟨z, hz, hzx⟩ have : z = x := hα hzx simpa [this] using hz · intro h have hmem : x ∈ Set.Iic y := h have : α x ∈ α '' Set.Iic y := ⟨x, hmem, rfl⟩ rwa [h_down y] at this