Boolean subalgebra

Boolean Subalgebras

Let $A$ be a Boolean algebra and $B$ a non-empty 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 non-empty 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 two-element Boolean algebra consisting of just $0$ and $1$.

• If $A$ contains a non-trivial element $a$ ($\ne 0$), then $0,1,a,a^{\prime }$ form a four-element Boolean subalgebra of $A$.

• Here is a concrete example. Let $A$ be the field of all sets (http://planetmath.org/RingOfSets) 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 $𝒯$, 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\le a$. It can be easily shown that $B$ is dense in $A$ is equivalent to any one of the following:

  1. for any $a\in A$, there is $b\in B$ such that $a\le b$;

  2. for any $x,y\in A$ with $x\le y$, there is $z\in B$ such that $x\le z\le y$.

  To see the last equivalence, notice first that by picking $x=0$ we see that $B$ is dense, and conversely, if $x\le y$, then there is $r\in B$ such that $r\le y$, so that $x\le x\vee r\le 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 $⟨X⟩$. As indicated by the remark above, $⟨X⟩$ is a Boolean subalgebra of $A$, the smallest subalgebra containing $X$. If $⟨X⟩=A$, then we say that the Boolean algebra $A$ itself is generated by $X$.

Proposition 1.

Every element of $\mathrm{⟨}X\mathrm{⟩}\mathrm{\subseteq }A$ has a disjunctive normal form (DNF). In other words, if $a\mathrm{\in }\mathrm{⟨}X\mathrm{⟩}$, then

$$a=\underset{i=1}{\overset{n}{\bigvee }}\underset{j=1}{\overset{\varphi (i)}{\bigwedge }}{a}_{ij}=(a_{11}\wedge \mathrm{\cdots }\wedge a_{1\varphi (1)})\vee (a_{21}\wedge \mathrm{\cdots }\wedge a_{2\varphi (2)})\vee \mathrm{\cdots }\vee (a_{n1}\wedge \mathrm{\cdots }\wedge a_{n\varphi (n)}),$$

where either $a_{i\mathit{}j}$ or $a_{i\mathit{}j}^{\mathrm{\prime }}$ belongs to $X$.

Proof.

Let $B$ be the set of all elements written in DNF using elements $X$. Clearly $B\subseteq ⟨X⟩$. What we want to show is that $⟨X⟩\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 \mathrm{\cdots }\wedge a_{1\varphi (1)})\vee (a_{21}\wedge \mathrm{\cdots }\wedge a_{2\varphi (2)})\vee \mathrm{\cdots }\vee (a_{n1}\wedge \mathrm{\cdots }\wedge a_{n\varphi (n)})$, then

   $b\wedge a$ $=$ $b\wedge ((a_{11}\wedge \mathrm{\cdots }\wedge a_{1\varphi (1)})\vee (a_{21}\wedge \mathrm{\cdots }\wedge a_{2\varphi (2)})\vee \mathrm{\cdots }\vee (a_{n1}\wedge \mathrm{\cdots }\wedge a_{n\varphi (n)}))$

   $=$ $(b\wedge a_{11}\wedge \mathrm{\cdots }\wedge a_{1\varphi (1)})\vee (b\wedge a_{21}\wedge \mathrm{\cdots }\wedge a_{2\varphi (2)})\vee \mathrm{\cdots }\vee (b\wedge a_{n1}\wedge \mathrm{\cdots }\wedge a_{n\varphi (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 \mathrm{\cdots }\wedge a_{i\varphi (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 \mathrm{\cdots }\wedge a_{1\varphi (1)})\vee (a_{21}\wedge \mathrm{\cdots }\wedge a_{2\varphi (2)})\vee \mathrm{\cdots }\vee (a_{n1}\wedge \mathrm{\cdots }\wedge a_{n\varphi (n)})$, then

   $$a^{\prime }=(a_{11}^{\prime }\vee \mathrm{\cdots }\vee a_{1\varphi (1)}^{\prime })\wedge (a_{21}^{\prime }\vee \mathrm{\cdots }\vee a_{2\varphi (2)}^{\prime })\wedge \mathrm{\cdots }\wedge (a_{n1}^{\prime }\vee \mathrm{\cdots }\vee a_{n\varphi (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$, $⟨X⟩\subseteq B$. ∎

Similarly, one can show that $⟨X⟩$ is the set of all elements in $A$ that can be written in conjunctive normal form (CNF) using elements of $X$.

Corollary 1.

Let $\mathrm{⟨}B\mathrm{,}x\mathrm{⟩}$ be the Boolean subalgebra (of $A$) generated by a Boolean subalgebra $B$ and an element $x\mathrm{\in }A$. Then every element of $\mathrm{⟨}B\mathrm{,}x\mathrm{⟩}$ has the form

$$(b_1\wedge x)\vee (b_2\wedge x^{\prime })$$

for some $b_{\mathrm{1}}\mathrm{,}{b}_{\mathrm{2}}\mathrm{\in }B$.

Proof.

Let $X$ be a generating set for $B$ (pick $X=B$ if necessary). By the proposition above, every element in $⟨B,x⟩$ is the join of elements of the form $a_1\wedge a_2\wedge \mathrm{\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 $⟨B,x⟩$ 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\mathrm{\Delta }{c}_2\le x\le b_1\leftrightarrow c_1$, where $\mathrm{\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 }\le b_2\vee x$ so that $c_2\vee x=(c_2\wedge x^{\prime })\vee x\le (b_2\vee x)\vee x=b_2\vee x$. Therefore, $c_2-b_2=c_2\wedge b_2^{\prime }\le (c_2\vee x)\wedge b_2^{\prime }\le (b_2\vee x)\wedge b_2^{\prime }=b_2^{\prime }\wedge x\le x$. Similarly, $b_2-c_2\le x$. Taking the join and we get $b_2\mathrm{\Delta }{c}_2\le x$. Dually, $b_1\mathrm{\Delta }{c}_1\le x^{\prime }$, and complementing this to get $x\le {(b_1\mathrm{\Delta }{c}_1)}^{\prime }=b_1\leftrightarrow c_1$.

  $(\Leftarrow )$. If $b_2-c_2\le x$, then $b_2\vee c_2=(b_2-c_2)\vee c_2\le x\vee c_2$, so that $(b_2\vee c_2)-x\le c_2-x$, or $(b_2-x)\vee (c_2-x)\le c_2-x$, which implies that $b_2-x\le c_2-x$. Similarly, $c_2-x\le b_2-x$. Putting the two inequalities together and we have $b_2-x=c_2-x$. Since $x\le b_1\leftrightarrow c_1$ is equivalent to $b_1\mathrm{\Delta }{c}_1\le 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 })$. ∎

Title	Boolean subalgebra
Canonical name	BooleanSubalgebra
Date of creation	2013-03-22 17:57:55
Last modified on	2013-03-22 17:57:55
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	9
Author	CWoo (3771)
Entry type	Definition
Classification	msc 06E05
Classification	msc 03G05
Classification	msc 06B20
Classification	msc 03G10
Synonym	dense subalgebra
Defines	dense Boolean subalgebra