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?



Incomplete subsets of the free boolean algebra on countably many generators
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$. 


