Lógica intuicionista

Lógica intuicionista, a veces más generalmente llamada lógica constructiva, se refiere a sistemas de lógica simbólica que difieren de los sistemas utilizados para la lógica clásica al reflejar más de cerca la noción de lógica constructiva. prueba. En particular, los sistemas de lógica intuicionista no asumen la ley del medio excluido y la eliminación de la doble negación, que son reglas de inferencia fundamentales en la lógica clásica.

La lógica intuicionista formalizada fue desarrollada originalmente por Arend Heyting para proporcionar una base formal para el programa de intuicionismo de L. E. J. Brouwer. Desde una perspectiva de la teoría de la prueba, el cálculo de Heyting es una restricción de la lógica clásica en la que se han eliminado la ley de eliminación del medio excluido y la doble negación. Sin embargo, la eliminación de la negación media y doble excluida aún se puede probar para algunas proposiciones caso por caso, pero no se cumple universalmente como lo hace con la lógica clásica. La explicación estándar de la lógica intuicionista es la interpretación BHK.

Se han estudiado varios sistemas de semántica para la lógica intuicionista. Una de estas semánticas refleja la semántica clásica con valores booleanos pero usa álgebras de Heyting en lugar de álgebras booleanas. Otra semántica utiliza modelos de Kripke. Estos, sin embargo, son medios técnicos para estudiar el sistema deductivo de Heyting en lugar de formalizaciones de las intuiciones semánticas informales originales de Brouwer. Los sistemas semánticos que afirman capturar tales intuiciones, debido a que ofrecen conceptos significativos de "verdad constructiva" (en lugar de meramente validez o demostrabilidad), son la interpretación dialéctica de Kurt Gödel, la realizabilidad de Stephen Cole Kleene, la lógica de problemas finitos de Yurii Medvedev o la lógica de computabilidad de Giorgi Japaridze.. Sin embargo, tal semántica induce persistentemente lógicas más fuertes que la lógica de Heyting. Algunos autores han argumentado que esto podría ser una indicación de la inadecuación del cálculo de Heyting en sí mismo, considerando que este último es incompleto como lógica constructiva.

Constructivismo matemático

En la semántica de la lógica clásica, las fórmulas proposiciones se asignan valores de verdad del conjunto de dos elementos {}⊤ ⊤ ,⊥ ⊥ }{displaystyle {topbot}} ("verdad" y "falso" respectivamente), independientemente de si tenemos evidencia directa para cualquier caso. Esto se denomina "ley de centro excluido", porque excluye la posibilidad de cualquier valor de verdad además de "verdad" o "falso". En contraste, las fórmulas proposicionales en la lógica intuitionista son no asignado un valor de verdad definido y sólo considerado "verdadero" cuando tenemos evidencia directa, por lo tanto prueba. (También podemos decir, en lugar de que la fórmula proposicional sea "verdadera" debido a la evidencia directa, que está habitada por una prueba en el sentido Curry-Howard.) Por lo tanto, las operaciones en la lógica intuitionista preservan la justificación, con respecto a la evidencia y la probabilidad, en lugar de la valoración de la verdad.

La lógica intuicionista es una herramienta de uso común en el desarrollo de enfoques para el constructivismo en matemáticas. El uso de lógicas constructivistas en general ha sido un tema controvertido entre matemáticos y filósofos (ver, por ejemplo, la controversia Brouwer-Hilbert). Una objeción común a su uso es la falta citada anteriormente de dos reglas centrales de la lógica clásica, la ley del medio excluido y la eliminación de la doble negación. Estos se consideran tan importantes para la práctica de las matemáticas que David Hilbert escribió sobre ellos: "Tomar el principio del medio excluido del matemático sería lo mismo, digamos, que proscribir el telescopio al astrónomo o al boxeador". el uso de sus puños. Prohibir las declaraciones de existencia y el principio del tercero excluido equivale a renunciar por completo a la ciencia de las matemáticas."

A pesar de los serios desafíos presentados por la incapacidad de utilizar las valiosas reglas de eliminación de negación doble y media excluida, la lógica intuicionista tiene un uso práctico. Una de las razones de esto es que sus restricciones producen pruebas que tienen la propiedad de existencia, lo que lo hace adecuado también para otras formas de constructivismo matemático. Informalmente, esto significa que si hay una prueba constructiva de que existe un objeto, esa prueba constructiva puede usarse como un algoritmo para generar un ejemplo de ese objeto, un principio conocido como la correspondencia de Curry-Howard entre pruebas y algoritmos. Una de las razones por las que este aspecto particular de la lógica intuicionista es tan valioso es que permite a los profesionales utilizar una amplia gama de herramientas informáticas, conocidas como asistentes de prueba. Estas herramientas ayudan a sus usuarios en la verificación (y generación) de pruebas a gran escala, cuyo tamaño generalmente impide la verificación humana habitual que implica la publicación y revisión de una prueba matemática. Como tal, el uso de asistentes de prueba (como Agda o Coq) está permitiendo a los matemáticos y lógicos modernos desarrollar y probar sistemas extremadamente complejos, más allá de aquellos que son factibles de crear y verificar únicamente a mano. Un ejemplo de una prueba que era imposible de verificar satisfactoriamente sin una verificación formal es la famosa prueba del teorema de los cuatro colores. Este teorema dejó perplejos a los matemáticos durante más de cien años, hasta que se desarrolló una prueba que descartó grandes clases de posibles contraejemplos, pero que dejó abiertas suficientes posibilidades como para que se necesitara un programa de computadora para terminar la prueba. Esa prueba fue controvertida durante algún tiempo, pero, más tarde, se verificó usando Coq.

