You are here
HomeBoolean subalgebra
Error message
 Notice: Trying to get property of nonobject in question_unanswered_block() (line 404 of /home/jcorneli/beta/sites/all/modules/question/question.module).
 Notice: Trying to get property of nonobject in question_unanswered_block() (line 404 of /home/jcorneli/beta/sites/all/modules/question/question.module).
 Notice: Trying to get property of nonobject in question_unanswered_block() (line 404 of /home/jcorneli/beta/sites/all/modules/question/question.module).
Primary tabs
Boolean subalgebra
Boolean Subalgebras
Let $A$ be a Boolean algebra and $B$ a nonempty subset of $A$. Consider the following conditions:
1. if $a\in B$, then $a^{{\prime}}\in B$,
2. if $a,b\in B$, then $a\vee b\in B$,
3. if $a,b\in B$, then $a\wedge b\in B$,
It is easy to see that, by de Morgan’s laws, conditions 1 and 2 imply conditions 1 and 3, and vice versa. Also, If $B$ satisfies 1 and 2, then $1=a\vee a^{{\prime}}\in B$ by picking an element $a\in B$. As a result, $0=1^{{\prime}}\in B$ as well.
A nonempty subset $B$ of a Boolean algebra $A$ satisfying conditions 1 and 2 (or equivalently 1 and 3) is called a Boolean subalgebra of $A$.
Examples.

Every Boolean algebra contains a unique twoelement Boolean algebra consisting of just $0$ and $1$.

If $A$ contains a nontrivial element $a$ ($\neq 0$), then $0,1,a,a^{{\prime}}$ form a fourelement Boolean subalgebra of $A$.

Here is a concrete example. Let $A$ be the field of all sets of a set $X$ (the power set of $X$). Let $B$ be the set of all finite and all cofinite subsets of $A$. Then $B$ is a subalgebra of $A$.

Continuing from the example above, if $X$ is equipped with a topology $\mathcal{T}$, then the set of all clopen sets in $X$ is a Boolean subalgebra of the algebra of all regular open sets of $X$.
Remarks. Let $A$ be a Boolean algebra.

Arbitrary intersections of Boolean subalgebras of $A$ is a Boolean subalgebra.

An arbitrary union of an increasing chain of Boolean subalgebras of $A$ is a Boolean subalgebra.

