Álgebra aplicada
El estudio de las estructuras ordenadas es fundamental en álgebra, lógica e informática. En este tema exploraremos los Conjuntos Parcialmente Ordenados (Posets) y su especialización en Retículos (Lattices), que proporcionan el marco formal para el Álgebra de Boole, la lógica proposicional y el Análisis Formal de Conceptos.
George Boole (1815-1864), un matemático autodidacta británico, revolucionó la lógica al demostrar que podía tratarse mediante sistemas algebraicos. Su obra The Laws of Thought (1854) sentó las bases del Álgebra de Boole. Décadas después, Garrett Birkhoff (1911-1996) formalizó la teoría de retículos, demostrando su aplicación en la lógica, la teoría de conjuntos y la física cuántica.
LatticeTheory
En esta práctica utilizamos la librería LatticeTheory de R, alojada en GitHub. Para instalarla:
install.packages("remotes")
remotes::install_github("malaga-fca-group/LatticeTheory")Un poset (partial ordered set) es un par \((X, \le)\) donde \(X\) es un conjunto y \(\le\) es una relación binaria que cumple:
Si además \(\forall x, y \in X\) se cumple \(x \le y\) o \(y \le x\), el orden es total y el poset se denomina cadena.
Una forma computacional de representar un orden parcial es mediante una matriz cuadrada \(A\), donde cada fila y columna corresponde a un elemento de \(X\). El valor \(a_{i,j} = 1\) indica que el elemento \(j\)-ésimo es menor o igual que el \(i\)-ésimo; \(a_{i,j} = 0\) en caso contrario.
Ejemplo 1 Construyamos un poset con 5 elementos \(\{a, b, c, d, e\}\):
A <- matrix(
c(
1, 0, 0, 0, 0,
1, 1, 0, 0, 0,
1, 1, 1, 0, 0,
1, 0, 0, 1, 0,
1, 1, 1, 1, 1
),
nrow = 5, byrow = TRUE,
dimnames = list(c("a", "b", "c", "d", "e"),
c("a", "b", "c", "d", "e"))
)
my_poset <- Poset$new(A)
my_posetPoset with 5 elements.
Elements: a, b, c, d, e.
Strict comparabilities:
a < b, a < c, a < d, a < e
b < c, b < e
c < e
d < eObservamos que, por ejemplo, \(a \le b\), \(b \le c\) y \(c \le e\), pero \(b\) y \(d\) no son comparables.
El diagrama de Hasse es una representación simplificada del poset donde se omiten las relaciones reflexivas y transitivas. Si \(x < y\) y no existe ningún \(z\) con \(x < z < y\), dibujamos a \(y\) por encima de \(x\) y los unimos con una línea.
Ejemplo 2
my_poset$plot()
En el diagrama, los nodos se ordenan de abajo hacia arriba siguiendo el orden del poset.
Sea \((X, \le)\) un poset y \(Y \subseteq X\). Definimos los siguientes conceptos:
Un elemento \(a \in Y\) es maximal si no existe ningún \(b \in Y\), \(b \neq a\), con \(a \le b\). Es decir, no hay ningún elemento por encima en \(Y\). Análogamente se define minimal.
Ejemplo 3
my_poset$maximals("a", "b", "d")[1] "b" "d"my_poset$minimals("b", "c", "d")[1] "b" "d"Los maximales de \(\{a, b, d\}\) son \(b\) y \(d\) (ninguno está por encima del otro). Los minimales de \(\{b, c, d\}\) también son \(b\) y \(d\) (son incomparables).
Un elemento \(y \in Y\) es el máximo si \(x \le y\) para todo \(x \in Y\). Es único si existe. Análogamente se define el mínimo.
Ejemplo 4
my_poset$maximum("a", "b", "c")[1] "c"my_poset$maximum("a", "b", "d")NULLmy_poset$minimum("a", "b", "d")[1] "a"El máximo de \(\{a, b, c\}\) es \(c\). Sin embargo, \(\{a, b, d\}\) no tiene máximo (pues \(b\) y \(d\) son incomparables), aunque sí tiene mínimo: \(a\).
Un elemento \(a \in X\) es cota superior de \(Y\) si \(y \le a\) para todo \(y \in Y\). Es decir, las cotas superiores son elementos de \(X\) (no necesariamente de \(Y\)) que están por encima de todos los de \(Y\). Análogamente se definen las cotas inferiores.
Ejemplo 5
my_poset$upper_bounds("a", "b", "d")[1] "e"my_poset$lower_bounds("b", "c", "d")[1] "a"La única cota superior de \(\{a, b, d\}\) es \(e\) (el único elemento por encima de todos). La única cota inferior de \(\{b, c, d\}\) es \(a\).
El supremo de \(Y\) (denotado \(\sup Y\) o \(\bigvee Y\)) es la menor de las cotas superiores. El ínfimo de \(Y\) (denotado \(\inf Y\) o \(\bigwedge Y\)) es la mayor de las cotas inferiores.
Si el supremo de \(Y\) existe y pertenece a \(Y\), entonces coincide con el máximo de \(Y\). Recíprocamente, si \(Y\) tiene máximo, ese elemento es también supremo de \(Y\). Lo análogo vale para ínfimo y mínimo.
Ejemplo 6
my_poset$supremum("b", "c", "d")[1] "e"my_poset$infimum("b", "c", "d")[1] "a"El supremo de \(\{b, c, d\}\) es \(e\) (la menor cota superior). El ínfimo es \(a\) (la mayor cota inferior).
Una extensión lineal de \((X, \le)\) es una relación de orden total \(\preceq\) sobre \(X\) que preserva el orden: si \(a \le b\) entonces \(a \preceq b\). Puede haber muchas extensiones lineales posibles.
Ejemplo 7
extension <- my_poset$linear_extension()
extensionLattice with 5 elements.
Elements: a, b, c, d, e.
Strict comparabilities:
a < b, a < c, a < d, a < e
b < c, b < d, b < e
c < d, c < e
d < eextension$plot()
La extensión lineal convierte el orden parcial en un orden total compatible.
Un retículo es un poset \((L, \le)\) donde para cada par de elementos \(x, y \in L\) existen su supremo y su ínfimo. Denotamos:
Un retículo es completo si existe el supremo y el ínfimo de cualquier subconjunto de elementos.
Desde un punto de vista algebraico, un retículo también puede definirse como un conjunto \(L\) dotado de dos operaciones \(\vee\) y \(\wedge\) que satisfacen ciertas leyes (conmutatividad, asociatividad, idempotencia y absorción).
Si ya tenemos un objeto Poset y es un retículo, podemos convertirlo con to_lattice(). También existen retículos predefinidos en la librería.
Una cadena es un conjunto dotado de un orden total:
Ejemplo 8
my_chain <- chain(4)
my_chainLattice with 4 elements.
Elements: a, b, c, d.
Strict comparabilities:
a < b, a < c, a < d
b < c, b < d
c < dmy_chain$plot()
Estos dos retículos son fundamentales en la teoría, pues caracterizan la distributividad:
Ejemplo 9
D <- diamond()
D$plot()
P <- pentagon()
P$plot()
El retículo de los divisores de un entero positivo \(n\) se denota \((\mathcal{D}_n, |)\). La relación de orden es la divisibilidad. En este retículo:
Ejemplo 10
div <- divisors_lattice(60)
divLattice with 12 elements.
Elements: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.
Strict comparabilities:
1 < 2, 1 < 3, 1 < 4, 1 < 5, 1 < 6, 1 < 10, 1 < 12, 1 < 15, 1 < 20, 1 < 30, 1 < 60
2 < 4, 2 < 6, 2 < 10, 2 < 12, 2 < 20, 2 < 30, 2 < 60
3 < 6, 3 < 12, 3 < 15, 3 < 30, 3 < 60
4 < 12, 4 < 20, 4 < 60
5 < 10, 5 < 15, 5 < 20, 5 < 30, 5 < 60
6 < 12, 6 < 30, 6 < 60
10 < 20, 10 < 30, 10 < 60
12 < 60
15 < 30, 15 < 60
20 < 60
30 < 60div$plot()
El retículo de partes de un conjunto \(\mathcal{P}(S)\) con la inclusión \(\subseteq\) es el ejemplo más puro de un retículo distributivo y complementado.
Ejemplo 11
B <- boole(3)
B$plot()
Como un retículo es un caso particular de poset, todas las funciones anteriores (maximals, minimals, etc.) siguen siendo válidas. Pero la estructura más rica permite definir nuevos conceptos.
Un retículo acotado tiene un elemento máximo (\(\top\), top) y un mínimo (\(\bot\), bottom). El top es el elemento neutro del operador \(\wedge\) y el bottom lo es del operador \(\vee\).
Todo retículo finito es completo y acotado.
Los métodos correspondientes son top() y bottom().
Un átomo es un vecino superior inmediato de \(\bot\). Un coátomo es un vecino inferior inmediato de \(\top\). Las funciones son atoms() y coatoms().
Ejemplo 12
div <- divisors_lattice(60)
div$atoms()[1] "2" "3" "5"div$coatoms()[1] "12" "20" "30"Los átomos del retículo de divisores de 60 están directamente relacionados con los factores primos de 60.
Un elemento \(x \in L\) es \(\vee\)-irreducible (join-irreducible) si no se puede expresar como supremo de dos elementos distintos a él. Gráficamente, son los que solo tienen un vecino inferior.
Un elemento \(x \in L\) es \(\wedge\)-irreducible (meet-irreducible) si no se puede expresar como ínfimo de dos elementos distintos a él. Gráficamente, tienen un solo vecino superior.
Cualquier elemento de un retículo finito distributivo se puede escribir de forma única (salvo redundancias) como supremo de elementos \(\vee\)-irreducibles.
Ejemplo 13
div$join_irreducibles()[1] "2" "3" "4" "5"div$meet_irreducibles()[1] "12" "15" "20" "30"En un retículo acotado, \(\hat{x}\) es complemento de \(x\) si \(x \vee \hat{x} = \top\) y \(x \wedge \hat{x} = \bot\). El complemento no tiene por qué existir, y de existir, no tiene por qué ser único.
Ejemplo 14
P <- pentagon()
P$complements("d")[1] "b" "c"En el pentágono, el elemento \(d\) tiene dos complementos: \(b\) y \(c\). Esto ocurre porque el pentágono no es distributivo.
Un retículo \((L, \vee, \wedge)\) es distributivo si para todo \(x, y, z \in L\): \[x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z)\] \[x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)\]
Un retículo es distributivo si y solo si no contiene subretículos isomorfos al Diamante (\(M_3\)) ni al Pentágono (\(N_5\)).
Además, en un retículo distributivo, si un elemento tiene complemento, éste es único.
Un Álgebra de Boole es un retículo acotado, distributivo y complementado. Es la estructura algebraica que subyace a la lógica proposicional clásica.
Ejemplo 15
B <- boole(3)
# Los elementos de un álgebra de Boole con 3 átomos
B$atoms()[1] "b" "c" "d"# El complemento de un átomo es único (gracias a la distributividad)
B$complements(B$atoms()[1])[1] "g"En un álgebra de Boole, cada elemento tiene un único complemento.
En este tema nos hemos centrado en operar y razonar sobre retículos y conjuntos parcialmente ordenados. Conceptos como subretículos, isomorfismos de retículos y homomorfismos se tratan en mayor profundidad en el material teórico de clase. Para completar la parte teórica, es imprescindible considerar el material proporcionado en clase y disponible en el campus virtual.