\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{BoolAlg}

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{definition}{Definition}\dotfill \pageref*{definition} \linebreak
\noindent\hyperlink{free_boolean_algebras}{Free Boolean algebras}\dotfill \pageref*{free_boolean_algebras} \linebreak
\noindent\hyperlink{StoneDuality}{Stone duality}\dotfill \pageref*{StoneDuality} \linebreak
\noindent\hyperlink{in_weak_foundations}{In weak foundations}\dotfill \pageref*{in_weak_foundations} \linebreak


\hypertarget{definition}{}\subsection*{{Definition}}\label{definition}

\textbf{$Bool Alg$} is the [[category]] whose [[objects]] are [[boolean algebras]] and whose [[morphisms]] are lattice [[homomorphisms]], that is [[functions]] which preserve finitary [[meets]] and [[joins]] (equivalently, binary meets and joins and the [[top]] and [[bottom]] elements); it follows that the homomorphisms preserve [[negation]]. $Bool Alg$ is a [[subcategory]] of [[Pos]], in fact a [[replete subcategory]] of both [[DistLat]] and [[HeytAlg]].

$Bool Alg$ is given by a finitary [[variety of algebras]], or equivalently by a [[Lawvere theory]], so it has all the usual properties of such categories. As usual, the [[Lawvere theory]] is the category opposite to the category of [[finitely generated object|finitely generated]] [[free object|free]] Boolean algebras.

\hypertarget{free_boolean_algebras}{}\subsection*{{Free Boolean algebras}}\label{free_boolean_algebras}

The free Boolean algebra $Bool(X)$ generated by a finite set $X$ is isomorphic to the \emph{double [[power set]]} $\mathcal{P}\mathcal{P}X$ of $X$; an element $a$ of $X$ is interpreted as the set of all those [[subsets]] of $X$ to which $a$ belongs, and the boolean algebra operations on the [[intersection]] and [[union]] as usual.

The \textbf{free Boolean algebra} on an arbitrary set $X$ is more complicated; it can be described in several ways. By [[abstract nonsense]], it can be described as a [[filtered colimit]] of finitely generated free Boolean algebras

\begin{displaymath}
Bool(X) = colim_{S \subseteq\subseteq X} Bool(S)
\end{displaymath}
(where $\subseteq\subseteq$ indicates a [[finite set|finite subset]]) in the category of Boolean algebras; here the colimit is over the [[directed system]] of finite subsets and inclusions between them.

A second, more concrete description is

\begin{displaymath}
Bool(X) = \mathcal{P}_{fin} \mathcal{P}_{fin} X
\end{displaymath}
where $\mathcal{P}_{fin}(X)$ denotes the set of [[Dedekind finite set|Dedekind finite]] [[subset]]s of $X$.

However, the Boolean operations are not what one might naively expect. The simplest way of describing the operations might be to consider Boolean algebras as equivalent to [[Boolean ring]]s (where binary addition is given by [[symmetric difference]]), and consider the construction of free Boolean rings by analogy with [[polynomial algebra]] constructions, where one forms the free [[vector space]] generated by a monoid of monomials.

Thus, in the first place, the monoid $M = \mathcal{P}_{fin} X$ (where the multiplication is given by [[intersection]]) can be seen as the free commutative idempotent monoid (that is the [[free semilattice]]) on $X$. In the second place,

\begin{displaymath}
Bool(S) = \mathcal{P}_{fin} M
\end{displaymath}
is seen as the free $\mathbb{F}_2$-vector space on $M$, where binary addition is given by symmetric difference of two finite subsets of $M$. The multiplication on $Bool(S)$ is inherited from multiplication on $M$, with the help of the distributive law.

(The naive prescription, where one uses the usual intersection and union on the Boolean algebra $\mathcal{P}_{fin} {|M|}$, is guaranteed to fail because this is an [[atomic Boolean algebra]], whereas the free Boolean algebra on an infinite set $X$ is atomless.)

A third description comes from Stone duality (see below).

\hypertarget{StoneDuality}{}\subsection*{{Stone duality}}\label{StoneDuality}