Sintaxis

La celosa Rieger-Nishimura. Sus nodos son las fórmulas proposicionales en una variable hasta la equivalencia lógica intuitionista, ordenada por implicación lógica intuitionista.

La sintaxis de las fórmulas de la lógica intuicionista es similar a la lógica proposicional o lógica de primer orden. Sin embargo, los conectivos intuicionistas no son definibles entre sí de la misma manera que en la lógica clásica, por lo tanto, su elección es importante. En la lógica proposicional intuicionista (IPL) se acostumbra usar →, ∧, ∨, ⊥ como conectores básicos, tratando ¬A como una abreviatura de ( A → ⊥). En la lógica intuicionista de primer orden se necesitan ambos cuantificadores ∃, ∀.

Más débil que la lógica clásica

La lógica intuitionista puede entenderse como un debilitamiento de la lógica clásica, lo que significa que es más conservadora en lo que permite a un razonador inferir, sin permitir nuevas inferencias que no podrían hacerse bajo la lógica clásica. Cada teorema de la lógica intuitionista es un teorema en la lógica clásica, pero no transversalmente. Muchas tautologías en la lógica clásica no son teoremas en la lógica intuitionista – en particular, como se ha dicho anteriormente, uno de los objetivos principales de la lógica intuitionista es no afirmar la ley del medio excluido para viciar el uso de la prueba no constructiva por la contradicción, que se puede utilizar para proporcionar afirmaciones de existencia sin proporcionar ejemplos explícitos de los objetos que demuestra existir. Decimos "no afirmar" porque si bien no es necesariamente cierto que la ley se mantiene en cualquier contexto, no se puede dar contraexample: tal contraexample sería una inferencia (inferir la negación de la ley para una determinada proposición) desagrada bajo la lógica clásica y por lo tanto no se permite en un debilitamiento estricto como la lógica intuitionista. De hecho, la doble negación de la ley se mantiene como una tautología del sistema: es decir, es un teorema que ¬ ¬ ()¬ ¬ ()PAlternativa Alternativa ¬ ¬ P)){displaystyle neg {big (}neg (Pvee neg P){big)}} independientemente de la proposición P{displaystyle P}. Así que el cálculo proposicional siempre es compatible con la lógica clásica. La situación es más intrincada para fórmulas lógicas predicadas cuando se niegan expresiones cuantificadas.

Cálculo secuencial

Gerhard Gentzen descubrió que una simple restricción de su sistema LK (su cálculo secuencial para la lógica clásica) da como resultado un sistema sólido y completo con respecto a la lógica intuicionista. Llamó a este sistema LJ. En LK se permite que aparezca cualquier cantidad de fórmulas en el lado de la conclusión de una secuencia; por el contrario, LJ permite como máximo una fórmula en esta posición.

Otros derivados de LK se limitan a derivaciones intuicionistas pero aún permiten múltiples conclusiones en un secuente. LJ' es un ejemplo.

Cálculo al estilo de Hilbert

La lógica intuitiva se puede definir usando el siguiente cálculo de estilo Hilbert. Esto es similar a una forma de axiomatizar la lógica proposicional clásica.

En lógica proposicional, la regla de inferencia es modus ponens

• MP: φ φ {displaystyle phi } y φ φ → → ↑ ↑ {displaystyle phi to psi } inferente ↑ ↑ {displaystyle psi }

y los axiomas son

• THEN-1: φ φ → → ()χ χ → → φ φ ){displaystyle phi to (chi to phi)}
• THEN-2: ()φ φ → → ()χ χ → → ↑ ↑ ))→ → ()()φ φ → → χ χ )→ → ()φ φ → → ↑ ↑ )){displaystyle (phi to (chi to psi)to (phi to chi)to (phi to psi)}
• Y-1: φ φ ∧ ∧ χ χ → → φ φ {displaystyle phi land chi to phi }
• Y-2: φ φ ∧ ∧ χ χ → → χ χ {displaystyle phi land chi to chi }
• Y-3: φ φ → → ()χ χ → → ()φ φ ∧ ∧ χ χ )){displaystyle phi to (chi to (phi land chi)}
• OR-1: φ φ → → φ φ Alternativa Alternativa χ χ {displaystyle phi to fi lor chi }
• OR-2: χ χ → → φ φ Alternativa Alternativa χ χ {displaystyle chi to phi lor chi }
• OR-3: ()φ φ → → ↑ ↑ )→ → ()()χ χ → → ↑ ↑ )→ → ()()φ φ Alternativa Alternativa χ χ )→ → ↑ ↑ )){displaystyle (phi to psi)to (chi to psi)to (phi lor chi)to psi)}
• FALSE: ⊥ ⊥ → → φ φ {displaystyle bot to phi }

