Boolean quotient algebra
Quotient Algebras via Congruences
Let be a Boolean algebra. A congruence
on is an equivalence relation
on such that respects the Boolean operations:
- •
if and , then
- •
if , then
By de Morgan’s laws, we also have and implying .
When is congruent to , we usually write .
Let be the set of congruence classes: , and write , or simply for the congruence class containing the element . Define on the following operations:
- •
- •
Because respects join and complementation, it is clear that these are well-defined operations on . Furthermore, we may define . It is also easy to see that and are the top and bottom elements of . Finally, it is straightforward to verify that is a Boolean algebra. The algebra is called the Boolean quotient algebra of via the congruence .
Quotient Algebras via Ideals and Filters
It is also possible to define quotient algebras via Boolean ideals and Boolean filters. Let be a Boolean algebra and an ideal of . Define binary relation on as follows:
where is the symmetric difference operator on . Then
- 1.
is an equivalence on , because
- –
, so is reflexive
- –
, so is symmetric
, and
- –
if and , then ; to see this, note that . Since the LHS (and hence the RHS) is in , and that and , RHS too. Similarly so that .
- –
- 2.
respects and , because
- –
if and , then , so that as well. That is proved similarly. Hence .
- –
, so preserves .
- –
Thus, is a congruence on . The quotient algebra is called the quotient algebra of via the ideal , and is often denoted by .
From this congruence , one can re-capture the ideal: .
Dually, one can obtain a quotient algebra from a Boolean filter. Specifically, if is a filter of a Boolean algebra , define on as follows:
where is the biconditional operator on . Then it is easy to show that too is a congruence on , so that one forms the quotient algebra of via the filter , denoted by . Of course, an easier approach to this is to realize that is a filter of iff is an ideal of , and the process of forming turns out to be identical to .
From , the filter can be recovered: .
In fact, given a congruence , the congruence class is a Boolean ideal and the congruence class is a Boolean filter, and that the quotient algebras derived from and are all the same: