Álgebra de Heyting

Un álgebra de Heyting${\displaystyle H}$es un retículo acotado que tiene todos los objetos exponenciales .

La red${\displaystyle H}$se considera una categoría donde se reúne,${\displaystyle \wedge }$, es el producto . La condición exponencial significa que para cualquier objeto${\displaystyle Y}$y${\displaystyle Z}$en${\displaystyle H}$una exponencial${\displaystyle Z^{Y}}$existe de forma única como objeto en${\displaystyle H}$.

Una implicación de Heyting (a menudo escrita usando${\displaystyle \Rightarrow }$o${\displaystyle \multimap }$para evitar confusiones con el uso de${\displaystyle \to }$para indicar un morfismo ) es simplemente una exponencial:${\displaystyle Y\flecha derecha Z}$es una notación alternativa para${\displaystyle Z^{Y}}$. De la definición de exponenciales tenemos esa implicación (${\displaystyle {\Rightarrow }:H\times H\to H}$) es el adjunto derecho para encontrarse (${\displaystyle \wedge :H\times H\to H}$). Esta adjunción se puede escribir como${\displaystyle (-\wedge Y)\dashv (Y\Rightarrow -)}$o más completamente como: $${\displaystyle (-\wedge Y):H{\stackrel {\longrightarrow }{\underset {\longleftarrow }{\top }}}H:(Y\Rightarrow -)}$$

Se puede dar una definición equivalente de álgebras de Heyting considerando las siguientes aplicaciones:

$${\displaystyle {\begin{cases}f_{a}\colon H\to H\\f_{a}(x)=a\wedge x\end{cases}}}$$

para algún a fijo en H. Un retículo acotado H es un álgebra de Heyting si y solo si cada aplicación f _a es el adjunto inferior de una conexión de Galois monótona . En este caso, el adjunto superior respectivo g _a viene dado por g _a ( x ) = a → x , donde → se define como se indicó anteriormente.

Otra definición más es como un retículo residuado cuya operación monoide es ∧. La unidad monoide debe ser entonces el elemento superior 1. La conmutatividad de este monoide implica que los dos residuos coinciden cuando a → b .

Dado un retículo acotado A con elementos máximo y mínimo 1 y 0, y una operación binaria →, estos forman juntos un álgebra de Heyting si y solo si se cumplen las siguientes condiciones:

1. ${\displaystyle a\to a=1}$
2. ${\displaystyle a\wedge (a\to b)=a\wedge b}$
3. ${\displaystyle b\wedge (a\to b)=b}$
4. ${\displaystyle a\to (b\wedge c)=(a\to b)\wedge (a\to c)}$

donde la ecuación 4 es la ley distributiva para →.

Esta caracterización de las álgebras de Heyting hace inmediata la demostración de los hechos básicos relativos a la relación entre el cálculo proposicional intuicionista y las álgebras de Heyting. (Para estos hechos, véanse las secciones " Identidades demostrables " y " Construcciones universales "). Se debe pensar en el elemento${\displaystyle \top }$como significado, intuitivamente, "demostrablemente verdadero". Compárese con los axiomas de la lógica intuicionista .

Dado un conjunto A con tres operaciones binarias →, ∧ y ∨, y dos elementos distinguidos${\displaystyle \bot }$y${\displaystyle \top }$, entonces A es un álgebra de Heyting para estas operaciones (y la relación ≤ definida por la condición que${\displaystyle a\leq b}$cuando a → b =${\displaystyle \top }$) si y solo si se cumplen las siguientes condiciones para cualesquiera elementos x , y y z de A :