A subalgebra $B$ of $A$ is said to be dense in $A$ if it is dense as a subset of the underlying poset $A$. In other words, $B$ is dense in $A$ iff for any $a\in A$, there is a $b\in B$ such that $b\leq a$. It can be easily shown that $B$ is dense in $A$ is equivalent to any one of the following:
(a) for any $a\in A$, there is $b\in B$ such that $a\leq b$;
(b) for any $x,y\in A$ with $x\leq y$, there is $z\in B$ such that $x\leq z\leq y$.
To see the last equivalence, notice first that by picking $x=0$ we see that $B$ is dense, and conversely, if $x\leq y$, then there is $r\in B$ such that $r\leq y$, so that $x\leq x\vee r\leq y$.
Subalgebras Generated by a Set
Let $A$ be a Boolean algebra and $X$ a subset of $A$. The intersection of all Boolean subalgebras (of $A$) containing $X$ is called the Boolean subalgebra generated by $X$, and is denoted by $\langle X\rangle$. As indicated by the remark above, $\langle X\rangle$ is a Boolean subalgebra of $A$, the smallest subalgebra containing $X$. If $\langle X\rangle=A$, then we say that the Boolean algebra $A$ itself is generated by $X$.
Proposition 1.
Every element of $\langle X\rangle\subseteq A$ has a disjunctive normal form (DNF). In other words, if $a\in\langle X\rangle$, then
$a=\bigvee_{{i=1}}^{{n}}\bigwedge_{{j=1}}^{{\phi(i)}}a_{{ij}}=(a_{{11}}\wedge% \cdots\wedge a_{{1\phi(1)}})\vee(a_{{21}}\wedge\cdots\wedge a_{{2\phi(2)}})% \vee\cdots\vee(a_{{n1}}\wedge\cdots\wedge a_{{n\phi(n)}}),$ 
where either $a_{{ij}}$ or $a_{{ij}}^{{\prime}}$ belongs to $X$.
Proof.
Let $B$ be the set of all elements written in DNF using elements $X$. Clearly $B\subseteq\langle X\rangle$. What we want to show is that $\langle X\rangle\subseteq B$. First, notice that the join of two elements in $B$ is in $B$. Second, the complement of an element in $B$ is also in $B$. We prove this in three steps:
1. If $a\in B$ and either $b$ or $b^{{\prime}}$ is in $X$, then $b\wedge a\in B$.
If $a=(a_{{11}}\wedge\cdots\wedge a_{{1\phi(1)}})\vee(a_{{21}}\wedge\cdots\wedge a% _{{2\phi(2)}})\vee\cdots\vee(a_{{n1}}\wedge\cdots\wedge a_{{n\phi(n)}})$, then
$\displaystyle b\wedge a$ $\displaystyle=$ $\displaystyle b\wedge((a_{{11}}\wedge\cdots\wedge a_{{1\phi(1)}})\vee(a_{{21}}% \wedge\cdots\wedge a_{{2\phi(2)}})\vee\cdots\vee(a_{{n1}}\wedge\cdots\wedge a_% {{n\phi(n)}}))$ $\displaystyle=$ $\displaystyle(b\wedge a_{{11}}\wedge\cdots\wedge a_{{1\phi(1)}})\vee(b\wedge a% _{{21}}\wedge\cdots\wedge a_{{2\phi(2)}})\vee\cdots\vee(b\wedge a_{{n1}}\wedge% \cdots\wedge a_{{n\phi(n)}})$ which is in DNF using elements of $X$.
2. If $a,b\in B$, then $a\wedge b\in B$.
In the last expression of the previous step, notice that each term $b\wedge a_{{i1}}\wedge\cdots\wedge a_{{i\phi(i)}}$ can be written in DNF by iteratively using the result of the previous step. Hence, the join of all these terms is again in DNF (using elements of $X$).
3. If $a\in B$, then $a^{{\prime}}\in B$.
If $a=(a_{{11}}\wedge\cdots\wedge a_{{1\phi(1)}})\vee(a_{{21}}\wedge\cdots\wedge a% _{{2\phi(2)}})\vee\cdots\vee(a_{{n1}}\wedge\cdots\wedge a_{{n\phi(n)}})$, then
$a^{{\prime}}=(a_{{11}}^{{\prime}}\vee\cdots\vee a_{{1\phi(1)}}^{{\prime}})% \wedge(a_{{21}}^{{\prime}}\vee\cdots\vee a_{{2\phi(2)}}^{{\prime}})\wedge% \cdots\wedge(a_{{n1}}^{{\prime}}\vee\cdots\vee a_{{n\phi(n)}}^{{\prime}}),$ which is the meet of $n$ elements in $B$. Consequently, by step 2, $a^{{\prime}}\in B$.
Since $B$ is closed under join and complementation, $B$ is a Boolean subalgebra of $A$. Since $B$ contains $X$, $\langle X\rangle\subseteq B$. ∎
Similarly, one can show that $\langle X\rangle$ is the set of all elements in $A$ that can be written in conjunctive normal form (CNF) using elements of $X$.
Corollary 1.
Let $\langle B,x\rangle$ be the Boolean subalgebra (of $A$) generated by a Boolean subalgebra $B$ and an element $x\in A$. Then every element of $\langle B,x\rangle$ has the form
$(b_{1}\wedge x)\vee(b_{2}\wedge x^{{\prime}})$ 
for some $b_{1},b_{2}\in B$.
Proof.
Let $X$ be a generating set for $B$ (pick $X=B$ if necessary). By the proposition above, every element in $\langle B,x\rangle$ is the join of elements of the form $a_{1}\wedge a_{2}\wedge\cdots\wedge a_{n}$, where each $a_{i}$ or $a_{i}^{{\prime}}$ is in $X$ or is $x$. By the absorption laws, the form is reduced to one of the three forms $a$, $a\wedge x$, or $a\wedge x^{{\prime}}$, where $a\in B$. Joins of elements in the form of the first kind is an element of $B$, since $B$ is a subalgebra. Joins of elements in the form of the second kind is again an element in the form of the second kind (for $(a_{1}\wedge x)\vee(a_{2}\wedge x)=(a_{1}\vee a_{2})\wedge x$), and similarly for the last case. Therefore, any element of $\langle B,x\rangle$ has the form $a\vee(a_{1}\wedge x)\vee(a_{2}\wedge x^{{\prime}})$. Since $a=(a\wedge x)\vee(a\wedge x^{{\prime}})$, by setting $b_{1}=a_{1}\vee a$ and $b_{2}=a_{2}\vee a$, we have the desired form. ∎
Remarks.

