Lógica intermedia

En lógica matemática , una lógica superintuicionista es una lógica proposicional que extiende la lógica intuicionista . Una lógica es un conjunto de fórmulas proposicionales con ciertas propiedades de cierre. Las lógicas están parcialmente ordenadas bajo el principio de contención. Una lógica es más fuerte que otra si y solo si la contiene .

La lógica clásica es la lógica superintuicionista consistente más fuerte . Por lo tanto, las lógicas superintuicionistas consistentes se denominan lógicas intermedias , porque se encuentran en un punto intermedio en cuanto al número de fórmulas que contienen entre la lógica intuicionista y la lógica clásica. ^{[ 1 ]}

Una lógica superintuicionista es un conjunto L de fórmulas proposicionales en un conjunto numerable 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 ambas 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).

Tal lógica es intermedia si además

4. L no es el conjunto de todas las fórmulas (es decir, la lógica inconsistente).

Existe un continuo de diferentes lógicas intermedias.

Existe un continuo de diferentes lógicas intermedias con la propiedad de disyunción (PD).

Las lógicas intermedias forman un retículo completo , con la lógica intuicionista en la base y la lógica clásica en la cima. Posee un único coatoma llamado SmL . De manera similar, las lógicas superintuicionistas forman un retículo completo, con la lógica intuicionista en la base y la lógica inconsistente en la cima. La lógica clásica es el único coatoma.

Muchas lógicas intermedias se obtienen añadiendo uno o más axiomas a la lógica intuicionista (generalmente denominada cálculo proposicional intuicionista IPC , pero también Int , IL o H ). Algunos ejemplos son:

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

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

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

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

Las variantes generalizadas inmediatas 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 Peirce PP, comparar con Consequentia mirabilis)

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

= IPC + p ∨ ( p → q ) (siguiendo de PEM a través del principio de explosión )

= IPC + ( q → p ) → ( p ∨ ¬ q ) (otra variante de PEM, ver implicación material )

• La 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 más abajo):

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

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

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

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

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

• La lógica de Jankov (1968) ^{[ 2 ]} o la 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 )

= IPC + ¬¬( p ∨ q ) → (¬¬ p ∨ ¬¬ q ) (una forma de desplazamiento de doble negación)

• La 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, en su mayor parte, no sigue ningún orden. Por ejemplo, se sabe que LC no demuestra todos los teoremas de SmL , pero no se compara directamente en fuerza con BD _2. Del mismo modo, p. ej., KP no se compara con SL . La lista de igualdades para cada lógica tampoco es exhaustiva. Por ejemplo, como con WPEM y la ley de De Morgan, se pueden expresar varias formas de DGP usando conjunciones.

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

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

Continuando:

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

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

• Lógicas n -valuadas de Gödel ( G _n ):

LC + BD _{n −1}

= LC + BC _{n −1}

• lógicas de cardinalidad limitada ( 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 limitado ( BTW _n ):

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

• lógicas de anchura acotada, también conocidas como lógica de anticadenas 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, 1974 ^{[ 3 ]} ) ( 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
• La lógica de problemas finitos de Medvedev ( LM , ML ): ^{[ 4 ] [ 5 ] [ 6 ]} definida semánticamente como la lógica de todos los marcos de la forma${\displaystyle \langle {\mathcal {P}}(X)\setminus \{X\},\subseteq \rangle }$para conjuntos finitos X ("hipercubos booleanos sin cima"), que no se sabe que sean recursivamente axiomatizables
• ...

Las lógicas proposicionales SL y KP poseen la propiedad de disyunción DP. La lógica de realizabilidad de Kleene y la lógica fuerte de Medvedev también la poseen. No existe una única lógica maximal con DP en el retículo. Cabe destacar que si una teoría consistente valida WPEM pero aún presenta enunciados independientes al asumir PEM, entonces no puede tener DP.

La semántica de Kripke se utiliza para estudiar semánticamente la lógica intuicionista. De manera similar, otras lógicas intermedias pueden estudiarse mediante modelos semánticos. Por ejemplo, la lógica de Gödel-Dummett tiene una caracterización semántica simple en términos de órdenes totales .

Dada una álgebra de Heyting H , el conjunto de fórmulas proposicionales válidas en H constituye una lógica intermedia. Recíprocamente, dada una lógica intermedia, es posible construir su álgebra de Lindenbaum-Tarski , que a su vez 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 valuación tal que${\displaystyle \{x\mid M,x\Vdash p\}}$es un subconjunto superior de F. El conjunto de fórmulas proposicionales 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 denomina modelo canónico ). Puede que no exista un marco de Kripke con esta propiedad, pero siempre existe un marco general .

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 denomina compañera modal de ρ M. En particular:

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

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

• Lista de sistemas lógicos

• Chagrov, Alexander; Zakharyaschev, Michael (1997). Lógica modal . Oxford: Clarendon Press . pág.  605. ISBN 9780198537793.
• Dragalin, Albert (1988). Intuicionismo matemático: Introducción a la teoría de la demostración . Providence, RI: American Mathematical Society . p.  228. ISBN 0-8218-4520-9.

• Medvedev, 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) por Elliott Mendelson. 
• Medvedev, 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 . 
• Medvedev, 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 la clásica". Journal of Symbolic Logic . 24 (2): 141– 153. doi : 10.2307/2964756 . JSTOR 2964756. S2CID 13357205 .  
• Gabbay, DM; De Jongh, DHJ (1974). "Una secuencia de lógicas intermedias finitamente axiomatizables decidibles con la propiedad de disyunción" . Journal of Symbolic Logic . 39 (1): 67‒78. doi : 10.2307/2272344 . JSTOR 2272344 . 

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