1. ${\displaystyle {\mbox{If }}x\leq y{\mbox{ and }}y\leq x{\mbox{ then }}x=y,}$
2. ${\displaystyle {\mbox{If }}\top \leq y,{\mbox{ then }}y=\top ,}$
3. ${\displaystyle x\leq y\to x,}$
4. ${\displaystyle x\to (y\to z)\leq (x\to y)\to (x\to z),}$
5. ${\displaystyle x\land y\leq x,}$
6. ${\displaystyle x\land y\leq y,}$
7. ${\displaystyle x\leq y\to (x\land y),}$
8. ${\displaystyle x\leq x\lor y,}$
9. ${\displaystyle y\leq x\lor y,}$
10. ${\displaystyle x\to z\leq (y\to z)\to (x\lor y\to z),}$
11. ${\displaystyle \bot \leq x.}$

Finalmente, definimos ¬ x como x →${\displaystyle \bot }$.

La condición 1 establece que deben identificarse fórmulas equivalentes. La condición  2 establece que las fórmulas demostrablemente verdaderas son cerradas bajo el modus ponens . Las condiciones  3 y 4 son condiciones de entonces  . Las condiciones 5, 6 y 7 son condiciones de y . Las condiciones  8, 9 y 10 son condiciones de o . La condición  11 es una condición falsa .

Por supuesto, si se eligiera un conjunto diferente de axiomas para la lógica, podríamos modificar el nuestro en consecuencia.

El pedido${\displaystyle \leq }$en un álgebra de Heyting H se puede recuperar de la operación → de la siguiente manera: para cualesquiera elementos a , b de H ,${\displaystyle a\leq b}$si y solo si a → b = 1.

A diferencia de algunas lógicas multivaluadas , las álgebras de Heyting comparten la siguiente propiedad con las álgebras booleanas: si la negación tiene un punto fijo (es decir, ¬ a = a para algún a ), entonces el álgebra de Heyting es el álgebra de Heyting trivial de un elemento.

Dada una fórmula${\displaystyle F(A_{1},A_{2},\ldots ,A_{n})}$del cálculo proposicional (utilizando, además de las variables, los conectores${\displaystyle \land ,\lor ,\lnot ,\to }$, y las constantes 0 y 1), es un hecho, demostrado desde el principio en cualquier estudio de las álgebras de Heyting, que las dos condiciones siguientes son equivalentes:

1. La fórmula F es demostrablemente verdadera en el cálculo proposicional intuicionista.
2. La identidad${\displaystyle F(a_{1},a_{2},\ldots ,a_{n})=1}$es cierto para cualquier álgebra de Heyting H y cualquier elemento${\displaystyle a_{1},a_{2},\ldots ,a_{n}\in H}$.

La metaimplicación de que la primera implica la segunda, que escribiremos como 1 ⇒ 2 , es sumamente útil y constituye el principal método práctico para demostrar identidades en álgebras de Heyting. En la práctica, se suele utilizar el teorema de deducción en dichas demostraciones.

Dado que para cualesquiera a y b en un álgebra de Heyting H tenemos${\displaystyle a\leq b}$Si y solo si a → b = 1, se deduce de 1 ⇒ 2 que siempre que una fórmula F → G sea demostrablemente verdadera, tenemos${\displaystyle F(a_{1},a_{2},\ldots ,a_{n})\leq G(a_{1},a_{2},\ldots ,a_{n})}$para cualquier álgebra de Heyting H y cualquier elemento${\displaystyle a_{1},a_{2},\ldots ,a_{n}\in H}$(Del teorema de deducción se deduce que F → G es demostrable (incondicionalmente) si y solo si G es demostrable a partir de F , es decir, si G es una consecuencia demostrable de F ). En particular, si F y G son demostrablemente equivalentes, entonces${\displaystyle F(a_{1},a_{2},\ldots ,a_{n})=G(a_{1},a_{2},\ldots ,a_{n})}$, ya que ≤ es una relación de orden.

La inferencia 1 ⇒ 2 se puede demostrar examinando los axiomas lógicos del sistema de prueba y verificando que su valor es 1 en cualquier álgebra de Heyting, y luego verificando que la aplicación de las reglas de inferencia a expresiones con valor 1 en un álgebra de Heyting da como resultado expresiones con valor 1. Por ejemplo, elijamos el sistema de prueba que tiene como única regla de inferencia el modus ponens , y cuyos axiomas son los de estilo Hilbert que se dan en Lógica intuicionista#Axiomatización . Entonces, los hechos que se deben verificar se derivan inmediatamente de la definición de álgebras de Heyting, que se asemeja a un axioma, dada anteriormente.

