Álgebra de Heyting

Concepto matemático

En matemáticas , un álgebra de Heyting (también conocida como álgebra pseudobooleana ^[1] ) es una red acotada (con operaciones de unión y encuentro escritas ∨ y ∧ y con el menor elemento 0 y el mayor elemento 1) equipada con una operación binaria a → b de implicación tal que ( c ∧ a ) ≤ b es equivalente a c ≤ ( a → b ). Desde un punto de vista lógico, A → B es por esta definición la proposición más débil para la cual el modus ponens , la regla de inferencia A → B , A ⊢ B , es válida. Al igual que las álgebras de Boole , las álgebras de Heyting forman una variedad axiomatizable con un número finito de ecuaciones. Las álgebras de Heyting fueron introducidas por Arend Heyting  (1930) para formalizar la lógica intuicionista .

Las álgebras de Heyting son redes distributivas . Toda álgebra de Boole es un álgebra de Heyting cuando a → b se define como ¬ a ∨ b , al igual que toda red distributiva completa que satisface una ley distributiva infinita unilateral cuando a → b se toma como el supremo del conjunto de todos los c para los que c ∧ a ≤ b . En el caso finito, toda red distributiva no vacía, en particular toda cadena finita no vacía , es automáticamente completa y completamente distributiva y, por lo tanto, un álgebra de Heyting.

De la definición se sigue que 1 ≤ 0 → a , lo que corresponde a la intuición de que cualquier proposición a está implícita en una contradicción 0. Aunque la operación de negación ¬ a no forma parte de la definición, es definible como a → 0. El contenido intuitivo de ¬ a es la proposición de que suponer a conduciría a una contradicción. La definición implica que a ∧ ¬ a = 0. Se puede demostrar además que a ≤ ¬¬ a , aunque el recíproco, ¬¬ a ≤ a , no es cierto en general, es decir, la eliminación de la doble negación no se cumple en general en un álgebra de Heyting.

Las álgebras de Heyting generalizan las álgebras de Boole en el sentido de que las álgebras de Boole son precisamente las álgebras de Heyting que satisfacen a ∨ ¬ a = 1 ( medio excluido ), equivalentemente ¬¬ a = a . Aquellos elementos de un álgebra de Heyting H de la forma ¬ a comprenden una red booleana, pero en general esta no es una subálgebra de H (ver más abajo).

Las álgebras de Heyting sirven como modelos algebraicos de la lógica intuicionista proposicional de la misma manera que las álgebras de Boole modelan la lógica clásica proposicional ^{[ cita requerida ]} . La lógica interna de un topos elemental se basa en el álgebra de Heyting de subobjetos del objeto terminal 1 ordenados por inclusión, equivalentemente los morfismos desde 1 hasta el clasificador de subobjetos Ω.

Los conjuntos abiertos de cualquier espacio topológico forman un álgebra de Heyting completa . Por lo tanto, las álgebras de Heyting completas se convierten en un objeto central de estudio en la topología sin sentido .

Toda álgebra de Heyting cuyo conjunto de elementos no mayores tiene un elemento mayor (y forma otra álgebra de Heyting) es subdirectamente irreducible , por lo que toda álgebra de Heyting puede hacerse subdirectamente irreducible añadiéndole un nuevo elemento mayor. De ello se deduce que incluso entre las álgebras de Heyting finitas existen infinitas que son subdirectamente irreducibles, y ninguna de ellas tiene dos que tengan la misma teoría de ecuaciones . Por tanto, ningún conjunto finito de álgebras de Heyting finitas puede proporcionar todos los contraejemplos de las no leyes del álgebra de Heyting. Esto contrasta marcadamente con las álgebras de Boole, cuya única irreducible subdirectamente es la de dos elementos, que por sí sola basta para todos los contraejemplos de las no leyes del álgebra de Boole, la base del método de decisión de la tabla de verdad simple . Sin embargo, es decidible si una ecuación se cumple para todas las álgebras de Heyting. ^[2]

Las álgebras de Heyting se denominan con menos frecuencia álgebras pseudobooleanas , ^[3] o incluso redes de Brouwer , ^[4] aunque el último término puede denotar la definición dual, ^[5] o tener un significado ligeramente más general. ^[6]

