En matemáticas , un álgebra booleana libre es un álgebra booleana con un conjunto distinguido de elementos, llamados generadores , tales que:
- Cada elemento del álgebra booleana se puede expresar como una combinación finita de generadores, utilizando las operaciones booleanas, y
- Los generadores son tan independientes como sea posible, en el sentido de que no hay relaciones entre ellos (nuevamente en términos de expresiones finitas usando las operaciones booleanas) que no se cumplen en cada álgebra booleana sin importar qué elementos se elijan.
Un simple ejemplo
Los generadores de un álgebra booleana libre pueden representar proposiciones independientes . Considere, por ejemplo, las proposiciones "Juan es alto" y "María es rica". Estos generan un álgebra booleana con cuatro átomos , a saber:
- Juan es alto y María es rica;
- Juan es alto y María no es rica;
- Juan no es alto y María es rica;
- John no es alto y Mary no es rica.
Otros elementos del álgebra de Boole son las disyunciones lógicas de los átomos, como "Juan es alto y María no es rica, o Juan no es alto y María es rica". Además, hay un elemento más, FALSO, que se puede considerar como la disyunción vacía; es decir, la disyunción de ningún átomo.
Este ejemplo produce un álgebra booleana con 16 elementos; en general, para n finito , el álgebra booleana libre con n generadores tiene 2 n átomos , y por lo tanto elementos.
Si hay infinitamente muchos generadores , una situación similar se presenta sólo que ahora no hay átomos . Cada elemento del álgebra de Boole es una combinación de un número finito de las proposiciones generadoras, y dos de esos elementos se consideran idénticos si son lógicamente equivalentes .
Otra forma de ver por qué el álgebra booleana libre en un conjunto de n elementos tiene elementos es tener en cuenta que cada elemento es una función de n bits a uno. Existen posibles entradas a dicha función y la función elegirá 0 o 1 para la salida de cada entrada, por lo que hay posibles funciones.
Definición teórica de categorías
En el lenguaje de la teoría de categorías , las álgebras booleanas libres se pueden definir simplemente en términos de una adjunción entre la categoría de conjuntos y funciones, Set , y la categoría de álgebras booleanas y homomorfismos de álgebra booleana, BA . De hecho, este enfoque se generaliza a cualquier estructura algebraica definible en el marco del álgebra universal .
Arriba, dijimos que un álgebra booleana libre es un álgebra booleana con un conjunto de generadores que se comportan de cierta manera; alternativamente, uno podría comenzar con un conjunto y preguntar qué álgebra genera. Cada conjunto X genera un álgebra de Boole libre FX definida como el álgebra tal que para cada álgebra B y función f : X → B , existe un homomorfismo de álgebra booleana único f ′: FX → B que extiende f . Diagramáticamente ,
donde i X es la inclusión y la flecha punteada denota unicidad. La idea es que una vez que uno elige dónde enviar los elementos de X , las leyes de los homomorfismos del álgebra booleana determinan dónde enviar todo lo demás en el álgebra libre FX . Si FX contuviera elementos inexpresables como combinaciones de elementos de X , entonces f ′ no sería único, y si los elementos de X no fueran lo suficientemente independientes, ¡entonces f ′ no estaría bien definido! Se muestra fácilmente que FX es único (hasta isomorfismo), por lo que esta definición tiene sentido. También se muestra fácilmente que un álgebra booleana libre con el grupo generador X, como se definió originalmente, es isomorfa a FX , por lo que las dos definiciones concuerdan.
Un defecto de la definición anterior es que el diagrama no captura que f ′ es un homomorfismo; dado que es un diagrama en Set, cada flecha denota una mera función. Podemos arreglar esto separándolo en dos diagramas, uno en BA y otro en Set . Para relacionar los dos, introducimos un functor U : BA → Conjunto que " olvida " la estructura algebraica, mapeando álgebras y homomorfismos a sus conjuntos y funciones subyacentes.
Si interpretamos la flecha superior como un diagrama en el BA y el triángulo inferior, como un diagrama en conjunto , entonces este diagrama expresa adecuadamente que cada función f : X → UB se extiende a una única álgebra de Boole homomorfismo f ': FX → B . Se puede pensar en el funtor U como un dispositivo para llevar el homomorfismo f ′ de regreso al conjunto para que pueda relacionarse con f .
El aspecto notable de esto es que el último diagrama es una de las varias definiciones (equivalentes) de cuando dos functores son adjuntos . Nuestra F se extiende fácilmente a un functor Set → BA , y nuestra definición de X que genera un álgebra de Boole libre FX es precisamente que U tiene una F adjunta izquierda .
Realización topológica
El álgebra de Boole libre con kappa generadores , donde κ es un finito o infinito número cardinal , puede realizarse como la colección de todos abiertos y cerrados subconjuntos de {0,1} κ , dada la topología del producto asumiendo que {0,1} tiene el discreto topología . Para cada α <κ, el α- ésimo generador es el conjunto de todos los elementos de {0,1} κ cuya α- ésima coordenada es 1. En particular, el álgebra booleana libre congenerators es la colección de todos los subconjuntos abiertos de un espacio de Cantor , a veces llamado álgebra de Cantor . Sorprendentemente, esta colección es contable . De hecho, mientras que el álgebra booleana libre con n generadores, n finito, tiene cardinalidad , el álgebra booleana libre con generadores, como para cualquier álgebra libre con generadores y contablemente muchas operaciones finitarias, tiene cardinalidad .
Para obtener más información sobre este enfoque topológico del álgebra booleana libre, consulte el teorema de representación de Stone para álgebras booleanas .
Ver también
Referencias
- Steve Awodey (2006) Teoría de categorías (Guías lógicas de Oxford 49). Prensa de la Universidad de Oxford.
- Paul Halmos y Steven Givant (1998) La lógica como álgebra . Asociación Matemática de América .
- Saunders Mac Lane (1998) Categorías para el matemático que trabaja . 2ª ed. (Textos de Posgrado en Matemáticas 5). Springer-Verlag.
- Saunders Mac Lane (1999) Álgebra , 3d. ed. Sociedad Matemática Estadounidense . ISBN 0-8218-1646-2 .
- Robert R. Stoll, 1963. Teoría y lógica de conjuntos , cap. 6.7. Reimpresión de Dover 1979.