18 votos

La mínima diferencia entre lo clásico y intuitionistic sequent cálculo

Considere la posibilidad de lógica proposicional primitiva conectivas $\{{\to},{\land},{\lor},{\bot}\}$. Vemos a $\neg \varphi$ como una abreviatura de $\varphi\to\bot$ $\varphi\leftrightarrow\psi$ como una abreviatura de $(\varphi\to\psi)\land(\psi\to\varphi)$, etc.

La clásica sequent cálculo LC tiene sus reglas, tales como

$$\frac{\Gamma \varphi\vdash \Pi \qquad \Sigma \psi\vdash \Pi} {\Gamma \Sigma \varphi\lor\psi \vdash \Pi}{\lor L} \qquad \frac{\Gamma\vdash\varphi,\Delta}{\Gamma\vdash\varphi\lor\psi\Delta}{\lor}R_1 \qquad \frac{\Gamma \vdash \psi \Delta}{\Gamma\vdash\varphi\lor\psi\Delta}{\lor}R_2 $$ $$ \frac{\Gamma\vdash\varphi,\Delta \qquad \Sigma\psi\vdash\Pi} {\Gamma \Sigma \varphi\a\psi \vdash \Delta\Pi} {\,} L \qquad \frac{\Gamma\varphi\vdash \psi\Delta}{\Gamma\vdash\varphi\a\psi\Delta} {\,} R $$ y así sucesivamente, donde $\Gamma$, $\Sigma$, $\Pi$, y $\Delta$ son finitos multisets de fórmulas.

Es bien sabido que si restringimos la forma de todos los sequents a tener exactamente una fórmula a la derecha de la $\vdash$, obtenemos un sistema a prueba de LJ para intuitionistic lógica proposicional. Esto corresponde a la necesidad de que todos los $\Delta$ está vacía y cada una de las $\Pi$ es un singleton en las formulaciones de las normas anteriores.

¿Todavía podemos obtener intuitionistic lógica si la única regla que tenemos que hacer que este cambio es ${\to}R$? En otras palabras, tenemos $$\frac{\Gamma,\varphi\vdash\psi}{\Gamma\vdash\varphi\to\psi}{\to}R'$$ junto con todas las otras reglas en su clásica formulación, incluyendo estructurales reglas con mucho $\Delta$s y $\Pi$s.


(Motivación: estoy tratando, una vez más, para envolver mi cabeza alrededor de lo que la esencial diferencia entre intuitionistic y la lógica clásica. Se dice a menudo que intuitionistic lógica surgió de Brouwer las más estrictas exigencias acerca de cómo una disyunción puede ser demostrado, pero que no puede ser toda la historia porque hay una diferencia, incluso para el implicational fragmento (sin diferencias). Ahora me pregunto si la disyunción es en realidad parte de la historia. La semántica de Kripke trata completamente clásico, y intuitionistic lógica se convierte en totalmente clásica si añadimos Peirce ley como un axioma (que de nuevo no hace mención de la disyunción). La anterior conjetura está inspirada en la de Curry-Howard isomorfismo donde Peirce ley asigna a call/cc, más o menos. Por lo tanto, tendría sentido que podemos obtener intuitionistic la lógica simplemente prohibiendo lambda abstracciones a partir de la captura de la continuación de variables).

12voto

Esto suena una campana. Y ah, sí, en la p. 48 de Sara Negri y Jan van de Platón admirable libro Estructurales Prueba de la Teoría (de la COPA, 2001), que escriben

No es la [general] de la característica de tener un conjunto múltiple como una succedent que lleva para la lógica clásica, pero la restricción $R\!\supset$ regla,

donde por el irrestricto $R\!\supset$ que significan sus clásicos $\to\! R$ regla, y la restricción de la regla sería su $\to\! R'$ regla.

A continuación, en la p. 108, de introducir un intuitionistic multisuccedent cálculo que ellos llaman G3im, que es exactamente igual a la de un clásico multisuccedent cálculo excepto para el $\supset$ reglas (aunque los dos a la izquierda y a la derecha las reglas de obtener manipulado). Supongo que el debate que siguió, y en 1988 el libro por Dragalin Matemática Intuitionism a que el cálculo es debido, parecería ser buenos puntos de partida para investigaciones posteriores (y me interesaría saber más acerca de cómo van las cosas!).

7voto

sewo Puntos 58

Peter Smith encontró una buena referencia de lo que más o menos resuelve la cuestión. Aquí están algunas observaciones finales que no encaje como comentario:

Sabiendo que es verdad que me dio el coraje para tratar de la prueba, que resultó ser más fácil de lo esperado. De hecho, cada una de las reglas clásicas , excepto ${\to}R$ (pero incluyendo los ${\to}L$) es derivable en el único succedent cálculo (con Corte) si $\Gamma\vdash\varphi,\psi,\ldots,\sigma$ es llevado a abreviar $\Gamma\vdash \varphi\lor\psi\lor\cdots\lor\sigma$. Esta comprobación resulta ser completamente de la rutina.

Esto apoya mi hipótesis de que la diferencia esencial entre lo clásico y intuitionistic es que el intuitionistic $\varphi\to\psi$ es un fuerte reclamo en el sentido de ser más difícil de probar (pero no más fácil a la conclusión de algo). Desde $\neg$ abrevia una implicación, esto también hace que las negaciones más difícil de probar en la intuitionistic lógica.

Lo que impide la libre ${\to}R$ desde que se deriva es que la derivada de la misma manera como los otros requieren razonamiento de$\varphi\to(\psi\lor \sigma)$$(\varphi\to\psi)\lor\sigma$, que no es intuitionistically posible.

En el caso particular $\psi=\bot$, lo que dice es que no podemos razón de $\varphi\to(\bot\lor\sigma)$ (lo cual es, obviamente, equivalente a $\varphi\to\sigma$)$\neg\varphi\lor \sigma$. Esto puede parecerse a $\lor$ es más difícil de probar en intuitionistic lógica, pero es realmente el $\neg$ que hace $\neg\varphi\lor\sigma$ más para concluir.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X