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 }Q{b}^{\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(modQ)$.

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\mathit{\hspace{1em}\hspace{1em}}\text{if and only if}\mathit{\hspace{1em}\hspace{1em}}a\mathrm{\Delta }b\in I,$$

where $\mathrm{\Delta }$ is the symmetric difference operator on $A$. Then

1. $\sim$ is an equivalence on $A$, because

   • $a\mathrm{\Delta }a=0\in I$, so $\sim$ is reflexive

   • $b\mathrm{\Delta }a=a\mathrm{\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\le a\vee b$ and $c^{\prime }\le (a-b)\vee c^{\prime }$, RHS $\ge a\wedge c^{\prime }=a-c\in I$ too. Similarly $c-a\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 }))\le (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 }\mathrm{\Delta }{b}^{\prime }=a\mathrm{\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\mathit{\hspace{1em}\hspace{1em}}\text{if and only if}\mathit{\hspace{1em}\hspace{1em}}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
Canonical name	BooleanQuotientAlgebra
Date of creation	2013-03-22 17:59:09
Last modified on	2013-03-22 17:59:09
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	8
Author	CWoo (3771)
Entry type	Definition
Classification	msc 06E05
Classification	msc 03G05
Classification	msc 06B20
Classification	msc 03G10