Lógica intermedia

Lógica proposicional que extiende la lógica intuicionista

En lógica matemática , una lógica superintuicionista es una lógica proposicional que extiende la lógica intuicionista . La lógica clásica es la lógica superintuicionista consistente más fuerte; por tanto, las lógicas superintuicionistas consistentes se denominan lógicas intermedias (las lógicas son intermedias entre la lógica intuicionista y la lógica clásica). ^[1]

Definición

Una lógica superintuicionista es un conjunto L de fórmulas proposicionales en un conjunto contable de variables p _i que satisfacen las siguientes propiedades:

1. todos los axiomas de la lógica intuicionista pertenecen a L ;

2. si F y G son fórmulas tales que F y F → G pertenecen a L , entonces G también pertenece a L (cierre bajo modus ponens );

3. si F ( p ₁ , p ₂ , ..., p _n ) es una fórmula de L y G ₁ , G ₂ , ..., G _n son fórmulas cualesquiera, entonces F ( G ₁ , G ₂ , ..., G _n ) pertenece a L (cierre bajo sustitución).

Semejante lógica es intermedia si, además,

4. L no es el conjunto de todas las fórmulas.

Propiedades y ejemplos

Existe un continuo de diferentes lógicas intermedias y muchas de esas lógicas exhiben la propiedad de disyunción (DP). Las lógicas superintuicionistas o intermedias forman un entramado completo con la lógica intuicionista como base y la lógica inconsistente (en el caso de las lógicas superintuicionistas) o la lógica clásica (en el caso de las lógicas intermedias) como cima. La lógica clásica es la única capa en el entramado de las lógicas superintuicionistas; La red de lógicas intermedias también tiene un coatom único, a saber, SmL ^{[ cita requerida ]} .

Las herramientas para estudiar la lógica intermedia son similares a las utilizadas para la lógica intuicionista, como la semántica de Kripke . Por ejemplo, la lógica de Gödel-Dummett tiene una caracterización semántica simple en términos de órdenes totales . Se pueden dar lógicas intermedias específicas mediante una descripción semántica.

Otros suelen obtenerse añadiendo uno o más axiomas a

• Lógica intuicionista (normalmente denominada cálculo proposicional intuicionista IPC , pero también Int , IL o H )

Ejemplos incluyen:

• Lógica clásica ( CPC , Cl , CL ):

= IPC + ¬¬ p → p (Eliminación por doble negación, DNE)

= IPC + (¬ p → p ) → p ( Consequentia mirabilis )

= IPC + p ∨ ¬ p ( Principio del tercero excluido , PEM)

Las variantes generalizadas de lo anterior (pero en realidad principios equivalentes sobre la lógica intuicionista) son, respectivamente,

= IPC + (¬ p → ¬ q ) → ( q → p ) ( principio de contraposición inversa )

= IPC + (( p → q ) → p ) → p ( principio de Pierce PP, comparar con Consequentia mirabilis)

= IPC + ( q → p ) → ((¬ q → p ) → p ) (otro esquema que generaliza Consequentia mirabilis)

= IPC + p ∨ ( p → q ) (siguiendo de PEM vía principio de explosión )

• Lógica de Smetanich ( SmL ):

= IPC + (¬ q → p ) → ((( p → q ) → p ) → p ) (un PP condicional)

• Lógica de Gödel-Dummett ( Dummett 1959) ( LC o G , ver extensiones a continuación):

= IPC + ( p → q ) ∨ ( q → p ) (Principio de Dirk Gfully, DGP o linealidad)

= IPC + ( p → ( q ∨ r )) → (( p → q ) ∨ ( p → r )) (una forma de independencia de la premisa IP)

= IPC + (( p ∧ q ) → r ) → (( p → r ) ∨ ( q → r )) (Cuarta ley de De Morgan generalizada )

• Profundidad acotada 2 ( BD ₂ , ver generalizaciones a continuación. Comparar con p ∨ ( p → q )):

= IPC + p ∨ ( p → ( q ∨ ¬ q ))

• Lógica de Jankov (1968) ^[2] o lógica de De Morgan ( KC ):

