Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Boolean ring
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Algebraic structure in mathematics}} In [[mathematics]], a '''Boolean ring''' {{math|''R''}} is a [[ring (mathematics)|ring]] for which {{math|1=''x''<sup>2</sup> = ''x''}} for all {{math|''x''}} in {{math|''R''}}, that is, a ring that consists of only [[idempotent element (ring theory)|idempotent element]]s.{{sfn|Fraleigh|1976|pp=25,200|ps=none}}{{sfn|Herstein|1975|pp=130,268|ps=none}}{{sfn|McCoy|1968|p=46|ps=none}} An example is the ring of [[modular arithmetic#Integers modulo m|integers modulo 2]]. Every Boolean ring gives rise to a [[Boolean algebra (structure)|Boolean algebra]], with ring multiplication corresponding to [[logical conjunction|conjunction]] or [[meet (mathematics)|meet]] {{math|β§}}, and ring addition to [[exclusive or|exclusive disjunction]] or [[symmetric difference]] (not [[logical disjunction|disjunction]] {{math|β¨}},{{refn|{{cite web|url=https://math.stackexchange.com/q/1621618|title = Disjunction as sum operation in Boolean Ring}}}} 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]]. == Notation == 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 {{math|1=''x'' + ''y'' = (''x'' β§ Β¬ ''y'') β¨ (Β¬ ''x'' β§ ''y'')}} for the ring sum of {{math|''x''}} and {{math|''y''}}, and use {{math|1=''xy'' = ''x'' β§ ''y''}} for their product. * In [[Mathematical logic|logic]], a common notation is to use {{math|1=''x'' β§ ''y''}} for the meet (same as the ring product) and use {{math|1=''x'' β¨ ''y''}} for the join, given in terms of ring notation (given just above) by {{math|1=''x'' + ''y'' + ''xy''}}. * In [[set theory]] and logic it is also common to use {{math|1=''x'' Β· ''y''}} for the meet, and {{math|''x'' + ''y''}} for the join {{math|1=''x'' β¨ ''y''}}.{{sfn|Koppelberg|1989|loc=Definition 1.1, p. 7|ps=none}} This use of {{math|+}} is different from the use in ring theory. * A rare convention is to use {{math|''xy''}} for the product and {{math|1=''x'' β ''y''}} for the ring sum, in an effort to avoid the ambiguity of {{math|+}}. 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 [[GF(2)|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]].{{efn|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.}}) == Examples == One example of a Boolean ring is the [[power set]] of any set {{math|''X''}}, where the addition in the ring is [[symmetric difference]], and the multiplication is [[intersection (set theory)|intersection]]. As another example, we can also consider the set of all [[finite set|finite]] or cofinite subsets of {{math|''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 for Boolean algebras|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 == [[File:Vennandornot.svg|center|500px|thumb|[[Venn diagram]]s for the Boolean operations of conjunction, disjunction, and complement]] Since the join operation {{math|β¨}} in a Boolean algebra is often written additively, it makes sense in this context to denote ring addition by {{math|β}}, a symbol that is often used to denote [[exclusive or]]. Given a Boolean ring {{math|''R''}}, for {{math|''x''}} and {{math|''y''}} in {{math|''R''}} we can define : {{math|1=''x'' β§ ''y'' = ''xy''}}, : {{math|1=''x'' β¨ ''y'' = ''x'' β ''y'' β ''xy''}}, : {{math|1=Β¬''x'' = 1 β ''x''}}. These operations then satisfy all of the axioms for meets, joins, and complements in a [[Boolean algebra (structure)|Boolean algebra]]. Thus every Boolean ring becomes a Boolean algebra. Similarly, every Boolean algebra becomes a Boolean ring thus: : {{math|1=''xy'' = ''x'' β§ ''y'',}} : {{math|1=''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 {{math|''R''}} satisfies {{math|1=''x'' β ''x'' = 0}} for all {{math|''x''}} in {{math|''R''}}, because we know : {{math|1=''x'' β ''x'' = (''x'' β ''x'')<sup>2</sup> = ''x''<sup>2</sup> β ''x''<sup>2</sup> β ''x''<sup>2</sup> β ''x''<sup>2</sup> = ''x'' β ''x'' β ''x'' β ''x''}} and since {{math|(''R'', β)}} is an abelian group, we can subtract {{math|''x'' β ''x''}} from both sides of this equation, which gives {{math|1=''x'' β ''x'' = 0}}. A similar proof shows that every Boolean ring is [[commutative]]: : {{math|1=''x'' β ''y'' = (''x'' β ''y'')<sup>2</sup> = ''x''<sup>2</sup> β ''xy'' β ''yx'' β ''y''<sup>2</sup> = ''x'' β ''xy'' β ''yx'' β ''y''}} and this yields {{math|1=''xy'' β ''yx'' = 0}}, which means {{math|1=''xy'' = ''yx''}} (using the first property above). The property {{math|1=''x'' β ''x'' = 0}} shows that any Boolean ring is an [[associative algebra]] over the [[field (mathematics)|field]] {{math|'''F'''<sub>2</sub>}} with two elements, in precisely one way.{{citation needed|date=March 2023}} In particular, any finite Boolean ring has as [[cardinality]] a [[power of two]]. Not every unital associative algebra over {{math|'''F'''<sub>2</sub>}} is a Boolean ring: consider for instance the [[polynomial ring]] {{math|'''F'''<sub>2</sub>[''X'']}}. The quotient ring {{math|1=''R'' / ''I''}} of any Boolean ring {{math|''R''}} modulo any ideal {{math|''I''}} is again a Boolean ring. Likewise, any [[subring]] of a Boolean ring is a Boolean ring. Any [[localization_of_a_ring|localization]] {{math|''RS''<sup>β1</sup>}} of a Boolean ring {{math|''R''}} by a set {{math|''S'' β ''R''}} is a Boolean ring, since every element in the localization is idempotent. The maximal ring of quotients {{math|''Q''(''R'')}} (in the sense of Utumi and [[Joachim Lambek|Lambek]]) of a Boolean ring {{math|''R''}} is a Boolean ring, since every partial endomorphism is idempotent.{{sfn|Brainerd|Lambek|1959|loc=Corollary 2|ps=none}} Every [[prime ideal]] {{math|''P''}} in a Boolean ring {{math|''R''}} is [[maximal ideal|maximal]]: the [[quotient ring]] {{math|''R'' / ''P''}} is an [[integral domain]] and also a Boolean ring, so it is isomorphic to the [[field (mathematics)|field]] {{math|'''F'''<sub>2</sub>}}, which shows the maximality of {{math|''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 ideal|principal]] (indeed, {{math|1=(''x'',''y'') = (''x'' + ''y'' + ''xy''))}}. Furthermore, as all elements are idempotents, Boolean rings are commutative [[von Neumann regular ring]]s and hence absolutely flat, which means that every module over them is [[flat module|flat]]. == Unification == [[Unification (logic)|Unification]] in Boolean rings is [[Decidability (logic)|decidable]],{{sfn|Martin|Nipkow|1986|ps=none}} that is, algorithms exist to solve arbitrary equations over Boolean rings. Both unification and matching in [[finitely generated algebra|finitely generated]] free Boolean rings are [[NP-complete]], and both are [[NP-hard]] in [[finitely presented algebra|finitely presented]] Boolean rings.{{sfn|Kandri-Rody|Kapur|Narendran|1985|ps=none}} (In fact, as any unification problem {{math|1=''f''(''X'') = ''g''(''X'')}} in a Boolean ring can be rewritten as the matching problem {{math|1=''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 [[Unification (computer science)#Unification problem, solution set|minimal complete set of unifiers]] is finite).{{sfn|Boudet|Jouannaud|Schmidt-SchauΓ|1989|ps=none}} == See also == * [[Ring sum normal form]] == Notes == {{notelist}} == Citations == {{reflist}} == References == * {{citation | last1=Atiyah | first1=Michael Francis | author-link1=Michael Atiyah | last2=Macdonald | first2=I. G. | author-link2=Ian G. Macdonald | title=Introduction to Commutative Algebra | publisher=Westview Press | isbn=978-0-201-40751-8 | year=1969}} * {{cite journal | last1=Boudet | first1=A. | last2=Jouannaud | first2=J.-P. | author2-link=J.-P. Jouannaud | last3=Schmidt-SchauΓ | first3=M. | year=1989 | title=Unification of Boolean Rings and Abelian Groups | journal=[[Journal of Symbolic Computation]] | volume=8 | issue=5 | pages=449β477 | doi=10.1016/s0747-7171(89)80054-9 | doi-access= }} * {{cite journal |last1=Brainerd |first1=B. |last2=Lambek |first2=J. |title=On the ring of quotients of a Boolean ring |journal=[[Canadian Mathematical Bulletin]] |date=1959 |volume=2 |pages=25β29 |doi=10.4153/CMB-1959-006-x |doi-access=free }} * {{citation | last1 = Fraleigh | first1 = John B. | year = 1976 | isbn = 978-0-201-01984-1 | title = A First Course In Abstract Algebra | edition = 2nd | publisher = [[Addison-Wesley]] }} * {{citation | last1 = Herstein | first1 = I. N. | author-link= Israel Nathan Herstein | year = 1975 | title = Topics In Algebra | edition= 2nd | publisher = [[John Wiley & Sons]] }} * {{cite book | last1 = Kandri-Rody | first1 = Abdelilah | last2 = Kapur | first2 = Deepak | last3 = Narendran | first3 = Paliath | year = 1985 | doi = 10.1007/3-540-15976-2_17 | chapter = An ideal-theoretic approach to word problems and unification problems over finitely presented commutative algebras | title = Rewriting Techniques and Applications | volume = 202 | pages = 345β364 | series = Lecture Notes in Computer Science | isbn = 978-3-540-15976-6 }} * {{cite book | last1=Koppelberg |first1=Sabine |title=Handbook of Boolean algebras, vol. 1 |date=1989 |publisher=North-Holland |location=Amsterdam |isbn=0-444-70261-X}} * {{cite book| last1=Martin |first1=U. |last2=Nipkow |first2=T. |chapter=Unification in Boolean Rings |title=Proc. 8th CADE |year=1986 |volume=230 |pages=506β513 | publisher=Springer | editor=JΓΆrg H. Siekmann |series=LNCS |doi=10.1007/3-540-16780-3_115| isbn=978-3-540-16780-8 }} * {{citation | first=Neal H. |last=McCoy |year=1968 |title=Introduction To Modern Algebra | edition = Revised |publisher=[[Allyn and Bacon]] |lccn=68015225}} * {{eom |title=Boolean ring |oldid=18972 |first=Yu. M. |last=Ryabukhin}} == External links == * John Armstrong, [http://unapologetic.wordpress.com/2010/08/04/boolean-rings Boolean Rings] {{Authority control}} [[Category:Ring theory]] [[Category:Boolean algebra]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Authority control
(
edit
)
Template:Citation
(
edit
)
Template:Citation needed
(
edit
)
Template:Cite book
(
edit
)
Template:Cite journal
(
edit
)
Template:Efn
(
edit
)
Template:Eom
(
edit
)
Template:Math
(
edit
)
Template:Notelist
(
edit
)
Template:Reflist
(
edit
)
Template:Refn
(
edit
)
Template:Sfn
(
edit
)
Template:Short description
(
edit
)