En axiomatization de la lógica proposicional, ¿por qué uniforme de sustitución se aplica sólo a los axiomas?

Question

Estoy leyendo un libro introductorio acerca de la lógica matemática para la Computación (sólo para referencia, el libro es "Lógica para Computação", por Corrêa da Silva, Dedo & Melo), y quisiera hacer una pregunta.

Actualmente estoy leyendo el capítulo que habla sobre deductivo sistemas, y comienza con Axiomatization. Más específicamente, se habla de axiomatization como una forma de inferencia lógica, es decir, un axiomatization de la lógica clásica.

El libro es en portugués, por lo que todos los presupuestos desde los que están traducidos al inglés.

Ya que soy nuevo en el tema, no estoy seguro de lo que debo especificar antes de pedir el particular, la duda, así que voy a poner aquí algunas de las definiciones y explicaciones que se dan en el libro (el contexto).

Contexto

Justo antes de que se presenta una axiomatization de la lógica clásica, se define el concepto de sustitución:

La sustitución de una fórmula de B por un átomo de p, dentro de una fórmula, es representado por $A[p:=B]$. Intuitivamente, si tenemos una fórmula $A=p\to(p\wedge q)$, y queremos sustituto $(r\wedge s)$$p$, el resultado de la sustitución es: $A[p:=(r\wedge s)]=(r\wedge s)\to((r\wedge s)\wedge q)$.

A continuación, se define un ejemplo:

Cuando una fórmula B de los resultados de la sustitución de uno o más átomos de una fórmula A, decimos que B es un ejemplo de la fórmula de Un

A continuación, se presenta un axiomatization para el clásico de la lógica proposicional, que contiene varios axiomas, incluyendo, por ejemplo, $p\to(q\to p)$$(p\to (q\to r))\to((p\to q)\to(p\to r))$. No estoy seguro de si debo transcribir el conjunto de axiomas aquí, pero creo que no es necesario (pero puedo detalle aquí si es necesario).

El axiomatization también incluye la regla de inferencia modus ponens: De$A\to B$$A$, uno deduce $B$.

En segundo lugar, indica que los axiomas se pueden crear instancias:

Los axiomas se pueden crear instancias, es decir, los átomos pueden ser uniformemente sustituido por cualquier otra fórmula de la lógica. En este caso, decimos que la fórmula resultante es un ejemplo de axioma. Con la noción de axiomatization, podemos definir la noción de deducción.

Definición 2.2.2 Una deducción es una secuencia de fórmulas $A_1,...,A_n$ de manera tal que cada fórmula en la secuencia es un ejemplo de un axioma, o se obtiene de las anteriores fórmulas por medio de las reglas de inferencia, que es, por modus ponens

Un teorema $A$ es una fórmula que no existe una deducción $A_1,...,A_n = A$. Representamos a un teorema como $\vdash_{\text{Ax}} A$ o, simplemente, $\vdash A$

Entonces, dice teoremas también puede ser instanciado para producir nuevos teoremas:

El axiomatization que aquí se presenta tiene la propiedad de uniforme de sustitución, es decir, si a es un teorema y B es una instancia de a, entonces B también es un teorema. La razón es muy simple: si se puede aplicar una sustitución para obtener B de a, podemos aplicar la misma sustitución en las fórmulas que se producen en la deducción de Una y, desde cualquier instancia de un axioma es deducible de fórmula, hemos transformado la deducción de Una en una deducción de B.

Duda

Ahora voy a presentar la parte del texto que ha generado la duda:

Ahora vamos a definir cuando una fórmula $A$ es deducible a partir de un conjunto de fórmulas $\Gamma$, también llamado una teoría o un conjunto de hipótesis, la cual es representada por $\Gamma \vdash_{\text{Ax}} A$. En este caso, se trata de la adaptación de la noción de deducción a incluir los elementos de $\Gamma$.

Definición 2.2.3 decimos que una fórmula $A$ es deducible a partir del conjunto de fórmulas $\Gamma$ si no es una deducción, es decir, una secuencia de fórmulas $A_1,...,A_n = A$ de manera tal que cada fórmula $A_i$ en la secuencia es:

1) una fórmula $A_i \in \Gamma$

2) o una instancia de un axioma

3) o se obtiene de las anteriores fórmulas por medio de modus ponens.

[...] Nota también que no se puede aplicar uniforme en la sustitución de los elementos de $\Gamma$; uniforme de sustitución sólo puede ser aplicado a los axiomas de la lógica.

Esta es la declaración que yo no entendía: "tenga en cuenta también que no se puede aplicar el uniforme de la sustitución de los elementos de la $\Gamma$; uniforme de sustitución sólo puede ser aplicado a los axiomas de la lógica". ¿Por qué esto es particularmente cierto? Desde teoremas se pueden crear instancias, parece que debería ser posible crear instancias de los elementos de $\Gamma$. Me estoy perdiendo algo?

Gracias de antemano.

Answer 1

Si usted hizo por lo menos en la manera en que el autor entiende, la teoría ya no vienen como de sonido.

Tenga en cuenta que la definición del conjunto Γ no dice nada acerca de sus miembros como axiomas o por la derivable de los axiomas. La primera cláusula de la definición 2.2.3 dice que "una fórmula de Un$_i$∈Γ" ¿Qué es Γ? El texto dice: "el conjunto de fórmulas Γ". El autor no aclarar, pero sí hace que Γ puede ser cualquier subconjunto finito del conjunto de todas las fórmulas proposicionales. Así que, sí se puede aplicar uniforme de la sustitución de un elemento, o incluso algunos de los elementos de la Γ siempre que los elemento(s) de aplicar uniforme de sustitución para calificar como un axioma, un teorema, o la negación de un teorema. Pero, no se puede aplicar uniforme de la sustitución de todos los elementos de la Γ sin destrozando cosas. Más específicamente, uniforme de sustitución en los términos de las deducciones no aplicadas semántica contingencias.

