ALGEBRA DE BOOLE

 Algebras de Boole ´ Sea (P, ≤) un conjunto parcialmente ordenado y sea S un subconjunto de P. Una cota superior de S es un elemento c ∈ P tal que s ≤ c para todo s ∈ S. Una cota inferior de S es un elemento d ∈ P tal que d ≤ s para todo s ∈ S. Una cota superior (inferior) c de S se denomina el supremo (´ınfimo) de S si es menor o igual (mayor o igual) que cualquier otra cota superior (cota inferior) de S. Si un subconjunto S de P admite supremo (´ınfimo) lo denotaremos por sup S (inf S). En el caso que S tenga dos elementos, x, y, el supremo (´ınfimo) de S ser´a denotado por x ∨ y (x ∧ y). Definici´on 1 Un ´algebra de Boole es un conjunto parcialmente ordenado (B, ≤) que verifica las siguientes condiciones: (i) B tiene un primer elemento denotado con 0 y un ´ultimo elemento denotado con 1, esto es: si x ∈ B, entonces 0 ≤ x y x ≤ 1. (ii) Todo par de elementos x, y de B admite supremo x ∨ y e ´ınfimo x ∧ y. (iii) Para todo x ∈ B, existe y ∈ B tal que x ∨ y = 1 y x ∧ y = 0. (iv) Si x, y, z ∈ B, entonces x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z). Observaciones 1 1) Un reticulado es un conjunto parcialmente ordenado que verifica la condici´on (ii) de la definici´on anterior. Si adem´as el reticulado verifica la condici´on (iv), se dice reticulado distributivo. Un reticulado que verifica las condiciones (i) y (iii) de la definici´on anterior se denomina reticulado complementado. Por lo tanto en el lenguaje de los reticulados un conjunto parcialmente ordenado (B, ≤) es un ´algebra de Boole si y s´olo si es un reticulado distributivo complementado. 1 2) Sea B un ´algebra de Boole y sea x ∈ B. De acuerdo a la condici´on (iii) existe y ∈ B tal que x ∨ y = 1 y x ∧ y = 0. M´as a´un, de la propiedad distributiva se deduce que dicho elemento y es ´unico y ser´a denotado por ¬x. El elemento ¬x se denomina el complemento de x. Ejemplos 1 1) El conjunto 2 = {0, 1} con el orden natural 0 < 1 es un ´algebra de Boole llamada el ´algebra de Boole minimal. 2) Si X es un conjunto, entonces el conjunto de partes de X, notado con P(X), es un ´algebra de Boole donde el orden definido es la relaci´on de inclusi´on, el primer elemento es el conjunto ∅, el ´ultimo elemento es X, y si A, B ∈ P(X), entonces A ∨ B = A ∪ B y A ∧ B = A ∩ B. M´as a´un, el complemento de un elemento A ∈ P(X) coincide con el habitual complemento conjuntista X\A. 3) Consideremos el lenguaje L de la l´ogica proposicional cuyo alfabeto consiste de un conjunto infinito numerable de s´ımbolos p1, p2, . . . , pn, . . . llamadas variables proposicionales, dos par´entesis (,) y el conjunto de conectivos {¬,∨,∧,→}. Los elementos de L se denominan f´ormulas del c´alculo proposicional y se definen inductivamente de acuerdo a la siguientes reglas: a) Las variables proposicionales son f´ormulas, b) si α es una f´ormula, entonces ¬α es una f´ormula y c) si α, β son f´ormulas, entonces (α ∨ β),(α ∧ β) y (α → β) son f´ormulas. Denotemos con F al conjunto de todas las f´ormulas. Una valuaci´on es una funci´on v : F → 2 que verifica v(¬α) = 1 − v(α), v(α ∨ β) = max(v(α), v(β)), v(α ∧ β) = min(v(α), v(β)) y v(α → β) = max(1 − v(α), v(β)), donde si x, y ∈ 2, max(x, y) y min(x, y) denotan el m´aximo y el m´ınimo de x, y respectivamente. Una f´ormula α se dice tautolog´ıa (contradicci´on) si v(α) = 1 (v(α) = 0) para toda valuaci´on v. Definimos en F la siguiente relaci´on de equivalencia ≡, donde α, β ∈ F: α ≡ β si y s´olo si v(α) = v(β) para toda valuaci´on v (o equivalentemente (α → β) y (β → α) son tautolog´ıas. Denotemos con F/ ≡ al conjunto cociente de F v´ıa la relaci´on de equivalencia ≡ y sea π : F → F/ ≡ la proyecci´on can´onica. Si definimos en F/equiv la relaci´on de orden dada por π(α) ≤ π(β) si y s´olo si (α → β) es tautolog´ıa, entonces ≤ est´a bien definida. M´as a´un (F/ ≡, ≤) es un ´algebra de Boole denominada el ´algebra de Lindenbaum de la l´ogica proposicional; en el que el primer elemento es π((α ∧ ¬α)), el ´ultimo elemento es π((α ∨ ¬α)) con α cualquier f´ormula, el supremo e ´ınfimo est´an dados por π(α) ∨ π(β) = π(α ∨ β), π(α) ∧ π(β) = π(α ∧ β) y el complemento por ¬π(α) = π(¬α). 2 4) Como una generalizaci´on del ejemplo 3), consideremos un lenguaje L de primer orden y sea T una teor´ıa de L, esto es, un conjunto de enunciados. Se define en el conjunto F de todas las f´ormulas de L la relaci´on de equivalencia ∼ mediante la regla: α ∼ β si y s´olo si (α → β) y (β → α) son demostrables en la teor´ıa T, donde α, β son f´ormulas . Si π : F → F/ ∼ es la proyecci´on can´onica, entonces F/ ∼ con el orden definido por π(α) ≤ π(β) si y s´olo si (α → β) es demostrable es una relaci´on bien definida y con este orden parcial (F/ ≡, ≤) es un ´algebra de Boole conocida como el ´algebra de LindenbaumTarski de la teor´ıa Ty que se denota por B(T). 5) Sea n un n´umero natural y sea Div(n) el conjunto de los divisores de n. Es f´acil ver que la relaci´on x ≤ y si y s´olo si x es divisor de y define una relaci´on de orden parcial en Div(n), donde x, y ∈ Div(n). Adem´as, Div(n) resulta ser un reticulado distributivo con primer elemento 1 y ´ultimo elemento n; y si x, y ∈ Div(n), x ∨ y coincide con el m´ınimo com´un m´ultiplo y x ∧ y con el m´aximo com´un divisor. M´as a´un, Div(n) es un ´algebra de Boole si y s´olo si n es libre de cuadrados. 6) Sea X un conjunto munido de un orden total ≤ con primer elemento 0 y ´ultimo elemento 1. Sea J(X) el conjunto determinado por las uniones finitas de intervalos de la forma [a, b) con a ≤ b. Notar que ∅ ∈ J(X) pues [0, 0) = ∅. Entonces J(X) con el orden de la inclusi´on es un ´algebra de Boole en el que ∅ es el primer elemento, [0, 1) es el ´ultimo elemento de J(X) y en el que el supremo y el ´ınfimo coinciden con las operaciones usuales conjuntistas de uni´on e intersecci´on. El ´algebra J(X) se denomina el ´algebra de intervalos del conjunto X. 7) Sea X un espacio topol´ogico, entonces el conjunto C(X) determinado por los subconjuntos de X que son a la vez abiertos y cerrados es un ´algebra de Boole con el orden de la inclusi´on, el conjunto vac´ıo como primer elemento, X como ´ultimo elemento y las operaciones de supremo, ´ınfimo y complemento son la uni´on, intersecci´on y complemento. 8) Sea X un espacio topol´ogico. Un subconjunto abierto U de X se dice regular si U = (U) o , donde para cada subconjunto A de X, A denota la clausura de A y Ao el interior de A. Es decir, U es un abierto regular si coincide con el interior de su clausura. Denotemos con Reg(X) al conjunto formado por los abiertos regulares de X. Entonces Reg(X) con el orden de la inclusi´on es un ´algebra de Boole, con el vac´ıo como primer elemento, X el ´ultimo elemento y las operaciones definidas de la siguiente manera, donde 3 U, V son abiertos regulares: U ∧V = U ∩V, U ∨V = (U ∪ V ) o y ¬U = X\U. Notar que en este ejemplo las operaciones de ´algebra de Boole no coincide con las operaciones habituales conjuntistas. Observaci´on 1 Sea (B, ≤) un ´algebra de Boole. Es f´acil ver que si en B consideramos la relaci´on de orden dual ≥, entonces (B, ≥) vuelve a ser un ´algebra de Boole en el que el primer elemento es el 1, el ´ultimo elemento es el 0, el supremo de (B, ≥) coincide con el ´ınfimo de B y el ´ınfimo de (B, ≥) con el supremo de B. El ´algebra (B, ≥) se denomina ´algebra de Boole dual de B. La siguiente proposici´on muestra algunas propiedades elementales que verifican las ´algebras de Boole en t´erminos de las operaciones. Proposici´on 1 Sea (B, ≤) un ´algebra de Boole. Entonces se verifican las siguientes condiciones: (i) Si x, y ∈ B, entonces x ≤ y si y s´olo si ¬y ≤ ¬x. (ii) Si x, y ∈ B, entonces ¬(x ∨ y) = (¬x ∧ ¬y) y ¬(x ∧ y) = (¬x ∨ ¬y). (iii) Si x ∈ B, entonces ¬¬x = x. (iv) Si x, y ∈ B, entonces x ≤ y si y s´olo si x∧¬y = 0 si y s´olo si ¬x∨y = 1. Definici´on 2 Sea B un ´algebra de Boole, un subconjunto no vac´ıo S de B se dice sub´algebra si verifica las siguientes condiciones: (i) Si x ∈ S, entonces ¬x ∈ S, (ii) Si x, y ∈ S, entonces x ∨ y ∈ S y x ∧ y ∈ S. De la definici´on anterior se deduce inmediatamente que toda sub´algebra S de un ´algebra de Boole B contiene al 0 y al 1, en particular el ´algebra minimal 2 es sub´algebra de toda ´algebra de Boole. En los ejemplos 1, J(X) y C(X) son sub´algebras de P(X), mientras que Reg(X) no es una sub´algebra de P(X). Si B es un ´algebra de Boole y (Si)i∈I es una familia de sub´algebras de B, entonces es inmediato ver que la intersecci´on T i∈I Si es una sub´algebra de B. En particular deducimos de esta propiedad que si X es un subconjunto de B entonces existe la menor sub´algebra hXi de B que contiene a X y se 4 determina como la intersecci´on de todas las sub´algebras de B que contienen a X. Esta intersecci´on est´a bien definida pues B es sub´algebra de B. El ´algebra hXi se define como la sub´algebra generada por X. Las ´algebras de Boole tienen la particularidad que sus operaciones inducen en B dos estructuras algebraicas conocidas: la de anillo y la de espacio vectorial, m´as precisamente tenemos el siguiente resultado. Teorema 1 Sea B un ´algebra de Boole. Entonces B posee una estructura de anillo conmutativo con unidad, en la que la suma de anillos se define como x + y = (x ∧ y) ∨ (y ∧ ¬x), el producto xy coincide con el ´ınfimo, el 0 es el elemento neutro para la suma y el 1 es el elemento neutro para el producto. M´as a´un, B con la suma es un grupo de exponente 2 (esto es x + x = 0 para todo x ∈ B) y en particular resulta que B es un espacio vectorial sobre el cuerpo de dos elementos Z2 = {0, 1}. Observar que como el producto de la estructura de anillo definida en B coincide con el ´ınfimo, entonces se tiene que x 2 = x∧x = x para todo x ∈ B. Un anillo A con unidad que verifica la ley x 2 = x para todo x ∈ A se llama anillo booleano. La raz´on de este t´ermino es que en todo anillo booleano A se puede probar que el producto es conmutativo, y A con la suma es un grupo de exponente 2. M´as a´un, definiendo para todo x, y ∈ A la relaci´on x ≤ y si y s´olo si x = xy, resulta que A es un ´algebra de Boole en el que el ´ınfimo coincide con el producto, el supremo es x ∨ y = x + y + xy, el 0 es el primer elemento y el 1 el ´ultimo elemento. Por lo tanto la clase de las ´algebras de Boole coincide con la clase de los anillos booleanos. Definici´on 3 Sean B, C ´algebras de Boole. Una aplicaci´on h : B → C se dice un homomorfismo si verifica las siguientes condiciones para todo x, y ∈ B : (a) h(x∧y) = h(x)∧h(y),(b) h(x∨y) = h(x)∨h(y) y (c) h(¬x) = ¬h(x). Todo homomorfismo preserva autom´aticamente las constantes 0 y 1; esto es si h : B → C es un homomorfismo entonces h(0) = 0 y h(1) = 1 . Un homomorfismo que sea adem´as inyectivo y suryectivo, se dice un isomorfismo. Dos ´algebras de Boole B, C se dicen isomorfas, y se escribe B ∼= C, si es posible construir un isomorfismo h : B → C entre ellas. Por ejemplo el ´algebra de Boole de los divisores de 30 dada en los ejemplos 1 es isomorfa al ´algebra de Boole del conjunto de partes P(X) de un conjunto X = {a, b, c} 5 con 3 elementos. En efecto si n es un divisor de 30, entonces n se escribe como n = 2α · 3 β · 5 γ , con α, β, γ enteros no negativos. Entonces la aplicaci´on f : Div(30) → P(X) que asigna a cada divisor n de 30 el subconjunto S de X definido como sigue: a ∈ S si y s´olo si α 6= 0, b ∈ S si y s´olo si β 6= 0 y c ∈ S si y s´olo si γ 6= 0, es un isomorfismo de ´algebras de Boole. Sea B un ´algebra de Boole. Una pregunta natural es la siguiente: ¿Es posible encontrar un conjunto X tal que B sea isomorfa al conjunto de partes P(X)?. La respuesta es en general negativa. Sin embargo el resultado es cierto si B es un ´algebra de Boole finita y como veremos, el resultado tambi´en es cierto para una clase particular de ´algebras de Boole que caracteriza justamente a las ´algebras de Boole que son isomorfas al conjunto de partes de alg´un conjunto X. Definici´on 4 Sea B un ´algebra de Boole. Un ´atomo de B es un elemento a de B diferente de 0 y que verifica la siguiente condici´on: si x ∈ B y x ≤ a, entonces x = 0 o x = a. Diremos que B es un ´algebra de Boole at´omica si para todo x ∈ B, x 6= 0 existe un ´atomo a tal que a ≤ x. Si X es un conjunto, entonces los ´atomos del ´algebra de Boole P(X) son exactamente los conjuntos unitarios {x}, con x ∈ X y es inmediato ver que adem´as P(X) es un ´algebra de Boole at´omica. En el extremo opuesto, el ´algebra de intervalos J([0, 1]) del intervalo real [0, 1] no tiene ´atomos. Proposici´on 2 Sea B un ´algebra de Boole y sea a ∈ B. Las siguientes condiciones son equivalentes: (i) a es un ´atomo. (ii) a 6= 0 y para todo x ∈ B, a ≤ x o a ≤ ¬x. (iii) a 6= 0 y para todo x, y ∈ B, a ≤ x ∨ y implica a ≤ x o a ≤ y. Teorema 2 Sea B un ´algebra de Boole finita con m´as de un elemento. Entonces B es un ´algebra de Boole at´omica que es isomorfa al ´algebra de Boole del conjunto de partes P(X), donde X es el conjunto de ´atomos de B. Corolario 1 Toda ´algebra de Boole finita B tiene 2 n elementos, donde n es el n´umero de ´atomos de B. 6 Definici´on 5 Sea B un ´algebra de Boole. Diremos que B es completa si todo subconjunto S de B tiene supremo Es interesante notar que si un ´algebra de Boole B tiene la propiedad que todo subconjunto del ´algebra tiene supremo, entonces todo subconjunto de B tiene ´ınfimo y viceversa. Con lo cual en la definici´on anterior basta pedir la condici´on referida al supremo. Claramente un argumento inductivo muestra que si S es un subconjunto finito de un ´algebra de Boole B entonces siempre existe el supremo. Sin embargo hay ejemplos de ´algebras de Boole en la que pueden haber subconjuntos sin supremo. Un ejemplo de esto es por ejemplo tomar el ´algebra de intervalos del intervalo racional IR = [0, 1] y tomar S el subconjunto de J(IR) determinado por los intervalos de la forma [0, x) con x un n´umero racional cuyo cuadrado sea menor que 2. El conjunto de partes de un conjunto X es siempre un ´algebra de Boole completa. Un ejemplo menos obvio es tomar el ´algebra de Boole Reg(X) de un espacio topol´ogico. El siguiente resultado da una caracterizaci´on de las ´algebras de Boole que son isomorfas al ´algebra de Boole del conjunto de partes de un conjunto.