Distributive lattice

Both views and their mutual correspondence are discussed in the article on lattices.

In the present situation, the algebraic description appears to be more convenient.

A lattice (L,∨,∧) is distributive if the following additional identity holds for all x, y, and z in L: Viewing lattices as partially ordered sets, this says that the meet operation preserves non-empty finite joins.

It is a basic fact of lattice theory that the above condition is equivalent to its dual:[1] In every lattice, if one defines the order relation p≤q as usual to mean p∧q=p, then the inequality x ∧ (y ∨ z) ≥ (x ∧ y) ∨ (x ∧ z) and its dual x ∨ (y ∧ z) ≤ (x ∨ y) ∧ (x ∨ z) are always true.

[3][4] However, independence proofs were given by Schröder, Voigt,(de) Lüroth, Korselt,[5] and Dedekind.

Note that this is not the same as being a subset that is a lattice under the original order (but possibly with different join and meet operations).

An alternative way of stating the same fact is that every distributive lattice is a subdirect product of copies of the two-element chain, or that the only subdirectly irreducible member of the class of distributive lattices is the two-element chain.

For example, an element of a distributive lattice is meet-prime if and only if it is meet-irreducible, though the latter is in general a weaker property.

[7] If a lattice is distributive, its covering relation forms a median graph.

That set union and intersection are indeed distributive in the above sense is an elementary fact.

Generalizing this result to infinite lattices, however, requires adding further structure.

The original lattice is recovered as the collection of clopen lower sets of this space.

However, the proofs of both statements require the Boolean prime ideal theorem, a weak form of the axiom of choice.

The first observation is that, using the laws of distributivity, every term formed by the binary operations

are finite subsets of G. However, it is still possible that two such terms denote the same element of the distributive lattice.

Consequently, a set of finite subsets of G will be called irredundant whenever all of its elements

are mutually incomparable (with respect to the subset ordering); that is, when it forms an antichain of finite sets.

The verification that this structure is a distributive lattice with the required universal property is routine.

If empty joins and empty meets are disallowed, the resulting free distributive lattices have two fewer elements; their numbers of elements form the sequence