= IPC + ¬¬ p ∨ ¬ p (PEM débil, también conocido como WPEM)

= IPC + ( p → q ) ∨ (¬ p → ¬ q ) (un DGP débil)

= IPC + ( p → ( q ∨ ¬ r )) → (( p → q ) ∨ ( p → ¬ r )) (una variante, con negación, de una forma de IP)

= IPC + ¬( p ∧ q ) → (¬ q ∨ ¬ p ) (cuarta ley de De Morgan )

• Lógica de Scott ( SL ):

= IPC + ((¬¬ p → p ) → ( p ∨ ¬ p )) → (¬¬ p ∨ ¬ p ) (un WPEM condicional)

• Lógica de Kreisel - Putnam ( KP ):

= IPC + (¬ p → ( q ∨ r )) → ((¬ p → q ) ∨ (¬ p → r )) (la otra variante, con negación, de una forma de IP)

Esta lista no es, en su mayor parte, ningún tipo de ordenamiento. Por ejemplo, se sabe que LC no prueba todos los teoremas de SmL , pero no se compara directamente en fuerza con BD ₂ . Asimismo, por ejemplo, KP no se compara con SL . La lista de igualdades para cada lógica tampoco es exhaustiva. Por ejemplo, al igual que ocurre con WPEM y la ley de De Morgan, se pueden expresar varias formas de DGP utilizando conjunción.

Incluso (¬¬ p ∨ ¬ p ) ∨ (¬¬ p → p ), un mayor debilitamiento de WPEM, no es un teorema de IPC .

También puede valer la pena señalar que, dando por sentada toda la lógica intuicionista, las igualdades dependen notablemente de la explosión. Por ejemplo, según la lógica mínima , el principio PEM ya es equivalente a Consequentia mirabilis, pero no implica ni la DNE ni el PP más fuertes, y no es comparable a la DGP.

Continuando:

• lógicas de profundidad acotada ( BD _n ):

IPC + p _n ∨ ( p _n → ( p _{n −1} ∨ ( p _{n −1} → ... → ( p ₂ ∨ ( p ₂ → ( p ₁ ∨ ¬ p ₁ )))...)))

• Lógicas valoradas en n de Gödel ( G _n ):

LC + BD _{n −1}

= LC + BC _{n −1}

• lógicas de cardinalidad acotada ( BC _n ):

${\displaystyle \textstyle \mathbf {IPC} +\bigvee _{i=0}^{n}{\bigl (}\bigwedge _{j<i}p_{j}\to p_{i}{\bigr )}}$

• lógicas de ancho superior acotado ( Por cierto _n ):

${\displaystyle \textstyle \mathbf {IPC} +\bigvee _{i=0}^{n}{\bigl (}\bigwedge _{j<i}p_{j}\to \neg \neg p_{i}{\bigr )}}$

• Lógicas de ancho acotado, también conocida como lógica de anti-cadenas acotadas, Ono (1972) ( BW _n , BA _n ):

${\displaystyle \textstyle \mathbf {IPC} +\bigvee _{i=0}^{n}{\bigl (}\bigwedge _{j\neq i}p_{j}\to p_{i}{\bigr )}}$

• lógicas de ramificación acotada, Gabbay y de Jongh (1969, 1974) ( T _n , BB _n ):

${\displaystyle \textstyle \mathbf {IPC} +\bigwedge _{i=0}^{n}{\bigl (}{\bigl (}p_{i}\to \bigvee _{j\neq i}p_{j}{\bigr )}\to \bigvee _{j\neq i}p_{j}{\bigr )}\to \bigvee _{i=0}^{n}p_{i}}$

Además:

• Lógicas de realizabilidad
• Lógica de problemas finitos de Medvedev ( LM , ML ): ^{[3] [4] [5]} definida semánticamente como la lógica de todos los marcos de la forma para conjuntos finitos X ("hipercubos booleanos sin parte superior"), no se sabe que sea recursivamente axiomatizable ${\displaystyle \langle {\mathcal {P}}(X)\setminus \{X\},\subseteq \rangle }$
• ...