Para hacer de este un sistema de lógica de predicados de primer orden, las reglas de generalización

• О О {displaystyle forall }-GEN: ↑ ↑ → → φ φ {displaystyle psi to phi } inferente ↑ ↑ → → ()О О xφ φ ){displaystyle psi to (forall x\phi)}, si x{displaystyle x} no es libre en ↑ ↑ {displaystyle psi }
• ∃ ∃ {displaystyle exists }-GEN: φ φ → → ↑ ↑ {displaystyle phi to psi } inferente ()∃ ∃ xφ φ )→ → ↑ ↑ {displaystyle (exists x\\fnMicrosoft Sans Serif)to psi }, si x{displaystyle x} no es libre en ↑ ↑ {displaystyle psi }

se añaden, junto con los axiomas

• PRED-1: ()О О xφ φ ()x))→ → φ φ ()t){displaystyle (forall x phi (x))to phi (t)}, si el término t{displaystyle t} es libre de sustitución para la variable x{displaystyle x} dentro φ φ {displaystyle phi } (es decir, si no ocurre ninguna variable en t{displaystyle t} se atan φ φ ()t){displaystyle phi (t)})
• PRED-2: φ φ ()t)→ → ()∃ ∃ xφ φ ()x)){displaystyle phi (t)to (exists x\phi (x)}, con la misma restricción que para PRED-1

Conectivas opcionales

Negación

Si uno desea incluir un conector ¬ ¬ {displaystyle lnot } para la negación en lugar de considerarla una abreviatura φ φ → → ⊥ ⊥ {displaystyle phi to bot }, es suficiente añadir:

• NO-1': ()φ φ → → ⊥ ⊥ )→ → ¬ ¬ φ φ {displaystyle (phi to bot)to lnot phi }
• NO-2': ¬ ¬ φ φ → → ()φ φ → → ⊥ ⊥ ){displaystyle lnot phi to (phi to bot)}

Hay una serie de alternativas disponibles si se desea omitir el conector ⊥ ⊥ {displaystyle bot } (falso). Por ejemplo, uno puede reemplazar los tres axiomas FALSE, NO-1', y NO-2' con los dos axiomas

• NO-1: ()φ φ → → χ χ )→ → ()()φ φ → → ¬ ¬ χ χ )→ → ¬ ¬ φ φ ){displaystyle (phi to chi)to (phi to lnot chi)to lnot phi)}
• NO-2: φ φ → → ()¬ ¬ φ φ → → χ χ ){displaystyle phi to (lnot phi to chi)}

como en el cálculo proposicional § Axioms. Alternativas a NO-1 son ()φ φ → → ¬ ¬ χ χ )→ → ()χ χ → → ¬ ¬ φ φ ){displaystyle (phi to lnot chi)to (chi to lnot phi)} o ()φ φ → → ¬ ¬ φ φ )→ → ¬ ¬ φ φ {displaystyle (phi to lnot phi)to lnot phi }.

Equivalencia

El conector Administración Administración {displaystyle leftrightarrow } para la equivalencia puede tratarse como una abreviatura, con φ φ Administración Administración χ χ {displaystyle phi leftrightarrow chi } de pie ()φ φ → → χ χ )∧ ∧ ()χ χ → → φ φ ){displaystyle (phi to chi)land (chi to phi)}. Alternativamente, se puede añadir el axioma

• IFF-1: ()φ φ Administración Administración χ χ )→ → ()φ φ → → χ χ ){displaystyle (phi leftrightarrow chi)to (phi to chi)}
• IFF-2: ()φ φ Administración Administración χ χ )→ → ()χ χ → → φ φ ){displaystyle (phi leftrightarrow chi)to (chi to phi)}
• IFF-3: ()φ φ → → χ χ )→ → ()()χ χ → → φ φ )→ → ()φ φ Administración Administración χ χ )){displaystyle (phi to chi)to (chi to phi)to (phi leftrightarrow chi)}

IFF-1 e IFF-2 pueden, si se desea, combinarse en un solo axioma ()φ φ Administración Administración χ χ )→ → ()()φ φ → → χ χ )∧ ∧ ()χ χ → → φ φ )){displaystyle (phi leftrightarrow chi)to (phi to chi)land (chi to phi)} usando conjunción.

Relación con la lógica clásica

El sistema de lógica clásica se obtiene sumando cualquiera de los siguientes axiomas:

• φ φ Alternativa Alternativa ¬ ¬ φ φ {displaystyle phi lor lnot phi } (Ley del centro excluido. También puede formularse ()φ φ → → χ χ )→ → ()()¬ ¬ φ φ → → χ χ )→ → χ χ ){displaystyle (phi to chi)to (lnot phi to chi)to chi)}.)
• ¬ ¬ ¬ ¬ φ φ → → φ φ {displaystyle lnot lnot phi to phi } (Erradicación doble de la negación)
• ()()φ φ → → χ χ )→ → φ φ )→ → φ φ {displaystyle (phi to chi)to phi)to phi } (La ley de Peter)
• ()¬ ¬ φ φ → → ¬ ¬ χ χ )→ → ()χ χ → → φ φ ){displaystyle (lnot to to lnot chi)to (chi to phi)} (Ley de contraposición)

