Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-07-31
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 PP be a nonempty finite poset of height h(P)h(P). Then PP can be covered by h(P)h(P) antichains, and no cover by fewer antichains exists. Thus the minimum number of antichains in an antichain cover of PP equals h(P)h(P).

Facts & Assumptions

Given: A nonempty finite poset PP with height h:=h(P)h:=h(P).

[F1]

A chain is a subset of pairwise comparable elements; an antichain is a subset of pairwise incomparable elements; and an antichain cover has union PP (Chain in a poset, Antichains, chain covers, and antichain covers of a poset).

[F2]

The height h(P)h(P) is the maximum cardinality of a chain in PP (Height and width of a nonempty finite poset).

[L1]

Every nonempty subset of N\mathbb N has a least element (The well-ordering principle); equivalently, every nonempty finite bounded collection of natural numbers has a greatest element.

Proof

technique · direct
1.1

For each xPx\in P, let r(x)r(x) be the greatest cardinality of a chain whose largest element is xx. Such a chain exists, since {x}\{x\} is one, and the greatest cardinality exists because the possible values form a nonempty finite subset of {1,,P}\{1,\ldots,|P|\}.

givenF1L1
1.2

Let CC be a chain of cardinality hh, which exists by [F2]. Every antichain contains at most one element of CC, so any antichain cover of PP needs at least hh members to cover the hh elements of CC.

F1F2
2.1

If x<yx<y, then appending yy to a chain of cardinality r(x)r(x) ending at xx gives a chain ending at yy, so r(y)r(x)+1r(y)\ge r(x)+1.

step 1.1F1
3.1

For i{1,,h}i\in\{1,\ldots,h\} put Ai:={xP:r(x)=i}A_i:=\{x\in P:r(x)=i\}. Each AiA_i is an antichain, since comparable distinct elements have different rr-values by step 2.1.

step 2.1F1
4.1

Every xPx\in P belongs to exactly one AiA_i, and 1r(x)h1\le r(x)\le h by the definition of height, so A1,,AhA_1,\ldots,A_h cover PP.

step 1.1step 3.1F2
5.1

Step 4.1 gives an antichain cover with hh members and step 1.2 rules out every smaller one. Hence the minimum antichain-cover number is h(P)h(P).

step 4.1step 1.2

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