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.
A finite lattice has a bottom and a top, and every element is the join of the join-irreducible elements below it
Statement
Every nonempty finite lattice has a least element and a greatest element . Moreover, every is the join of the join-irreducible elements . For this is the empty join.
Facts & Assumptions
Given: A nonempty finite lattice .
Every pair in a lattice has a meet and a join (Lattices, distributive lattices, and order ideals).
A join-irreducible element is non-bottom and cannot be written as a join of two strictly smaller elements (Join-irreducible elements of a nonempty finite lattice).
Every nonempty subset of has a least element; a subset of a finite set is finite, and a proper subset has strictly smaller cardinality (The well-ordering principle, A subset of a finite set is finite, with , and equality holds if and only if ).
Proof
Since is nonempty and finite, [L1] lets us choose for which the principal ideal has least cardinality. If , then is a proper subset of and [L1] makes its cardinality strictly smaller, contradicting that choice, so is minimal. If is another minimal element, then , so minimality gives . Thus the minimal element is unique and lies below every , because forces . Call it .
Dually, choosing an element whose principal filter has least cardinality gives a unique maximal element , and every lies below it.
We prove the decomposition of by induction on the cardinality of its principal ideal . For , the empty join is .
Assume every element with a smaller principal ideal is the join of the join-irreducibles below it.
If is join-irreducible, then itself is the required one-term join.
If is not join-irreducible, there are with . The principal ideals of and are proper subsets of , so [L1] gives each strictly smaller cardinality and the induction hypothesis writes each as a join of join-irreducibles below it. Joining those two finite families writes as a join of join-irreducibles below .
In every case, steps 2.1, 4.1 and 4.2 give a finite subfamily of the join-irreducibles below whose join is . Let be the set of all join-irreducibles below . Since every member of is at most , its finite join is at most ; since , that join is also at least . Hence is the join of all members of .
Step 5.1 proves the decomposition for every , while steps 1.1 and 1.2 provide the bottom and top.
Depends on
Used by
Cited to discharge well-definedness by Join-irreducible elements of a nonempty finite lattice.
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
- MIT OpenCourseWare 18.212, Lecture 16: Distributive lattices (standard reference, not scraped)