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. Un ejemplo es el anillo de enteros módulo 2.

Todo anillo booleano da lugar a un álgebra booleana, con la multiplicación de anillos correspondiente a la conjunción o encuentro ∧, y la suma de anillos a la disyunción exclusiva o diferencia simétrica (no a la disyunción ∨, que constituiría un semianillo). A la inversa, cada álgebra booleana da lugar a un anillo booleano. Los anillos booleanos llevan el nombre del fundador del álgebra booleana, George Boole.

Anotaciones

Hay al menos cuatro sistemas de notación diferentes e incompatibles para los anillos booleanos y las álgebras:

• En álgebra conmutativa la notación estándar es utilizar x+Sí. =x∧ ¬Sí.) ∨x∧Sí.) para la suma del anillo x y Sí., y uso xy = x∧Sí. para su producto.
• En lógica, una notación común es usar x∧Sí. para el encuentro (igual que el producto del anillo) y uso xAlternativaSí. para la unión, dada en términos de la notación de anillo (se dio justo arriba) por x+Sí.+xy.
• En la teoría de conjuntos y la lógica también es común utilizar x·Sí. para el encuentro, y x+Sí. para la unión xAlternativaSí.. Este uso de + es diferente del uso en la teoría del anillo.
• Una convención rara es usar xy para el producto y x⊕Sí. para la suma del anillo, en un esfuerzo para 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" se ha utilizado para referirse a un anillo booleano con una identidad. La existencia de la identidad es necesaria para considerar el anillo como un álgebra sobre el campo de dos elementos: de lo contrario no puede haber un homomorfismo de anillo (unitario) del campo de dos elementos en el anillo booleano. (Esto es lo mismo que el antiguo uso de los términos "anillo" y "álgebra" en la teoría de la medida).

Ejemplos

Un ejemplo de un 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. Más generalmente, con estas operaciones, cualquier campo de conjuntos es un anillo booleano. Según el teorema de representación de Stone, cada anillo booleano es isomorfo a un campo de conjuntos (tratados como un anillo con estas operaciones).

Relación con álgebras booleanas

Diagramas de Venn para las operaciones booleanas de conjunción, disyunción y complemento

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

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

x ∧ Sí. = xy,

x Alternativa Sí. = x ⊕ Sí. ⊕ xy,

¬x = 1 ⊕ x.

Estas operaciones satisfacen todos los axiomas de encuentros, uniones y complementos en un álgebra booleana. Así, cada anillo booleano se convierte en un álgebra booleana. De manera similar, cada álgebra booleana se convierte en un anillo booleano así:

xy = x ∧ Sí.,

x ⊕ Sí. =x Alternativa Sí.) ∧ ¬x ∧ Sí.).

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 es válido a partir de un álgebra booleana.

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

Propiedades de los anillos booleanos

Cada 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 cual da x ⊕ x = 0. Una demostración similar muestra que todo anillo booleano es conmutativo:

x ⊕ Sí. =x ⊕ Sí.)² = x² ⊕ xy ⊕ Yx ⊕ Sí.² = x ⊕ xy ⊕ Yx ⊕ Sí.

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

La propiedad x ⊕ x = 0 muestra que cualquier anillo booleano es un álgebra asociativa sobre el campo F₂ con dos elementos, precisamente de una 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: considere, por ejemplo, el anillo polinomial F₂[ X].

El anillo cociente R/I de cualquier anillo booleano R módulo cualquier ideal I es de nuevo un booleano anillo. Asimismo, cualquier subanillo de un anillo booleano es un anillo booleano.

Cualquier localización RS− − 1{displaystyle RS^{-1} de un anillo booleano R por un conjunto S⊆ ⊆ R{displaystyle Ssubseteq R} es un anillo booleano, ya que cada elemento en la localización es idempotente.

El anillo máximo de los cocientes Q()R){displaystyle Q(R)} (en el sentido de Utumi y Lambek) de un anillo booleano R es un anillo booleano, ya que cada endomorfismo parcial es idempotente.

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

Todo ideal generado de forma finita 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 conmutativos de von Neumann y, por lo tanto, absolutamente planos, lo que significa que todos los módulos sobre ellos son planos.

Unificación

La unificación en anillos booleanos es decidible, es decir, existen algoritmos para resolver ecuaciones arbitrarias sobre anillos booleanos. Tanto la unificación como la coincidencia en anillos booleanos libres generados finitamente son NP-completos, y ambos son NP-duros en anillos booleanos presentados finitamente. (De hecho, como cualquier problema de unificación f(X) = g(X) en un anillo booleano puede reescribirse como el problema de coincidencia 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 finitos de lo contrario (es decir, si los símbolos de función que no aparecen en la firma de los anillos booleanos son todos constantes, entonces existe un unificador más general y, de lo contrario, el mínimo completo conjunto de unificadores es finito).