En general, se puede tomar como el axioma extra cualquier tautología clásica que no sea válida en el marco de dos elementos Kripke ∘ ∘ restablecimiento restablecimiento ∘ ∘ {displaystyle circ {longrightarrow }circ } (en otras palabras, eso no está incluido en la lógica de Smetanich).

Otra relación viene dada por la traducción negativa de Gödel-Gentzen, que proporciona una integración de la lógica clásica de primer orden en la lógica intuicionista: una fórmula de primer orden es demostrable en lógica clásica si y solo si su traducción de Gödel-Gentzen es demostrable intuitivamente. Por lo tanto, la lógica intuicionista puede verse, en cambio, como un medio para extender la lógica clásica con semántica constructiva.

En 1932, Kurt Gödel definió un sistema de lógicas intermedio entre la lógica clásica y la intuicionista; Las lógicas de Gödel se conocen concomitantemente como lógicas intermedias.

Reglas admisibles

En la lógica intuitionista o una teoría fija usando la lógica, la situación puede ocurrir que una implicación siempre sostiene metateóricamente, pero no en el lenguaje. Por ejemplo, en el cálculo proposición puro, si ()¬ ¬ A)→ → ()BAlternativa Alternativa C){displaystyle (neg A)to (Blor C)} es provable, entonces lo es ()¬ ¬ A→ → B)Alternativa Alternativa ()¬ ¬ A→ → C){displaystyle (neg Ato B)lor (neg Ato C)}. Otro ejemplo es que ()A→ → B)→ → ()AAlternativa Alternativa C){displaystyle (Ato B)to (Alor C)} ser provable siempre significa que así es ()()A→ → B)→ → A)Alternativa Alternativa ()()A→ → B)→ → C){bignMicrosoft Sans Serif}lor {big (}(Ato B)to C{big)}}}. Uno dice que el sistema está cerrado bajo estas implicaciones como reglas y pueden ser adoptados.

No interdefinibilidad de operadores

En la lógica proposicional clásica, es posible tomar uno de conjunción, disyunción o implicación como primitivo, y definir los otros dos en términos de este junto con la negación, como en los tres axiomas de la lógica proposicional de Łukasiewicz.. Incluso es posible definir los cuatro en términos de un único operador suficiente como la flecha de Peirce (NOR) o el trazo de Sheffer (NAND). De manera similar, en la lógica clásica de primer orden, uno de los cuantificadores se puede definir en términos del otro y la negación. Estas son fundamentalmente consecuencias de la ley de la bivalencia, que convierte a todos estos conectivos en meras funciones booleanas.

La ley de la bivalencia no está obligada a mantener en la lógica intuitiva, sólo la ley de la no contradicción. Como resultado, ninguno de los conectores básicos puede ser dispensado con, y los axiomas anteriores son todos necesarios. Así que la mayoría de las identidades clásicas entre conectores y cuantificadores son sólo teoremas de lógica intuitionista en una dirección. Algunos de los teoremas van en ambas direcciones, es decir, son equivalencias, como se discutió posteriormente. A continuación se presenta una lista de implicaciones que implican negaciones. Combinando los axiomas THEN-1 y THEN-2 arriba, ()P→ → ¬ ¬ Q)Administración Administración ()Q→ → ¬ ¬ P){displaystyle (Pto neg Q)leftrightarrow (Qto neg P)} a continuación, una conversión que puede utilizarse para obtener nuevas implicaciones.

Cuantificación existencial versus universal:

• ()∃ ∃ xφ φ ()x))→ → ¬ ¬ ()О О x¬ ¬ φ φ ()x)){displaystyle (exists x phi (x))to neg (forall x\neg phi (x)}
• ()∃ ∃ x¬ ¬ φ φ ()x))→ → ¬ ¬ ()О О xφ φ ()x)){displaystyle (exists x\neg phi (x))to neg (forall x\\phi (x)}

Y a la inversa,

• ()О О x¬ ¬ φ φ ()x))Administración Administración ¬ ¬ ()∃ ∃ xφ φ ()x)){displaystyle (forall x\\neg phi (x))leftrightarrow neg (exists x\\phi (x)}
• ()О О xφ φ ()x))→ → ¬ ¬ ()∃ ∃ x¬ ¬ φ φ ()x)){displaystyle (forall x phi (x)))to neg (exists x\neg phi (x)}

Hay variaciones finitas de aquellas con solo dos proposiciones.

Disyunción vs conjunción:

