nLab Boolean ring

Redirected from "boolean ring".
Boolean rings

Boolean rings

Idea

A boolean algebra is an algebraic structure that models the fragment of the classical propositional calculus that deals with the connectives “and”, “or”, “implies”, and “not”. In some approaches the definition of boolean algebra is rather lengthy, but boolean algebras are equivalent to boolean rings, which are simply rings obeying the identity x 2=xx^2 = x.

In a boolean ring, the multiplication can be interpreted as the conjunction, the multiplicative unit 11 as the truth value “true”, the additive unit 00 as the truth value “false”. The unary operation x1+xx \mapsto 1 + x provides the negation. Compared to boolean algebras, which are also semirings but not rings (except the trivial boolean algebra), the addition expresses the exclusive disjunction and not the inclusive disjunction. The fact that the exclusive disjunction of xx and xx is the truth value “false” makes the commutative additive monoid an abelian group where x=x-x = x.

Definitions

A ring with unit RR is boolean if the operation of multiplication is idempotent; that is, x 2=xx^2 = x for every element xx. Although the terminology would make sense for rings without unit, the common usage assumes a unit.

Boolean rings and the ring homomorphisms between them form a category BoolRingBool Ring.

Properties

  • A boolean ring is an algebra over the field 𝔽 2 \mathbb{F}_2 with two elements, since

    2x=4x2x=4x 22x=(2x) 22x=2x2x=0. 2 x = 4 x - 2 x = 4 x^2 - 2 x = (2 x)^2 - 2 x = 2 x - 2 x = 0 .
  • RR is commutative (meaning that xy=yxx y = y x for all x,yx, y):

    yx=x+yxy+yx=(x+y) 2x 2y 2+yx=x 2+xy+yx+y 2x 2y 2+yx=xy+2yx=xy. y x = x + y - x - y + y x = (x + y)^2 - x^2 - y^2 + y x = x^2 + x y + y x + y^2 - x^2 - y^2 + y x = x y + 2 y x = x y .

Thus, multiplication in a boolean ring makes it into a semilattice, while addition makes it into a vector space over the field with two elements, 𝔽 2\mathbb{F}_2.

Define xyx \vee y to mean x+xy+yx + x y + y. Then:

  • \vee is commutative (as it would be in any commutative ring) and idempotent:
    xx=x+x 2+x=3x=x. x \vee x = x + x^2 + x = 3 x = x .
  • The absorption law (xxy=xx \vee x y = x) also holds:
    xxy=x+x 2y+xy=x+2xy=x. x \vee x y = x + x^2 y + x y = x + 2 x y = x .

    We could now prove the other absorption law to conclude that RR is a lattice using multiplication as meet and \vee as join.

  • But in fact, we can skip that step since it follows the distributive law (x(yz)=xyxzx (y \vee z) = x y \vee x z):
    x(yz)=x(y+yz+z)=xy+xyz+xz=xy+x 2yz+xz=xy+(xy)(xz)+xz=xyxz. x (y \vee z) = x (y + y z + z) = x y + x y z + x z = x y + x^2 y z + x z = x y + (x y) (x z) + x z = x y \vee x z .

    Thus RR is a distributive lattice.

Next define ¬x\neg{x} to be x+1x + 1. Then:

  • ¬x\neg{x} is a pseudocomplement of xx (meaning that x(¬x)=0x (\neg{x}) = 0):
    x(¬x)=x(x+1)=x 2+x=2x=0. x (\neg{x}) = x (x + 1) = x^2 + x = 2 x = 0 .

    By relativising from x+1x + 1 to xy+x+1x y + x + 1, we can show that RR is a Heyting algebra.

  • But don't bother, because ¬x\neg{x} is also an op-pseudocomplement of xx:
    x¬x=x+x(x+1)+(x+1)=x 2+3x+1=x+x+1=1. x \vee \neg{x} = x + x (x + 1) + (x + 1) = x^2 + 3 x + 1 = x + x + 1 = 1 .

    Therefore, ¬x\neg{x} is a complement of xx, and RR is a Boolean algebra.

Conversely, starting with a boolean algebra RR (with the meet written multiplicatively), let x+yx + y be x(¬y)(¬x)yx (\neg{y}) \vee (\neg{x}) y (which is called exclusive disjunction in {,}\{\top,\bot\} and symmetric difference in 2 X2^X). Then RR is a boolean ring.

In fact, we have:

Proposition

The categories of Boolean rings and Boolean algebras are equivalent.

Proof

Since the Boolean algebra operations ,,¬,0,1\wedge, \vee, \neg, 0, 1 are definable from the Boolean ring operations +,,,0,1+, -, \cdot, 0, 1, and conversely, it follows that a function f:|A||B|f: {|A|} \to {|B|} between the underlying sets of Boolean rings is a Boolean ring homomorphism (i.e., preserves the Boolean ring operations) if and only if it is a Boolean algebra homomorphism (between the Boolean algebra structures defined on the same sets). In other words, the subsets

