# Embedding a brouwerian lattice into a boolean lattice

I have already asked a similar question at

http://math.stackexchange.com/questions/470704/can-a-brouwerian-lattice-be-extended-into-a-boolean-algebra

but have received no answer. Sorry, I ask a similar question second time, as it is very important for my research.

Is it true that every brouwerian lattice (=locale =frame) can be order-embedded into a boolean lattice?

If yes, can we warrant that this embedding preserves joins and finite meets?

-
Every partial order can be order-embedded into a powerset algebra (=complete atomic Boolean lattice) by mapping each element to the cone it generates. Every distributive lattice can be lattice-embedded into a powerset algebra (by adding top and/or bottom if they are missing, and then mapping each element to the set of prime filters that contain it). The mapping also preserves $\bot$ and $\top$ if the lattice already has them. I don’t know what to do about infinite joins. –  Emil Jeřábek Aug 19 '13 at 12:30
A couple more comments: (1) Every Heyting algebra can be embedded in a complete one (i.e., a locale) while preserving all existing joins and meets using the MacNeille completion. (2) There is no embedding of a locale in a complete Boolean algebra preserving abritrary meets as well as joins unless finite joins distribute over infinite meets (which fails in general). (3) An embedding of a locale in an atomic complete Boolean algebra preserving all joins and finite meets exists iff the locale is spatial. I see no reason why this condition should be necessary for non-atomic Boolean algebras. –  Emil Jeřábek Aug 19 '13 at 14:00

$\def\pw{\mathcal P}$The answer to all the questions is yes. Here are some relevant embedding results:

Proposition 1: Every partial order $(P,\le)$ can be embedded in the powerset lattice $(\pw(P),\subseteq)$, i.e., an atomic complete Boolean algebra. The embedding can be made to preserve all existing meets, or all existing joins (but not both at the same time).

Proof: Map $a\in P$ to $\{b\in P:b\le a\}$ or to $\{b\in P:a\nleq b\}$.

Proposition 2 (Dedekind–MacNeille completion): Every partial order $(P,\le)$ can be embedded in a complete lattice $(L,\le)$ in such way that all existing joins and meets are preserved, and $P$ is dense in $L$ in the sense that every element of $L$ is the join of a subset of $P$, and the meet of a subset of $P$. If $P$ is a Heyting or Boolean algebra, then so is $L$, and the embedding preserves (relative) complements.

Proposition 3: Every distributive lattice $(L,\le)$ can be embedded in a powerset algebra so that all existing finite joins and meets are preserved.

Proof: Let $X$ be the set of prime filters on $L$, and define $f\colon L\to\pw(X)$ as $f(a)=\{f\in X:a\in F\}$. Here, a filter is an upward closed subset of $L$ which is closed under all existing finite meets, and it is prime if its complement is closed under all existing finite joins. Note that the join of the empty set is the smallest element of the lattice, if it exists, and dually for empty meets.

Proposition 4: For every Heyting algebra $(H,\le)$, there is an embedding of $H$ into a complete Boolean algebra (not necessarily atomic) that preserves finite meets and all existing joins (but not necessarily relative complements).

Proof: By Proposition 3, we may assume that $H$ is a bounded sublattice of some $\pw(X)$. Let $B$ be the Boolean subalgebra of $\pw(X)$ generated by the elements of $H$, and $\tilde B$ be the Dedekind–MacNeille completion of $B$. It suffices to show that the inclusion $H\subseteq B$ preserves all existing joins.

The key point is that for every $x\in B$, there exists $\hat x\in H$ such that $$\tag{*} a\le x\iff a\le\hat x$$ for every $a\in H$. This can be shown as follows: by expressing $x$ in the conjunctive normal form, and using the closure of $H$ under finite joins and meets, we can write $x=\bigwedge_{i<n}(-b_i\lor c_i)$ for some $n\in\omega$, $b_i,c_i\in H$. Then \begin{align*} a\le x&\iff\forall i<n\:a\le-b_i\lor c_i\\ &\iff\forall i<n\:a\land b_i\le c_i\\ &\iff\forall i<n\:a\le(b_i\to_Hc_i)\\ &\iff a\le\bigwedge_{i<n}(b_i\to_Hc_i)=:\hat x. \end{align*} Now assume that $b\in H$ is the join of $A\subseteq H$. For any $x\in B$, we have \begin{align*} b\le x&\iff b\le\hat x\\ &\iff\forall a\in A\:a\le\hat x\\ &\iff\forall a\in A\:a\le x, \end{align*} hence $b$ is the join of $A$ in $B$ as well.

