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.
Height and width of a nonempty finite poset
Definition
Let be a nonempty finite poset. Its height is
and its width is
Here and the cardinalities below are finite cardinalities (The cardinality of a finite set).
The maxima exist. A chain is a subset of whose elements are pairwise comparable and an antichain one whose distinct elements are pairwise incomparable (Chain in a poset, Antichains, chain covers, and antichain covers of a poset); each is a subset of , hence finite with cardinality at most by A subset of a finite set is finite, with , and equality holds if and only if . The possible cardinalities therefore form nonempty subsets of the finite set — the empty subset is vacuously both a chain and an antichain, so occurs, and every singleton is both, so some cardinality occurs. A nonempty finite set of natural numbers has a greatest member, as follows from The well-ordering principle by applying leastness to the corresponding differences from . Thus and are natural numbers with .
The empty poset is excluded so that and are at least : on the empty poset the only chain and the only antichain are empty, so both maxima would be and every statement below with a nonzero lower bound would need a separate convention.
Depends on
Used by
- A maximal antichain of size one in a finite poset of width two Counterexample
- False: every maximal antichain in a finite poset has maximum cardinality False statement
- The down-set and up-set chain covers from a suitable maximum antichain splice to a width-sized chain cover Lemma
- Dilworth's theorem: the minimum number of chains covering a finite poset equals its width Theorem
- Mirsky's theorem: the minimum number of antichains covering a finite poset equals its height Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 37 results over 17 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)