# 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\pmod{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 well-defined 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. 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 $(a-b)\vee(b-c)=((a-b)\vee b)\wedge((a-b)\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(a-b)\vee c^{\prime}$, RHS $\geq a\wedge c^{\prime}=a-c\in I$ too. Similarly $c-a\in I$ so that $a\sim c$.

2. 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 re-capture 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.$
Title Boolean quotient algebra BooleanQuotientAlgebra 2013-03-22 17:59:09 2013-03-22 17:59:09 CWoo (3771) CWoo (3771) 8 CWoo (3771) Definition msc 06E05 msc 03G05 msc 06B20 msc 03G10