How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced — the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted — a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated — a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The down-set and up-set chain covers from a suitable maximum antichain splice to a width-sized chain cover
Statement
Let be a nonempty finite poset of width , and let be a maximum antichain that is neither the set of all minimal elements nor the set of all maximal elements. Form and as in A maximal antichain splits a finite poset into its down-set and up-set with the antichain as their intersection. Then and are nonempty proper induced subposets of , both have width , and both have cardinality strictly smaller than . If each has a chain cover with as many chains as its width, then those covers splice along to give a chain cover of with exactly chains.
Facts & Assumptions
Given: A nonempty finite poset of width , a maximum antichain satisfying the Statement, and minimum-size chain covers of and .
For the down-set and up-set determined by a maximal antichain, and (A maximal antichain splits a finite poset into its down-set and up-set with the antichain as their intersection).
The width is the maximum cardinality of an antichain (Height and width of a nonempty finite poset).
Every subset of a finite set is finite, and equality of cardinalities for a subset forces equality of the sets (A subset of a finite set is finite, with , and equality holds if and only if ).
A partial order is transitive: implies (Partial order and partially ordered set).
Proof
The antichain has cardinality and lies in both and . Since every antichain of either induced subposet is also an antichain of , both and have width exactly .
Both induced subposets are nonempty because they contain . They are proper subsets of : indeed, would force to be exactly the set of maximal elements, since every maximal element of must then lie in and no can have an element strictly above it. Dually, would force to be exactly the set of minimal elements. By finiteness, each therefore has cardinality strictly smaller than .
By the hypothesis and step 1.1, choose chain covers of and of , indexed so that . Such indexing is possible because each cover has chains, each chain contains at most one member of , and all members of must be covered.
Fix . If and , then for some , so , contradicting that is an antichain. Hence every satisfies . Dually, every satisfies . Thus by transitivity, so is a chain.
The chains cover . Thus they form the required width-sized chain cover of .
Depends on
- A maximal antichain splits a finite poset into its down-set and up-set with the antichain as their intersection
- Height and width of a nonempty finite poset
- A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$
- Partial order and partially ordered set
Used by
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 39 results over 18 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- M. Keller and W. T. Trotter, Applied Combinatorics, §6.4 (standard reference, not scraped)