AFTD Auto-Formalizing Theoretical Domains

has_symmetric_chain_decomposition

def

A ranked poset admits a symmetric chain decomposition if its elements can be partitioned into symmetric saturated chains.

Statement

def has_symmetric_chain_decomposition {α : Type*} [PartialOrder α] (rank : α → ℤ) : Prop
Defined in
arXiv:2610.24148, Section 2.3
Verified
21 Oct 2026
Axioms
none listed
Built on 1
  • 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…
Used by 2
  • fractional_scd_of_scdIf a finite ranked poset admits an ordinary symmetric chain decomposition, then it admits a fractional symmetric chain decomposition.
  • fractional_scd_with_denominator_one_of_scdIf a finite partially ordered type with an integer rank function admits an ordinary symmetric chain decomposition, then it admits a…

Read back from the Lean

For a partially ordered type α and an integer-valued function rank : α → ℤ, has_symmetric_chain_decomposition rank asserts that there exists a family of subsets 𝒞 : Set (Set α) such that: 1. Every set C ∈ 𝒞 is a symmetric saturated chain with respect to rank: there exists an integer k such that: - For every integer m, some x ∈ C has rank x = m if and only if m = -k + 2 * j for some integer j with 0 ≤ j ≤ k. - rank is injective on C: for all x, y ∈ C, if rank x = rank y, then x = y. - For all x, y ∈ C, if rank y = rank x + 2, then x is covered by y (x ⋖ y, meaning x < y and no element strictly lies between them). 2. Every element x : α belongs to a unique set C ∈ 𝒞 (i.e., 𝒞 partitions α, modulo possibly containing the empty set).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A symmetric chain decomposition of a ranked poset. -/
def has_symmetric_chain_decomposition {α : Type*} [PartialOrder α] (rank : α → ℤ) : Prop :=
  ∃ 𝒞 : Set (Set α),
    (∀ C ∈ 𝒞, is_symmetric_saturated_chain rank C) ∧
    (∀ x : α, ∃! C ∈ 𝒞, x ∈ C)
See it in the graphDiscuss this resultChallenge it