Boolean ring

In mathematics, a Boolean ring R is a ring for which x² = x for all x in R,^[1]^[2]^[3] such as the ring of integers modulo 2. That is, R consists only of idempotent elements.^[4]^[5]

Every Boolean ring gives rise to a Boolean algebra, with ring multiplication corresponding to conjunction or meet ∧, and ring addition to exclusive disjunction or symmetric difference (not disjunction ∨, which would constitute a semiring). Boolean rings are named after the founder of Boolean algebra, George Boole.

Notations

There are at least four different and incompatible systems of notation for Boolean rings and algebras.

In commutative algebra the standard notation is to use x + y = (x ∧ ¬ y) ∨ (¬ x ∧ y) for the ring sum of x and y, and use xy = x ∧ y for their product.
In logic, a common notation is to use x ∧ y for the meet (same as the ring product) and use x ∨ y for the join, given in terms of ring notation (given just above) by x + y + xy.
In set theory and logic it is also common to use x · y for the meet, and x + y for the join x ∨ y. This use of + is different from the use in ring theory.
A rare convention is to use xy for the product and x ⊕ y for the ring sum, in an effort to avoid the ambiguity of +.

Historically, the term "Boolean ring" has been used to mean a "Boolean ring possibly without an identity", and "Boolean algebra" has been used to mean a Boolean ring with an identity. The existence of the identity is necessary to consider the ring as an algebra over the field of two elements: otherwise there cannot be a (unital) ring homomorphism of the field of two elements into the Boolean ring. (This is the same as the old use of the terms "ring" and "algebra" in measure theory.^{[lower-alpha 1]})

Examples

One example of a Boolean ring is the power set of any set X, where the addition in the ring is symmetric difference, and the multiplication is intersection. As another example, we can also consider the set of all finite or cofinite subsets of X, again with symmetric difference and intersection as operations. More generally with these operations any field of sets is a Boolean ring. By Stone's representation theorem every Boolean ring is isomorphic to a field of sets (treated as a ring with these operations).

Relation to Boolean algebras

Venn diagrams for the Boolean operations of conjunction, disjunction, and complement

Since the join operation ∨ in a Boolean algebra is often written additively, it makes sense in this context to denote ring addition by ⊕, a symbol that is often used to denote exclusive or.

Given a Boolean ring R, for x and y in R we can define

x ∧ y = xy,

x ∨ y = x ⊕ y ⊕ xy,

¬x = 1 ⊕ x.

These operations then satisfy all of the axioms for meets, joins, and complements in a Boolean algebra. Thus every Boolean ring becomes a Boolean algebra. Similarly, every Boolean algebra becomes a Boolean ring thus:

xy = x ∧ y,

x ⊕ y = (x ∨ y) ∧ ¬(x ∧ y).

If a Boolean ring is translated into a Boolean algebra in this way, and then the Boolean algebra is translated into a ring, the result is the original ring. The analogous result holds beginning with a Boolean algebra.

A map between two Boolean rings is a ring homomorphism if and only if it is a homomorphism of the corresponding Boolean algebras. Furthermore, a subset of a Boolean ring is a ring ideal (prime ring ideal, maximal ring ideal) if and only if it is an order ideal (prime order ideal, maximal order ideal) of the Boolean algebra. The quotient ring of a Boolean ring modulo a ring ideal corresponds to the factor algebra of the corresponding Boolean algebra modulo the corresponding order ideal.

Properties of Boolean rings

Every Boolean ring R satisfies x ⊕ x = 0 for all x in R, because we know

x ⊕ x = (x ⊕ x)² = x² ⊕ x² ⊕ x² ⊕ x² = x ⊕ x ⊕ x ⊕ x

and since (R,⊕) is an abelian group, we can subtract x ⊕ x from both sides of this equation, which gives x ⊕ x = 0. A similar proof shows that every Boolean ring is commutative:

x ⊕ y = (x ⊕ y)² = x² ⊕ xy ⊕ yx ⊕ y² = x ⊕ xy ⊕ yx ⊕ y

and this yields xy ⊕ yx = 0, which means xy = yx (using the first property above).

The property x ⊕ x = 0 shows that any Boolean ring is an associative algebra over the field F₂ with two elements, in just one way. In particular, any finite Boolean ring has as cardinality a power of two. Not every associative algebra with one over F₂ is a Boolean ring: consider for instance the polynomial ring F₂[X].

The quotient ring R/I of any Boolean ring R modulo any ideal I is again a Boolean ring. Likewise, any subring of a Boolean ring is a Boolean ring.

Every prime ideal P in a Boolean ring R is maximal: the quotient ring R/P is an integral domain and also a Boolean ring, so it is isomorphic to the field F₂, which shows the maximality of P. Since maximal ideals are always prime, prime ideals and maximal ideals coincide in Boolean rings.

Boolean rings are von Neumann regular rings.

Boolean rings are absolutely flat: this means that every module over them is flat.

Every finitely generated ideal of a Boolean ring is principal (indeed, (x,y)=(x+y+xy)).

Unification

Unification in Boolean rings is decidable,^[6] that is, algorithms exist to solve arbitrary equations over Boolean rings. Both unification and matching in finitely generated free Boolean rings are NP-complete, and NP-hard in finitely presented Boolean rings.^[7] (In fact, as any unification problem f(X) = g(X) in a Boolean ring can be rewritten as the matching problem f(X) + g(X) = 0, the problems are equivalent.)

Unification in Boolean rings is unitary if all the uninterpreted function symbols are nullary and finitary otherwise (i.e. if the function symbols not occurring in the signature of Boolean rings are all constants then there exists a most general unifier, and otherwise the minimal complete set of unifiers is finite).^[8]

Notes

↑ When a Boolean ring has an identity, then a complement operation becomes definable on it, and a key characteristic of the modern definitions of both Boolean algebra and sigma-algebra is that they have complement operations.

References

↑ Fraleigh (1976, p. 200)
↑ Herstein (1964, p. 91)
↑ McCoy (1968, p. 46)
↑ Fraleigh (1976, p. 25)
↑ Herstein (1964, p. 224)
↑ Martin, U.; Nipkow, T. (1986). "Unification in Boolean Rings". In Jörg H. Siekmann. Proc. 8th CADE. LNCS. 230. Springer. pp. 506–513.
↑ Kandri-Rody, A., Kapur, D., and Narendran, P., "An ideal-theoretic approach to word problems and unification problems over finitely presented commutative algebras," Proc. of the first Conference on Rewriting Techniques and Applications, Dijon, France, May 1985, LNCS 202, Springer Verlag, New York, 345-364.
↑ A. Boudet, J.-P. Jouannaud, M. Schmidt-Schauß (1989). "Unification of Boolean Rings and Abelian Groups" (PDF). Journal of Symbolic Computation. 8: 449–477. doi:10.1016/s0747-7171(89)80054-9.

Bibliography

Atiyah, Michael Francis; Macdonald, I. G. (1969), Introduction to Commutative Algebra, Westview Press, ISBN 978-0-201-40751-8
Fraleigh, John B. (1976), A First Course In Abstract Algebra (2nd ed.), Reading: Addison-Wesley, ISBN 0-201-01984-1
Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN 978-1114541016
McCoy, Neal H. (1968), Introduction To Modern Algebra (Revised ed.), Boston: Allyn and Bacon, LCCN 68015225
Ryabukhin, Yu. M. (2001), "Boolean_ring", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4

External links

John Armstrong, Boolean Rings

This article is issued from Wikipedia - version of the 10/11/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.