poset_down_set_preserving_bijective_eq
Let 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 Set.Iic x equals the principal down-set Set.Iic (β x), then α = β.
Statement
theorem poset_down_set_preserving_bijective_eq {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)) : α = β
- Source
- 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- 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 finite types equipped with partial orders, and let $\alpha, \beta : P \to Q$ be functions. If both $\alpha$ and $\beta$ are bijective, and for every $x \in P$, the image under $\alpha$ of the principal down-set of $x$ (i.e., $\{y : P \mid y \le x\}$) equals the principal down-set of $\beta(x)$ in $Q$ (i.e., $\{z : Q \mid z \le \beta(x)\}$), then $\alpha = \beta$.
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 proceeds by strong induction on the cardinality $n = |\downarrow x|$ of the principal down-set $\downarrow x$. In the inductive step, the induction hypothesis ensures that $\alpha$ and $\beta$ agree on all strict predecessors $y < x$. Defining $C = \alpha(\downarrow x \setminus \{x\})$, the agreement on strict predecessors and injectivity of $\beta$ imply that $\beta x \notin C$. Since $C \cup \{\beta x\}$ is a subset of $\downarrow(\beta x)$ with the same finite cardinality, the two sets coincide; because $\alpha x \in \downarrow(\beta x)$ and $\alpha x \notin C$ by injectivity of $\alpha$, it follows that $\alpha x = \beta x$. Extensionality then gives $\alpha = \beta$.
Strictly smaller elements have principal down-sets of strictly smaller cardinality: if $y < x$, then $|\downarrow y| < |\downarrow x|$.
If $y < x$, any $z \le y$ satisfies $z \le x$ by transitivity (`le_trans`), so $\downarrow y \subseteq \downarrow x$. Moreover, $x \in \downarrow x$ by reflexivity (`le_rfl`), but $x \notin \downarrow y$ because $x \le y$ would contradict $y < x$ (`not_le_of_gt`). Hence $\downarrow y \subsetneq \downarrow x$ (`Set.ssubset_iff_subset_ne`), which implies $|\downarrow y| < |\downarrow x|$ because $P$ is finite (`Set.ncard_lt_ncard`, `Set.toFinite`).
uses
Set.ssubset_iff_subset_ne,le_trans,le_rfl,not_le_of_gt,Set.ncard_lt_ncard,Set.toFiniteclassical have hcard_lt : ∀ x y : P, y < x → (Set.Iic y).ncard < (Set.Iic x).ncard := by intro x y hyx have hss : Set.Iic y ⊂ Set.Iic x := by rw [Set.ssubset_iff_subset_ne] constructor · intro z hz exact le_trans hz hyx.le · intro heq have hxmem : x ∈ Set.Iic x := le_rfl have : x ∈ Set.Iic y := by rw [heq]; exact hxmem exact (not_le_of_gt hyx) this exact Set.ncard_lt_ncard hss (Set.toFinite _)
By strong induction on the size of principal down-sets, $\alpha$ and $\beta$ agree on all strict predecessors of $x$: if $y < x$, then $\alpha y = \beta y$.
We set up strong induction on $n = |\downarrow x|$ using `Nat.strong_induction_on`. For any element $y < x$, the down-set $\downarrow y$ has cardinality strictly less than $n$ by the strict monotonicity lemma `hcard_lt`. The induction hypothesis then immediately implies $\alpha y = \beta y$.
uses
Nat.strong_induction_onhave key : ∀ n : ℕ, ∀ x : P, (Set.Iic x).ncard = n → α x = β x := by intro n induction n using Nat.strong_induction_on with | h n ih => intro x hx have hagree : ∀ y : P, y < x → α y = β y := by intro y hy exact ih (Set.Iic y).ncard (by rw [← hx]; exact hcard_lt x y hy) y rfl
For the deleted image $C = \alpha(\downarrow x \setminus \{x\})$, the cardinality satisfies $|C| + 1 = |\downarrow(\beta x)|$.
Because $\alpha$ is injective, it preserves set cardinalities (`Set.ncard_image_of_injective`), so $|C| = |\downarrow x \setminus \{x\}|$. Removing the element $x \in \downarrow x$ gives $|C| + 1 = |\downarrow x|$ (`Set.ncard_sdiff_singleton_add_one`). Furthermore, the hypothesis $\alpha(\downarrow x) = \downarrow(\beta x)$ together with injectivity of $\alpha$ means $|\downarrow(\beta x)| = |\downarrow x|$. Combining these gives $|C| + 1 = |\downarrow(\beta x)|$.
uses
Set.ncard_image_of_injective,Set.ncard_sdiff_singleton_add_onelet C : Set Q := α '' (Set.Iic x \ {x}) have hCcard : C.ncard = (Set.Iic x \ {x}).ncard := by exact Set.ncard_image_of_injective _ hα.injective have hdiffcard : (Set.Iic x \ {x}).ncard + 1 = (Set.Iic x).ncard := by exact Set.ncard_sdiff_singleton_add_one (by simp) have hTcard : (Set.Iic (β x)).ncard = (Set.Iic x).ncard := by rw [← h_down x] exact Set.ncard_image_of_injective _ hα.injective have hCcardT : C.ncard + 1 = (Set.Iic (β x)).ncard := by rw [hCcard, hdiffcard, hTcard]
$\beta x \notin C$.
Suppose $\beta x \in C$, meaning $\beta x = \alpha y$ for some $y \in \downarrow x \setminus \{x\}$. Then $y \le x$ and $y \ne x$, so $y < x$ (`lt_of_le_of_ne`). By agreement on strict predecessors, $\alpha y = \beta y$, so $\beta x = \beta y$. Injectivity of $\beta$ then implies $y = x$, which contradicts $y \ne x$.
uses
lt_of_le_of_nehave hβx_notinC : β x ∉ C := by rintro ⟨y, hy, hαy⟩ have hyne : y ≠ x := by simpa using hy.2 have hyx : y < x := lt_of_le_of_ne hy.1 hyne have hαeqβ : α y = β y := hagree y hyx have : y = x := hβ.injective (by rw [← hαeqβ, hαy]) exact hyne this
$C \cup \{\beta x\} \subseteq \downarrow(\beta x)$.
Every element of $C$ has the form $\alpha y$ for some $y \le x$, hence belongs to $\alpha(\downarrow x) = \downarrow(\beta x)$. Since also $\beta x \in \downarrow(\beta x)$ by reflexivity (`le_rfl`, `Set.mem_singleton_iff`), the union $C \cup \{\beta x\}$ is a subset of $\downarrow(\beta x)$.
uses
Set.mem_singleton_iff,le_rflhave hCsubT : C ⊆ Set.Iic (β x) := by rintro q ⟨y, hy, rfl⟩ have : α y ∈ α '' Set.Iic x := ⟨y, hy.1, rfl⟩ rwa [h_down x] at this have hsub : C ∪ {β x} ⊆ Set.Iic (β x) := by intro q hq rcases hq with hq | hq · exact hCsubT hq · rw [Set.mem_singleton_iff] at hq rw [hq] exact le_rfl
$\downarrow(\beta x) = C \cup \{\beta x\}$.
Since $\beta x \notin C$, the set $C$ and the singleton $\{\beta x\}$ are disjoint (`Set.disjoint_singleton_right`). Their union therefore has cardinality $|C| + 1$ (`Set.ncard_union_eq`, `Set.ncard_singleton`), which equals $|\downarrow(\beta x)|$. Since $C \cup \{\beta x\} \subseteq \downarrow(\beta x)$ and both sets are finite with equal cardinality, they are equal (`Set.eq_of_subset_of_ncard_le`, `Set.toFinite`).
uses
Set.disjoint_singleton_right,Set.ncard_union_eq,Set.toFinite,Set.ncard_singleton,Set.eq_of_subset_of_ncard_lehave hdisj : Disjoint C ({β x} : Set Q) := by rw [Set.disjoint_singleton_right] exact hβx_notinC have hunioncard : (C ∪ {β x}).ncard = C.ncard + 1 := by rw [Set.ncard_union_eq hdisj (Set.toFinite _) (Set.toFinite _), Set.ncard_singleton] have hT_eq : Set.Iic (β x) = C ∪ {β x} := by refine (Set.eq_of_subset_of_ncard_le hsub ?_ (Set.toFinite _)).symm rw [hunioncard, hCcardT]
$\alpha x = \beta x$ for each $x \in P$.
By reflexivity (`le_rfl`), $\alpha x \in \alpha(\downarrow x) = \downarrow(\beta x) = C \cup \{\beta x\}$. On the other hand, $\alpha x \notin C$, because if $\alpha x = \alpha y$ for some $y \in \downarrow x \setminus \{x\}$, injectivity of $\alpha$ would force $y = x$, contradicting $y \ne x$. Eliminating the case $\alpha x \in C$ (`False.elim`), we must have $\alpha x \in \{\beta x\}$, which means $\alpha x = \beta x$.
uses
le_rfl,False.elimhave hαx_inT : α x ∈ Set.Iic (β x) := by rw [← h_down x] exact ⟨x, le_rfl, rfl⟩ have hαx_notinC : α x ∉ C := by rintro ⟨y, hy, hαy⟩ have hyne : y ≠ x := by simpa using hy.2 exact hyne (hα.injective hαy) have hαx_in_union : α x ∈ C ∪ {β x} := by rw [← hT_eq] exact hαx_inT rcases hαx_in_union with h | h · exact False.elim (hαx_notinC h) · simpa using h
$\alpha = \beta$.
Having shown $\alpha x = \beta x$ for every $x \in P$ by strong induction, the two functions are equal by function extensionality (`funext`).
funext x exact key (Set.Iic x).ncard x rfl
Set.ssubset_iff_subset_ne- A set $s$ is a strict subset of $t$ if and only if $s \subseteq t$ and $s \ne t$.
le_trans- If $a \le b$ and $b \le c$, then $a \le c$ (transitivity of order).
le_rfl- $a \le a$ (reflexivity of order).
not_le_of_gt- If $a < b$, then $b \le a$ is false.
Set.ncard_lt_ncard- A strict subset of a finite set has strictly smaller cardinality.
Set.toFinite- Any subset of a finite type is a finite set.
Nat.strong_induction_on- Strong induction on natural numbers: to prove $p(n)$ for all $n$, it suffices to show that $(\forall m < n, p(m)) \implies p(n)$.
Set.ncard_image_of_injective- An injective function preserves the cardinality of any set: $|f(s)| = |s|$.
Set.ncard_sdiff_singleton_add_one- Removing an element $a \in s$ from a finite set $s$ satisfies $|s \setminus \{a\}| + 1 = |s|$.
lt_of_le_of_ne- In a partial order, if $a \le b$ and $a \ne b$, then $a < b$.
Set.mem_singleton_iff- $a \in \{b\} \iff a = b$.
Set.disjoint_singleton_right- A set $s$ is disjoint from a singleton $\{a\}$ if and only if $a \notin s$.
Set.ncard_union_eq- The cardinality of the union of disjoint finite sets is the sum of their cardinalities: $|s \cup t| = |s| + |t|$.
Set.ncard_singleton- The cardinality of a singleton set $\{a\}$ is $1$.
Set.eq_of_subset_of_ncard_le- A subset of a finite set with at least as many elements is the entire set: if $s \subseteq t$ and $|t| \le |s|$, then $s = t$.
False.elim- From False, any proposition follows (ex falso quodlibet).
- In Lean, `Set.Iic x` denotes the principal down-set $\{y \mid y \le x\}$, and `Set.ncard` is the cardinality of a set as a natural number. The finiteness obligations `Set.toFinite _` are resolved automatically using the `Fintype` instances on $P$ and $Q$.
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.
/-- Two bijections between finite posets matching images of principal down-sets are equal. -/theorem poset_down_set_preserving_bijective_eq {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)) : α = β := by classical have hcard_lt : ∀ x y : P, y < x → (Set.Iic y).ncard < (Set.Iic x).ncard := by intro x y hyx have hss : Set.Iic y ⊂ Set.Iic x := by rw [Set.ssubset_iff_subset_ne] constructor · intro z hz exact le_trans hz hyx.le · intro heq have hxmem : x ∈ Set.Iic x := le_rfl have : x ∈ Set.Iic y := by rw [heq]; exact hxmem exact (not_le_of_gt hyx) this exact Set.ncard_lt_ncard hss (Set.toFinite _) have key : ∀ n : ℕ, ∀ x : P, (Set.Iic x).ncard = n → α x = β x := by intro n induction n using Nat.strong_induction_on with | h n ih => intro x hx have hagree : ∀ y : P, y < x → α y = β y := by intro y hy exact ih (Set.Iic y).ncard (by rw [← hx]; exact hcard_lt x y hy) y rfl let C : Set Q := α '' (Set.Iic x \ {x}) have hCcard : C.ncard = (Set.Iic x \ {x}).ncard := by exact Set.ncard_image_of_injective _ hα.injective have hdiffcard : (Set.Iic x \ {x}).ncard + 1 = (Set.Iic x).ncard := by exact Set.ncard_sdiff_singleton_add_one (by simp) have hTcard : (Set.Iic (β x)).ncard = (Set.Iic x).ncard := by rw [← h_down x] exact Set.ncard_image_of_injective _ hα.injective have hCcardT : C.ncard + 1 = (Set.Iic (β x)).ncard := by rw [hCcard, hdiffcard, hTcard] have hβx_notinC : β x ∉ C := by rintro ⟨y, hy, hαy⟩ have hyne : y ≠ x := by simpa using hy.2 have hyx : y < x := lt_of_le_of_ne hy.1 hyne have hαeqβ : α y = β y := hagree y hyx have : y = x := hβ.injective (by rw [← hαeqβ, hαy]) exact hyne this have hCsubT : C ⊆ Set.Iic (β x) := by rintro q ⟨y, hy, rfl⟩ have : α y ∈ α '' Set.Iic x := ⟨y, hy.1, rfl⟩ rwa [h_down x] at this have hsub : C ∪ {β x} ⊆ Set.Iic (β x) := by intro q hq rcases hq with hq | hq · exact hCsubT hq · rw [Set.mem_singleton_iff] at hq rw [hq] exact le_rfl have hdisj : Disjoint C ({β x} : Set Q) := by rw [Set.disjoint_singleton_right] exact hβx_notinC have hunioncard : (C ∪ {β x}).ncard = C.ncard + 1 := by rw [Set.ncard_union_eq hdisj (Set.toFinite _) (Set.toFinite _), Set.ncard_singleton] have hT_eq : Set.Iic (β x) = C ∪ {β x} := by refine (Set.eq_of_subset_of_ncard_le hsub ?_ (Set.toFinite _)).symm rw [hunioncard, hCcardT] have hαx_inT : α x ∈ Set.Iic (β x) := by rw [← h_down x] exact ⟨x, le_rfl, rfl⟩ have hαx_notinC : α x ∉ C := by rintro ⟨y, hy, hαy⟩ have hyne : y ≠ x := by simpa using hy.2 exact hyne (hα.injective hαy) have hαx_in_union : α x ∈ C ∪ {β x} := by rw [← hT_eq] exact hαx_inT rcases hαx_in_union with h | h · exact False.elim (hαx_notinC h) · simpa using h funext x exact key (Set.Iic x).ncard x rfl