AFTD Auto-Formalizing Theoretical Domains

fractional_scd_of_scd

theoremverified

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

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.

  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.

    lines 7–8

      rcases h with ⟨𝒞, hchain, hpart⟩
      refine ⟨𝒞.toFinset, fun _ => 1, ?_, ?_, ?_⟩
  2. 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.

    lines 9–11

    uses Set.mem_toFinset

      · intro C hC
        rw [Set.mem_toFinset] at hC
        exact hchain C hC
  3. The weight assigned to each chain is non-negative.

    Each chain receives weight 1, and 0 ≤ 1 holds by `zero_le_one`.

    lines 12–13

    uses zero_le_one

      · intro C _
        exact zero_le_one
  4. 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.

    lines 14–15

      · intro x
        rcases hpart x with ⟨C, ⟨hC𝒞, hxC⟩, huniq⟩
  5. 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.

    lines 16–23

    uses Finset.mem_filter, Set.mem_toFinset, Finset.mem_singleton

        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⟩
  6. 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.

    lines 24–25

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

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

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