Anillo booleano

En matemáticas , un anillo booleano R es un anillo para el cual x ² = x para todo x en R , es decir, un anillo que consta solo de elementos idempotentes . ^{[ 1 ] [ 2 ] [ 3 ]} Un ejemplo es el anillo de enteros módulo 2 .

Todo anillo booleano da lugar a un álgebra booleana , donde la multiplicación de anillos corresponde a la conjunción o intersección ∧ , y la adición de anillos a la disyunción exclusiva o diferencia simétrica (no a la disyunción ∨ , ^{[ 4 ]} que constituiría un semianillo ). Recíprocamente, toda álgebra booleana da lugar a un anillo booleano. Los anillos booleanos reciben su nombre del fundador del álgebra booleana, George Boole .

Existen al menos cuatro sistemas de notación diferentes e incompatibles para anillos y álgebras booleanas:

• En álgebra conmutativa, la notación estándar es usar x + y = ( x ∧ ¬ y ) ∨ (¬ x ∧ y ) para la suma de anillos de x e y , y usar xy = x ∧ y para su producto.
• En lógica , una notación común es usar x ∧ y para la intersección (igual que el producto de anillos) y usar x ∨ y para la unión, dada en términos de notación de anillos (dada justo arriba) por x + y + xy .
• En teoría de conjuntos y lógica también es común usar x · y para la intersección, y x + y para la unión x ∨ y . ^{[ 5 ]} Este uso de + es diferente del uso en teoría de anillos.
• Una convención poco común es usar xy para el producto y x ⊕ y para la suma del anillo, en un esfuerzo por evitar la ambigüedad de + .

Históricamente, el término «anillo booleano» se ha utilizado para referirse a un «anillo booleano posiblemente sin identidad», y «álgebra booleana» para referirse a un anillo booleano con identidad. La existencia de la identidad es necesaria para considerar el anillo como un álgebra sobre el cuerpo de dos elementos ; de lo contrario, no puede existir un homomorfismo de anillos (unitario) del cuerpo de dos elementos en el anillo booleano. (Esto es equivalente al uso antiguo de los términos «anillo» y «álgebra» en la teoría de la medida . ^{[ a ]} )

Un ejemplo de anillo booleano es el conjunto potencia de cualquier conjunto X , donde la suma en el anillo es la diferencia simétrica y la multiplicación es la intersección . Como otro ejemplo, también podemos considerar el conjunto de todos los subconjuntos finitos o cofinitos de X , nuevamente con la diferencia simétrica y la intersección como operaciones. De manera más general, con estas operaciones, cualquier cuerpo de conjuntos es un anillo booleano. Según el teorema de representación de Stone, todo anillo booleano es isomorfo a un cuerpo de conjuntos (tratado como un anillo con estas operaciones).

Dado que la operación de unión ∨ en un álgebra booleana a menudo se escribe de forma aditiva, tiene sentido en este contexto denotar la suma de anillos mediante ⊕ , un símbolo que se usa a menudo para denotar la disyunción exclusiva .

Dado un anillo booleano R , para x e y en R podemos definir

x ∧ y = xy ,

x ∨ y = x ⊕ y ⊕ xy ,

¬ x = 1 ⊕ x .

Estas operaciones satisfacen entonces todos los axiomas para intersecciones, uniones y complementos en un álgebra booleana . Por lo tanto, todo anillo booleano se convierte en un álgebra booleana. De manera similar, todo álgebra booleana se convierte en un anillo booleano de la siguiente manera:

xy = x ∧ y ,

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

Si un anillo booleano se traduce a un álgebra booleana de esta manera, y luego el álgebra booleana se traduce a un anillo, el resultado es el anillo original. El resultado análogo se cumple partiendo de un álgebra booleana.

Una aplicación entre dos anillos booleanos es un homomorfismo de anillos si y solo si es un homomorfismo de las álgebras booleanas correspondientes. Además, un subconjunto de un anillo booleano es un ideal de anillo (ideal de anillo primo, ideal de anillo maximal) si y solo si es un ideal de orden (ideal de orden primo, ideal de orden maximal) del álgebra booleana. El anillo cociente de un anillo booleano módulo un ideal de anillo corresponde al álgebra de factores del álgebra booleana correspondiente módulo el ideal de orden correspondiente.

Todo anillo booleano R satisface x ⊕ x = 0 para todo x en R , porque sabemos

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

y dado que ( R , ⊕) es un grupo abeliano, podemos restar x ⊕ x de ambos lados de esta ecuación, lo que da x ⊕ x = 0. Una demostración similar muestra que todo anillo booleano es conmutativo :

x ⊕ y = ( x ⊕ y ) ² = x ² ⊕ xy ⊕ yx ⊕ y ² = x ⊕ xy ⊕ yx ⊕ y y esto produce xy ⊕ yx = 0 , lo que significa xy = yx (usando la primera propiedad anterior).

