8 votos

Propiedades de la comprensión y las críticas de un cálculo sequent (específico)

En Ebbinghaus et al., La Lógica matemática, un secuente de cálculo con las siguientes reglas se utiliza:

(Ant) $\begin{array}{ll} \Gamma & \varphi \\ \hline \Gamma' & \varphi\end{array}$, if $\Gamma \subseteq \Gamma'$ $\qquad$ (Assm) $\begin{array}{ll} \\ \hline \Gamma & \varphi\end{array}$ si $\varphi \in \Gamma$

(PC) $\begin{array}{lll} \Gamma & \psi & \varphi \\ \Gamma & \lnot \psi & \varphi \\ \hline \Gamma & & \varphi\end{array}$ $\qquad\qquad$ (Ctr) $\begin{array}{lll} \Gamma & \lnot\varphi & \psi \\ \Gamma & \lnot \varphi & \lnot \psi \\ \hline \Gamma & & \varphi\end{array}$

($\lor A$) $\begin{array}{lll} \Gamma & \varphi & \chi \\ \Gamma & \psi & \chi\\ \hline \Gamma & (\varphi\lor\psi) & \chi\end{array}$ $\qquad$ ($\lor S$) $\begin{array}{ll} \Gamma & \varphi \\ \hline \Gamma & (\varphi\lor\psi)\end{matriz}$, $\begin{array}{ll} \Gamma & \varphi \\ \hline \Gamma & (\psi\lor\varphi)\end{array}$

($\exists A$) $\begin{array}{lll} \Gamma & \varphi\frac{y}{x} & \psi \\ \hline \Gamma & \exists x\varphi & \psi\end{array}$, if $s$ is not free in $\Gamma \; \exists x\varphi \; \psi$

($\exists S$) $\begin{array}{ll} \Gamma & \varphi\frac{t}{x} \\ \hline \Gamma & \exists x\varphi\end{array}$

($\equiv$) $\begin{array}{l} \\ \hline t \equiv t\end{array}$ $\qquad\qquad$ (Sub) $\begin{array}{lll} \Gamma & & \varphi\frac{t}{x} \\ \hline \Gamma & t \equiv t' & \varphi\frac{t'}{x}\end{array}$

Parece que este cálculo sólo consiste en la deducción de reglas, sin ningún tipo de esquemas de axioma. Es esto correcto? O debemos interpretar (Assm) y ($\equiv$) como axioma esquemas, debido a que deducir algo de la nada? Lo que sobre (Ant) y (Sub), cuando la conclusión no está determinada únicamente por las premisas, porque pueden contener fórmulas arbitrarias o términos?

[Pregunta extra: La de Hilbert del sistema sólo tiene dos deducción de reglas, pero muchos de los axiomas y esquemas de axioma. Con la de Hilbert del sistema, a menudo me he tenido que buscar "pruebas" en algún lugar, porque no he podido encontrar por mí mismo. Con el secuente cálculo, me parecen ser capaces de encontrar las pruebas mí mismo. Hay un matemático explicación para este fenómeno?]

En su revisión del citado libro, Peter Smith critica fuertemente el elegido de sistema de deducción:

Ch. 4 se llama " Un Secuente de Tornasol. La versión elegida es realmente, realmente, no es muy agradable. Para empezar (aunque a un menor punto de que sólo afecta a la legibilidad), en lugar de escribir un secuente como $\text{‘}\Gamma \vdash \varphi\text{'}$ o $\text{‘}\Gamma \Rightarrow \varphi\text{'}$, o incluso el $\text{‘}\Gamma : \varphi\text{'}$, EFT sólo tienes que escribir un unpunctuated $\text{‘}\Gamma \; \varphi\text{'}$. Mucho más serio, que la adopción de un sistema de reglas que muchos dirían que se mezcla estructurales de las reglas clásicas y las reglas lógicas para las conectivas sin principios camino (perdiendo sólo la información que es un secuente sistema puede ser utilizado para resaltar). [Para ser más específicos, se introduce un clásico 'de Prueba por Casos de' regla que nos lleva desde el sequents (en su notación) $\Gamma \; \psi \; \varphi$$\Gamma \; \lnot \psi \; \varphi$$\Gamma \; \varphi$, y luego apelar a la Prueba por Casos a la Corte como un derivado de la regla. Esto realmente se enturbia las aguas de varias maneras!]

La cosa más cercana a la (Corte) que se deriva como consecuencia de las reglas en el libro de la Regla de la Cadena:

(Ch) $\begin{array}{lll} \Gamma & & \varphi \\ \Gamma & \varphi & \psi \\ \hline \Gamma & & \psi \end{array}$ $\quad$ while (Cut) would be $\begin{array}{lcr} \Gamma & \vdash & \Delta \; \varphi \\ \varphi \; \Lambda & \vdash & \psi \\ \hline \Gamma \; \Lambda & \vdash & \Delta \; \psi \end{matriz}$ or $\begin{array}{lll} \Gamma & & \varphi \\ \varphi & \Lambda & \psi \\ \hline \Gamma & \Lambda & \psi \end{array}$