Classical [[Stone duality]] comes about as follows. The two-element Boolean algebra can be regarded as a Boolean algebra object $\mathbf{2}$ in the category of [[compact Hausdorff spaces]] $CH$. Thus, for each finitary Boolean algebra operation $\theta\colon \mathbf{2}^n \to \mathbf{2}$, there is a corresponding operation on the representable functor $CH(-, \mathbf{2}): CH^{op} \to Set$ given by

\begin{displaymath}
CH(-, \mathbf{2})^n \cong CH(-, \mathbf{2}^n) \stackrel{CH(-, \theta)}{\to} CH(-, \mathbf{2})
\end{displaymath}
and therefore we obtain a lift

\begin{displaymath}
CH(-, \mathbf{2}): CH^{op} \to BoolAlg
\end{displaymath}
A \emph{[[Stone space]]} is by definition a totally disconnected compact Hausdorff space. Let $Stone \hookrightarrow CH$ denote the full subcategory of Stone spaces.

\begin{uthm}
The representable functor restricts to an [[equivalence of categories]] $Stone^{op} \to BoolAlg$.

\end{uthm}
This important theorem can be exploited to give a third description of the free Boolean algebra on a set $X$:

\begin{displaymath}
Bool(X) \cong CH(2^X, \mathbf{2})
\end{displaymath}
where $2$ denotes the 2-element compact Hausdorff space, and $2^X$ the product space $\prod_X 2$. Indeed, the inverse equivalence

\begin{displaymath}
BoolAlg^{op} \to Stone
\end{displaymath}
takes a Boolean algebra $B$ to its [[spectrum]], i.e., the space of Boolean algebra maps $Bool(B, 2)$ (\emph{this} $2$ is the two-element Boolean algebra $\mathbb{Z}_2$!) equipped with the [[Zariski topology]]. Applied to $B = Bool(X)$, we have

\begin{displaymath}
BoolAlg(B, 2) \cong Set(X, 2) = 2^X
\end{displaymath}
where the Zariski topology coincides with the [[product topology]] on $2^X$. By the equivalence, we therefore retrieve $Bool(X)$ as $CH(2^X, \mathbf{2})$. This in turn is identified with the Boolean algebra of [[clopen subset]]s of the generalised [[Cantor space]] $2^X$.

A second description of the inverse equivalence $BoolAlg^{op} \to Stone$ comes about through the yoga of [[ambimorphic object|ambimorphic objects]]. Namely, the Boolean compact Hausdorff space $\mathbf{2}$ can equally well be seen as a [[compact Hausdorff object]] in the category of Boolean algebras. Thus, the representable functor $Bool(-, \mathbf{2}): Bool^{op} \to Set$ lifts canonically to a functor

\begin{displaymath}
Bool^{op} \to CH
\end{displaymath}
and in fact part of the Stone representation theorem is that this factors through the inclusion $Stone \hookrightarrow CH$ as the inverse equivalence $Bool^{op} \to Stone$. In particular this lift determines the topology, providing an description alternative to the description in terms of the Zariski topology (although they are of course the same).

\hypertarget{in_weak_foundations}{}\subsection*{{In weak foundations}}\label{in_weak_foundations}

Boolean algebras are less interesting in [[constructive mathematics]], since [[power sets]] are not boolean algebras. However, they are still a perfectly good algebraic construct, and the explicit construction of free algebras in terms of finite subsets is still correct. Stone duality also works in constructive mathematics, but it must be done using [[locales]] instead of standard [[topological spaces]].

In [[predicative mathematics]], the explicit construction of free algebras works if we have general [[inductive object]]s; the [[natural numbers object]] alone is not enough.

category: category

[[!redirects BoolLat]] [[!redirects Bool Lat]] [[!redirects BoolAlg]] [[!redirects BoolALg]] [[!redirects Bool Alg]] [[!redirects BoolRing]] [[!redirects Bool Ring]]

[[!redirects free boolean algebra]] [[!redirects free Boolean algebra]] [[!redirects free boolean lattice]] [[!redirects free Boolean lattice]] [[!redirects free boolean ring]] [[!redirects free Boolean ring]]

[[!redirects double powerset]] [[!redirects double power set]]



\end{document}