1 ⇒ 2 también proporciona un método para demostrar que ciertas fórmulas proposicionales, aunque tautologías en la lógica clásica, no pueden demostrarse en la lógica proposicional intuicionista. Para demostrar que alguna fórmula${\displaystyle F(A_{1},A_{2},\ldots ,A_{n})}$no es demostrable, basta con exhibir un álgebra de Heyting H y elementos${\displaystyle a_{1},a_{2},\ldots ,a_{n}\in H}$de tal manera que${\displaystyle F(a_{1},a_{2},\ldots ,a_{n})\neq 1}$.

Si se desea evitar mencionar la lógica, entonces en la práctica se hace necesario demostrar como un lema una versión del teorema de deducción válida para álgebras de Heyting: para cualesquiera elementos a , b y c de un álgebra de Heyting H , tenemos${\displaystyle (a\land b)\to c=a\to (b\to c)}$.

Para más información sobre la metaimplicación 2 ⇒ 1, consulte la sección " Construcciones universales " a continuación.

Las álgebras de Heyting son siempre distributivas . Específicamente, siempre tenemos las identidades

1. ${\displaystyle a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)}$
2. ${\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)}$

La ley distributiva a veces se enuncia como un axioma, pero de hecho se deduce de la existencia de pseudocomplementos relativos. La razón es que, al ser el adjunto inferior de una conexión de Galois ,${\displaystyle \wedge }$preserva todos los supremos existentes . La distributividad a su vez es simplemente la preservación de los supremos binarios por${\displaystyle \wedge }$.

Mediante un argumento similar, la siguiente ley distributiva infinita se cumple en cualquier álgebra de Heyting completa:

$${\displaystyle x\wedge \bigvee Y=\bigvee \{x\wedge y\mid y\in Y\}}$$

para cualquier elemento x en H y cualquier subconjunto Y de H. Recíprocamente, cualquier retículo completo que satisfaga la ley distributiva infinita anterior es un álgebra de Heyting completa, con $${\displaystyle a\to b=\bigvee \{c\mid a\land c\leq b\}}$$ siendo su operación de pseudocomplemento relativo.

Un elemento x de un álgebra de Heyting H se denomina regular si se cumple alguna de las siguientes condiciones equivalentes:

1. x = ¬¬ x .
2. x = ¬ y para algún y en H .

La equivalencia de estas condiciones se puede reformular simplemente como la identidad ¬¬¬ x = ¬ x , válida para todo x en H .

Los elementos x e y de un álgebra de Heyting H se denominan complementos entre sí si x ∧ y = 0 y x ∨ y = 1. Si existe, cualquier y de este tipo es único y debe ser igual a ¬ x . Decimos que un elemento x está complementado si admite un complemento. Es cierto que si x está complementado, también lo está ¬ x , y entonces x y ¬ x son complementos entre sí. Sin embargo, de forma confusa, incluso si x no está complementado, ¬ x puede tener un complemento (distinto de x ). En cualquier álgebra de Heyting, los elementos 0 y 1 son complementos entre sí. Por ejemplo, es posible que ¬ x sea 0 para todo x distinto de 0, y 1 si x = 0, en cuyo caso 0 y 1 son los únicos elementos regulares.

Cualquier elemento complementado de un álgebra de Heyting es regular, aunque lo contrario no es cierto en general. En particular, 0 y 1 son siempre regulares.

Para cualquier álgebra de Heyting H , las siguientes condiciones son equivalentes:

1. H es un álgebra booleana ;
2. cada x en H es regular; ^{[ 11 ]}
3. Cada x en H se complementa. ^{[ 12 ]}

En este caso, el elemento a → b es igual a ¬ a ∨ b .