La propiedad x ⊕ x = 0 muestra que cualquier anillo booleano es un álgebra asociativa sobre el cuerpo F ₂ con dos elementos, de una sola manera. En particular, cualquier anillo booleano finito tiene como cardinalidad una potencia de dos . No toda álgebra asociativa unitaria sobre F ₂ es un anillo booleano: considérese, por ejemplo, el anillo de polinomios F ₂ [ X ] .

El anillo cociente R / I de cualquier anillo booleano R módulo cualquier ideal I es también un anillo booleano. Del mismo modo, cualquier subanillo de un anillo booleano es un anillo booleano.

Cualquier localización RS ⁻¹ de un anillo booleano R por un conjunto S ⊆ R es un anillo booleano, ya que cada elemento en la localización es idempotente.

El anillo maximal de cocientes Q ( R ) (en el sentido de Utumi y Lambek ) de un anillo booleano R es un anillo booleano, puesto que todo endomorfismo parcial es idempotente. ^{[ 6 ]}

Todo ideal primo P en un anillo booleano R es maximal : el anillo cociente R / P es un dominio de integridad y también un anillo booleano, por lo que es isomorfo al cuerpo F² , que demuestra la maximalidad de P. Dado que los ideales maximales son siempre primos, los ideales primos y _los ideales maximales coinciden en los anillos booleanos.

Todo ideal finitamente generado de un anillo booleano es principal (de hecho, ( x , y ) = ( x + y + xy )) . Además, como todos los elementos son idempotentes, los anillos booleanos son anillos regulares de von Neumann conmutativos y, por lo tanto, absolutamente planos, lo que significa que todo módulo sobre ellos es plano .

La unificación en anillos booleanos es decidible , ^{[ 7 ]} es decir, existen algoritmos para resolver ecuaciones arbitrarias sobre anillos booleanos. Tanto la unificación como el emparejamiento en anillos booleanos libres finitamente generados son NP-completos , y ambos son NP-difíciles en anillos booleanos finitamente presentados . ^{[ 8 ]} (De hecho, como cualquier problema de unificación f ( X ) = g ( X ) en un anillo booleano puede reescribirse como el problema de emparejamiento f ( X ) + g ( X ) = 0 , los problemas son equivalentes).

La unificación en anillos booleanos es unitaria si todos los símbolos de función no interpretados son nulos y finita en caso contrario (es decir, si los símbolos de función que no aparecen en la signatura de los anillos booleanos son todos constantes, entonces existe un unificador más general , y en caso contrario el conjunto mínimo completo de unificadores es finito). ^{[ 9 ]}

• Suma de anillos en forma normal

• Atiyah, Michael Francis ; Macdonald, IG (1969), Introducción al álgebra conmutativa , Westview Press, ISBN 978-0-201-40751-8
• Boudet, A.; Jouannaud, J.-P. ; Schmidt-Schauß, M. (1989). "Unificación de anillos booleanos y grupos abelianos". Journal of Symbolic Computation . 8 (5): 449– 477. doi : 10.1016/s0747-7171(89)80054-9 .
• Brainerd, B.; Lambek, J. (1959). "Sobre el anillo de cocientes de un anillo booleano" . Boletín Matemático Canadiense . 2 : 25–29 . doi : 10.4153/CMB-1959-006-x .
• Fraleigh, John B. (1976), Un primer curso de álgebra abstracta (2.ª  ed.), Addison-Wesley , ISBN 978-0-201-01984-1
• Herstein, IN (1975), Temas de álgebra (2.ª  ed.), John Wiley & Sons
• Kandri-Rody, Abdelilah; Kapur, Deepak; Narendran, Paliath (1985). «Un enfoque teórico de ideales para problemas de palabras y problemas de unificación sobre álgebras conmutativas finitamente presentadas». Técnicas y aplicaciones de reescritura . Notas de clase en informática. Vol.  202. págs. 345–364 . doi : 10.1007/3-540-15976-2_17 . ISBN  978-3-540-15976-6.
• Koppelberg, Sabine (1989). Manual de álgebras booleanas, vol. 1. Ámsterdam: North-Holland. ISBN 0-444-70261-X.
• Martin, U.; Nipkow, T. (1986). «Unificación en anillos booleanos». En Jörg H. Siekmann (ed.). Actas del 8.º CADE . LNCS. Vol.  230. Springer. pp. 506–513 . doi : 10.1007/3-540-16780-3_115 . ISBN  978-3-540-16780-8.
• McCoy, Neal H. (1968), Introducción al álgebra moderna (  Edición revisada), Allyn and Bacon , LCCN 68015225 
• Ryabukhin, Yu. M. (2001) [1994], "Anillo booleano" , Enciclopedia de Matemáticas , EMS Press

• John Armstrong, Anillos booleanos