
Key concepts for Boolean Algebra
USE THE EDITFIND BROWSER OPTION TO SEARCH
Back to the M567 course page
 Semigroup ( S , × )

Set S with associative multiplication: x × ( y × z ) = ( x × y ) × z.
 Semilattice ( S , × )

Commutative ( x × y = y × x ) and idempotent ( x × x = x ) semigroup.
 Meet semilattice ( S , · )

Semilattice with order x < _{·} y iff x = x · y .
 Join semilattice ( S , + )

Semilattice with order x < _{+} y iff y = x + y .
 Lattice ( S , + , · )

Set S with join semilattice structure ( S , + ) and meet semilattice structure ( S , · ) such that x < _{+} y iff x < _{·} y .
 Absorptive laws

x · ( x + y ) = x and x + ( x · y ) = x .
 Monoid ( S , × , e)

Semigroup ( S , × ) with identity element: e × x = x = x × e .
 Bounded semilattice ( S , × , e)

Commutative idempotent monoid.
 Bounded meet semilattice ( S , · , 1)

x < _{·} 1 for all x in S .
 Bounded join semilattice ( S , + , 0 )

0 < _{+} x for all x in S .
 Bounded lattice ( S , + , · , 0 , 1)

0 < x < 1 for all x in S .
 Distributive lattice ( S , + , · )

x · ( y + z ) = ( x · y ) + ( x · z ) and x + ( y · z ) = ( x + y ) · ( x + z ) .
 Complement (in bounded distributive lattice)