• ()φ φ Alternativa Alternativa ↑ ↑ )→ → ¬ ¬ ()¬ ¬ φ φ ∧ ∧ ¬ ¬ ↑ ↑ ){displaystyle (phi vee psi)to neg (neg phi wedge neg psi)}
• ()¬ ¬ φ φ Alternativa Alternativa ↑ ↑ )→ → ¬ ¬ ()φ φ ∧ ∧ ¬ ¬ ↑ ↑ ){displaystyle (neg phi vee psi)to neg (phi wedge neg psi)}
• ()¬ ¬ φ φ Alternativa Alternativa ¬ ¬ ↑ ↑ )→ → ¬ ¬ ()φ φ ∧ ∧ ↑ ↑ ){displaystyle (neg phi vee neg psi)to neg (phi wedge psi)}

Y a la inversa,

• ()¬ ¬ φ φ ∧ ∧ ¬ ¬ ↑ ↑ )Administración Administración ¬ ¬ ()φ φ Alternativa Alternativa ↑ ↑ ){displaystyle (neg phi wedge neg psi)leftrightarrow neg (phi vee psi)}
• ()φ φ ∧ ∧ ¬ ¬ ↑ ↑ )→ → ¬ ¬ ()¬ ¬ φ φ Alternativa Alternativa ↑ ↑ ){displaystyle (phi wedge neg psi)to neg (neg phi vee psi)}
• ()φ φ ∧ ∧ ↑ ↑ )→ → ¬ ¬ ()¬ ¬ φ φ Alternativa Alternativa ¬ ¬ ↑ ↑ ){displaystyle (phi wedge psi)to neg (neg phi vee neg psi)}

Así que las declaraciones negadas son antecedentes débiles y a su vez no todas las leyes clásicas de De Morgan sostienen. Véase también LLPO{displaystyle {mathrm {LLPO}} para una variante relativa a dos predicaciones decidables existencialmente cerradas.

Continuando,

Conjunción vs. implicación:

• ()φ φ ∧ ∧ ↑ ↑ )→ → ¬ ¬ ()φ φ → → ¬ ¬ ↑ ↑ ){displaystyle (phi wedge psi)to neg (phi to neg psi)}
• ()φ φ ∧ ∧ ¬ ¬ ↑ ↑ )→ → ¬ ¬ ()φ φ → → ↑ ↑ ){displaystyle (phi wedge neg psi)to neg (phi to psi)}

Y a la inversa,

• ()φ φ → → ¬ ¬ ↑ ↑ )Administración Administración ¬ ¬ ()φ φ ∧ ∧ ↑ ↑ ){displaystyle (phi to neg psi)leftrightarrow neg (phi wedge psi)}
• ()φ φ → → ↑ ↑ )→ → ¬ ¬ ()φ φ ∧ ∧ ¬ ¬ ↑ ↑ ){displaystyle (phi to psi)to neg (phi wedge neg psi)}

Las fórmulas para ¬ ¬ ()φ φ ∧ ∧ ↑ ↑ ){displaystyle neg (phi wedge psi)} se puede utilizar para implicar ()¬ ¬ φ φ Alternativa Alternativa ¬ ¬ ↑ ↑ )→ → ()φ φ → → ¬ ¬ ↑ ↑ ){displaystyle (neg phi vee neg psi)to (phi to neg psi)} y también valida la versión con las posiciones φ φ {displaystyle phi } y ¬ ¬ φ φ {displaystyle neg phi } cambiado. Estos últimos son formas del syllogismo disyuntivo para proposiciones negadas, ¬ ¬ ↑ ↑ {displaystyle neg psi }. Una forma de strenghtenend todavía tiene en la lógica intuitionista, como sigue.

Disyunción versus implicación:

• ()φ φ Alternativa Alternativa ↑ ↑ )→ → ()¬ ¬ φ φ → → ↑ ↑ ){displaystyle (phi vee psi)to (neg phi to psi)}
• ()¬ ¬ φ φ Alternativa Alternativa ↑ ↑ )→ → ()φ φ → → ↑ ↑ ){displaystyle (neg phi vee psi)to (phi to psi)}

Así que, por ejemplo, intuitivamente "Either P{displaystyle P} o Q{displaystyle Q}"es una fórmula proposición más fuerte que "Si no P{displaystyle P}, entonces Q{displaystyle Q}", mientras que estos son clásicamente intercambiables. Tal implicación para general ↑ ↑ {displaystyle psi } no es válido en la lógica mínima.

Equivalencias:

Las listas anteriores también contienen equivalencias. En primer lugar, la equivalencia que implica una conjunción y una disyunción proviene de ()PAlternativa Alternativa Q)→ → R{displaystyle (Plor Q)to R} en realidad siendo más fuerte que P→ → R{displaystyle Pto R}. Ambas partes de la equivalencia se pueden entender como conjunciones de implicaciones independientes (de absurdo). En interpretaciones funcionales, corresponde a construcciones si-clasas. Así que, por ejemplo. "No"P{displaystyle P} o Q{displaystyle Q})" es equivalente a "Not P{displaystyle P}, y tampoco Q{displaystyle Q}". En segundo lugar, la equivalencia que implica una implicación y una conjunción corresponde a la curación. Debido a la simetría de la conjunción conectivo, implica de nuevo

