Wikipedia 10K Redux by Reagle from Starling archive. Bugs abound!!!

<-- Previous | Newer --> | Current: 980274539 UNKNOWN at Tue, 23 Jan 2001 18:28:59 +0000.


A lattice is a PartialOrderedSet (X, <=) where any two elements x,y have both a GreatestLowerBound xvy and LeastUpperBound x^y.

The operations v,^ on a lattice form an algebraic structure satisfying the following properties:

    ava=a                   a^a=a                   (idempotency laws)
    avb=bva                 a^b=b^a                 (commutativity laws)
    av(bvc)=(avb)vc         a^(b^c)=(a^b)^c         (associativity laws)
    av(a^b)=a               a^(bvc)=a               (absorption laws)

Moreover, any algebra satisfying the above properties is a lattice, where x<=y is defined to be true if and only if xvy=y (or equivalently, x^y=x).

A lattice which satisfies the following properties is referred to as a boolean algebra:

    There exists some element 0, such that av0=a for all a                 (bounded below)
    There exists some element 1, such that a^1=a for all a                 (bounded above)
    For all a,b,c, (avb)^c=(a^c)v(b^c) and (a^b)vc=(avc)^(bvc)             (distributive laws - these are equivalent)
    For every a, there exists an element ~a such that av~a=1 and a^~a=0    (existence of complements)

Complements are unique within bounded distributive lattices.  Boolean algebrae are very similar to RinGs, except they have complements instead of inverses, and moreover the distributive laws work for each operation over the other.

The subobjects of any given object form a boolean algebra under <= taken to mean "is a subobject of".  In the case of sets, v and ^ become unions and intersections; in the case of groups they become semidirect products and intersections, and so forth.