Definición formal

Un álgebra de Heyting H es una red acotada tal que para todos a y b en H hay un elemento máximo x de H tal que

${\displaystyle a\wedge x\leq b.}$

Este elemento es el pseudocomplemento relativo de a con respecto a b y se denota a → b . Escribimos 1 y 0 para el elemento más grande y el más pequeño de H , respectivamente.

En cualquier álgebra de Heyting, se define el pseudocomplemento ¬ a de cualquier elemento a haciendo ¬ a = ( a →0). Por definición, , y ¬ a es el elemento más grande que tiene esta propiedad. Sin embargo, en general no es cierto que , por lo tanto ¬ es solo un pseudocomplemento, no un verdadero complemento , como sería el caso en un álgebra de Boole. ${\displaystyle a\wedge \lnot a=0}$ ${\displaystyle a\vee \lnot a=1}$

Un álgebra de Heyting completa es un álgebra de Heyting que es una red completa .

Una subálgebra de un álgebra de Heyting H es un subconjunto H ₁ de H que contiene 0 y 1 y está cerrado bajo las operaciones ∧, ∨ y →. De ello se deduce que también está cerrado bajo ¬. Una subálgebra se convierte en un álgebra de Heyting mediante las operaciones inducidas.

Definiciones alternativas

Definición de teoría de categorías

Un álgebra de Heyting es una red acotada que tiene todos los objetos exponenciales . ${\displaystyle H}$

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

Una implicación de Heyting (que se suele escribir con o para evitar confusiones como el uso de para indicar un funtor ) es simplemente una exponencial: es una notación alternativa para . De la definición de exponenciales tenemos que la implicación ( ) es un adjunto derecho de ( ). Este adjunto se puede escribir como o de forma más completa como: ${\displaystyle \Rightarrow }$ ${\displaystyle \multimap }$ ${\displaystyle \to }$ ${\displaystyle Y\Rightarrow Z}$ ${\displaystyle Z^{Y}}$ ${\displaystyle \Rightarrow :H\times H\to H}$ ${\displaystyle \wedge :H\times H\to H}$ ${\displaystyle (-\wedge Y)\dashv (Y\Rightarrow -)}$ $${\displaystyle (-\wedge Y):H{\stackrel {\longrightarrow }{\underset {\longleftarrow }{\top }}}H:(Y\Rightarrow -)}$$

Definiciones de teoría reticular

Se puede dar una definición equivalente de las álgebras de Heyting considerando las 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 . Una red acotada 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 es la de una red residual 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 .

Red acotada con una operación de implicación

Dada una red acotada A con elementos más grandes y más pequeños 1 y 0, y una operación binaria →, estos juntos forman un álgebra de Heyting si y solo si se cumple lo siguiente:

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 →.

Caracterización utilizando los axiomas de la lógica intuicionista

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

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

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 dice que se deben identificar fórmulas equivalentes. La condición 2 dice que las fórmulas demostrablemente verdaderas están cerradas bajo modus ponens . Las condiciones 3 y 4 son entonces condiciones. Las condiciones 5, 6 y 7 son condiciones y . Las condiciones 8, 9 y 10 son condiciones 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.

Ejemplos

El álgebra de Heyting libre sobre un generador (también conocida como red de Rieger-Nishimura)

• Toda álgebra de Boole es un álgebra de Heyting, con p → q dado por ¬ p ∨ q .
• Todo conjunto totalmente ordenado que tiene un elemento menor 0 y un elemento mayor 1 es un álgebra de Heyting (si se lo considera como un retículo). En este caso, p → q es igual a 1 cuando p≤q , y q en caso contrario.
• El álgebra de Heyting más simple que no es ya un álgebra de Boole es el conjunto totalmente ordenado {0, ⁠1/2⁠ , 1} (visto como una red), dando como resultado las operaciones:

  En este ejemplo, que ⁠1/2⁠ ∨¬ ⁠1/2⁠ = ⁠1/2⁠ ∨( ⁠1/2⁠ → 0) = ⁠1/2⁠ ∨0 = ⁠1/2⁠ falsifica la ley del tercero excluido.

