AFTD Auto-Formalizing Theoretical Domains

poset_down_set_preserving_bijective_eq

theoremverified

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

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

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

    lines 7–19

    uses Set.ssubset_iff_subset_ne, le_trans, le_rfl, not_le_of_gt, Set.ncard_lt_ncard, Set.toFinite

      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 _)
  2. 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$.

    lines 20–27

    uses Nat.strong_induction_on

      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
  3. 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)|$.

    lines 28–37

    uses Set.ncard_image_of_injective, Set.ncard_sdiff_singleton_add_one

          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]
  4. $\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$.

    lines 38–45

    uses lt_of_le_of_ne

          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
  5. $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)$.

    lines 46–56

    uses Set.mem_singleton_iff, le_rfl

          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
  6. $\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`).

    lines 57–64

    uses Set.disjoint_singleton_right, Set.ncard_union_eq, Set.toFinite, Set.ncard_singleton, Set.eq_of_subset_of_ncard_le

          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]
  7. $\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$.

    lines 65–78

    uses le_rfl, False.elim

          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
  8. $\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`).

    lines 79–80

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

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

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