BoolRing(A,B)Set(|A|,|B|),BoolAlg(A,B)Set(|A|,|B|)BoolRing(A, B) \hookrightarrow Set({|A|}, {|B|}), \qquad BoolAlg(A, B) \hookrightarrow Set({|A|}, {|B|})

coincide. Therefore the categories of Boolean rings and of Boolean algebras are equivalent as concrete categories.

The category of Boolean algebras is discussed further in BoolAlg, but some of the results about this category are proved there by working with the equivalent category of Boolean rings.

Here is a very convenient result: although a boolean ring RR is a rig in two different ways (as a ring or as a distributive lattice), these have the same concept of ideal!

Examples

The most familiar example is the power set 𝒫S\mathcal{P}S of any set SS. This is a boolean ring with symmetric difference as the addition and the intersection of sets as the multiplication. In constructive mathematics, one would use the set of decidable subsets 2 S2^S instead of the set of all subsets 𝒫S\mathcal{P}S to get the corresponding boolean ring.

More generally, given any Boolean ring RR and a set SS, the function ring R SR^S is a Boolean ring.

In classical mathematics the free boolean ring on a set XX can be identified with 𝒫 f𝒫 fX\mathcal{P}_f \mathcal{P}_f X, where 𝒫 fX\mathcal{P}_f X is the set of all finite subsets of XX. In fact 𝒫 f\mathcal{P}_f can be extended to a functor in two different ways, which agree on objects but differ on morphisms, and each of these gives a monad:

  • the monad for semilattices, M:SetSetM \colon Set \to Set (which we use to describe multiplication in a boolean ring)

  • the monad for vector spaces over the field with 2 elements, S:SetSetS \colon Set \to Set (which we use to describe addition in a boolean ring).

These two monads are related by a distributive law which expresses the distributivity of multiplication over addition. Their composite SMS \circ M is then the monad for Boolean rings.

Terminology

Back in the day, the term ‘ring’ meant (more often than now is the case) a possibly nonunital ring; that is a semigroup, rather than a monoid, in Ab. This terminology applied also to boolean rings, and it changed even more slowly. Thus older books will make a distinction between ‘boolean ring’ (meaning an idempotent semigroup in AbAb) and ‘boolean algebra’ (meaning an idempotent monoid in AbAb), in addition to (or even instead of) the difference between ++ and \vee as fundamental operation. This distinction survives most in the terminology of σ\sigma-rings and σ\sigma-algebras.

Remark

We pause to note that “idempotent monoid” doesn’t make sense a priori in a general monoidal category: generally speaking the idempotency axiom would be expressed by an equation

1 M=(Mδ MMMmultM)1_M = \left(M \stackrel{\delta_M}{\to} M \otimes M \stackrel{mult}{\to} M \right)

where δ M\delta_M is an appropriate diagonal map, not generally available for monoidal categories. But in a concrete monoidal category M\mathbf{M} where the underlying-set functor U:MSetU: \mathbf{M} \to Set is lax monoidal, the meaning is that the evident equation holds:

1 U(M)=(U(M)δU(M)×U(M)λU(MM)U(mult)U(M))1_{U(M)} = \left(U(M) \stackrel{\delta}{\to} U(M) \times U(M) \stackrel{\lambda}{\to} U(M \otimes M) \stackrel{U(mult)}{\to} U(M) \right)

where λ\lambda is a lax monoidal constraint.

Analogues

Inasmuch as a semilattice is a commutative idempotent monoid, a boolean ring may be defined as a semilattice in AbAb. However, with boolean rings, we do not need to hypothesize commutativity; it follows. That is, any idempotent monoid in AbAb is commutative; indeed, any idempotent magma in AbAb is commutative.

Proof

Write the magma operation as (x,y)xy(x, y) \mapsto x y. Then for any element xx, idempotence and bilinearity imply

x+x=(x+x)(x+x)=(x+x)x+(x+x)x=(xx+xx)+(xx+xx)=(x+x)+(x+x)x + x = (x + x)(x + x) = (x + x)x + (x + x)x = (x x + x x) + (x x + x x) = (x + x) + (x + x)

which by cancellation gives x+x=0x + x = 0, or x=xx = -x. Similarly, for any elements x,yx, y,

x+y=(x+y)(x+y)=(x+y)x+(x+y)y=(xx+yx)+(xy+yy)=x+yx+xy+yx + y = (x + y)(x + y) = (x + y)x + (x + y)y = (x x + y x) + (x y + y y) = x + y x + x y + y

which by cancellation gives yx+xy=0y x + x y = 0, or yx=(xy)=xyy x = -(x y) = x y.

Last revised on July 7, 2023 at 20:08:26. See the history of this page for a list of all contributions to it.