Ejemplos de cómo se podría aplicar uniforme de la sustitución de los elementos de Γ. Supongamos Γ sólo contiene C-Kpq-q y K. Kpq.r como fórmulas (el "-"y "."s son informales signos de puntuación para poder hacer estas fórmulas más fáciles de leer... K significa la conjunción lógica, C para el material condicional aquí y puedo usar notación polaca). Entonces podemos escribir una deducción como este:

• K. Kpq.r \begin{gather} \exists x.(x^2 = 2) \\ \Diamond \exists x.(x^2 = 2) \\ \exists x.\Diamond(x^2 = 2) \endhyothesis 1
• • C-Kpq-p \begin{gather} \exists p.\mathit{wearingHat}(p) \\ \Diamond \exists p.\mathit{wearingHat}(p) \\ \exists p.\Diamond\mathit{wearingHat}(p) \endhipótesis 2
• • C-K. Kpq.r-r -----2 p/Kpq, q/r 3
• • r -----1, 3 condicional-4
• C-C. Kpq.q-r -----2-4 condicional-en 5

$\vdash$C-KKpqr-C. CKpqq.r -----1-5 introducción condicional 6

Supongamos que tenemos C-p-C. Cpq.p y C-Cpq-C. Cqr.La rcp, y C. CCpqq.r como hipótesis. Entonces podemos escribir una deducción como este:

• C-p-C. Cpq.q -----hipótesis 1
• • C-Cpq-C. Cqr.La rcp -----hipótesis 2
• • • C. CCpqq.r -----hipótesis 3
• • • C-C p CCpqq-C. C CCpqq r.La rcp -----2 p/CCpqq 4
• • • C. C CCpqq r.La rcp -----1, 4 condicional 5
• • • La rcp -----3, 5 condicional, 6
• • C. CCCpqqr.La rcp -----3-6 condicional-en 7
• C. CCpqCCqrCpr.CCCCpqqrCpr -----2-7 condicional-en 8

$\vdash$C-CpCCpqq-C. CCpqCCqrCpr.C:CCCpqqr:Rcp -----1-8 condicional-en 9

Supongamos que tenemos K-p-Np (la negación de un teorema), C-Kpq-p (un teorema), y p (a un contingente de la proposición) como hipótesis. Entonces podemos escribir:

• p -------hipótesis 1
• • C-Kpq-p ------ hipótesis 2
• • • K-p-Np -------hipótesis 3
• • • K-Cpq-NCpq ------- 3 p/Cpq 4
• • • C-KCpqNCpq-Cpq ----- 2 p/Cpq, p/NCpq 5
• • • Cpq ------- 2, 3 condicional-6
• • C-KpNp-Cpq ------3-6 condicional-en 7
• C-CKpqp-C. KpNp.Cpq ------2-7 condicional-en 8

$\vdash$C-p-C. CKpqp.C:KpNp:Cpq ------1-8 condicional-en 9

Ahora supongamos que usted se aplique uniforme de sustitución para cualquier posible permisible elemento de Γ. Entonces, sería posible escribir deducciones como las siguientes:

 1 C   p   q  |hypothesis
 2   CpCqp    |axiom
 3 C CpCqp q  |1 p/CpCqp, q/q where "x/y" indicates x has gotten substituted by y
 4 q          |2, 3 modus ponens

Dado que el sistema tiene la deducción meta-teorema (o, equivalentemente, introducción condicional), se sigue que CCpqq sería un teorema en el cálculo proposicional. Pero, si p es falsa y q es falsa, entonces CCpqq=CC000=C10=0. En consecuencia, una teoría ya no vienen como de sonido. También, usted tendría la inferencia de reglas con las que se podría "probar" el consecuente de un condicional a partir de la recepción de la misma.

Añadido: Usted puede aplicar uniforme de sustitución a las contradicciones dada la deducción metatheorem, y no destrozar cosas, ya que las contradicciones son falsas para todas las interpretaciones. Contradicciones siempre en un valor determinado. Por lo tanto, cualquier sustitución instancia de una contradicción es falsa también. Así que, cuando usted descarga cualquier introducido contradicciones introducción condicional, usted va a terminar con una tautología de la clásica lógica proposicional, y por lo tanto tiene solidez.

Añadido: sí existe algo de otra excepción, si el autor para introducir la lógica proposicional con cuantificadores. San Jaskowski original del papel de las Reglas de La Suposición en la Lógica Formal en lo que llamamos "deducción natural" tiene una norma de sustitución cuando tenemos lo que llamamos el cuantificador universal en condiciones especiales.

Answer 2

Esto se hace para evitar que el número de reglas de inferencia a un mínimo, con el fin de ser capaz de razonar más fácilmente sobre los teoremas y las deducciones. Los axiomas necesitan un tratamiento especial con el fin de tener una suficientemente rico teoría.

Es una práctica más común (creo) para hablar sobre los esquemas de axioma, que son infinitos conjuntos de axiomas – que corresponde a lo que su libro se llama las instancias de un axioma.

Una característica importante es que debe ser efectivamente decidable determinar si una fórmula es una instancia de un axioma o no.

Answer 3

Si $A \to B$ es un axioma, no debe ser posible derivar $C \to D$; hay valoraciones en las que la primera es verdadera y la segunda es falsa. Pero, ésta es una instancia de sustitución de la antigua. Por lo tanto no es de sonido para aplicar la sustitución arbitraria de los axiomas.