()φ φ → → ¬ ¬ ↑ ↑ )Administración Administración ()↑ ↑ → → ¬ ¬ φ φ ){displaystyle (phi to neg psi)leftrightarrow (psi to neg phi)}

Los casos especiales de esta conversión componen las listas anteriores. La simetría de la conjunción también puede entenderse como razón de por qué la negación de φ φ {displaystyle phi } se puede mover entre antecedente y consecuente en las dos primeras listas arriba.

Las equivalencias en las listas se pueden generalizar conjuntamente a la equivalencia

()О О x.φ φ ()x)→ → ()↑ ↑ ()x)→ → χ χ ))Administración Administración ()∃ ∃ x.φ φ ()x)∧ ∧ ↑ ↑ ()x))→ → χ χ {displaystyle {big (}forall x.phi (x)to (psi (x)to chi){big)},,,leftrightarrow ,,,{big (}exists x.phi (x)land psi (x){big)}to chi }

para χ χ {displaystyle chi } como ⊥ ⊥ {displaystyle bot } son dos caracterizaciones de separación.

Una equivalencia en sí misma generalmente se define como una conjunción de implicaciones, y luego es equivalente a ella.

• ()φ φ Administración Administración ↑ ↑ )Administración Administración ()()φ φ → → ↑ ↑ )∧ ∧ ()↑ ↑ → → φ φ )){displaystyle (phi leftrightarrow psi)leftrightarrow {big (}(phi to psi)land (psi to phi){big)}}

Con él, tales conectivos se vuelven a su vez definibles a partir de él:

• ()φ φ → → ↑ ↑ )Administración Administración ()()φ φ Alternativa Alternativa ↑ ↑ )Administración Administración ↑ ↑ ){displaystyle (phi to psi)leftrightarrow (phi lor psi)leftrightarrow psi)}
• ()φ φ → → ↑ ↑ )Administración Administración ()()φ φ ∧ ∧ ↑ ↑ )Administración Administración φ φ ){displaystyle (phi to psi)leftrightarrow (phi land psi)leftrightarrow phi)}
• ()φ φ ∧ ∧ ↑ ↑ )Administración Administración ()()φ φ → → ↑ ↑ )Administración Administración φ φ ){displaystyle (phi land psi)leftrightarrow (phi to psi)leftrightarrow phi)}
• ()φ φ ∧ ∧ ↑ ↑ )Administración Administración ()()()φ φ Alternativa Alternativa ↑ ↑ )Administración Administración ↑ ↑ )Administración Administración φ φ ){displaystyle (phi land psi)leftrightarrow ((phi lor psi)leftrightarrow phi)}

A su vez, {}Alternativa Alternativa ,Administración Administración ,⊥ ⊥ }{displaystyle {lorleftrightarrowbot}} y {}∧ ∧ ,Administración Administración ,¬ ¬ }{displaystyle {landleftrightarrowneg}} son bases completas de conexiones intuitionistas.

Conectivos funcionalmente completos:

Como lo muestra Alexander V. Kuznetsov, cualquiera de los siguientes conectores, el primero ternario, el segundo quinario, es por sí mismo funcionalmente completo: cualquiera de los dos puede desempeñar el papel de un único operador suficiente para la lógica proposicional intuicionista, por lo tanto formando un análogo del trazo de Sheffer de la lógica proposicional clásica:

• ()()PAlternativa Alternativa Q)∧ ∧ ¬ ¬ R)Alternativa Alternativa ()¬ ¬ P∧ ∧ ()QAdministración Administración R)){bign}neg Pland (Q)neg R{big)}lor {big (}neg Pland (Qleftrightarrow R){big)}}
• P→ → ()Q∧ ∧ ¬ ¬ R∧ ∧ ()SAlternativa Alternativa T)){displaystyle Pto {big (}Qland neg Rland (Slor T){big)}

Semántica

La semántica es bastante más complicada que en el caso clásico. Se puede dar una teoría modelo mediante álgebras de Heyting o, de manera equivalente, mediante semántica de Kripke. Recientemente, Bob Constable demostró que una teoría del modelo similar a la de Tarski es completa, pero con una noción de completitud diferente a la clásica.

Las declaraciones no probadas en la lógica intuicionista no reciben un valor de verdad intermedio (como a veces se afirma erróneamente). Uno puede probar que tales declaraciones no tienen un tercer valor de verdad, un resultado que se remonta a Glivenko en 1928. En cambio, permanecen con un valor de verdad desconocido, hasta que se prueban o refutan. Los enunciados se refutan deduciendo de ellos una contradicción.

Una consecuencia de este punto de vista es que la lógica intuitionista no tiene interpretación como una lógica de dos valores, ni siquiera como una lógica de valor finito, en el sentido familiar. Aunque la lógica intuitionista conserva las proposiciones triviales {}⊤ ⊤ ,⊥ ⊥ }{displaystyle {topbot}} de la lógica clásica, cada prueba de una fórmula proposicional se considera un valor proposicional válido, por lo tanto por la noción de Heyting de proposiciones-como-sets, fórmulas proposicionales son (potencialmente no-finitas) conjuntos de sus pruebas.

