Incomplete subsets of the free boolean algebra on countably many generators

Question

I know that it is provable that the free boolean algebra on countably many generators is incomplete. For the sake of concreteness, let's call the generators $p_1, p_2, p_3,...$ and refer to them as "basic formulas". I have been looking for a concrete example of a subset which lacks either a least upper bound or a greatest lower bound. In fact, I almost gave up; I've been trying to do this for months.

However, I stumbled upon this page: http://thue.stanford.edu/bool.html

The author claims that in the free boolean algebra on countably many generators (FBACMG), "any set $X$ of variables has a least upper bound if and only if the set is finite."

This seems wrong to me: consider the set of basic formulas. If I am not mistaken, it has no upper bounds except the tautology, and thus the tautology must be its least upper bound.

Am I wrong, or is the site wrong? And if the site is wrong, is it possible to describe a subset of the FBACMG which provably has no least upper bound or no greatest lower bound? If not can I prove that it is impossible to describe such a set?

Answer 1

That page is mistaken and you are right in your example: if $F$ is an element of the free Boolean algebra on the set $\{p_1, p_2, \ldots\}$ and $p_i \leq F$ for all $i$, then surely $1 \leq F$. One concrete way to think about this is by appeal to Stone duality: the free Boolean algebra is realized concretely as the Boolean algebra consisting of clopen subsets of Cantor space $C = 2^{\mathbb{N}}$. The variable $p_i$ corresponds to the clopen $C_i$ consisting of all points whose $i$-th coordinate is $1$. If some clopen $F$ contains all these $C_i$, then $F$ must be the entire space since the ordinary set-theoretic union of all those $C_i$, which is the complement of the singleton $\{(0, 0, 0,\ldots)\}$, is dense in $C$.

However, similar topological considerations show that this Boolean algebra is not complete. Consider Cantor space $C$ as a subspace of $[0, 1]$ consisting of real numbers between $0$ and $1$ whose ternary expansions have only $0, 2$ as digits. Now any open set in Cantor space is a (countable) union of basic open sets which are finite intersections $C_{i_1} \cap \ldots \cap C_{i_n}$. Say we take the open $U$ given by the interval $(.020202..., .202020...) \cap C$, and suppose there were a smallest clopen $F$ containing this. Then, being closed, it would contain the set $[.020202..., .202020...] \cap C$. But being open, $F$ would have to contain all points of $C$ within some $\epsilon$ of $.020202...$. Clearly then you could find a smaller clopen inside $F$ (use $\epsilon/2$ instead), and we reach a contradiction. So the collection of basic clopens we use to form $U$ as a union could have no least upper bound in the Boolean algebra.

Edit: I will slightly modify the "$U$" construction above and work instead with the open set $V = (.020202..., 1 = .222222...]$, where again we realize Cantor space $C$ as the subspace of $[0, 1]$ consisting of numbers which in base-3 expansion $\sum_{i = 1}^\infty \frac{a_i}{3^i}$ have $a_i = 0$ or $a_i = 2$ for all $i$. The key point to remember is that the clopen (closed and open) set consisting of all elements of $C$ that (in base 3) start as $.a_1 a_2 \ldots a_n$ corresponds to a conjunction of literals $\lambda_1 \wedge \ldots \wedge \lambda_n$ where $\lambda_i = p_i$ if $a_i = 2$ and $\lambda_i = \neg p_i$ if $a_i = 0$. For example, $p_1$ corresponds to the clopen $[.2, 1] \cap C$, and $\neg p_1 \wedge p_2$ to $[.02, .022222... = .1] \cap C$.

Thus, if I am not mistaken, the open set $V = (.020202\ldots, 1]$ is the union of intervals corresponding to the sequence of conjunctions

$$F_1 = p_1,$$ $$F_2 = \neg p_1 \wedge p_2 \wedge p_3,$$ $$F_3 = \neg p_1 \wedge p_2 \wedge \neg p_3 \wedge p_4 \wedge p_5,$$ $$\ldots,$$ $$F_{n+1} = (\bigwedge_{i=1}^{2n} \neg^i(p_i)) \wedge p_{2n+1},$$ $$\ldots$$