I should note that $B$ is sometimes called the wrapping algebra of $H$ in modal logic literature. It is not just a Boolean algebra, it also carries the structure of an S4Grz-modal algebra, which allows to recover $H$ back from $B$.

-
In addition to the proposition 4, can we require $H\bot=\bot$? –  porton Aug 19 '13 at 18:25
I don’t understand what this equation means. The embedding preserves the bottom element (which is the empty join), if that’s what you are asking. –  Emil Jeřábek Aug 19 '13 at 19:18
A frame may be a subframe of several non-isomorphic complete boolean algebras, right? –  porton Aug 29 '13 at 13:43

In Peter Johnstone's book Stone Spaces, on page 53, we have the following corollary.

$\mathbf{Corollary}$ Every frame is isomorphic to a subframe of a complete Boolean algebra.

Of course by a subframe, we mean a subset that contains $0,1$ is closed under arbitrary joins and finite meets.

$\large\mathbf{Added} (10/19/13)$

I will outline two ways in which a frame can be embedded into a complete Boolean algebra.

Recall that a Nucleus on a frame $L$ is a mapping $\nu:L\rightarrow L$ such that $x\leq\nu(x)=\nu(\nu(x))$ and $\nu(x\wedge y)=\nu(x\wedge y)$. If $L$ is a frame, then the set $N(L)$ of Nuclei on $L$ is itself a frame.

If $M$ is a frame, then let $B_{M}=\{x^{**}|x\in M\}$ where $x^{*}$ denotes the pseudocomplement of $x$. Then $B_{M}$ is a complete Boolean algebra. If $(X,\mathcal{T})$ is a topological space, then $B_{\mathcal{T}}$ is the regular open algebra of the space $\mathcal{T}$. The mapping $x\mapsto x^{**}$ is a frame homomorphism.

If $L$ is a frame and $a\in L$, then the mapping $c(a):L\rightarrow L$ defined by $c(a)(x)=a\vee x$ is a Nucleus. Furthermore, the mapping $c:L\rightarrow N(L)$ is a frame homomorphism and each $c(a)$ is a complemented element of the frame $L$. In particular, the mapping $L\rightarrow B_{N(L)},a\mapsto c(a)^{**}$ is an injective frame homomorphism, so $L$ can be embedded as a subframe of the complete Boolean algebra $B_{N(L)}$. This embedding of a frame is the one given in Johnstone's book Stone Spaces.

There is another way to embed a frame in a complete Boolean algebra that I just thought of.

Let $\mathfrak{b}(a)=\{x\rightarrow a|x\in L\}=\{x|x=(x\rightarrow a)\rightarrow a\}$. Then each $\mathfrak{b}(a)$ is a complete Boolean algebra. Let $\phi:L\rightarrow\prod_{a\in L}\mathfrak{b}(a)$ be the mapping where $\phi(x)=((x\rightarrow a)\rightarrow a)_{a\in L}$ for each $x\in L$. Then $\phi$ is an injective frame homomorphism and clearly $\prod_{a\in L}\mathfrak{b}(a)$ is a complete Boolean algebra.

$\large\mathbf{Added} (8/23/13)$ In Emil Jeřábek's answer, it is shown that every Heyting algebra can be embedded into a complete Boolean algebra such that the embedding preserves all least upper bounds and finite greatest lower bounds. This fact can be extending to a broader class of posets besides Heyting algebras which I shall call pre-frames.

A pre-frame is a poset $A$ such that if $R\subseteq A$, $\bigvee R$ exists and $x\leq\bigvee R$, then there is some $S\subseteq A$ with $S\preceq R$ and $\bigvee S=x$. It is easy to see that a meet-semilattice $A$ is a pre-frame if and only if whenever $R\subseteq A$,$\bigvee R$ exists, and $a\in A$, then $\bigvee_{r\in R}(a\wedge r)$ exists, and $a\wedge\bigvee R=\bigvee_{r\in R}(a\wedge r)$.

Essentially, a pre-frame is a poset which looks like a frame except for the fact that suprema and infima do not necessarily exist. A poset is a frame if and only if it is a complete lattice and a pre-frame.

I shall now show that every Heyting algebra is a pre-frame, but this fact requires some basic facts about Galois adjoints.

Recall that if $A,B$ are posets, then $f:A\rightarrow B$ is a left-Galois adjoint to $g:B\rightarrow A$ if $f(a)\leq b\Leftrightarrow a\leq g(b)$. It is not to hard to show that all left-Galois adjoints preserve all least upper bounds. In other words, if $R\subseteq A$ and $\bigvee R$ exists, then $f[R]$ has a least upper bound and $\bigvee f[R]=f(\bigvee R)$.