• Toda topología proporciona un álgebra de Heyting completa en la forma de su red de conjuntos abiertos . En este caso, el elemento A → B es el interior de la unión de A ^c y B , donde A ^c denota el complemento del conjunto abierto A . No todas las álgebras de Heyting completas tienen esta forma. Estas cuestiones se estudian en la topología sin sentido , donde las álgebras de Heyting completas también se denominan marcos o locales .
• Toda álgebra interior proporciona un álgebra de Heyting en la forma de su red de elementos abiertos. Toda álgebra de Heyting tiene esta forma, ya que un álgebra de Heyting puede completarse en un álgebra de Boole tomando su extensión booleana libre como una red distributiva acotada y luego tratándola como una topología generalizada en esta álgebra de Boole.
• El álgebra de Lindenbaum de la lógica intuicionista proposicional es un álgebra de Heyting.
• Los elementos globales del clasificador de subobjetos Ω de un topos elemental forman un álgebra de Heyting; es el álgebra de Heyting de valores de verdad de la lógica intuicionista de orden superior inducida por el topos. De manera más general, el conjunto de subobjetos de cualquier objeto X en un topos forma un álgebra de Heyting.
• Las álgebras de Łukasiewicz–Moisil (LM _n ) también son álgebras de Heyting para cualquier n ^[7] (pero no son MV-álgebras para n ≥ 5 ^[8] ).

Propiedades

Propiedades generales

El ordenamiento en un álgebra de Heyting H se puede recuperar de la operación → como sigue: para cualquier elemento a , b de H , si y sólo si a → b = 1. ${\displaystyle \leq }$ ${\displaystyle a\leq b}$

A diferencia de algunas lógicas multivaluadas , las álgebras de Heyting comparten la siguiente propiedad con las álgebras de Boole: 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.

Identidades demostrables

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

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

La metaimplicación 1 ⇒ 2 es extremadamente útil y es el principal método práctico para demostrar identidades en las álgebras de Heyting. En la práctica, se utiliza con frecuencia el teorema de deducción en dichas demostraciones.

