 ## Key concepts for Boolean Algebra

USE THE EDIT-FIND 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  x2 = 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:
1. (a ->a) = 1 ;
2. a · (a ->b) = a · b ;
3. b · (a ->b) = b ;
4. 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
F : ( S , < ) --> ( R , > )
G : ( R , > ) --> ( S , < )
functors between poset categories, so
xF > a  in  R  iff  x < aG  in  S .
Closed elements in Galois connection
Image elements  xF  in  R  for  x  in  S  and  aG  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 non-empty 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)
1. Bounded distributive lattice  ( S , + , · , 0 , 1) ;
2. Complete join semilattice  ( S , < + ) ;
3. Infinite distributivity:
x · sup X  =  sup ( x · X )
for element  x  and subset  X  of  S .
Frame examples
1. Power set 2X of a set  X .
2. 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 --> 2Pt 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
1. Counit is opposite of frame homomorphism
f : A --> W(Pt A) .
2. 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.
T0-space  X
Distinct points are not members of exactly the same open sets
[y : X --> Pt W(X) injects].
T1-space or Fréchet space
Distinct points contained in distinct open neighborhoods.
T2-space or Hausdorff space
Distinct points contained in disjoint open neighborhoods.
Specialization order on T0-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
1. Algebraic, and:
2. Compact elements form a sub-bounded-lattice.
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  LJ  of ideals of  L .
Functor  K : CohLoc
--> DLat
Sends a coherent locale  A  to the bounded distributive lattice  AK  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, non-empty open sets.
Connected topological space
Not separated.
Totally disconnected topological space
The only connected subspaces are singletons.
Totally separated ( " super - T2 " ) 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.
Zero-dimensional topological space
Clopen subsets form a basis.
Stone space
Satisfies any of the following equivalent conditions:
1. Compact, Hausdorff, totally disconnected;
2. Compact, totally separated;
3. Compact, T0 , zero-dimensional;
4. 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 2X of  X .
Ultrafilter on set  X
Maximal (proper) filter in power set 2X 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.