If $X$ is a Heyting algebra, then $c\wedge a\leq b$ iff $c\leq a\rightarrow b$. Therefore, if we define $f_{a},g_{a}$ by $f_{a}(c)=a\wedge c$ and $g_{a}(b)=a\rightarrow b$, then $f_{a}(c)\leq b$ if and only if $c\leq g_{a}(b)$. Therefore, the mappings $f_{a}$ is a left-Galois adjoint to the mapping $g_{a}$. In particular, the mapping $f_{a}$ preserves all least upper bounds. Said differently, if $I$ is an index set and $b_{i}\in X$ for $i\in I$ and $\bigvee_{i\in I}b_{i}$ exists, then $\bigvee_{i\in I}(a\wedge b_{i})$ exists, and $a\wedge\bigvee_{i\in I}b_{i}=\bigvee_{i\in I}(a\wedge b_{i})$. Therefore, every Heyting algebra is a pre-frame.

$\mathbf{Theorem}$ Let $A$ be a pre-frame. Let $\mathcal{C}$ denote the collection of all downwards closed subsets of $A$ which are closed under taking all least upper bounds. Then $\mathcal{C}$ is a frame. Furthermore, the mapping $e:A\rightarrow\mathcal{C}$ given by $e(a)=\downarrow a$ is an order preserving map that preserves all least upper bounds and all greatest lower bounds.

$\mathbf{Proof}$ Clearly $\mathcal{C}$ is a complete lattice.

Now assume that $L\subseteq A$ is a lower set. Then I claim that $\{\bigvee R|R\subseteq L,\bigvee R\,\textrm{exists}\}\in\mathcal{C}$. Clearly, $\{\bigvee R|R\subseteq L,\bigvee R\,\textrm{exists}\}$ is closed under taking all least upper bounds. To see that $\{\bigvee R|R\subseteq L,\bigvee R\,\textrm{exists}\}$ is downwards closed, we take note that if $x\leq\bigvee R$ for some $R\subseteq L$, then $x=\bigvee S$ for some $S$ with $S\preceq R$. Since $R\subseteq L,S\preceq R$, and $L$ is a lower set, we have $S\subseteq L$ as well. Therefore $x\in\{\bigvee R|R\subseteq L,\bigvee R\,\textrm{exists}\}$. We conclude that $\{\bigvee R|R\subseteq L,\bigvee R\,\textrm{exists}\}\in\mathcal{C}$.

To prove that $\mathcal{C}$ is a frame, assume that $L\in\mathcal{C}$ and $L_{i}\in\mathcal{C}$ for $i\in I$. Clearly, $\bigvee_{i\in I}(L\cap L_{i})\subseteq L\cap\bigvee_{i\in I}L_{i}$. For the other direction, assume that $x\in L\cap\bigvee_{i\in I}L_{i}$. Then $\bigcup_{i\in I}L_{i}$ is a lower set. Therefore, $\{\bigvee R|R\subseteq\bigcup_{i\in I}L_{i},\bigvee R\,\mathrm{exists}\}$ is the least element in $\mathcal{C}$ containing $\bigcup_{i\in I}L_{i}$. In other words, $\{\bigvee R|R\subseteq\bigcup_{i\in I}L_{i},\bigvee R\,\mathrm{exists}\}=\bigvee_{i\in I}L_{i}$ where the least upper bound is taken in $\mathcal{C}$. Therefore, we have $x=\bigvee R$ for some $R\subseteq\bigcup_{i\in I}L_{i}$. However, since $x=\bigvee R\in L$ and $L$ is a lower set, we have $R\subseteq L$. Therefore, since $R\in L\cap\bigcup_{i\in I}L_{i}=\bigcup_{i\in I}(L\cap L_{i})$, we have $x=\bigvee R\in\bigvee_{i\in I}(L\cap L_{i})$. We conclude that $L\cap\bigvee_{i\in I}L_{i}\subseteq\bigvee_{i\in I}(L\cap L_{i})$. Therefore $\mathcal{C}$ is a frame.

The fact that $e$ preserves all suprema and infima is fairly trivial. To see that the mapping $e$ preserves all greatest lower bounds, we simply observe that by definition $\downarrow(\bigwedge R)=\bigcap_{r\in R}\downarrow r$. Furthermore, if $a_{i}\in A$ for $i\in I$ and $\bigvee_{i\in I}a_{i}$ exists, then clearly $\bigvee_{i\in I}(\downarrow a_{i})=\downarrow(\bigvee_{i\in I}a_{i})$. $\mathbf{QED}$

In particular, since every frame is isomorphic to a subframe of a complete Boolean algebra, every pre-frame $L$ can be embedded in a complete Boolean algebra in a way so that the embedding preserves finite meets and all joins that exist in $L$.

-