fractional_scd_with_denominator_one_of_scd
If a finite partially ordered type with an integer rank function admits an ordinary symmetric chain decomposition, then it admits a fractional symmetric chain decomposition with denominator 1.
Statement
open scoped Classical BigOperators in theorem fractional_scd_with_denominator_one_of_scd {α : Type*} [Fintype α] [PartialOrder α] (rank : α → ℤ) (h : has_symmetric_chain_decomposition rank) : has_fractional_scd_with_denominator rank 1
- Source
- arXiv:2610.24148, Section 2.7.4
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- has_fractional_scd_with_denominatorA partially ordered type with an integer rank function admits a fractional symmetric chain decomposition with denominator D if there…
- is_symmetric_saturated_chainA subset of a ranked poset is a symmetric saturated chain if there is an integer k such that the chain contains exactly one element of…
- has_symmetric_chain_decompositionA ranked poset admits a symmetric chain decomposition if its elements can be partitioned into symmetric saturated chains.
Read back from the Lean
For any finite partially ordered type α and any function rank : α → ℤ, if rank admits a symmetric chain decomposition (that is, a partition of α into symmetric saturated chains), then rank admits a fractional symmetric chain decomposition with denominator 1.
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
An ordinary symmetric chain decomposition partitions the poset into symmetric saturated chains. By assigning each chain weight 1, each element belongs to exactly one chain and thus has a total covering weight of 1, yielding a fractional symmetric chain decomposition with denominator 1.
The collection of chains $\mathcal{C}$ can be represented as a finite set $s$, with every chain in $s$ being a symmetric saturated chain.
From the assumption that an ordinary symmetric chain decomposition exists, we obtain a collection $\mathcal{C}$ of symmetric saturated chains that partition $\alpha$. Since $\alpha$ is a finite type, the collection $\mathcal{C}$ is finite and is converted into a `Finset` $s = \mathcal{C}\text{.toFinset}$. Membership in $s$ is equivalent to membership in $\mathcal{C}$ by `Set.mem_toFinset`, so every $C \in s$ is indeed a symmetric saturated chain.
uses
Set.mem_toFinsetclassical obtain ⟨𝒞, hsC, huniq⟩ := h let s := 𝒞.toFinset have h1 : ∀ C ∈ s, is_symmetric_saturated_chain rank C := by intro C hC rw [Set.mem_toFinset] at hC exact hsC C hC
Assigning weight $1$ to every chain in $s$ satisfies the nonnegativity and denominator-1 conditions for a fractional symmetric chain decomposition.
We provide the finite set $s$ and the constant weight function $\tau(C) = 1$ as our candidate fractional decomposition. For each chain $C \in s$, the weight is nonnegative ($0 \le 1$), and setting $k = 1$ satisfies $\tau(C) = k / 1$.
refine ⟨s, fun _ => 1, h1, ?_, ?_, ?_⟩ · intro C hC; norm_num · intro C hC; exact ⟨1, by norm_num⟩
For any element $x \in \alpha$, the subcollection of chains in $s$ containing $x$ is the singleton $\{C_0\}$, where $C_0$ is the unique chain containing $x$.
By the definition of an ordinary decomposition, every $x \in \alpha$ belongs to a unique chain $C_0 \in \mathcal{C}$. By extensionality, a chain $C$ is in the filtered finset $\{C \in s \mid x \in C\}$ if and only if $C \in s$ and $x \in C$. Since $C \in s \iff C \in \mathcal{C}$ via `Set.mem_toFinset`, the uniqueness of $C_0$ implies that $C$ is in the filtered set if and only if $C = C_0$.
uses
Finset.mem_filter,Finset.mem_singleton,Set.mem_toFinset· intro x obtain ⟨C0, hC0mem, hC0uniq⟩ := huniq x have hfilt : s.filter (fun C => x ∈ C) = {C0} := by ext C simp only [Finset.mem_filter, Finset.mem_singleton] constructor · rintro ⟨hCs, hxC⟩ rw [Set.mem_toFinset] at hCs exact hC0uniq C ⟨hCs, hxC⟩ · intro h subst h exact ⟨by rw [Set.mem_toFinset]; exact hC0mem.1, hC0mem.2⟩
The total weight of the chains containing $x$ equals $1$.
Rewriting the sum over the filtered set using the identity $\{C \in s \mid x \in C\} = \{C_0\}$, the sum over the singleton set reduces by `Finset.sum_singleton` to $\tau(C_0) = 1$.
uses
Finset.sum_singletonrw [hfilt, Finset.sum_singleton]
Set.mem_toFinset- An element belongs to the `Finset` representation `s.toFinset` of a set `s` if and only if it belongs to `s`.
Finset.mem_filter- An element belongs to `s.filter p` if and only if it belongs to `s` and satisfies predicate `p`.
Finset.mem_singleton- An element belongs to the singleton set `{a}` if and only if it equals `a`.
Finset.sum_singleton- The sum of a function over a singleton set `{a}` is the value of the function evaluated at `a`.
- The proof uses classical logic to convert the set of chains $\mathcal{C}$ into a `Finset` via `Set.toFinset`, which is valid because the carrier type $\alpha$ is finite.
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.
open scoped Classical BigOperators in/-- An ordinary symmetric chain decomposition yields a fractional symmetric chain decomposition with denominator 1. -/theorem fractional_scd_with_denominator_one_of_scd {α : Type*} [Fintype α] [PartialOrder α] (rank : α → ℤ) (h : has_symmetric_chain_decomposition rank) : has_fractional_scd_with_denominator rank 1 := by classical obtain ⟨𝒞, hsC, huniq⟩ := h let s := 𝒞.toFinset have h1 : ∀ C ∈ s, is_symmetric_saturated_chain rank C := by intro C hC rw [Set.mem_toFinset] at hC exact hsC C hC refine ⟨s, fun _ => 1, h1, ?_, ?_, ?_⟩ · intro C hC; norm_num · intro C hC; exact ⟨1, by norm_num⟩ · intro x obtain ⟨C0, hC0mem, hC0uniq⟩ := huniq x have hfilt : s.filter (fun C => x ∈ C) = {C0} := by ext C simp only [Finset.mem_filter, Finset.mem_singleton] constructor · rintro ⟨hCs, hxC⟩ rw [Set.mem_toFinset] at hCs exact hC0uniq C ⟨hCs, hxC⟩ · intro h subst h exact ⟨by rw [Set.mem_toFinset]; exact hC0mem.1, hC0mem.2⟩ rw [hfilt, Finset.sum_singleton]