Las lógicas proposicionales SL y KP tienen la propiedad de disyunción DP. La lógica de la realizabilidad de Kleene y la lógica fuerte de Medvedev también la tienen. No existe una lógica máxima única con DP en la red. Tenga en cuenta que si una teoría consistente valida WPEM pero aún tiene declaraciones independientes al asumir PEM, entonces no puede tener DP.

Semántica

Dada un álgebra de Heyting H , el conjunto de fórmulas proposicionales que son válidas en H es una lógica intermedia. Por el contrario, dada una lógica intermedia es posible construir su álgebra de Lindenbaum-Tarski , que entonces es un álgebra de Heyting.

Un marco de Kripke intuicionista F es un conjunto parcialmente ordenado , y un modelo de Kripke M es un marco de Kripke con una valoración tal que es un subconjunto superior de F. El conjunto de fórmulas proposicionales que son válidas en F es una lógica intermedia. Dada una lógica intermedia L es posible construir un modelo de Kripke M tal que la lógica de M sea L (esta construcción se llama modelo canónico ). Puede que no exista un marco Kripke con esta propiedad, pero siempre existe un marco general . ${\displaystyle \{x\mid M,x\Vdash p\}}$

Relación con la lógica modal

Sea A una fórmula proposicional. La traducción de Gödel- Tarski de A se define recursivamente de la siguiente manera:

• ${\displaystyle T(p_{n})=\Box p_{n}}$
• ${\displaystyle T(\neg A)=\Box \neg T(A)}$
• ${\displaystyle T(A\land B)=T(A)\land T(B)}$
• ${\displaystyle T(A\vee B)=T(A)\vee T(B)}$
• ${\displaystyle T(A\to B)=\Box (T(A)\to T(B))}$

Si M es una lógica modal que extiende S4 entonces ρ M = { A | T ( A ) ∈ M } es una lógica superintuicionista, y M se llama compañero modal de ρ M . En particular:

• IPC = ρS4
• KC = ρ S4.2
• CL = ρ S4.3
• CPC = ρ S5

Para cada lógica intermedia L hay muchas lógicas modales M tales que L  = ρ M .

Ver también

• Lista de sistemas lógicos

Notas

1. "Lógica intermedia", Enciclopedia de Matemáticas , EMS Press , 2001 [1994].
2. Terwijn 2006.
3. Medvédev 1962.
4. Medvédev 1963.
5. Medvédev 1966.

Referencias

• Chagrov, Alejandro; Zakharyaschev, Michael (1997). Lógica modal . Oxford: Prensa de Clarendon . pag. 605.ISBN​ 9780198537793.

• Medvédev, Yu T. (1962). "[Problemas finitos]" (PDF) . Matemáticas soviéticas (en ruso). 3 (1): 227–230. doi :10.2307/2272084. JSTOR  2272084. Traducción al inglés de XXXVIII 356(20) de Elliott Mendelson.
• Medvédev, Yu T. (1963). "[Interpretación de fórmulas lógicas mediante problemas finitos y su relación con la teoría de la legibilidad]" (PDF) . Matemáticas soviéticas (en ruso). 4 (1): 180–183. doi :10.2307/2272084. JSTOR  2272084. Traducción al inglés de XXXVIII 356(21) por Sue Ann Walker.
• Medvédev, Yu T. (1966). «[Interpretación de fórmulas lógicas mediante problemas finitos]» (PDF) . Matemáticas soviéticas (en ruso). 7 (4): 857–860. doi :10.2307/2272084. JSTOR  2272084. Traducción al inglés de XXXVIII 356(22) por Sue Ann Walker

• Terwijn, Sebastiaan A. (2006). "Lógica constructiva y el entramado de Medvedev". Revista de lógica formal de Notre Dame . 47 (1): 73–82. doi :10.1305/ndjfl/1143468312.

• Umezawa, Toshio (junio de 1959). "Sobre lógicas intermedias entre la lógica de predicados intuicionista y clásica". Revista de Lógica Simbólica . 24 (2): 141-153. doi :10.2307/2964756. JSTOR  2964756. S2CID  13357205.

enlaces externos

• "Lógica intermedia", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]