Boolean quotient algebra

Quotient Algebras via Congruences

Let A be a Boolean algebraMathworldPlanetmath. A congruenceMathworldPlanetmathPlanetmathPlanetmath on A is an equivalence relationMathworldPlanetmath Q on A such that Q respects the Boolean operations:

  • if aQb and cQd, then (ac)Q(bd)

  • if aQb, then aQb

By de Morgan’s laws, we also have aQb and cQd implying (ac)Q(bd).

When a is congruent to b, we usually write ab(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 aA. Define on B the following operationsMathworldPlanetmath:

  • [a][b]:=[ab]

  • [a]:=[a]

Because Q respects join and complementation, it is clear that these are well-defined operations on B. Furthermore, we may define [a][b]:=([a][b])=([a][b])=[ab]=[(ab)]=[ab]. 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 relationMathworldPlanetmath on A as follows:

ab  if and only if  aΔbI,

where Δ is the symmetric difference operator on A. Then

  1. 1.

    is an equivalence on A, because

    • aΔa=0I, so is reflexiveMathworldPlanetmathPlanetmathPlanetmathPlanetmath

    • bΔa=aΔb, so is symmetricPlanetmathPlanetmathPlanetmath, and

    • if ab and bc, then ac; to see this, note that (a-b)(b-c)=((a-b)b)((a-b)c)=(ab)((a-b)c). Since the LHS (and hence the RHS) is in I, and that aab and c(a-b)c, RHS ac=a-cI too. Similarly c-aI so that ac.

  2. 2.

    respects and , because

    • if ab and cd, then (ac)-(bd)=(ac)(bd)=(ac)(bd)=(a(bd))(c(bd))(ab)(cd)I, so that (ac)-(bd)I as well. That (bd)-(ac)I is proved similarly. Hence (ac)(bd).

    • aΔb=aΔb, so preserves .

Thus, is a congruence on A. The quotient algebra A/ is called the quotient algebra of A via the ideal I, and is often denoted by A/I.

From this congruence , 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 on A as follows:

ab  if and only if  abF,

where is the biconditionalMathworldPlanetmathPlanetmath operator on A. Then it is easy to show that 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:={aaF} is an ideal of A, and the process of forming A/F turns out to be identical to A/F.

From , 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:

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