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.

✓ 8 results · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 8 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Chains, Antichains, Sperner and Dilworth — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-07-31Open item page →

The Boolean lattice on four elements: ranks, width, shadows, and a symmetric chain decomposition

Example

Let $A = {1, 2, 3, 4}$ . The Boolean lattice $B (A)$ has rank sizes

$1, 4, 6, 4, 1,$

so its width is $6$ . For $F = {{1, 2}, {1, 3}}$ , both its lower and upper shadows have three members:

$\partial F = {{1}, {2}, {3}}, \nabla F = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}} .$

Facts & Assumptions

Given: The set $A = {1, 2, 3, 4}$ and the family $F$ in the Example.

[F1]

The rank- $k$ level of $B (A)$ is the family of $k$ -subsets (The Boolean lattice of subsets of a finite set and its rank levels).

[F2]

Lower and upper shadows consist of the immediate subsets and supersets one rank away (The lower and upper shadows of a uniform set family).

[L1]

Sperner's theorem says the width of $B (A)$ is its middle binomial coefficient (Sperner's theorem and its equality cases: a largest antichain is a complete middle level).

[L2]

Every finite Boolean lattice has a symmetric chain decomposition (Every finite Boolean lattice has a symmetric chain decomposition).

Verification

technique · direct

1.1

Listing subsets by cardinality gives rank sizes $1, 4, 6, 4, 1$ , and [L1] gives width $6$ .

givenF1L1

1.2

Deleting one element from a member of $F$ gives exactly ${1}, {2}, {3}$ , while adjoining one element gives exactly $123, 124, 134$ . Thus the displayed shadows are correct.

givenF2

1.3

The following symmetric chains partition all sixteen subsets: $\emptyset \subset 1 \subset 12 \subset 123 \subset 1234$ ; $4 \subset 14 \subset 124$ ; $2 \subset 23 \subset 234$ ; $24$ ; $3 \subset 13 \subset 134$ ; and $34$ . Their endpoint ranks sum to $4$ , in agreement with [L2].

F1L2

2.1

Steps 1.1, 1.2, and 1.3 verify the ranks, width, shadows, and an explicit symmetric chain decomposition.

step 1.1step 1.2step 1.3∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-07-31Open item page →

A six-element poset of width three and a three-chain cover

Example

Let $P = {a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}}$ with $a_{i} < b_{i}$ for each $i$ , and no other comparabilities between distinct elements. Then ${a_{1}, a_{2}, a_{3}}$ is an antichain, and

${a_{1} < b_{1}}, {a_{2} < b_{2}}, {a_{3} < b_{3}}$

is a chain cover. The width is exactly $3$ , and this cover is minimum.

Facts & Assumptions

Given: The six-element poset $P$ described in the Example.

[L1]

In a finite poset, the minimum number of chains in a chain cover equals the width (Dilworth's theorem: the minimum number of chains covering a finite poset equals its width).

Verification

technique · direct

1.1

The set ${a_{1}, a_{2}, a_{3}}$ is an antichain, so the width is at least $3$ .

given

1.2

Every antichain contains at most one element from each comparable pair ${a_{i}, b_{i}}$ , so it has at most $3$ elements. Hence the width is exactly $3$ .

given

1.3

The three displayed two-element chains cover all six elements, so they form a chain cover of cardinality $3$ .

given

2.1

By steps 1.2 and 1.3, and equivalently by [L1], the displayed cover has the minimum possible number of chains.

step 1.2step 1.3L1∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-07-31Open item page →

The divisors of $60$ form a finite distributive lattice and realize Birkhoff's representation concretely

Example

Order the positive divisors of $60$ by divisibility. Since $60 = 2^{2} \cdot 3 \cdot 5$ , every divisor has a unique form

$2^{α} 3^{β} 5^{γ}, 0 \leq α \leq 2, 0 \leq β, γ \leq 1.$

Divisibility is componentwise comparison of the exponent triples. Meet and join are componentwise minimum and maximum, so this is a finite distributive lattice.

Facts & Assumptions

Given: The positive divisors of $60$ , ordered by divisibility.

[L1]

Every positive integer has a prime factorization unique up to order (The fundamental theorem of arithmetic: every integer $n \geq 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i < r} p_{i} = \prod_{j < s} q_{j}$ with every $p_{i}$ and $q_{j}$ prime, then $r = s$ and $q_{i} = p_{π (i)}$ for some $π \in Sym (r)$ ).

[L2]

Every finite distributive lattice is isomorphic to the order-ideal lattice of its join-irreducible poset (Birkhoff representation theorem: every finite distributive lattice is isomorphic to the lattice of order ideals of its join-irreducible poset).

Verification

technique · direct

1.1

By [L1], the exponent-triple description is unique, and $d ∣ e$ exactly when every exponent of $d$ is at most the corresponding exponent of $e$ .

givenL1

2.1

Componentwise minimum and maximum give the greatest common divisor and least common multiple, and the distributive identities hold coordinatewise for minimum and maximum on chains. Thus the divisor poset is a finite distributive lattice.

