Álgebra de Lindenbaum

El álgebra de Lindenbaum de una teoría matemática es el conjunto de enunciados del lenguaje de ésta módulo la siguiente relación de equivalencia : dos enunciados A y B están en la misma clase de equivalencia si es posible probar en la teoría que a resulta en B y B tiene la consecuencia a . La relación de consecuencia lógica sobre los enunciados, que es compatible con la relación de equivalencia, induce por cociente una relación de orden en el álgebra de Lindenbaum.

Cuando la teoría es la del cálculo proposicional en lógica clásica , el álgebra de Lindenbaum, provisto de conjunción , disyunción y negación (que son compatibles con la equivalencia) forma un álgebra booleana . Esta álgebra, a veces también llamada álgebra de Lindenbaum-Tarski , fue introducida por Adolf Lindenbaum y Alfred Tarski en 1935.

Dos formas de ver las álgebras de Boole

Hay dos formas de definir un álgebra booleana , la definición algebraica (como un anillo unitario donde cada elemento es idempotente ) que es más bien semántica en el sentido de que enfatiza operaciones como la conjunción y su efecto sobre ellos. Valores de verdad, y la definición topológica (como un retículo distributivo (conjunto ordenado) acotado complementado) que es más sintáctico en el sentido de que enfatiza la noción de deducción . La construcción del álgebra de Lindenbaum puede verse como un intento de reconciliar estos dos aspectos.

Como un anillo unitario

En su trabajo fundacional, George Boole realiza cálculos algebraicos reales sobre proposiciones, notando aditivamente la disyunción lógica y multiplicativamente la conjunción lógica . Además, señala la negación como lo contrario: para él, el álgebra de proposiciones es esencialmente un anillo dotado de propiedades particulares (como la distributividad de la suma con respecto a la multiplicación).

Esta forma de ver las álgebras de Boole es fundamental en la teoría de conjuntos, y en particular en la teoría de la probabilidad, tal como la axiomatizó Kolmogorov , la intersección de eventos correspondiente a la conjunción de las proposiciones que representan (ver más abajo). También es significativo que

  1. cuando dos eventos son incompatibles, la probabilidad de que se encuentren es la suma de sus probabilidades;
  2. cuando dos eventos son independientes, la probabilidad de su intersección es el producto de sus probabilidades.

En lógica difusa, de hecho, la probabilidad es una forma entre otras de calcular valores de verdad. Esta interpretación booleana de probabilidades ya está presente en Boole con una traducción del tercero excluida por el hecho de que la suma de las probabilidades de dos eventos contrarios es igual a 1.

Como una celosía (conjunto ordenado)

En la lógica proposicional moderna, la notación "∧" para la conjunción es la misma que se usa en aritmética para denotar la MCD . En ambos casos, se trata de un límite inferior para una relación de orden parcial (de la misma manera, la notación "∨" es común a la disyunción y al PPCM ). En aritmética, la relación de orden parcial es divisibilidad . En la lógica de proposiciones, la relación de orden parcial entre dos proposiciones p y q es la relación de la deducción , denotada por p ⊢ q lo que equivale a afirmar que la implicación entre estas dos proposiciones es verdadera, es decir ⊢ p ⇒ q .

Esta es una relación de preorden . En efecto :

  1. p ⊢ p (reflexividad)
  2. Si p ⊢ q y q ⊢ r entonces p ⊢ r (transitividad)
  3. Pero si p ⊢ q y q ⊢ p , no necesariamente tenemos p = q (antisimetría), solo p ≡ q (es decir ⊢ p ⇔ q ).

La idea del álgebra de Lindenbaum equivale a considerar como iguales dos proposiciones lógicamente equivalentes, lo que significa que la relación de deducción se convierte en una relación real de orden, no entre proposiciones, sino entre clases de equivalencias: el álgebra de Lindenbaum es el cociente conjunto del conjunto de proposiciones por la relación de equivalencia.

Implicación y relación de orden

El modus ponens puede interpretarse entonces como una prohibición de ir aguas arriba: siguiendo las flechas de las implicaciones, nos dirigimos hacia proposiciones que son al menos tan verdaderas como aquellas de las que partimos. Si admitimos que los axiomas son verdaderos, entonces lo que deducimos solo puede serlo también.

