fractional_scd_of_scd
If a finite ranked poset admits an ordinary symmetric chain decomposition, then it admits a fractional symmetric chain decomposition.
Statement
open scoped Classical in theorem fractional_scd_of_scd {α : Type*} [Fintype α] [PartialOrder α] (rank : α → ℤ) (h : has_symmetric_chain_decomposition rank) : has_fractional_symmetric_chain_decomposition rank
- Source
- arXiv:2610.24148, Section 2.7.1
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- has_symmetric_chain_decompositionA ranked poset admits a symmetric chain decomposition if its elements can be partitioned into symmetric saturated chains.
- has_fractional_symmetric_chain_decompositionA ranked poset admits a fractional symmetric chain decomposition if there exists a finite set of symmetric saturated chains and…
- 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…
Read back from the Lean
Let $\alpha$ be a finite type equipped with a partial order, and let $\mathrm{rank} : \alpha \to \mathbb{Z}$ be a rank function. If $\alpha$ admits a symmetric chain decomposition with respect to $\mathrm{rank}$, then $\alpha$ admits a fractional symmetric chain decomposition with respect to $\mathrm{rank}$.
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 viewing this partition as a finite set of chains and assigning weight 1 to every chain, we obtain a fractional symmetric chain decomposition: the weights are non-negative, and for each element x, the unique chain containing x contributes weight 1 while all others contribute 0, yielding a total sum of 1.
The partition 𝒞 (converted to a finite set) together with weight 1 assigned to each chain provides a candidate fractional symmetric chain decomposition.
We extract from the hypothesis `h` the family of chains 𝒞, the guarantee that each member is a symmetric saturated chain, and the condition that 𝒞 partitions α. Because α is finite, the collection of subsets 𝒞 can be represented as a finite set `𝒞.toFinset`. We provide this finset and the constant weight function assigning 1 to every chain as candidate witnesses for the fractional decomposition, leaving three obligations: verifying the chain property, non-negativity of weights, and the unit sum condition at each element.
rcases h with ⟨𝒞, hchain, hpart⟩ refine ⟨𝒞.toFinset, fun _ => 1, ?_, ?_, ?_⟩
Every chain in the finite collection is a symmetric saturated chain.
For any chain `C` in `𝒞.toFinset`, we rewrite finset membership to set membership `C ∈ 𝒞` using `Set.mem_toFinset`. The chain condition then holds immediately by the assumption that 𝒞 is a symmetric chain decomposition.
uses
Set.mem_toFinset· intro C hC rw [Set.mem_toFinset] at hC exact hchain C hC
The weight assigned to each chain is non-negative.
Each chain receives weight 1, and 0 ≤ 1 holds by `zero_le_one`.
uses
zero_le_one· intro C _ exact zero_le_one
For every element x, there is a unique chain C in 𝒞 that contains x.
Given an arbitrary element x, the partition property of 𝒞 provides a unique chain `C ∈ 𝒞` such that `x ∈ C`, along with the uniqueness guarantee that any other chain in 𝒞 containing x must equal C.
· intro x rcases hpart x with ⟨C, ⟨hC𝒞, hxC⟩, huniq⟩
The subcollection of chains containing x consists solely of the singleton {C}.
By finset extensionality, a chain D belongs to `𝒞.toFinset.filter (x ∈ ·)` if and only if D = C. Unfolding the definitions of filtering, finset conversion, and singleton membership with `Finset.mem_filter`, `Set.mem_toFinset`, and `Finset.mem_singleton`, this is equivalent to `D ∈ 𝒞 ∧ x ∈ D ↔ D = C`. The forward implication is precisely the uniqueness of C, and the reverse implication is the fact that C is in 𝒞 and contains x.
uses
Finset.mem_filter,Set.mem_toFinset,Finset.mem_singletonhave hfilt : 𝒞.toFinset.filter (x ∈ ·) = {C} := by ext D simp only [Finset.mem_filter, Set.mem_toFinset, Finset.mem_singleton] constructor · rintro ⟨hD𝒞, hxD⟩ exact huniq D ⟨hD𝒞, hxD⟩ · rintro rfl exact ⟨hC𝒞, hxC⟩
The sum of the weights of all chains containing x is 1.
Rewriting the filtered set of chains with `{C}`, the sum over all chains containing x reduces to the single term for C. Since the weight of C is 1, the sum over the singleton evaluates directly to 1.
rw [hfilt] simp
Set.mem_toFinset- An element belongs to the finset `s.toFinset` if and only if it belongs to the set `s`.
zero_le_one- Zero is less than or equal to one in an ordered structure.
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies property `p`.
Finset.mem_singleton- An element belongs to the singleton finset `{a}` if and only if it equals `a`.
- While an ordinary symmetric chain decomposition is defined using an arbitrary collection of chains `Set (Set α)`, the fractional version is defined with a finite set `Finset (Set α)`. Because `α` has a `Fintype` instance, the set of chains `𝒞` can be converted to a `Finset` via `Set.toFinset` under classical logic.
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 in/-- Every finite ranked poset admitting a symmetric chain decomposition also admits a fractional symmetric chain decomposition. -/theorem fractional_scd_of_scd {α : Type*} [Fintype α] [PartialOrder α] (rank : α → ℤ) (h : has_symmetric_chain_decomposition rank) : has_fractional_symmetric_chain_decomposition rank := by rcases h with ⟨𝒞, hchain, hpart⟩ refine ⟨𝒞.toFinset, fun _ => 1, ?_, ?_, ?_⟩ · intro C hC rw [Set.mem_toFinset] at hC exact hchain C hC · intro C _ exact zero_le_one · intro x rcases hpart x with ⟨C, ⟨hC𝒞, hxC⟩, huniq⟩ have hfilt : 𝒞.toFinset.filter (x ∈ ·) = {C} := by ext D simp only [Finset.mem_filter, Set.mem_toFinset, Finset.mem_singleton] constructor · rintro ⟨hD𝒞, hxD⟩ exact huniq D ⟨hD𝒞, hxD⟩ · rintro rfl exact ⟨hC𝒞, hxC⟩ rw [hfilt] simp