Los elementos regulares (o complementados) de cualquier álgebra de Heyting H constituyen un álgebra booleana H _reg (o H _comp ), en la que las operaciones ∧, ¬ y →, así como las constantes 0 y 1, coinciden con las de H. En el caso de H _comp , la operación ∨ también es la misma, por lo que H _comp es una subálgebra de H. Sin embargo, en general, H _reg no será una subálgebra de H , porque su operación de unión ∨ _reg puede ser diferente de ∨. Para x , y ∈ H _reg , tenemos x ∨ _reg y = ¬(¬ x ∧ ¬ y ). Véanse a continuación las condiciones necesarias y suficientes para que ∨ _reg coincida con ∨.

Una de las dos leyes de De Morgan se satisface en toda álgebra de Heyting, a saber:

$${\displaystyle \forall x,y\in H:\qquad \lnot (x\vee y)=\lnot x\wedge \lnot y.}$$

Sin embargo, la otra ley de De Morgan no siempre se cumple. En su lugar, tenemos una ley de De Morgan débil:

$${\displaystyle \forall x,y\in H:\qquad \lnot (x\wedge y)=\lnot \lnot (\lnot x\vee \lnot y).}$$

Las siguientes afirmaciones son equivalentes para todas las álgebras de Heyting H :

1. H satisface ambas leyes de De Morgan,
2. ${\displaystyle \lnot (x\wedge y)=\lnot x\vee \lnot y{\mbox{ for all }}x,y\in H,}$
3. ${\displaystyle \lnot (x\wedge y)=\lnot x\vee \lnot y{\mbox{ for all regular }}x,y\in H,}$
4. ${\displaystyle \lnot \lnot (x\vee y)=\lnot \lnot x\vee \lnot \lnot y{\mbox{ for all }}x,y\in H,}$
5. ${\displaystyle \lnot \lnot (x\vee y)=x\vee y{\mbox{ for all regular }}x,y\in H,}$
6. ${\displaystyle \lnot (\lnot x\wedge \lnot y)=x\vee y{\mbox{ for all regular }}x,y\in H,}$
7. ${\displaystyle \lnot x\vee \lnot \lnot x=1{\mbox{ for all }}x\in H.}$

La condición 2 es la otra ley de De Morgan. La condición 6 dice que la operación de unión ∨ _reg en el álgebra booleana H _reg de elementos regulares de H coincide con la operación ∨ de H. La condición 7 establece que todo elemento regular está complementado, es decir, H _reg = H _comp .

Demostramos la equivalencia. Es evidente que las metaimplicaciones 1 ⇒ 2, 2 ⇒ 3 y 4 ⇒ 5 son triviales. Además, 3 ⇔ 4 y 5 ⇔ 6 resultan simplemente de la primera ley de De Morgan y la definición de elementos regulares. Demostramos que 6 ⇒ 7 tomando ¬ x y ¬¬ x en lugar de x e y en 6 y usando la identidad a ∧ ¬ a = 0. Nótese que 2 ⇒ 1 se deduce de la primera ley de De Morgan, y 7 ⇒ 6 resulta del hecho de que la operación de unión ∨ en la subálgebra H _comp es simplemente la restricción de ∨ a H _comp , teniendo en cuenta las caracterizaciones que hemos dado de las condiciones 6 y 7. La metaimplicación 5 ⇒ 2 es una consecuencia trivial de la ley débil de De Morgan, tomando ¬ x y ¬ y en lugar de x e y en 5.

Las álgebras de Heyting que satisfacen las propiedades anteriores están relacionadas con la lógica de De Morgan del mismo modo que las álgebras de Heyting en general están relacionadas con la lógica intuicionista.

Dadas dos álgebras de Heyting H ₁ y H ₂ y una aplicación f  : H ₁ → H ₂ , decimos que ƒ es un morfismo de álgebras de Heyting si, para cualesquiera elementos x e y en H 1 _, se cumple:

1. ${\displaystyle f(0)=0,}$
2. ${\displaystyle f(x\land y)=f(x)\land f(y),}$
3. ${\displaystyle f(x\lor y)=f(x)\lor f(y),}$
4. ${\displaystyle f(x\to y)=f(x)\to f(y),}$

De cualquiera de las últimas tres condiciones (2, 3 o 4) se deduce que f es una función creciente, es decir, que f ( x ) ≤ f ( y ) siempre que x ≤ y .

Supongamos que H ₁ y H ₂ son estructuras con operaciones →, ∧, ∨ (y posiblemente ¬) y constantes 0 y 1, y que f es una aplicación sobreyectiva de H ₁ a H ₂ con las propiedades 1 a 4 mencionadas anteriormente. Entonces, si H ₁ es un álgebra de Heyting, también lo es H _2. Esto se deduce de la caracterización de las álgebras de Heyting como retículos acotados (considerados como estructuras algebraicas en lugar de conjuntos parcialmente ordenados) con una operación → que satisface ciertas identidades.

La aplicación identidad f ( x ) = x de cualquier álgebra de Heyting en sí misma es un morfismo, y la composición g ∘ f de cualesquiera dos morfismos f y g es un morfismo. Por lo tanto, las álgebras de Heyting forman una categoría .

Dada una álgebra de Heyting H y cualquier subálgebra H ₁ , la aplicación de inclusión i  : H ₁ → H es un morfismo.

Para cualquier álgebra de Heyting H , el mapa x ↦ ¬¬ x define un morfismo de H sobre el álgebra booleana de sus elementos regulares H _reg . En general , este no es un morfismo de H sobre sí mismo, ya que la operación de unión de H _reg puede ser diferente de la de H.

La metaimplicación 2 ⇒ 1 en la sección " Identidades demostrables " se demuestra mostrando que el resultado de la siguiente construcción es en sí mismo un álgebra de Heyting:

1. Consideremos el conjunto L de fórmulas proposicionales en las variables A ₁ , A ₂ ,..., A _n .
2. Dotamos a L de un preorden ≼ definiendo F ≼ G si G es una consecuencia lógica (intuicionista) de F , es decir, si G es demostrable a partir de F. Es inmediato que ≼ es un preorden.
3. Consideremos la relación de equivalencia F ~ G inducida por el preorden F≼G. (Se define como F ~ G si y solo si F ≼ G y G ≼ F. De hecho, ~ es la relación de equivalencia lógica (intuicionista)).
4. Sea H ₀ el conjunto cociente L /~. Esta será la álgebra de Heyting deseada.
5. Escribimos [ F ] para la clase de equivalencia de una fórmula F . Las operaciones →, ∧, ∨ y ¬ se definen de manera obvia en L . Verificamos que dadas las fórmulas F y G , las clases de equivalencia [ F → G ], [ F ∧ G ], [ F ∨ G ] y [¬ F ] dependen solo de [ F ] y [ G ]. Esto define las operaciones →, ∧, ∨ y ¬ en el conjunto cociente H ₀ = L /~. Además, definimos 1 como la clase de enunciados demostrablemente verdaderos, y establecemos 0=[⊥].
6. Verificamos que H ₀ , junto con estas operaciones, es un álgebra de Heyting. Hacemos esto usando la definición tipo axioma de las álgebras de Heyting. H ₀ satisface las condiciones THEN-1 a FALSE porque todas las fórmulas de las formas dadas son axiomas de la lógica intuicionista. MODUS-PONENS se deduce del hecho de que si una fórmula ⊤→ F es demostrablemente verdadera, donde ⊤ es demostrablemente verdadera, entonces F es demostrablemente verdadera (por aplicación de la regla de inferencia modus ponens). Finalmente, EQUIV resulta del hecho de que si F → G y G → F son ambas demostrablemente verdaderas, entonces F y G son demostrables entre sí (por aplicación de la regla de inferencia modus ponens), por lo tanto [ F ]=[ G ].