Relación de orden, relación de deducción e implicación

En un álgebra de Boole (el álgebra de Lindenbaum es uno), la definición de la relación de orden desde el límite inferior es a ≤ b si y solo si a × b = a . Esto equivale a decir que p ⇒ q es verdadero si y solo si p ∧ q ⇔ p es, o nuevamente p ⊢ q si y solo si p ∧ q ≡ p . Esta es una relación entre proposiciones, por lo tanto, un objeto de naturaleza diferente de las proposiciones mismas. Por ejemplo, en el álgebra booleana de partes de un conjunto, la relación de orden es la inclusión (ver más abajo), una relación entre dos conjuntos (y no un conjunto).

La participación como propuesta

En cálculo proposicional, la proposición p ⇒ q se define como la proposición ¬p ∨ q  : por lo tanto, ¡es una proposición, y no una relación! Pero si establecemos la tabla de verdad de p ⇒ q , encontramos la función indicadora de la gráfica dirigida de la relación de orden anterior.

Las paradojas de la participación formal

Cuando CI Lewis inventó la lógica modal , fue en un intento de escapar de lo que llamó las paradojas de la implicación formal  :

  1. 2 + 2 = 5 implica 2 + 2 = 3 (falso conduce a falso)
  2. 2 + 2 = 5 implica 2 + 2 = 4 (falso conduce a verdadero)
  3. 2 + 2 = 4 implica por dos puntos distintos que pasa una línea recta (lo verdadero implica lo verdadero, incluso cuando no hay relación entre las dos proposiciones)

La interpretación de la implicación como una relación de orden permitida por el álgebra de Lindenbaum elimina la aparente "paradoja", dando un significado algebraico a la implicación. En particular, podemos distinguir:

  1. La clase de antilogías , que es más pequeña que todos los elementos del álgebra de Lindenbaum, y en particular más pequeña que ella misma;
  2. La clase de tautologías , que es mayor que todos los elementos del álgebra de Lindenbaum, y en particular mayor que ella misma.

Propiedades del álgebra de Lindenbaum

Llamamos átomo de un álgebra de Boole, cualquier elemento de él tal que solo cero sea más pequeño que él. En el caso del álgebra de Boole de las partes de un conjunto, los átomos son los singleton.

Caso terminado

Dados de 4 caras 250.jpg

En un experimento probabilístico en un universo finito, el número de variables proposicionales es finito y corresponde a los átomos. Por ejemplo, si lanzamos un dado de cuatro lados , los átomos son 4 en número:

  1. el dado cae en 1; Denotaremos esta proposición 1 ;
  2. el dado cae en 2; Denotaremos esta proposición 2 ;
  3. el dado cae en 3; Denotaremos esta proposición 3 ;
  4. el dado cae en 4; tomaremos nota de esta proposición 4 .

La primera de estas proposiciones está representada en la teoría de la probabilidad por el conjunto {1} . Y el evento {2,4} correspondiente a un resultado par está escrito por la proposición no atómica 2∨4 . Asimismo, el evento imposible {} (o ∅) corresponde a una antilogía y el evento cierto {1,2,3,4} corresponde a una tautología.

Parte de la gráfica del álgebra de Boole correspondiente se representa en el diagrama de Hasse de la figura 1.

El álgebra de Boole no se representa en su totalidad porque, por ejemplo, 4⇒2∨3∨4 (si los dados cayeron en 4, entonces cayeron en más de 1) aunque ninguna flecha va de {4} a {2,3,4} . Sin embargo, hay una flecha que va de {4} a {2.4} y otra que va de {2.4} a {2,3,4} . Podemos considerar estas dos flechas como una demostración de la proposición "si el dado cayó en 4, entonces cayó en más de 1", que en francés se puede escribir de la siguiente manera:

  1. Si los dados caen en 4, entonces caen en un número par;
  2. Sin embargo, los números pares de este dado son mayores que 1;
  3. Entonces, si el dado cayó en 4, entonces cayó en más de 1.