step 1.1algebra

2.2

Its join-irreducibles are $2, 4, 3, 5$ . In their inherited order, $2 < 4$ and $3, 5$ are incomparable with these and with each other.

step 1.1

3.1

A divisor $d$ maps to the order ideal of join-irreducibles dividing it: its $2$ -exponent chooses $\emptyset$ , ${2}$ , or ${2, 4}$ , while its $3$ - and $5$ -exponents independently choose whether to include $3$ and $5$ . This is exactly the Birkhoff map of [L2].

step 2.2L2

4.1

Hence the divisors of $60$ concretely realize Birkhoff's representation as the order ideals of the poset $2 < 4$ with isolated elements $3$ and $5$ .

step 2.1step 3.1∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-07-31Open item page →

Four explicit petals with a common two-element core form a sunflower

Example

The four sets

${1, 2, 3, 4}, {1, 2, 5, 6}, {1, 2, 7, 8}, {1, 2, 9, 10}$

form a $4$ -petal sunflower. Their common core is ${1, 2}$ and their petals are the pairwise disjoint sets ${3, 4}$ , ${5, 6}$ , ${7, 8}$ , and ${9, 10}$ .

Facts & Assumptions

Given: The four sets displayed in the Example.

[F1]

Distinct sets form a sunflower when all pairwise intersections equal one common core (Sunflowers, petals, and their common core).

Verification

technique · direct

1.1

Every displayed set contains ${1, 2}$ , and outside this pair their elements lie in disjoint two-element blocks.

given

2.1

Therefore the intersection of any two distinct displayed sets is exactly ${1, 2}$ .

step 1.1

3.1

By [F1], the four sets form a sunflower with the stated core and petals.

step 2.1F1∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-07-31Open item page →

All $k$ -sets through a fixed point form an intersecting family attaining the Erdős-Ko-Rado bound

Example

Let $A$ be an $n$ -element set with $1 \leq k$ and $n \geq 2 k$ , and fix $a \in A$ . The star

$S_{a} = {S \in [A]^{k} : a \in S}$

is intersecting and has cardinality $(\binom{n - 1}{k - 1})$ , attaining the Erdős-Ko-Rado bound.

Facts & Assumptions

Given: An $n$ -element set $A$ , natural numbers $1 \leq k$ and $n \geq 2 k$ , and a point $a \in A$ .

[L1]

Erdős-Ko-Rado bounds an intersecting family of $k$ -subsets by $(\binom{n - 1}{k - 1})$ and states that a star attains the bound (Erdős-Ko-Rado theorem: for $1 \leq k$ and $n \geq 2 k$ , an intersecting family of $k$ -subsets of an $n$ -set has size at most $(\binom{n - 1}{k - 1})$ , and a star attains the bound).

[F1]

