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.
Mirsky's theorem: the minimum number of antichains covering a finite poset equals its height
Statement
Let be a nonempty finite poset of height . Then can be covered by antichains, and no cover by fewer antichains exists. Thus the minimum number of antichains in an antichain cover of equals .
Facts & Assumptions
Given: A nonempty finite poset with height .
A chain is a subset of pairwise comparable elements; an antichain is a subset of pairwise incomparable elements; and an antichain cover has union (Chain in a poset, Antichains, chain covers, and antichain covers of a poset).
The height is the maximum cardinality of a chain in (Height and width of a nonempty finite poset).
Every nonempty subset of has a least element (The well-ordering principle); equivalently, every nonempty finite bounded collection of natural numbers has a greatest element.
Proof
For each , let be the greatest cardinality of a chain whose largest element is . Such a chain exists, since is one, and the greatest cardinality exists because the possible values form a nonempty finite subset of .
Let be a chain of cardinality , which exists by [F2]. Every antichain contains at most one element of , so any antichain cover of needs at least members to cover the elements of .
If , then appending to a chain of cardinality ending at gives a chain ending at , so .
For put . Each is an antichain, since comparable distinct elements have different -values by step 2.1.
Every belongs to exactly one , and by the definition of height, so cover .
Step 4.1 gives an antichain cover with members and step 1.2 rules out every smaller one. Hence the minimum antichain-cover number is .
Depends on
Used by
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 32 results over 14 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)