No veo cómo (Ch) o (Cut) podría reemplazar (PC). No estoy seguro de si esto está relacionado con el hecho de que el anterior cálculo interpreta un secuente $\phi \; \varphi \; \psi \; \chi$$\phi \rightarrow (\varphi \rightarrow (\psi \rightarrow \chi))$, de modo que cada sequent debe tener exactamente una succedent, y el $\vdash$ signo puede ser omitido. Es posible añadir (Cut) como regla general, quitar una de las otras reglas, y posiblemente ajustar el resto de reglas ligeramente, y obtener el mismo cálculo (donde el original sin modificar las reglas puede ser obtenida tal y como se deriva de las reglas)?

7voto

sewo Puntos 58

Sí, (Assm) y ($\equiv$) son los axiomas -- formalmente un axioma no es ni más ni menos que una regla de inferencia que no requiere de instalaciones.

No es un problema particular de que el nombre de una regla de inferencia tiene instancias que concluye diferentes cosas de idénticas premisas, excepto notationally: por supuesto que significa que no se puede reconstruir una prueba de secuencia de saber que los axiomas son usadas y que se denomina reglas que se utilizan con el que los locales en cada línea. Pero eso no es una peculiaridad de este cálculo; "estructurales" reglas tales como (Ant) la tarifa estándar en muchos de los sistemas de prueba.


El (Cad) de la regla es moralmente equivalente a su formulación de (Cut). Si usted tiene $\Gamma\varphi$$\varphi\Lambda\psi$, entonces se puede concluir $\Gamma\Lambda\varphi$ $\Gamma\Lambda\varphi\psi$ a partir de ellos mediante la aplicación de Hormiga para cada uno de ellos. Entonces (Ch) concluye $\Gamma\Lambda\psi$.

Que no se parece a la de la cita de Peter Smith afirma que Corte podría reemplazar la (PC) de la regla. Incluso en la adecuada secuente del cálculo, de la Corte no sustituye a nada, gracias a la eliminación de corte teorema no es ni siquiera necesario.

Sin embargo, en Ebbinghaus' del sistema, tanto de (PC) y (Ctr) son "cortados" en que sus premisas contiene una fórmula $\psi$ que desaparece por completo en la conclusión. Por lo general en el secuente cálculos, la talla es la única regla donde una premisa que puede contener una fórmula que tiene una estructura más compleja que cualquier fórmula en la conclusión. Y, como se señaló anteriormente, la Corte no es ni siquiera necesario.

Aquí, en el otro lado, (PC) y (Ctr) son necesarios-si los eliminamos, se pierde completamente la capacidad de razonar acerca de la negación, y con ella la capacidad de razonar acerca de implicación (que supongo que es para ser tratada como una abreviatura para $\neg p\lor q$).

Y es que realmente la mayoría de las naciones unidas-sequentlike a la falta ($\neg$) y ($\neg$S) de las reglas. En su lugar, el (Ctr) de la regla es perverso lo suficiente como para añadir más conectivas a la fórmula de la conclusión, cuando la construcción de sus instalaciones.


Más tarde edit: Aquí es un conjunto de naturales secuente-como ($\neg$) y ($\neg$S) de las reglas de la sintaxis de Ebbinghaus:

$$(\neg a) \frac{\Gamma\quad \varphi}{\Gamma\quad\neg\varphi\quad\psi} \qquad (\neg S) \frac{\Gamma\quad \varphi\quad \mathcal Un}{\Gamma\quad\neg\varphi} \text{ donde }\mathcal Un\text{ es una variable proposicional no es libre en }\Gamma \varphi $$

Sin embargo, estas reglas no son suficientes para hacer de $\neg p\lor q$ trabajo así como una representación de $p\to q$ - la costumbre de la eliminación de la regla de $\to$ pasa a través de la fina, pero $\to$ no puede ser introducido sensefully si está construido sobre una disyunción que funciona intuitionistically. La adición de uno de (PC) o (Ctr) de nuevo en probablemente guarde eso, sin embargo.

1voto

Mauro ALLEGRANZA Puntos 34146

Creo que, a pesar de los "consejos" que :

el anterior cálculo interpreta un secuente $\phi \; \varphi \; \psi \; \chi$$\phi \rightarrow (\varphi \rightarrow (\psi \rightarrow \chi))$, de modo que cada sequent debe tener exactamente una succedent, y el $\vdash$ signo puede ser omitido

hay una forma más "natural" para leer las reglas anteriores.

Considere la definición od sequent [página 59] :

Si llamamos a una lista no vacía (secuencia) de las fórmulas de un secuente, entonces podemos usar sequents para describir las etapas de una prueba. Por ejemplo, la etapa con suposiciones $\varphi_0, ... \varphi_{n-1}$ y reclamar $\varphi$ es representado por el secuente $\varphi_0, ... \varphi_{n-1} \varphi$.

Por lo tanto, se puede "restaurar" la $\vdash$ signo con el fin de volver a una forma más "natural" conjunto de reglas.

