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.
Birkhoff representation theorem: every finite distributive lattice is isomorphic to the lattice of order ideals of its join-irreducible poset
Statement
Let be a nonempty finite distributive lattice and let be its poset of join-irreducible elements. The map
is a lattice isomorphism. Its inverse sends an order ideal to , with the empty join equal to .
Facts & Assumptions
Given: A nonempty finite distributive lattice , its join-irreducible poset , and the map in the Statement.
Every is the join of the join-irreducible elements below it, and has a bottom (A finite lattice has a bottom and a top, and every element is the join of the join-irreducible elements below it).
Every join-irreducible element of a distributive lattice is join-prime (Every join-irreducible element of a distributive lattice is join-prime).
The order ideals of a finite poset form a distributive lattice under union and intersection (The order ideals of a finite poset form a distributive lattice under union and intersection).
Every subset of a finite set is finite (A subset of a finite set is finite, with , and equality holds if and only if ).
A bijection is a map that is both injective and surjective (Injection, surjection, bijection).
Proof
The poset is finite because it is a subset of . For every , the set is an order ideal of : if and satisfies , then . Thus is well defined.
For an order ideal , construct , taking . Then .
For , one has . Also , because a join-irreducible satisfies exactly when or by [L2].
The map is injective. If , then [L1] writes both and as the join of the same set of join-irreducibles, so .
Conversely, suppose . If , then , forcing , contrary to join-irreducibility. Thus is nonempty. Repeated application of join-primality [L2] to the finite join gives for some . Since is an order ideal, . Hence .
Step 2.3 proves that is surjective, while step 2.2 proves injectivity. Step 2.1 shows that it preserves meets and joins. Moreover [L1] gives , so is its inverse. Therefore is the asserted lattice isomorphism.
Depends on
- A finite lattice has a bottom and a top, and every element is the join of the join-irreducible elements below it
- Every join-irreducible element of a distributive lattice is join-prime
- The order ideals of a finite poset form a distributive lattice under union and intersection
- Injection, surjection, bijection
- 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$
Used by
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 50 results over 23 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
- Archive of Formal Proofs, Birkhoff's Representation Theorem for Finite Distributive Lattices (standard reference, not scraped)
- MIT OpenCourseWare 18.212, Lecture 16: Distributive lattices (standard reference, not scraped)