$(\binom{m}{j})$ counts the $j$ -subsets of an $m$ -element set (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

Verification

technique · direct

1.1

Any two members of $S_{a}$ intersect at $a$ , so the star is intersecting.

given

1.2

The map $S \mapsto S ∖ {a}$ is a bijection from $S_{a}$ to the $(k - 1)$ -subsets of $A ∖ {a}$ . Hence $∣ S_{a} ∣ = (\binom{n - 1}{k - 1})$ .

givenF1

2.1

By [L1], step 1.2 equals the universal upper bound, so the star is extremal.

step 1.1step 1.2L1∎

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-07-31Open item page →

A maximal antichain of size one in a finite poset of width two

Statement refuted

The false statement False: every maximal antichain in a finite poset has maximum cardinality claims that every maximal antichain in a finite poset has maximum cardinality.

Facts & Assumptions

Given: The poset $P = {a, b, c}$ with $a < b$ , $a < c$ , and $b, c$ incomparable.

[F1]

An antichain is maximal when no larger antichain contains it, and maximum when no antichain has greater cardinality; the width is the maximum cardinality of an antichain (Antichains, chain covers, and antichain covers of a poset, Height and width of a nonempty finite poset).

Counterexample

technique · direct

1.1

The singleton ${a}$ is an antichain and cannot be enlarged, since both $b$ and $c$ are comparable with $a$ .

givenF1

1.2

The pair ${b, c}$ is an antichain. No three-element antichain exists, because the only three-element subset is $P$ itself and it contains the comparable pair $a, b$ ; hence the width of $P$ is $2$ .

givenF1

2.1

Thus ${a}$ is maximal of cardinality $1$ but not maximum, providing the required counterexample.

step 1.1step 1.2∎

Remarks


\node[font=\scriptsize,anchor=north] at (0,-.65) {maximal antichain $\{a\}$}; \draw[blue!75!black,dashed] (-2.05,2.2)--(2.05,2.2); \node[font=\scriptsize,anchor=south] at (0,2.27) {maximum antichain $\{b,c\}$}; \end{tikzpicture} ```

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-07-31Open item page →

When $k < n < 2 k$ , the entire $k$ th level is intersecting and exceeds the Erdős-Ko-Rado star bound

Statement refuted

The false statement False: the Erdős-Ko-Rado bound holds without the hypothesis $n \geq 2 k$ claims the Erdős-Ko-Rado star bound without assuming $n \geq 2 k$ .

Facts & Assumptions

Given: Natural numbers satisfying exactly $k < n < 2 k$ , an $n$ -element set $A$ , and the full level $F = [A]^{k}$ .

[F1]

An intersecting family has nonempty intersection between every pair of members, and $(\binom{n}{k}) = ∣ [A]^{k} ∣$ (Intersecting uniform families of finite sets, The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

[L1]

The binomial closed formula gives $(\binom{n}{k}) = \frac{n}{k} (\binom{n - 1}{k - 1})$ for $1 \leq k \leq n$ ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ ).

Counterexample

technique · direct

1.1

If $S, T \in [A]^{k}$ were disjoint, then $∣ S \cup T ∣ = 2 k > n = ∣ A ∣$ , impossible. Hence the entire level $F$ is intersecting.

givenF1

1.2

By [L1], $∣ F ∣ = (\binom{n}{k}) = (n / k) (\binom{n - 1}{k - 1})$ . Since $k < n$ , the factor $n / k$ is greater than $1$ , so $∣ F ∣ > (\binom{n - 1}{k - 1})$ .

givenF1L1algebra

2.1

Thus for every $k < n < 2 k$ , the full $k$ th level is an intersecting family larger than a star, refuting the bound outside its stated range.

step 1.1step 1.2∎

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-07-31Open item page →

The diamond $M_{3}$ and pentagon $N_{5}$ violate distributivity by explicit joins and meets

Statement refuted

Every finite lattice is distributive.

Facts & Assumptions

Given: The diamond $M_{3} = {0, 1, a, b, c}$ , where $a, b, c$ are incomparable atoms, and the pentagon $N_{5} = {0, a, b, c, 1}$ , where $0 < a < b < 1$ , $0 < c < 1$ , and $c$ is incomparable with $a, b$ .

[F1]

Distributivity requires $x \land (y \lor z) = (x \land y) \lor (x \land z)$ for all elements (Lattices, distributive lattices, and order ideals).

Counterexample

technique · direct

1.1

In $M_{3}$ , one has $b \lor c = 1$ , $a \land b = 0$ , and $a \land c = 0$ . Therefore $a \land (b \lor c) = a$ , while $(a \land b) \lor (a \land c) = 0$ .

givenF1

1.2

In $N_{5}$ , one has $a \lor c = 1$ , $b \land a = a$ , and $b \land c = 0$ . Therefore $b \land (a \lor c) = b$ , while $(b \land a) \lor (b \land c) = a$ .

givenF1

2.1

Since $a \neq 0$ in $M_{3}$ and $a \neq b$ in $N_{5}$ , each lattice violates the distributive identity in [F1]. Both are finite, so either one refutes the Statement.

step 1.1step 1.2F1∎

Remarks


\node[font=\normalsize] at (2.8,3.35) {$N_5$}; \node[elt] (n0) at (2.2,0) {$0$}; \node[elt] (na) at (1.5,.95) {$a$}; \node[elt] (nb) at (1.5,2.05) {$b$}; \node[elt] (nc) at (4.1,1.45) {$c$}; \node[elt] (n1) at (2.2,2.9) {$1$}; \draw[gray!75] (n0)--(na)--(nb)--(n1) (n0)--(nc)--(n1); \end{tikzpicture} ```

Chains, Antichains, Sperner and Dilworth — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The Boolean lattice on four elements: ranks, width, shadows, and a symmetric chain decomposition

Example

Facts & Assumptions

Verification

A six-element poset of width three and a three-chain cover

Example

Facts & Assumptions

Verification

The divisors of 6060 form a finite distributive lattice and realize Birkhoff's representation concretely

Example

Facts & Assumptions

Verification

Four explicit petals with a common two-element core form a sunflower

Example

Facts & Assumptions

Verification

All kk-sets through a fixed point form an intersecting family attaining the Erdős-Ko-Rado bound

Example

Facts & Assumptions

Verification

A maximal antichain of size one in a finite poset of width two

Statement refuted

Facts & Assumptions

Counterexample

Remarks

When k<n<2kk<n<2k, the entire kkth level is intersecting and exceeds the Erdős-Ko-Rado star bound

Statement refuted

Facts & Assumptions

Counterexample

The diamond M3M3​ and pentagon N5N5​ violate distributivity by explicit joins and meets

Statement refuted

Facts & Assumptions

Counterexample

Remarks

Sources

The divisors of $60$ form a finite distributive lattice and realize Birkhoff's representation concretely

All $k$ -sets through a fixed point form an intersecting family attaining the Erdős-Ko-Rado bound

When $k < n < 2 k$ , the entire $k$ th level is intersecting and exceeds the Erdős-Ko-Rado star bound

The diamond $M_{3}$ and pentagon $N_{5}$ violate distributivity by explicit joins and meets