Puesto que para cualquier a y b en un álgebra de Heyting H tenemos si y solo si a → b = 1, se sigue de 1 ⇒ 2 que siempre que una fórmula F → G sea demostrablemente verdadera, tenemos para cualquier álgebra de Heyting H , y cualesquiera elementos . (Se sigue del teorema de deducción 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 , puesto que ≤ es una relación de orden. ${\displaystyle a\leq b}$ ${\displaystyle F(a_{1},a_{2},\ldots ,a_{n})\leq G(a_{1},a_{2},\ldots ,a_{n})}$ ${\displaystyle a_{1},a_{2},\ldots ,a_{n}\in H}$ ${\displaystyle F(a_{1},a_{2},\ldots ,a_{n})=G(a_{1},a_{2},\ldots ,a_{n})}$

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, escojamos el sistema de prueba que tiene modus ponens como su única regla de inferencia, y cuyos axiomas son los de estilo Hilbert dados en Lógica intuicionista#Axiomatización . Entonces los hechos a verificar se siguen inmediatamente de la definición de tipo axiomático de las álgebras de Heyting dada anteriormente.

1 ⇒ 2 también proporciona un método para demostrar que ciertas fórmulas proposicionales, aunque tautologías en lógica clásica, no pueden demostrarse en lógica proposicional intuicionista. Para demostrar que alguna fórmula no es demostrable, es suficiente exhibir un álgebra de Heyting H y elementos tales que . ${\displaystyle F(A_{1},A_{2},\ldots ,A_{n})}$ ${\displaystyle a_{1},a_{2},\ldots ,a_{n}\in H}$ ${\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 probar como lema una versión del teorema de deducción válida para las á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, ver la sección "Construcciónes universales" a continuación.

Distributividad

Las álgebras de Heyting son siempre distributivas . En concreto, 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 se enuncia a veces como un axioma, pero en realidad se deduce de la existencia de pseudocomplementos relativos. La razón es que, al ser el adjunto inferior de una conexión de Galois , conserva todos los suprema existentes . La distributividad, a su vez, es simplemente la conservación de la suprema binaria por . ${\displaystyle \wedge }$ ${\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. A la inversa, cualquier red completa 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 pseudo-complementaria relativa.

Elementos regulares y complementados

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

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

La equivalencia de estas condiciones puede replantearse 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 complementarios entre sí si x ∧ y = 0 y x ∨ y = 1. Si existe, cualquier y de este tipo es único y, de hecho, debe ser igual a ¬ x . Llamamos a un elemento x complementado si admite un complemento. Es cierto que si x es complementado, entonces también lo es ¬ x , y entonces x y ¬ x son complementarios entre sí. Sin embargo, de manera confusa, incluso si x no es complementado, ¬ x puede tener un complemento (no igual a x ). En cualquier álgebra de Heyting, los elementos 0 y 1 son complementarios entre sí. Por ejemplo, es posible que ¬ x sea 0 para cada x diferente 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 la recíproca no es cierta 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 de Boole ;
2. toda x en H es regular; ^[9]
3. cada x en H se complementa. ^[10]

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

Los elementos regulares (respectivamente complementados) de cualquier álgebra de Heyting H constituyen un álgebra de Boole H _reg (respectivamente 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 tanto 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 ). Vea a continuación las condiciones necesarias y suficientes para que ∨ _reg coincida con ∨.

Las leyes de De Morgan en un álgebra de Heyting

Una de las dos leyes de De Morgan se cumple en cada á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 se complementa, es decir, H _reg = H _comp .

Demostramos la equivalencia. Claramente 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 de 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 sigue 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 , tomando 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 de la misma manera que las álgebras de Heyting en general están relacionadas con la lógica intuicionista.

Morfismos del álgebra de Heyting

Definición

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

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 tres últimas 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 f es una aplicación sobreyectiva de H ₁ a H ₂ con las propiedades 1 a 4 anteriores. Entonces, si H ₁ es un álgebra de Heyting, también lo es H ₂ . Esto se desprende de la caracterización de las álgebras de Heyting como retículos acotados (pensados ​​como estructuras algebraicas en lugar de conjuntos parcialmente ordenados) con una operación → que satisface ciertas identidades.

Propiedades

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

Ejemplos

Dada un á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 , la función x ↦ ¬¬ x define un morfismo de H sobre el álgebra de Boole de sus elementos regulares H _reg . En general, no se trata de 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 .

Cocientes

Sea H un álgebra de Heyting y sea F ⊆ H . Llamamos a F un filtro sobre H si satisface las siguientes propiedades:

1. ${\displaystyle 1\in F,}$
2. ${\displaystyle {\mbox{If }}x,y\in F{\mbox{ then }}x\land y\in F,}$
3. ${\displaystyle {\mbox{If }}x\in F,\ y\in H,\ {\mbox{and }}x\leq y{\mbox{ then }}y\in F.}$

La intersección de cualquier conjunto de filtros en H es nuevamente un filtro. Por lo tanto, dado cualquier subconjunto S de H existe un filtro más pequeño que contiene a S . Lo llamamos filtro generado por S . Si S está vacío, F = {1}. De lo contrario, F es igual al conjunto de x en H tales que existen y ₁ , y ₂ , ..., y _n ∈ S con y ₁ ∧ y ₂ ∧ ... ∧ y _n ≤ x .

Si H es un álgebra de Heyting y F es un filtro sobre H , definimos una relación ~ sobre H de la siguiente manera: escribimos x ~ y siempre que x → y e y → x pertenezcan ambos a F . Entonces ~ es una relación de equivalencia ; escribimos H / F para el conjunto cociente . Existe una única estructura de álgebra de Heyting sobre H / F tal que la sobreyección canónica p _F  : H → H / F se convierte en un morfismo de álgebra de Heyting. Llamamos al álgebra de Heyting H / F el cociente de H por F .

Sea S un subconjunto de un álgebra de Heyting H y sea F el filtro generado por S . Entonces H / F satisface la siguiente propiedad universal:

Dado cualquier morfismo de álgebras de Heyting f  : H → H ′ que satisface f ( y ) = 1 para cada y ∈ S , f se factoriza de forma única a través de la sobreyección canónica p _F  : H → H / F . Es decir, hay un morfismo único f ′  : H / F → H ′ que satisface f ′ p _F = f . Se dice que el morfismo f ′ es inducido por f .

Sea f  : H ₁ → H ₂ un morfismo de las álgebras de Heyting. El núcleo de f , escrito ker f , es el conjunto f ⁻¹ [{1}]. Es un filtro sobre H ₁ . (Se debe tener cuidado porque esta definición, si se aplica a un morfismo de las álgebras de Boole, es dual a lo que se llamaría el núcleo del morfismo visto como un morfismo de anillos). Por lo anterior, f induce un morfismo f ′  : H ₁ /(ker f ) → H ₂ . Es un isomorfismo de H ₁ /(ker f ) sobre la subálgebra f [ H ₁ ] de H ₂ .

Construcciones universales

Álgebra de Heyting de fórmulas proposicionales ennortevariables hasta la equivalencia intuicionista

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. Dote 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. Considérese la relación de equivalencia F ~ G inducida por el preorden F≼G. (Se define por F ~ G si y sólo si F ≼ G y G ≼ F . De hecho, ~ es la relación de equivalencia lógica (intuicionista).)
4. Sea H ₀ el conjunto cociente L /~. Ésta 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 . Verifique 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 /~. Defina además 1 como la clase de enunciados demostrablemente verdaderos y establezca 0=[⊥].
6. Verifique que H ₀ , junto con estas operaciones, es un álgebra de Heyting. Hacemos esto usando la definición de tipo axiomático 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 una a partir de la otra (por aplicación de la regla de inferencia modus ponens), por lo tanto [ F ]=[ G ].

Como siempre bajo la definición axiomática 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 .

Álgebra de Heyting libre sobre un conjunto arbitrario de generadores

De hecho, la construcción precedente puede llevarse a cabo para cualquier conjunto de variables { A _i  : i ∈ I } (posiblemente infinito). Se obtiene de esta manera 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 son fórmulas demostrablemente equivalentes, F (〈a _i〉)= G (〈a _i〉) para cualquier familia de elementos 〈a _i〉en H .

Álgebra de Heyting de fórmulas equivalentes respecto de una teoríayo

Dado un conjunto de fórmulas T en las variables { A _i }, vistas como axiomas, se podría haber llevado a cabo la misma construcción 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 las á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 . (Notemos que H _T , tomada con la familia de sus elementos 〈[ A _i ]〉, satisface por sí misma esta propiedad.) La existencia y unicidad del morfismo se prueba de la misma manera que para H ₀ , excepto que uno debe modificar la metaimplicación 1 ⇒ 2 en "Identidades demostrables" de modo que 1 se lea "demostrablemente verdadero a partir de T ", y 2 se lea "cualquier elemento a ₁ , a ₂ ,..., a _n en H que satisfaga 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 ₀ sobre 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 las formas H _T . Para comprobarlo, sea H cualquier álgebra de Heyting 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 sobreyectiva. No es difícil demostrar que f es inyectiva.

Comparación con las álgebras de Lindenbaum

Las construcciones que acabamos de dar juegan un papel completamente análogo con respecto a las álgebras de Heyting al de las álgebras de Lindenbaum con respecto a las álgebras de Boole . De hecho, el álgebra de Lindenbaum B _T en las variables { A _i } con respecto a los axiomas T es simplemente nuestra 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 necesitan ser añadidos para hacer demostrables todas las tautologías clásicas.

Álgebras de Heyting aplicadas a la lógica intuicionista

Si se interpretan los axiomas de la lógica proposicional intuicionista como términos de un álgebra de Heyting, entonces se evaluarán como el elemento más grande, 1, en cualquier álgebra de Heyting bajo cualquier asignación de valores a las variables de la fórmula. Por ejemplo, ( P ∧ Q )→ P es, por definición del pseudocomplemento, el elemento más grande x tal que . Esta inecuación se satisface para cualquier x , por lo que el más grande de tales x es 1. ${\displaystyle P\land Q\land x\leq P}$

Además, la regla del modus ponens nos permite derivar la fórmula Q a partir de las fórmulas P y P → Q . Pero en cualquier álgebra de Heyting, si P tiene el valor 1, y P → Q tiene el valor 1, entonces significa que , y por lo tanto ; solo puede ser que Q tenga el valor 1. ${\displaystyle P\land 1\leq Q}$ ${\displaystyle 1\land 1\leq Q}$

Esto significa que si una fórmula es deducible a partir de las leyes de la lógica intuicionista, al derivarse de sus axiomas mediante la regla del modus ponens, entonces siempre tendrá el valor 1 en todas las álgebras de Heyting bajo cualquier asignación de valores a las variables de la fórmula. Sin embargo, se puede construir un álgebra de Heyting en la que el valor de la ley de Peirce no sea siempre 1. Consideremos el álgebra de 3 elementos {0, ⁠1/2⁠ ,1} como se indica anteriormente. Si asignamos ⁠1/2⁠ a P y 0 a Q , entonces el valor de la ley de Peirce (( P → Q )→ P )→ P es ⁠1/2⁠ . De ello se deduce que la ley de Peirce no puede derivarse de manera intuicionista. Véase el isomorfismo de Curry-Howard para el contexto general de lo que esto implica en la teoría de tipos .

También se puede demostrar lo contrario: si una fórmula siempre tiene el valor 1, entonces es deducible a partir de las leyes de la lógica intuicionista, por lo que las fórmulas intuicionistamente válidas son exactamente aquellas que siempre tienen un valor de 1. Esto es similar a la noción de que las fórmulas clásicamente válidas son aquellas fórmulas que tienen un valor de 1 en el álgebra de Boole de dos elementos bajo cualquier posible asignación de verdadero y falso a las variables de la fórmula, es decir, son fórmulas que son tautologías en el sentido habitual de la tabla de verdad. Un álgebra de Heyting, desde el punto de vista lógico, es entonces una generalización del sistema habitual de valores de verdad, y su elemento más grande 1 es análogo a 'verdadero'. El sistema lógico de dos valores habitual es un caso especial de un álgebra de Heyting, y el más pequeño no trivial, en el que los únicos elementos del álgebra son 1 (verdadero) y 0 (falso).

Problemas de decisión

En 1965, Saul Kripke demostró que el problema de si una ecuación dada se cumple en cada álgebra de Heyting es decidible. ^{[2] La} complejidad computacional precisa del problema fue establecida por Richard Statman en 1979, quien demostró que era PSPACE-completo ^[11] y, por lo tanto, al menos tan difícil como decidir ecuaciones del álgebra de Boole (demostrada coNP-completa en 1971 por Stephen Cook ) ^[12] y se conjeturó que era considerablemente más difícil. La teoría elemental o de primer orden de las álgebras de Heyting es indecidible. ^[13] Sigue abierto si la teoría universal de Horn de las álgebras de Heyting, o problema de palabras , es decidible. ^[14] En cuanto al problema verbal, se sabe que las álgebras de Heyting no son localmente finitas (ninguna álgebra de Heyting generada por un conjunto finito no vacío es finita), a diferencia de las álgebras de Boole, que son localmente finitas y cuyo problema verbal es decidible. Se desconoce si existen álgebras de Heyting libres y completas, excepto en el caso de un único generador, donde el álgebra de Heyting libre en un generador es trivialmente completable mediante la unión de un nuevo tope.

Representación topológica y teoría de la dualidad

Toda álgebra de Heyting H es naturalmente isomorfa a una subred acotada L de conjuntos abiertos de un espacio topológico X , donde la implicación de L está dada por el interior de . Más precisamente, X es el espacio espectral de ideales primos de la red acotada H y L es la red de subconjuntos abiertos y cuasi compactos de X . ${\displaystyle U\to V}$ ${\displaystyle (X\setminus U)\cup V}$

De manera más general, la categoría de álgebras de Heyting es dualmente equivalente a la categoría de espacios de Heyting. ^[15] Esta dualidad puede verse como una restricción de la dualidad clásica de Stone de redes distributivas acotadas a la subcategoría (no completa) de álgebras de Heyting.

Alternativamente, la categoría de las álgebras de Heyting es dualmente equivalente a la categoría de los espacios de Esakia . Esto se denomina dualidad de Esakia .

Notas

1. "Álgebra pseudobooleana - Enciclopedia de matemáticas".
2. Kripke, SA: 1965, 'Análisis semántico de la lógica intuicionista I'. En: JN Crossley y MAE Dummett (eds.): Formal Systems and Recursive Functions. Ámsterdam: Holanda Septentrional, págs. 92-130.
3. Helena Rasiowa; Romano Sikorski (1963). Las Matemáticas de las Metamatemáticas . Państwowe Wydawnictwo Naukowe (PWN). págs. 54–62, 93–95, 123–130.
4. AG Kusraev; Samson Semenovich Kutateladze (1999). Análisis de valores booleanos. Springer. pág. 12. ISBN 978-0-7923-5921-0.
5. Yankov, VA (2001) [1994], "Red de Brouwer", Enciclopedia de Matemáticas , EMS Press
6. Thomas Scott Blyth (2005). Redes y estructuras algebraicas ordenadas. Springer. p. 151. ISBN 978-1-85233-905-0.
7. Georgescu, G. (2006). "Lógicas N-valuadas y álgebras de Łukasiewicz–Moisil". Axiomathes . 16 (1–2): 123–136. doi :10.1007/s10516-005-4145-6. S2CID  121264473., Teorema 3.6
8. Iorgulescu, A.: Conexiones entre álgebras MV _n y álgebras Łukasiewicz–Moisil de valor n —I. Discrete Math. 181, 155–177 (1998) doi :10.1016/S0012-365X(97)00052-6
9. Rutherford (1965), Tesis 26.2, pág. 78.
10. Rutherford (1965), Tesis 26.1, pág. 78.
11. Statman, R. (1979). "La lógica proposicional intuicionista es completa en el espacio polinomial". Theoretical Comput. Sci . 9 : 67–72. doi :10.1016/0304-3975(79)90006-9. hdl : 2027.42/23534 .
12. Cook, SA (1971). "La complejidad de los procedimientos de demostración de teoremas". Actas del Tercer Simposio Anual de la ACM sobre la Teoría de la Computación, ACM, Nueva York . págs. 151–158. doi : 10.1145/800157.805047 .
13. Grzegorczyk, Andrzej (1951). "Indecidibilidad de algunas teorías topológicas" (PDF) . Fundamentos Mathematicae . 38 : 137–52. doi :10.4064/fm-38-1-137-152.
14. Peter T. Johnstone, Stone Spaces , (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5 . (Véase el párrafo 4.11) 
15. ver sección 8.3 en * Dickmann, Max; Schwartz, Niels; Tressl, Marcus (2019). Espacios espectrales . Nuevas monografías matemáticas. Vol. 35. Cambridge: Cambridge University Press . doi :10.1017/9781316543870. ISBN . 9781107146723. Número de identificación del sujeto  201542298.

Véase también

• Topología de Alexandrov
• Lógicas superintuicionistas (también conocidas como lógicas intermedias)
• Lista de temas de álgebra de Boole
• Álgebra de Ockham

Referencias

• Rutherford, Daniel Edwin (1965). Introducción a la teoría de retículos . Oliver y Boyd. OCLC  224572.
• F. Borceux, Manual de álgebra categórica 3 , en Enciclopedia de matemáticas y sus aplicaciones , vol. 53, Cambridge University Press, 1994. ISBN 0-521-44180-3 OCLC  52238554 
• G. Gierz, K. Hoffmann, K. Keimel, J. D. Lawson, M. Mislove y DS Scott , Redes y dominios continuos , en Enciclopedia de matemáticas y sus aplicaciones , vol. 93, Cambridge University Press, 2003.
• S. Ghilardi. Álgebras de Heyting libres como álgebras de bi-Heyting , Math. Rep. Acad. Sci. Canada XVI., 6:240–244, 1992.
• Heyting, A. (1930), "Die formalen Regeln der intuitionistischen Logik. I, II, III", Sitzungsberichte Akad. Berlín : 42–56, 57–71, 158–169, JFM  56.0823.01
• Dickmann, Max; Schwartz, Niels; Tressl, Marcus (2019). Espacios espectrales . Nuevas monografías matemáticas. Vol. 35. Cambridge: Cambridge University Press . doi :10.1017/9781316543870. ISBN . 9781107146723. Número de identificación del sujeto  201542298.

Enlaces externos

• Álgebra de Heyting en PlanetMath .