AFTD Auto-Formalizing Theoretical Domains

order_reflecting_of_injective_down_set_preserving

theoremverified

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

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.

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

    line 6

      constructor
  2. If α 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.

    lines 7–13

      · 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
  3. 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.

    lines 14–17

      · 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

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