and the claim is that there is no least upper bound of this sequence. The topological argument translates into saying that any finite Boolean formula $F$ which dominates all these (in the usual order of the Boolean algebra) must also dominate some formula of the form $\bigwedge_{i=1}^{2n} \neg^i(p_i)$, but then we can slip in yet another dominating formula $F' < F$ by taking the union of $F_1, \ldots, F_{n+1}$ plus $\bigwedge_{i=1}^{2n+2} \neg^i(p_i)$. So there is no least upper bound $F$.

Answer 2

Yes, that claim in the post is wrong, and you are correct to object. What is true — and I was very surprised to learn this — is that in the free Boolean algebra on a countably infinite set of generators, every subset of the generators has a least upper bound.

This is not to say that the Boolean algebra is complete, since it is easy to see that it is not: the free Boolean algebra on a countable set of generators is countably infinite, since every element is represented by a term, but no countably infinite Boolean algebra is complete, since it must have an infinite antichain, and all subsets of an antichain must have distinct least upper bounds when they exist. So if it were complete, it would have to have size continuum.

In the free Boolean algebra on generators $p_0,\ p_1,\ldots$, the "disjointified" collection $p_0,\ p_1\wedge\neg p_0,\ p_2\wedge\neg(p_0\vee p_1),\ldots$ is an infinite (maximal) antichain. One can prove that a subset of this antichain has a least upper bound in the free algebra just in case it is finite or cofinite.

Nevertheless, to stress the point, every subset of the generating set itself does have a least upper bound.

Theorem. If $B$ is the free Boolean algebra on a set of generators $Y$, then every subset of $Y$ has a least upper bound in $B$. Furthermore, the infinite subsets of $Y$ all have least upper bound $1$.

One can begin to see the latter claim intuitively, if you should merely try to imagine what would be the least upper bound of a infinite subset of $Y$ that, say, contains all the variables except some $p$. There is no natural candidate, other than $1$ itself; note that $\neg p$ is not an upper bound of the other variables, since variables are not disjoint in the free Boolean algebra.

Proof. Clearly, any finite subset $X\subset Y$ has a least upper bound, which is simply the finite disjunction of the elements of the set $\bigvee_{p\in X} p$.

Suppose now that $X\subset Y$ is infinite. (This argument was noticed also by user მამუკა ჯიბლაძე in the comments.) Clearly $1$ is an upper bound of $X$; what we need to show is that there is no smaller upper bound. Suppose that $u<1$ is an element of $B$. Using the term algebra, we know that every element of $B$ is represented as a term using finitely many variables of $Y$. Fix such a term, and let $p$ be some element of $X$ not appearing in that term. Since $u<1$ and $p$ does not appear in the term for $u$, I claim that there is a homomorphism sending $u$ to $0$ and $p$ to $1$. To see this, we merely need to settle the values of the variables appearing in the term for $u$ in such a way that $u$ becomes $0$, and this is determined by settling the values of the variables appearing in that term, and we can independently send $p$ to $1$ by freeness. Since homomorphisms preserve order, it cannot be that $p\leq u$. So we have shown that no element of $B$ other than $1$ is an upper bound of $X$, and so the least upper bound of $X$ is $1$.

An alternative argument was suggested in the comments by Andreas Blass: if $X\subset Y$ is infinite with upper bound $u$, let $p$ be variable of $X$ not used the term representing $u$. By freeness, there is an automorphism of the Boolean algebra sending $p$ to $\neg p$ and fixing all other variables and therefore also fixing $u$. Since $p\leq u$, it follows by applying the automorphism that also $(\neg p)\leq u$. Since $1=p\vee\neg p$, this means $u=1$. QED

Meanwhile, if instead of the free algebra one has the Boolean algebra generated by an infinite set of atoms, then something closer to the claim is true:

