PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: Very high
[parent] Boolean subalgebra (Definition)

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'\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'\in B$ by picking an element $ a\in B$. As a result, $ 0=1'\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.

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 $ \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
$\displaystyle a=\bigvee_{i=1}^{n} \bigwedge_{j=1}^{\phi(i)} a_{ij}=(a_{11}\wedg... ...wedge a_{2\phi(2)}) \vee \cdots \vee (a_{n1}\wedge \cdots \wedge a_{n\phi(n)}),$
where either $ a_{ij}$ or $ a_{ij}'$ 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'$ 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}\we... ...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_... ..._{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'\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 a'=(a_{11}'\vee \cdots \vee a_{1\phi(1)}')\wedge (a_{21}'\vee \cd... ...ee a_{2\phi(2)}') \wedge \cdots \wedge (a_{n1}'\vee \cdots \vee a_{n\phi(n)}'),$
    which is the meet of $ n$ elements in $ B$. Consequently, by step 2, $ a'\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$. $ \qedsymbol$

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
$\displaystyle (b_1\wedge x)\vee (b_2\wedge x')$
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'$ 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'$, 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')$. Since $ a=(a\wedge x)\vee (a\wedge x')$, by setting $ b_1=a_1\vee a$ and $ b_2=a_2\vee a$, we have the desired form. $ \qedsymbol$

Remarks.

  • If $ a=(b_1\wedge x)\vee (b_2\wedge x')$, then $ a'=(b_2'\wedge x)\vee (b_1'\wedge x')$.
  • Representing $ a$ in terms of $ (b_1\wedge x)\vee (b_2\wedge x')$ is not unique. Actually, we have the following fact: $ (b_1\wedge x)\vee (b_2\wedge x')=(c_1\wedge x)\vee (c_2\wedge x')$ iff $ b_2\Delta c_2\le x\le 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')$. As a result, $ c_2\wedge x'\le b_2\vee x$ so that $ c_2\vee x=(c_2\wedge x')\vee x\le (b_2\vee x)\vee x=b_2\vee x$. Therefore, $ c_2-b_2 = c_2\wedge b_2' \le (c_2\vee x)\wedge b_2' \le (b_2\vee x)\wedge b_2' = b_2'\wedge x \le x$. Similarly, $ b_2 -c_2\le x$. Taking the join and we get $ b_2\Delta c_2\le x$. Dually, $ b_1\Delta c_1\le x'$, and complementing this to get $ x\le (b_1\Delta c_1)'= 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\Delta c_1 \le x'$ (dual statements), we also have $ b_1-x'=c_1-x'$ 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')=(c_1\wedge x)\wedge (c_2\wedge x')$. $ \qedsymbol$



"Boolean subalgebra" is owned by CWoo.
(view preamble)

View style:

Other names:  dense subalgebra
Also defines:  dense Boolean subalgebra

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: equality, inequalities, operators, biconditional, symmetric difference, reduced, absorption, proposition, necessary, generating set, conjunctive normal form, closed under, term, expression, complement, join, disjunctive normal form, generated by, equivalence, equivalent, iff, dense in, poset, dense, chain, increasing, union, intersections, regular open sets, algebra, clopen sets, topology, subalgebra, cofinite, finite, power set, non-trivial element, contains, satisfies, imply, de Morgan's laws, easy to see, subset, Boolean algebra
There are 5 references to this entry.

This is version 6 of Boolean subalgebra, born on 2008-04-03, modified 2008-04-26.
Object id is 10471, canonical name is BooleanSubalgebra.
Accessed 360 times total.

Classification:
AMS MSC: 03G10 (Mathematical logic and foundations :: Algebraic logic :: Lattices and related structures)
 06B20 (Order, lattices, ordered algebraic structures :: Lattices :: Varieties of lattices)
 03G05 (Mathematical logic and foundations :: Algebraic logic :: Boolean algebras)
 06E05 (Order, lattices, ordered algebraic structures :: Boolean algebras :: Structure theory)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)