You are here
HomeBoolean quotient algebra
Primary tabs
Boolean quotient algebra
Quotient Algebras via Congruences
Let $A$ be a Boolean algebra. A congruence on $A$ is an equivalence relation $Q$ on $A$ such that $Q$ respects the Boolean operations:

if $aQb$ and $cQd$, then $(a\vee c)Q(b\vee d)$

if $aQb$, then $a^{{\prime}}Qb^{{\prime}}$
By de Morgan’s laws, we also have $aQb$ and $cQd$ implying $(a\wedge c)Q(b\wedge d)$.
When $a$ is congruent to $b$, we usually write $a\equiv b\;\;(\mathop{{\rm mod}}Q)$.
Let $B$ be the set of congruence classes: $B=A/Q$, and write $[a]Q$, or simply $[a]$ for the congruence class containing the element $a\in A$. Define on $B$ the following operations:

$[a]\vee[b]:=[a\vee b]$

$[a]^{{\prime}}:=[a^{{\prime}}]$
Because $Q$ respects join and complementation, it is clear that these are welldefined operations on $B$. Furthermore, we may define $[a]\wedge[b]:=([a]^{{\prime}}\vee[b]^{{\prime}})^{{\prime}}=([a^{{\prime}}]% \vee[b^{{\prime}}])^{{\prime}}=[a^{{\prime}}\vee b^{{\prime}}]^{{\prime}}=[(a^% {{\prime}}\vee b^{{\prime}})^{{\prime}}]=[a\wedge b]$. It is also easy to see that $[1]$ and $[0]$ are the top and bottom elements of $B$. Finally, it is straightforward to verify that $B$ is a Boolean algebra. The algebra $B$ is called the Boolean quotient algebra of $A$ via the congruence $Q$.
Quotient Algebras via Ideals and Filters
It is also possible to define quotient algebras via Boolean ideals and Boolean filters. Let $A$ be a Boolean algebra and $I$ an ideal of $A$. Define binary relation $\sim$ on $A$ as follows:
$a\sim b\qquad\mbox{if and only if}\qquad a\Delta b\in I,$ 
where $\Delta$ is the symmetric difference operator on $A$. Then
1. $\sim$ is an equivalence on $A$, because

$a\Delta a=0\in I$, so $\sim$ is reflexive

$b\Delta a=a\Delta b$, so $\sim$ is symmetric, and

if $a\sim b$ and $b\sim c$, then $a\sim c$; to see this, note that $(ab)\vee(bc)=((ab)\vee b)\wedge((ab)\vee c^{{\prime}})=(a\vee b)\wedge((a% b)\vee c^{{\prime}})$. Since the LHS (and hence the RHS) is in $I$, and that $a\leq a\vee b$ and $c^{{\prime}}\leq(ab)\vee c^{{\prime}}$, RHS $\geq a\wedge c^{{\prime}}=ac\in I$ too. Similarly $ca\in I$ so that $a\sim c$.

2. $\sim$ respects $\vee$ and ${}^{{\prime}}$, because

if $a\sim b$ and $c\sim d$, then $(a\vee c)(b\vee d)=(a\vee c)\wedge(b\vee d)^{{\prime}}=(a\vee c)\wedge(b^{{% \prime}}\wedge d^{{\prime}})=(a\wedge(b^{{\prime}}\wedge d^{{\prime}}))\vee(c% \wedge(b^{{\prime}}\wedge d^{{\prime}}))\leq(a\wedge b^{{\prime}})\vee(c\wedge d% ^{{\prime}})\in I$, so that $(a\vee c)(b\vee d)\in I$ as well. That $(b\vee d)(a\vee c)\in I$ is proved similarly. Hence $(a\vee c)\sim(b\vee d)$.

$a^{{\prime}}\Delta b^{{\prime}}=a\Delta b$, so $\sim$ preserves ${}^{{\prime}}$.

Thus, $\sim$ is a congruence on $A$. The quotient algebra $A/\sim$ is called the quotient algebra of $A$ via the ideal $I$, and is often denoted by $A/I$.
From this congruence $\sim$, one can recapture the ideal: $I=[0]$.
Dually, one can obtain a quotient algebra from a Boolean filter. Specifically, if $F$ is a filter of a Boolean algebra $A$, define $\sim$ on $A$ as follows:
$a\sim b\qquad\mbox{if and only if}\qquad a\leftrightarrow b\in F,$ 
where $\leftrightarrow$ is the biconditional operator on $A$. Then it is easy to show that $\sim$ too is a congruence on $A$, so that one forms the quotient algebra of $A$ via the filter $F$, denoted by $A/F$. Of course, an easier approach to this is to realize that $F$ is a filter of $A$ iff $F^{{\prime}}:=\{a^{{\prime}}\mid a\in F\}$ is an ideal of $A$, and the process of forming $A/F^{{\prime}}$ turns out to be identical to $A/F$.
From $\sim$, the filter $F$ can be recovered: $F=[1]$.
In fact, given a congruence $Q$, the congruence class $[0]Q$ is a Boolean ideal and the congruence class $[1]Q$ is a Boolean filter, and that the quotient algebras derived from $Q,[0]Q$ and $[1]Q$ are all the same:
$A/Q=A/[0]Q=A/[1]Q.$ 
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