x' · x = 0 and x' + x = 1 .
 Boolean algebra ( S , + , · , 0 , 1 , ' )

Bounded distributive lattice ( S , + , · , 0 , 1) ,
x'' = x , 0' = 1 , x' · x = 0 and x' + x = 1 .
 De Morgan laws

x' · y' = ( x + y ) ' and ( x · y ) ' = x' + y' .
 Symmetric difference/exclusive or (in Boolean algebra)

x xor y = ( x · y' ) + ( x' · y ) .
 Boolean ring

Ring with 1 and x^{2} = x .
 Implication in Boolean algebra

( c > a ) = c ' + a.
 Heyting algebra ( S , + , · , 0 , 1 , > )

Bounded lattice with (c · x) < a iff x < ( c >a ) .
 Identities for a Heyting algebra ( S , + , · , 0 , 1 , > )

Bounded lattice identities, together with:

(a >a) = 1 ;

a · (a >b) = a · b ;

b · (a >b) = b ;

a > (b · c) = (a >b) · (a >c) .
 Pseudocomplement x ' in Heyting algebra

x ' = ( x > 0 ) .
 Topology on set X

Subset of the power set of X, including X and the empty set, closed under finite intersections and arbitrary unions.
 Mal'tsev operation

P ( x , x , y ) = y = P ( y , x , x ) .
 Galois connection

Left adjoint
F : ( S , < ) > ( R , > )
and right adjoint
G : ( R , > ) > ( S , < )
functors between poset categories, so
x^{F} > a in R iff x < a^{G} in S .
 Closed elements in Galois connection

Image elements x^{F} in R for x in S and a^{G} in S for a in R .
 Galois correspondence

Mutually inverse isomorphisms F and G between corresponding sets of closed elements.
 Complete meet semilattice ( S, < )

Has all products (greatest lower bounds or infima), including empty product 1 .
 Free complete join semilattice on set X

Set of all subsets of X under union.
 Free join semilattice on set X

Set of all finite nonempty subsets of X under union.
 Free bounded join semilattice on set X

Set of all finite subsets of X under union.
 Free distributive lattice on set X .

Set of all finite antichains in free semilattice on X .
 Order in free distributive lattice on set X .

Antichain P not greater than antichain Q iff each element of P is dominated by an element of Q .
 Subsemigroup in semigroup ( S , × )

Subset W with x × y in W if x and y in W .
 Wall in semigroup ( S , × )

Subset W with x × y in W if and only if x and y in W .
 Ideal

Wall in join semilattice.
 Filter

Wall in meet semilattice.
 Prime ideal in a lattice

Ideal whose complement is a filter.
 Prime filter in a lattice

Filter whose complement is an ideal.
 Ideal of bounded join semilattice

Kernel of bounded join semilattice homomorphism.
 Ideal of distributive lattice

Kernel of lattice homomorphism.
 Prime ideal of lattice

Kernel of lattice homomorphism to 2.
 Maximal ideal of distributive lattice

Maximal proper ideal, necessarily prime.
 Frame ( S , + , · , 0 , 1)

 Bounded distributive lattice ( S , + , · , 0 , 1) ;
 Complete join semilattice ( S , < _{+} ) ;
 Infinite distributivity:
x · sup X = sup ( x · X )
for element x and subset X of S .
 Frame examples

 Power set 2^{X} of a set X .
 Set W(X) of open sets of a topological space X .
 Frame homomorphism

Bounded lattice homomorphism preserving arbitrary joins.
 Free frame on set X

Set of all downsets in free bounded meet semilattice on X .
 Category Loc of locales

Opposite of category Frm of frames.
 Point p of locale A

Frame homomorphism p : A > 2 .
 Prime element a of locale A

Downset a ^{>} is a prime ideal.
 Space Pt A of points of locale A

Set Pt A of prime elements or points of locale A , with topology (set of open sets) given by the image f(A) of the frame homomorphism
f : A > 2^{Pt A}
taking frame element a to those points p mapping a to 1 .
 Functor W : Top
> Loc

Continuous map f : X > Y taken to opposite of
f ^{1} : W(Y) > W(X) .
 Functor Pt : Loc
> Top right adjoint to W : Top > Loc


Counit is opposite of frame homomorphism
f : A > W(Pt A) .

Unit is continuous map
y : X > Pt W(X)
taking an element x of X to the complement of the closure of {x}.

Spatial locale A

Frame homomorphism
f : A > W(Pt A)
is an isomorphism.

Sober topological space X

Map
y : X > Pt W(X)
bijects.

T_{0}space X

Distinct points are not members of exactly the same open sets
[y : X > Pt W(X) injects].

T_{1}space or Fréchet space

Distinct points contained in distinct open neighborhoods.

T_{2}space or Hausdorff space

Distinct points contained in disjoint open neighborhoods.

Specialization order on T_{0}space X

x < y if and only if x lies in the closure of
the singleton {y} .

Alexandrov topology on a poset

Open sets are the upper sets of the poset.

Directed poset

Any two elements have an upper bound.

Compact (or "finite") element k of complete join semilattice A

If k < sup S for subset S of A ,
then k < sup F for finite subset F of S .

Equivalent characterizations of compact elements

May replace "subset S " by
"directed subset S " or
"ideal S " .

Algebraic complete join semilattice

Each element is a join of compact elements.

Coherent locale or frame


Algebraic, and:

Compact elements form a subboundedlattice.

Coherent frame morphism

Frame homomorphism sending compact elements to compact elements.
 Category CohLoc of coherent locales

Opposite of category CohFrm of coherent frames and coherent frame morphisms.
 Category DLat

Category of bounded distributive lattices.
 Functor J : DLat
> CohLoc

Sends a (bounded) distributive lattice L to the coherent locale L^{J} of ideals of L .
 Functor K : CohLoc
> DLat

Sends a coherent locale A to the bounded distributive lattice A^{K} of compact elements of A .

Coherent topological space X

Sober space X, for which the locale W(X) of open sets is coherent.

Spectrum Spec(L) of bounded distributive lattice L

Space of prime ideals P of lattice L .

Topology on spectrum Spec(L)

A prime ideal P lies in the open set determined by an ideal I of L if and only if P does not contain I .

Stone Representation Theorem for Distributive Lattices

Each bounded distributive lattice is represented as the lattice of compact open sets of its spectrum, a coherent space.

Separated topological space

A union of disjoint, nonempty open sets.

Connected topological space

Not separated.

Totally disconnected topological space

The only connected subspaces are singletons.

Totally separated ( " super  T_{2} " ) topological space

For each pair of distinct points x , y , there is a clopen subset U such that U contains x and the complement U ' contains y .

Basis of a topological space

Set of (open) subsets such that, for each element x of the intersection of two basic open sets, the point x lies in another basic set contained within the intersection.

Topology determined by a basis

Open sets are unions of basic open sets.

Zerodimensional topological space

Clopen subsets form a basis.

Stone space

Satisfies any of the following equivalent conditions:
 Compact, Hausdorff, totally disconnected;
 Compact, totally separated;
 Compact, T_{0} , zerodimensional;
 Coherent and Hausdorff.

Stone Representation Theorem for Boolean Algebras

Each Boolean algebra is represented as the algebra of clopen sets of its spectrum, a coherent Hausdorff space.
 Filter on set X

Filter in power set 2^{X} of X .
 Ultrafilter on set X

Maximal (proper) filter in power set 2^{X} of X .
 Neighborhood filter N ( x ) for element x of topological space X

Set of all subsets of X that contain a neighborhood of x .
 Limit Lim F = x of filter F on topological space X

Filter F contains neighborhood filter N ( x ) .

Compact space

Existence of limits.

Hausdorff space

Uniqueness of limits.