Theorem. If $B$ is the Boolean algebra generated by an infinite set of atoms $Y$, then the subsets of $Y$ with a least upper bound in $B$ are exactly the finite or co-finite subsets of $Y$.

Proof. It is not difficult to see that the Boolean algebra $B$ is isomorphic to the set of finite and co-finite subsets of $Y$, with the usual set-theoretic operations. If $X\subset Y$ is infinite and co-infinite, therefore, then clearly no finite or co-finite set can be a least upper bound of $X$.QED

Answer 3

The answer by Todd Trimble is precise enough, I just would like to complement it with some additional considerations.

Upper bounds of any subset of any Boolean algebra form a $\textit{normal filter}$, and lower bounds of any subset form a $\textit{normal ideal}$. Normal filters are in one-to-one correspondence with $\textit{regular closed}$ subsets of the Stone space of the algebra, and normal ideals with $\textit{regular open}$ subsets of the Stone space (so also both (normal filters) $\leftrightarrow$ (normal ideals) and (regular closeds) $\leftrightarrow$ (regular opens) are in one-to-one (order reversing) correspondences with each other).

Thus subsets without a lub are detected by $\textit{nonprincipal}$ normal filters which correspond to $\textit{nonclopen}$ regular closed sets, and subsets without a glb are detected by nonprincipal normal ideals which correspond to nonclopen regular open sets.

Caveat (and I made an actual mistake in my comment to the question here): given a set of clopens whose intersection is not (cl)open, it does not yet produce an example of a set without a glb in the algebra. For that, in addition, $\textit{interior of that intersection must not be closed}$. In other words, union of clopens contained in that intersection must not be closed.

An example of a regular open set in the Cantor space $C\subset\mathbb R$ is its intersection with some open interval $(a,b)$. This regular open is not clopen whenever either $a$ or $b$ is in $C\setminus\{\frac i{3^j}\mid i,j=0,1,2,...\}$.

In this realization of $C$, the variables $p_i$ correspond to the following clopens: \begin{align*} p_1&\mapsto C\cap[0,\frac13];\\ p_2&\mapsto C\cap([0,\frac19]\cup[\frac23,\frac79]);\\ p_3&\mapsto C\cap([0,\frac1{27}]\cup[\frac29,\frac7{27}]\cup[\frac23,\frac{19}{27}]\cup[\frac89,\frac{25}{27}]);\\ \cdots \end{align*} and the formulæ $\neg^{\varepsilon_1}p_1\land\cdots\land\neg^{\varepsilon_n}p_n$ capture all clopens of the form $C_{ij}:=C\cap[\frac i{3^j},\frac{i+1}{3^j}]$ with $j\leqslant n$. For example, $p_1\land p_2\mapsto C_{02}$, $p_1\land\neg p_2\mapsto C_{22}$, $\neg p_1\land p_2\mapsto C_{62}$, $\neg p_1\land\neg p_2\mapsto C_{82}$, ..., $p_1\land\cdots\land p_n\mapsto C_{0n}$, ..., $\neg p_1\land\cdots\land\neg p_n\mapsto C_{3^n-1,n}$, etc.

Thus given any nonclopen regular open $C\cap(a,b)$ as above, a set of formulæ without a lub in the free Boolean algebra corresponds to $\{C_{ij}\mid C_{ij}\subset(a,b), i,j=0,1,...\}$, i. e. to $\{C_{ij}\mid3^ja<i<3^jb-1\}$.

Todd's example is one such, chosen in a way to need as less mess as possible.

Of course there are lots of other sets without lubs. First, you may represent a nonclopen regular open as a union of clopens in many different ways. Second, most nonclopen regular opens are not of the form $C\cap(a,b)$; one can take $C\cap((a,b)\cup(a',b'))$, etc. - many (although by no means any) infinite unions of intervals also produce nonclopen regular opens of $C$.

(I hope I did not make another mistake somewhere :D )