Por supuesto, (Ant) es un Debilitamiento de la regla y (Assm) es el Supuesto de la regla.

Sobre la parte más "complicada" reglas", de la "intención de la lectura" es :

($\lor A$) $\begin{array}{lll} \Gamma , \varphi \vdash \chi \\ \Gamma , \psi \vdash \chi\\ \hline \Gamma , (\varphi\lor\psi) \vdash \chi\end{array}$ $\qquad$ ($\lor S$) $\begin{array}{ll} \Gamma \vdash \varphi \\ \hline \Gamma \vdash (\varphi\lor\psi)\end{matriz}$, $\begin{array}{ll} \Gamma \vdash \varphi \\ \hline \Gamma \vdash (\psi\lor\varphi)\end{array}$

($\exists A$) $\begin{array}{lll} \Gamma , \varphi\frac{y}{x} \vdash \psi \\ \hline \Gamma , \exists x\varphi \vdash \psi\end{array}$, if $s$ is not free in $\Gamma , \; \exists x\varphi \; \psi$

($\exists S$) $\begin{array}{ll} \Gamma \vdash \varphi\frac{t}{x} \\ \hline \Gamma \vdash \exists x\varphi\end{array}$

y así sucesivamente ...

De esta manera, también la Regla de la Cadena parece menos terrible :

(Ch) $\begin{array}{lll} \Gamma \vdash \varphi \\ \Gamma , \varphi \vdash \psi \\ \hline \Gamma \vdash \psi \end{array}$ $\quad$

y que es "muy similar" a la habitual (Cut).

Como lo dijo Henning, el $\rightarrow$ conectivo se define a través de $\lnot p \lor q$ [vea la página 34], y por lo tanto el modus ponens es un derivado de la regla [página 63], utilizando (Ch) :

$\begin{array}{lll} \Gamma \vdash \lnot \varphi \lor \psi \\ \Gamma \vdash \varphi \\ \hline \Gamma \vdash \psi \end{array}$

Por supuesto, de esta manera, la clásica "semántica" está "incrustado" en el sistema.

Finalmente, la elección del nombre para la $\lnot$-reglas es muy objetable; mientras que la Contradicción de la Regla (Ctr) es claramente (RAA), en presencia de ($\lor$A), que es una prueba por casos de la regla, la Prueba por Casos de la Regla (PC) sería mejor llamarlo (siguiente Tennant) Dilema.

En conclusión, todas estas innovaciones fue la pena ?

0voto

Mauro ALLEGRANZA Puntos 34146

Ahora creo que la "inspiración" para Ebbinghaus et al.'s cálculo deductivo es Tait cálculo [1].

Ver

  • Helmut Schwichtenberg, Prueba de la Teoría : Algunas Aplicaciones de Corte de Eliminación, en Jon Barwise (editor), Manual de la lógica matemática (1999), página 867-en

y

[Este cálculo "incrustar" la lógica clásica a través de] la de Morgan leyes ($¬(A∧B)↔ ¬A∨¬B,¬∀xA ↔ ∃x¬A$, etc.) y estos permiten que cualquier fórmula para ser llevado a la negación forma normal, es decir, construido a partir de átomos o negado los átomos mediante la aplicación de $∨, ∧, ∃, ∀$. Para tales fórmulas Tait [1968] derivado de un engañosamente simple cálculo con sólo una regla para cada símbolo.

Las reglas de Tait del cálculo es la siguiente, donde, en orden a una sola en particular la fórmula de un conjunto finito, la convención es que los $\Gamma, A$ denota el conjunto finito $\Gamma \cup \{ A \}$.

$$\Gamma, Rx, \lnot Rx \, \, \text{(Ax)}$$

$${\Gamma , A_0, A_1 \over \Gamma, (A_0 \lor A_1)}\, \, (\lor)$$

$${\Gamma , A_0 \quad \Gamma, A_1 \over \Gamma, (A_0 \land A_1)}\, \, (\land)$$

$${\Gamma , A(t) \over \Gamma, \exists xA(x)}\, \, (\exists)$$

$${\Gamma , A \over \Gamma, \forall xA}\, \, (\forall)$$

$${\Gamma , C \quad \Gamma, \lnot C \over \Gamma}\, \, \text{(Cut)}$$

donde en los axiomas $Rx$ es un átomo, y en el $∀$-regla de $x$ no es libre en $\Gamma$.

Que esto es un equivalente a la formulación de la lógica clásica es fácil. Primer aviso de que cualquier conjunto finito se desprende que el anterior es, cuando se la considera como una disyunción, válido en todos los modelos clásicos y por lo tanto (integridad) clásicamente se pueden derivar. En la dirección opuesta, si $\Gamma \vdash_C A$ [es decir, derivable en el clásico deducción natural], a continuación, $¬\Gamma, A$ es derivable en el puro Tait cálculo.


Nota a pie de página :

[1] publicado Originalmente como W. W. Tait, NORMAL DERIVABILITY EN la LÓGICA CLÁSICA, en Jon Barwise (editor), la Sintaxis y La Semántica de Infinitary Idiomas (1968), en la página 204.

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