Como siempre bajo la definición tipo axioma de las álgebras de Heyting, definimos ≤ en H ₀ por la condición de que x ≤ y si y solo si x → y =1. Dado que, por el teorema de deducción , una fórmula F → G es demostrablemente verdadera si y solo si G es demostrable a partir de F , se sigue que [ F ]≤[ G ] si y solo si F≼G. En otras palabras, ≤ es la relación de orden en L /~ inducida por el preorden ≼ en L .

De hecho, la construcción anterior puede llevarse a cabo para cualquier conjunto de variables { A _i  : i ∈ I } (posiblemente infinito). De esta manera se obtiene el álgebra de Heyting libre sobre las variables { A _i }, que denotaremos nuevamente por H ₀ . Es libre en el sentido de que, dada cualquier álgebra de Heyting H dada junto con una familia de sus elementos ⟨ a _i : i ∈ I ⟩ , existe un único morfismo f : H ₀ → H que satisface f ([ A _i ])= a _i . La unicidad de f no es difícil de ver, y su existencia resulta esencialmente de la metaimplicación 1 ⇒ 2 de la sección " Identidades demostrables " anterior, en la forma de su corolario de que siempre que F y G sean fórmulas demostrablemente equivalentes, F (⟨ a _i ⟩)= G (⟨ a _i ⟩) para cualquier familia de elementos ⟨ a _i ⟩ en H .

Dado un conjunto de fórmulas T en las variables { A _i }, vistas como axiomas, la misma construcción podría haberse llevado a cabo con respecto a una relación F ≼ G definida en L para significar que G es una consecuencia demostrable de F y el conjunto de axiomas T . Denotemos por H _T el álgebra de Heyting así obtenida. Entonces H _T satisface la misma propiedad universal que H ₀ anterior, pero con respecto a álgebras de Heyting H y familias de elementos ⟨ a _i ⟩ que satisfacen la propiedad de que J (⟨ a _i ⟩)=1 para cualquier axioma J (⟨ A _i ⟩) en T . (Observemos que H _T , junto con la familia de sus elementos ⟨[ A _i ⟩, satisface esta propiedad.) La existencia y unicidad del morfismo se prueba de la misma manera que para H ₀ , excepto que hay que modificar la metaimplicación 1 ⇒ 2 en " Identidades demostrables " de modo que 1 se lea "demostrablemente verdadero de T " y 2 se lea "cualesquiera elementos a ₁ , a ₂ ,..., a _n en H que satisfagan las fórmulas de T ".

El álgebra de Heyting H _T que acabamos de definir puede verse como un cociente del álgebra de Heyting libre H ₀ en el mismo conjunto de variables, aplicando la propiedad universal de H ₀ con respecto a H _T , y la familia de sus elementos ⟨[ A _i ]⟩.

Toda álgebra de Heyting es isomorfa a una de la forma H _T . Para ver esto, sea H un álgebra de Heyting cualquiera, y sea ⟨ a _i : i ∈ I ⟩ una familia de elementos que generan H (por ejemplo, cualquier familia sobreyectiva). Ahora consideremos el conjunto T de fórmulas J (⟨ A _i ⟩) en las variables ⟨ A _i : i ∈ I ⟩ tales que J (⟨ a _i ⟩)=1. Entonces obtenemos un morfismo f : H _T → H por la propiedad universal de H _T , que es claramente sobreyectivo. No es difícil demostrar que f es inyectivo.

Las construcciones que acabamos de presentar desempeñan un papel completamente análogo con respecto a las álgebras de Heyting al de las álgebras de Lindenbaum con respecto a las álgebras booleanas . De hecho, el álgebra de Lindenbaum B _T en las variables { A _i } con respecto a los axiomas T es simplemente nuestro H _{T ∪ T 1} , donde T ₁ es el conjunto de todas las fórmulas de la forma ¬¬ F → F , ya que los axiomas adicionales de T ₁ son los únicos que se necesitan agregar para que todas las tautologías clásicas sean demostrables.