If $a=(b_{1}\wedge x)\vee(b_{2}\wedge x^{{\prime}})$, then $a^{{\prime}}=(b_{2}^{{\prime}}\wedge x)\vee(b_{1}^{{\prime}}\wedge x^{{\prime}})$.

Representing $a$ in terms of $(b_{1}\wedge x)\vee(b_{2}\wedge x^{{\prime}})$ is not unique. Actually, we have the following fact: $(b_{1}\wedge x)\vee(b_{2}\wedge x^{{\prime}})=(c_{1}\wedge x)\vee(c_{2}\wedge x% ^{{\prime}})$ iff $b_{2}\Delta c_{2}\leq x\leq b_{1}\leftrightarrow c_{1}$, where $\Delta$ and $\leftrightarrow$ are the symmetric difference and biconditional operators.
Proof.
$(\Rightarrow)$. The LHS can be rewritten as $(b_{1}\vee b_{2})\wedge(b_{2}\vee x)\wedge(b_{1}\vee x^{{\prime}})$. As a result, $c_{2}\wedge x^{{\prime}}\leq b_{2}\vee x$ so that $c_{2}\vee x=(c_{2}\wedge x^{{\prime}})\vee x\leq(b_{2}\vee x)\vee x=b_{2}\vee x$. Therefore, $c_{2}b_{2}=c_{2}\wedge b_{2}^{{\prime}}\leq(c_{2}\vee x)\wedge b_{2}^{{\prime% }}\leq(b_{2}\vee x)\wedge b_{2}^{{\prime}}=b_{2}^{{\prime}}\wedge x\leq x$. Similarly, $b_{2}c_{2}\leq x$. Taking the join and we get $b_{2}\Delta c_{2}\leq x$. Dually, $b_{1}\Delta c_{1}\leq x^{{\prime}}$, and complementing this to get $x\leq(b_{1}\Delta c_{1})^{{\prime}}=b_{1}\leftrightarrow c_{1}$.
$(\Leftarrow)$. If $b_{2}c_{2}\leq x$, then $b_{2}\vee c_{2}=(b_{2}c_{2})\vee c_{2}\leq x\vee c_{2}$, so that $(b_{2}\vee c_{2})x\leq c_{2}x$, or $(b_{2}x)\vee(c_{2}x)\leq c_{2}x$, which implies that $b_{2}x\leq c_{2}x$. Similarly, $c_{2}x\leq b_{2}x$. Putting the two inequalities together and we have $b_{2}x=c_{2}x$. Since $x\leq b_{1}\leftrightarrow c_{1}$ is equivalent to $b_{1}\Delta c_{1}\leq x^{{\prime}}$ (dual statements), we also have $b_{1}x^{{\prime}}=c_{1}x^{{\prime}}$ or $b_{1}\wedge x=c_{1}\wedge x$. Combining (via meet) this equality with the last one, we get $(b_{1}\wedge x)\wedge(b_{2}\wedge x^{{\prime}})=(c_{1}\wedge x)\wedge(c_{2}% \wedge x^{{\prime}})$. ∎
Mathematics Subject Classification
06E05 no label found03G05 no label found06B20 no label found03G10 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Comments
dense subalgebra
Boolean subalgebra
Let $A=P(N)$ be the algebra of subsets of the naturals. Let $B$ be the subalgebra of finite and cofinite sets, that is, $x\in A$ iff $x<\infty\ OR\ x^{{\prime}}<\infty$. Then $B$ is dense since every subset contains a finite subset. But it is not true that $(\forall x<=y)(\exists z\in B):\ x<=z<=y$. For example, take $y=2N,\ x=6N$ (i.e the set of naturals divisible by 2 and the set of naturals divisible by 6). Then $x<=y$ but no finite or cofinite subset can be between them because only infinite subsets with infinite compliment can be between these two sets.