Observamos (figura 2) que hay otras trayectorias de flechas que van de {4} a {2,3,4} , por ejemplo, la del extremo derecho, que se reduce a "si el dado cayó en 4, cayó en más de 2, por lo que a fortiori más de 1 ”. El hecho de que lo falso implica lo verdadero se visualiza por la posición del conjunto vacío en la parte inferior del diagrama (pero también por la posición del universo en la parte superior). En la figura 2, hemos coloreado en verde todos los teoremas que se pueden deducir de "el dado ha caído en 1".

El hecho de que la relación de orden no sea total impide reducir este diagrama a puntos alineados, pero en la figura 3 donde los conjuntos están representados por su función indicadora, reconocemos un tesseract . De manera más general, un álgebra booleana finita siempre tiene un número de elementos que es una potencia de 2 (aquí, 16), y el diagrama de Hasse es un hipercubo de dimensión finita. Para el cálculo proposicional clásico con una infinidad de variables proposicionales, podemos imaginar el álgebra de Lindenbaum como un hipercubo de dimensión infinita.

Caso infinito

En este caso, el álgebra de Lindenbaum no tiene átomos, y topológicamente es un espacio de Cantor . Ahora bien, este tipo de espacios son todos homeomórficos entre sí, y un álgebra de Lindenbaum es, topológicamente, idéntico al conjunto de Cantor .

El álgebra de Lindenbaum de una teoría del cálculo de predicados también es un espacio de Cantor. En este caso, el límite inferior de la familia generado por un predicado que tiene una variable libre se obtiene precediéndolo con un cuantificador universal y su límite superior, precediéndolo con un cuantificador existencial  :

[∀x, P (x)] ⇒ P (x) ⇒ [∃ x, P (x)]

El ultrafiltro que se muestra en verde arriba (generado por un átomo) admite una generalización en el álgebra de Lindenbaum del cálculo de predicados. Esta noción de ultrafiltros permite definir una topología en el álgebra de Lindenbaum, en la que todo lo abierto es cerrado y viceversa.

Teoremas

Teorema de piedra

Más precisamente, el espacio de Stone de un álgebra booleana es el conjunto de sus ultrafiltros, y es sobre este espacio que Marshall Stone definió su topología admitiendo como base de abiertos (que también son cerrados) los conjuntos ultrafiltros que contienen un elemento del álgebra booleana . El conjunto de espacios abiertos-cerrados de Stone, provisto de la intersección y la unión, es un álgebra de Boole.

Teorema  : el  álgebra de Lindenbaum es isomórfica, como álgebra booleana (y como cualquier álgebra booleana), al álgebra booleana abierta-cerrada de su espacio de piedra.

Como resultado, el álgebra de Lindenbaum es un espacio compacto (como se ve en las figuras de arriba).

Teorema de la compacidad

Entonces de cualquier recubrimiento del álgebra de Lindenbaum por cerrado (es decir, por aberturas) podemos extraer un recubrimiento finito: este es el teorema de compacidad de la lógica de predicados.

Teorema de completitud

Y dado que el álgebra de Lindenbaum es un espacio compacto , se deduce que es un espacio de Baire . Helena Rasiowa y Roman Sikorski  (en) dedujeron una prueba topológica del teorema de completitud .

Modelos no estándar

Las construcciones de ultraproductos en álgebras de aritmética y análisis de Lindenbaum, respectivamente, llevaron al descubrimiento

  1. de la aritmética no estándar ( Thoralf Skolem , 1922)
  2. de análisis no estándar ( Abraham Robinson , 1961)

Notas y referencias

  1. (en) George Boole , Una investigación de las leyes del pensamiento ,1854( leer en línea )
  2. Boole 1854 , cap. 18
  3. (en) GE Hughes  (en) y MJ Creswell  (de) , Introducción a la lógica modal , Londres, Methuen,1968( ISBN  978-0-416-29460-6 ) , cap.  17
  4. Hughes y Creswell 1968 , Apéndice 2
  5. (en) John L. Bell y Alan B. Slomson , Modelos y Ultraproductos, una introducción , Mineola, Dover ,2006, 322  p. , bolsillo ( ISBN  978-0-486-44979-1 )

Ver también

Artículo relacionado

Tipo (teoría del modelo)

Bibliografía

(en) Peter Johnstone  (de) , Stone Spaces , CUP ,mil novecientos ochenta y dos, 370  p. ( ISBN  978-0-521-23893-9 )