Lógica intermedia

La lógica proposicional 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 lo 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 ambas a L , entonces G también pertenece a L (clausura 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 (clausura bajo sustitución).

Una lógica de este tipo 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 ellas exhiben la propiedad de disyunción (PD). Las lógicas superintuicionistas o intermedias forman una red completa 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 parte superior. La lógica clásica es la única capa en la red de lógicas superintuicionistas; la red de lógicas intermedias también tiene una capa única, a saber, SmL ^{[ cita requerida ]} .

Las herramientas para estudiar las lógicas intermedias son similares a las que se utilizan 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 . Las lógicas intermedias específicas pueden darse mediante una descripción semántica.

Otros a menudo se dan añadiendo uno o más axiomas a

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

Algunos ejemplos incluyen:

• 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)

Variantes generalizadas de lo anterior (pero en realidad principios equivalentes a 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 a través del principio de explosión )

• Lógica de Smetanich ( LSM ):

= 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 Gently, 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 ) (4ª 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 orden. Por ejemplo, se sabe que LC no prueba todos los teoremas de SmL , pero no se compara directamente en fuerza con BD ₂ . Del mismo modo, por ejemplo, KP no se compara con SL . La lista de igualdades para cada lógica tampoco es de ninguna manera exhaustiva. Por ejemplo, como con WPEM y la ley de De Morgan, se pueden expresar varias formas de DGP utilizando conjunción.

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

También puede ser interesante señalar que, si se da por sentada toda la lógica intuicionista, las igualdades dependen en gran medida de la explosión. Por ejemplo, en el caso de la lógica mínima , como principio, el PEM ya es equivalente a Consequentia mirabilis, pero no implica la DNE más fuerte, ni el PP, y no es comparable con el 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 n -valuadas 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ógica de ancho superior acotado ( 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 ancho acotado, 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 (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ógica 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 cima"), no conocidos por ser recursivamente axiomatizables ${\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 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. Nótese que si una teoría consistente valida WPEM pero aún tiene enunciados independientes al suponer PEM, entonces no puede tener DP.

Semántica

Dada una álgebra de Heyting H , el conjunto de fórmulas proposicionales válidas en H es una lógica intermedia. A la inversa, dada una lógica intermedia es posible construir su álgebra de Lindenbaum–Tarski , que es entonces 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 valuació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 denomina modelo canónico ). Puede que no exista un marco de Kripke con esta propiedad, pero siempre existe un marco general . ${\displaystyle \{x\mid M,x\Vdash p\}}$

Relación con las lógicas modales

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 un compañero 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 .

Véase también

• Lista de sistemas lógicos

Notas

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

Referencias

• Chagrov, Alexander; Zakharyaschev, Michael (1997). Lógica modal . Oxford: Clarendon Press . pág. 605. ISBN. 9780198537793.

• 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) de 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". Notre Dame Journal of Formal Logic . 47 (1): 73–82. doi :10.1305/ndjfl/1143468312.

• Umezawa, Toshio (junio de 1959). "Sobre lógicas intermedias entre la lógica intuicionista y la lógica de predicados clásica". Journal of Symbolic Logic . 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]