¿Es decidible la teoría ecuacional de las álgebras booleanas generalizadas?

Question

Se puede comprobar fácilmente mediante el uso de tablas de verdad si una fórmula proposicional es una identidad lógica. Así, la teoría de las álgebras booleanas es decidible. Pero un álgebra booleana generalizada (GBA), es decir, un álgebra booleana con un elemento superior opcional que suele llamarse "unidad" y que a veces se denota como " $1$ ", es necesariamente infinito, y dicho procedimiento de decisión podría ser más complejo. Sin embargo, tales álgebras parecen ser lo suficientemente simples como para esperar que su teoría sea decidible. El universo de la teoría de conjuntos con las operaciones de unión, intersección y diferencia es un ejemplo de una GBA "grande": una GBA sobre una clase.

Un GBA se define estrictamente como un entramado distributivo relativamente complementado con $0$ ( https://planetmath.org/generalizedbooleanalgebra ), o como un entramado con $0$ cuyo ideal principal es un álgebra booleana.

Answer 1

La teoría ecuacional de las GBAs es exactamente la misma que la teoría ecuacional de las álgebras booleanas restringida al lenguaje de las GBAs (es decir, con sólo complementos relativos en lugar de complementos y sin $1$ ).

De hecho, cualquier GBA se incrusta en un álgebra de Boole (por complementos formalmente contiguos). En concreto, si $A$ es un GBA, dejemos que $B=\{0,1\}\times A$ . Pida $B$ diciendo $(0,a)\leq (0,b)$ si $a\leq b$ , $(1,a)\leq(1,b)$ si $b\leq a$ y $(0,a)\leq(1,b)$ si $a\wedge b=0$ (y $(1,a)\not\leq(0,b)$ para todos $a,b$ ). Entonces es fácil comprobar que $B$ es un álgebra booleana, y $A$ se incrusta como un sub-GBA de $B$ a través de $a\mapsto (0,a)$ . La idea es que $(0,a)$ representa $a$ y $(1,a)$ representa el complemento de $a$ .

(Desde la perspectiva de los anillos booleanos, un GBA no es más que un anillo booleano posiblemente no vital, y esta construcción sólo da su unitización como un $\mathbb{F}_2$ -de la álgebra. El grupo aditivo de la unitización es $\mathbb{F}_2\oplus A$ y la multiplicación se define por $(i+a)(j+b)=ij+(ib+ja+ab)$ para $i,j\in\mathbb{F}_2$ y $a,b\in A$ .)

Por lo tanto, cada ecuación en el lenguaje de GBAs que se mantiene en cada álgebra booleana también se mantiene en cada GBA (y obviamente a la inversa, ya que cada álgebra booleana es un GBA), y así la teoría ecuacional de GBAs es decidible (por el mismo algoritmo).