Heyting álgebra semántica

En la lógica clásica, a menudo discutimos los valores de verdad que puede tomar una fórmula. Los valores generalmente se eligen como miembros de un álgebra booleana. Las operaciones de encuentro y unión en el álgebra booleana se identifican con los conectores lógicos ∧ y ∨, de modo que el valor de una fórmula de la forma A ∧ B es el encuentro de el valor de A y el valor de B en el álgebra booleana. Entonces tenemos el útil teorema de que una fórmula es una proposición válida de la lógica clásica si y sólo si su valor es 1 para cada valoración, es decir, para cualquier asignación de valores a sus variables.

Un teorema correspondiente es cierto para la lógica intuicionista, pero en lugar de asignar a cada fórmula un valor de un álgebra booleana, se usan valores de un álgebra de Heyting, de las cuales las álgebras booleanas son un caso especial. Una fórmula es válida en lógica intuicionista si y solo si recibe el valor del elemento superior para cualquier valoración en cualquier álgebra de Heyting.

Se puede demostrar que para reconocer fórmulas válidas, es suficiente considerar una única álgebra de Heyting cuyos elementos son los subconjuntos abiertos de la recta real R. En este álgebra tenemos:

Valor[⊥ ⊥ ]=∅ ∅ Valor[⊤ ⊤ ]=RValor[A∧ ∧ B]=Valor[A]∩ ∩ Valor[B]Valor[AAlternativa Alternativa B]=Valor[A]∪ ∪ Valor[B]Valor[A→ → B]=int()Valor[A]∁ ∁ ∪ ∪ Valor[B]){fnMicrosoft Sans Serif} {fnMicrosoft} {fnMicrosoft} {fnMicrosoft} {f} {fnMicrosoft} {fnMicrosoft} {fnMicrosoft} {fnMicrosoft} {fnMicrosoft} {fnMicrosoft ]} {f} {fnMicrosoft} {fnMicrosoft} {fnMicrosoft} {f} {fnMicrosoft} {fnMicrosoft} {fnMicrosoft} {fnMicrosoft} {fnMicrosoft}fnMicrosoft} {fnMicrosoft}fnMicrosoft} {fnMicrosoft} {f}}fnMicrosoft} {fnMicrosoft} {f}}fnMicrosoft}fnMicrosoft}fnMicrosoft}fnMicrosoft}fnMicrosoft} {fnMi

donde int(X) es el interior de X y X^∁ su complemento.

La última identidad relativa a A → B nos permite calcular el valor de ¬A:

Valor[¬ ¬ A]=Valor[A→ → ⊥ ⊥ ]=int()Valor[A]∁ ∁ ∪ ∪ Valor[⊥ ⊥ ])=int()Valor[A]∁ ∁ ∪ ∪ ∅ ∅ )=int()Valor[A]∁ ∁ ){displaystyle {begin{aligned}{text{Value}[neg] ################################################################################################################################################################################################################################################################

Con estas asignaciones, las fórmulas intuicionistamente válidas son precisamente aquellas a las que se les asigna el valor de toda la línea. Por ejemplo, la fórmula ¬(A ∧ ¬A) es válida, porque no importa qué conjunto X se elija como el valor de la fórmula A, se puede demostrar que el valor de ¬(A ∧ ¬A) es la línea completa:

Valor[¬ ¬ ()A∧ ∧ ¬ ¬ A)]=int()Valor[A∧ ∧ ¬ ¬ A]∁ ∁ )Valor[¬ ¬ B]=int()Valor[B]∁ ∁ )=int()()Valor[A]∩ ∩ Valor[¬ ¬ A])∁ ∁ )=int()()Valor[A]∩ ∩ int()Valor[A]∁ ∁ ))∁ ∁ )=int()()X∩ ∩ int()X∁ ∁ ))∁ ∁ )=int()∅ ∅ ∁ ∁ )int()X∁ ∁ )⊆ ⊆ X∁ ∁ =int()R)=R{displaystyle {begin{aligned}{text{Value}[neg] (Aland neg A)] {fnMicrosoft Sans Serif} X^{complement }\\text{int}(mathbf {R})\ {R} end{aligned}}

Entonces, la valoración de esta fórmula es verdadera y, de hecho, la fórmula es válida. Pero se puede demostrar que la ley del tercero excluido, A ∨ ¬A, es inválida usando un valor específico del conjunto de valores positivos números reales para A:

0}cup {text{int}}left({x>0}^{complement }right)\&={x>0}cup {text{int}}left({xleqslant 0}right)\&={x>0}cup {xValor[AAlternativa Alternativa ¬ ¬ A]=Valor[A]∪ ∪ Valor[¬ ¬ A]=Valor[A]∪ ∪ int()Valor[A]∁ ∁ )Valor[¬ ¬ B]=int()Valor[B]∁ ∁ )={}x■0}∪ ∪ int(){}x■0}∁ ∁ )={}x■0}∪ ∪ int(){}x⩽ ⩽ 0})={}x■0}∪ ∪ {}x.0}={}xل ل 0}ل ل R{begin{aligned} {text{Value}[Alor neg A] limit={text{Value}}[A]cup {text{Value}}[neg A]\cH00={f} {cH00} {cH00}} {cH00} {cH00}} {cH00}}}} {cH00}}}}}}}}}} {cH00}}}}}}}}}}}}}}}cH00} {cambien]}}} {cH00} {cH00}}}}}}}}}}}}}}} {cH00} {cH00}} {cH00} {cH00}}}}}}}}}}}}}}}}}}}}}}}}}}} {cH00}}}} {cH00}}}}}}}}}}}} {c {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {R} end{aligned}}0}cup {text{int}}left({x>0}^{complement }right)\&={x>0}cup {text{int}}left({xleqslant 0}right)\&={x>0}cup {x

La interpretación de cualquier fórmula intuitivamente válida en el álgebra infinita de Heyting descrita anteriormente da como resultado el elemento superior, que representa verdadero, como la valoración de la fórmula, independientemente de qué valores del álgebra se asignen a las variables de la fórmula. Por el contrario, para cada fórmula inválida, hay una asignación de valores a las variables que arroja una valoración que difiere del elemento superior. Ningún álgebra de Heyting finita tiene la segunda de estas dos propiedades.

Semántica de Kripke

Sobre la base de su trabajo sobre la semántica de la lógica modal, Saul Kripke creó otra semántica para la lógica intuicionista, conocida como semántica de Kripke o semántica relacional.

Semántica similar a Tarski

Se descubrió que la semántica similar a la de Tarski para la lógica intuicionista no era posible de probar completa. Sin embargo, Robert Constable ha demostrado que una noción más débil de completitud aún se mantiene para la lógica intuicionista bajo un modelo similar al de Tarski. En esta noción de completitud no nos interesan todos los enunciados que son verdaderos de cada modelo, sino los enunciados que son verdaderos de la misma manera en cada modelo. Es decir, una sola prueba de que el modelo juzga que una fórmula es verdadera debe ser válida para todos los modelos. En este caso, no sólo hay una prueba de completitud, sino que es válida según la lógica intuicionista.

Relación con otras lógicas

La lógica intuicionista está relacionada por dualidad con una lógica paraconsistente conocida como brasileña, anti-intuicionista o lógica dual-intuicionista.

El subsistema de lógica intuicionista con el axioma FALSO eliminado se conoce como lógica mínima.

Relación con la lógica de muchos valores

El trabajo de Kurt Gödel sobre la lógica multivaluada mostró en 1932 que la lógica intuicionista no es una lógica de valores finitos. (Consulte la sección titulada Semántica del álgebra de Heyting anterior para obtener una interpretación lógica de valor infinito de la lógica intuicionista).

Relación con lógicas intermedias

Cualquier álgebra de Heyting finita que no sea equivalente a un álgebra booleana define (semánticamente) una lógica intermedia. Por otro lado, la validez de las fórmulas en la lógica intuicionista pura no está ligada a ningún álgebra de Heyting individual, sino que se relaciona con todas y cada una de las álgebras de Heyting al mismo tiempo.

Relación con la lógica modal

Cualquier fórmula de la lógica proposicional intuicionista (IPC) puede traducirse al lenguaje de la lógica modal normal S4 de la siguiente manera:

⊥ ⊥ Alternativa Alternativa =⊥ ⊥ AAlternativa Alternativa =▪ ▪ AsiAes primo (un literal positivo)()A∧ ∧ B)Alternativa Alternativa =AAlternativa Alternativa ∧ ∧ BAlternativa Alternativa ()AAlternativa Alternativa B)Alternativa Alternativa =AAlternativa Alternativa Alternativa Alternativa BAlternativa Alternativa ()A→ → B)Alternativa Alternativa =▪ ▪ ()AAlternativa Alternativa → → BAlternativa Alternativa )()¬ ¬ A)Alternativa Alternativa =▪ ▪ ()¬ ¬ ()AAlternativa Alternativa ))¬ ¬ A:=A→ → ⊥ ⊥ {displaystyle {begin{aligned}bot ↑=bot \A^{*} {f}=f} Recuadro A paciente {text{if}A{text{ is prime (a positive literal)}(Awedge B)^{*} {=A^{*}wedge B^{*}(Avee B)^{*} B^{*}(Ato B)^{*}=Boxleft(A^{*}to B^{*}derecha)(neg A)^{*} {=Box (neg (neg (A^{*})}) Condenadoneg A:=Ato bot end{aligned}}}

y se ha demostrado que la fórmula traducida es válida en la lógica modal proposicional S4 si y solo si la fórmula original es válida en IPC. El conjunto anterior de fórmulas se denomina traducción de Gödel-McKinsey-Tarski.

También hay una versión intuitiva de la lógica modal S4 llamada Lógica modal constructiva CS4.

Cálculo lambda

Existe un isomorfismo de Curry-Howard extendido entre el IPC y el cálculo lambda de tipo simple.