Boolean ring

TheInfoList

OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a Boolean ring ''R'' is a ring for which ''x''2 = ''x'' for all ''x'' in ''R'', that is, a ring that consists only of idempotent elements. An example is the ring of integers modulo 2. Every Boolean ring gives rise to a
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in ...
, with ring multiplication corresponding to conjunction or meet ∧, and ring addition to
exclusive disjunction Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , , ...
or
symmetric difference In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and \ is \. Th ...
(not
disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
∨, which would constitute a semiring). Conversely, every Boolean algebra gives rise to a Boolean ring. 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 Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premise ...
, 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 Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
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 In mathematics, the concept of a measure is a generalization and formalization of geometrical measures (length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many simila ...
.)

# Examples

One example of a Boolean ring is the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is pos ...
of any set ''X'', where the addition in the ring is
symmetric difference In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and \ is \. Th ...
, and the multiplication is
intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...
. 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

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 Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
. 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 In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in ...
. 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 In ring theory, a branch of abstract algebra, a ring homomorphism is a structure-preserving function between two rings. More explicitly, if ''R'' and ''S'' are rings, then a ring homomorphism is a function such that ''f'' is: :addition preserv ...
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bico ...
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 In ring theory, a branch of abstract algebra, a quotient ring, also known as factor ring, difference ring or residue class ring, is a construction quite similar to the quotient group in group theory and to the quotient space in linear algebra. ...
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'')2 = ''x''2 ⊕ ''x''2 ⊕ ''x''2 ⊕ ''x''2 = ''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 In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
: :''x'' ⊕ ''y'' = (''x'' ⊕ ''y'')2 = ''x''2 ⊕ ''xy'' ⊕ ''yx'' ⊕ ''y''2 = ''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 In mathematics, an associative algebra ''A'' is an algebraic structure with compatible operations of addition, multiplication (assumed to be associative), and a scalar multiplication by elements in some field ''K''. The addition and multiplica ...
over the field F2 with two elements, in precisely one way. In particular, any finite Boolean ring has as
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
a
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negativ ...
. Not every unital associative algebra over F2 is a Boolean ring: consider for instance the
polynomial ring In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variable ...
F2 'X'' The quotient ring ''R''/''I'' of any Boolean ring ''R'' modulo any ideal ''I'' is again a Boolean ring. Likewise, any
subring In mathematics, a subring of ''R'' is a subset of a ring that is itself a ring when binary operations of addition and multiplication on ''R'' are restricted to the subset, and which shares the same multiplicative identity as ''R''. For those ...
of a Boolean ring is a Boolean ring. Any
localization Localization or localisation may refer to: Biology * Localization of function, locating psychological functions in the brain or nervous system; see Linguistic intelligence * Localization of sensation, ability to tell what part of the body is ...
$RS^$ of a Boolean ring ''R'' by a set $S\subseteq R$ is a Boolean ring, since every element in the localization is idempotent. The maximal ring of quotients $Q\left(R\right)$ (in the sense of Utumi and Lambek) of a Boolean ring ''R'' is a Boolean ring, since every partial endomorphism is idempotent. Every
prime ideal In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together wi ...
''P'' in a Boolean ring ''R'' is maximal: the
quotient ring In ring theory, a branch of abstract algebra, a quotient ring, also known as factor ring, difference ring or residue class ring, is a construction quite similar to the quotient group in group theory and to the quotient space in linear algebra. ...
''R''/''P'' is an
integral domain In mathematics, specifically abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural set ...
and also a Boolean ring, so it is isomorphic to the field F2, which shows the maximality of ''P''. Since maximal ideals are always prime, prime ideals and maximal ideals coincide in Boolean rings. Every finitely generated ideal of a Boolean ring is principal (indeed, (''x'',''y'') = (''x'' + ''y'' + ''xy'')). Furthermore, as all elements are idempotents, Boolean rings are commutative von Neumann regular rings and hence absolutely flat, which means that every module over them is flat.

# Unification

Unification in Boolean rings is decidable, 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 both are NP-hard in finitely presented Boolean rings. (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).

* Ring sum normal form