AFTD Auto-Formalizing Theoretical Domains

fractional_scd_with_denominator_one_of_scd

theoremverified

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.

  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.

    lines 7–13

    uses Set.mem_toFinset

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

    lines 14–16

      refine ⟨s, fun _ => 1, h1, ?_, ?_, ?_⟩
      · intro C hC; norm_num
      · intro C hC; exact ⟨1, by norm_num⟩
  3. 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$.

    lines 17–28

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

    line 29

    uses Finset.sum_singleton

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

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