Consecuente

En lógica matemática, un consecuencia es un tipo muy general de afirmación condicional.

A1,...... ,Am⊢ ⊢ B1,...... ,Bn.{displaystyle A_{1},,dotsA_{m},vdash ,B_{1},,dots B_{n}.

Un consecuente puede tener cualquier número m de fórmulas de condición A_i (llamadas "antecedentes") y cualquier número n de fórmulas afirmadas B_j (llamadas "sucesores" o "consecuentes"). Se entiende que un consecuente significa que si todas las condiciones antecedentes son verdaderas, entonces al menos una de las fórmulas del consecuente es verdadera. Este estilo de afirmación condicional casi siempre se asocia con el marco conceptual del cálculo secuencial.

Introducción

La forma y semántica de los secuentes

Las secuencias se entienden mejor en el contexto de los siguientes tres tipos de juicios lógicos:

1. Afirmación incondicional. No hay fórmulas anteriores.
   • Ejemplo: ⊢ B
   • Significa: B es verdad.
2. Afirmación condicional. Cualquier número de fórmulas anteriores.
   1. Sencilla aserción condicional. Una fórmula consecutiva simple.
      • Ejemplo: A₁, A₂, A₃ ⊢ B
      • Significado: IF A₁ Y A₂ Y A₃ son ciertas, entonces B es verdad.
   2. Secuencia. Cualquier número de fórmulas consiguientes.
      • Ejemplo: A₁, A₂, A₃ ⊢ B₁, B₂, B₃, B₄
      • Significado: IF A₁ Y A₂ Y A₃ son ciertas, entonces B₁ O B₂ O B₃ O B₄ es verdad.

Por lo tanto, los secuentes son una generalización de afirmaciones condicionales simples, que son una generalización de afirmaciones incondicionales.

La palabra "O" aquí está el OR inclusivo. La motivación para la semántica disyuntiva en el lado derecho de un secuente proviene de tres beneficios principales.

1. La simetría de las reglas clásicas de inferencia para los secunts con tal semántica.
2. La facilidad y simplicidad de convertir tales reglas clásicas a reglas intuitionistas.
3. La capacidad de probar la integridad del cálculo predicado cuando se expresa de esta manera.

Los tres beneficios fueron identificados en el documento fundacional de Gentzen (1934, p. 194).

No todos los autores se han adherido al significado original de Gentzen para la palabra "secuente". Por ejemplo, Lemmon (1965) usó la palabra "secuente" estrictamente para aserciones condicionales simples con una y sólo una fórmula consecuente. Huth & Ryan 2004, pág. 5.

Detalles de sintaxis

En un secuente general de la forma

.. ⊢ ⊢ .. {displaystyle Gamma vdash Sigma }

tanto Γ como Σ son secuencias de fórmulas lógicas, no conjuntos. Por lo tanto, tanto el número como el orden de ocurrencia de las fórmulas son significativos. En particular, la misma fórmula puede aparecer dos veces en la misma secuencia. El conjunto completo de reglas de inferencia de cálculo secuencial contiene reglas para intercambiar fórmulas adyacentes a la izquierda y a la derecha del símbolo de aserción (y, por lo tanto, permutar arbitrariamente las secuencias izquierda y derecha), y también para insertar fórmulas arbitrarias y eliminar copias duplicadas dentro de la izquierda. y las secuencias correctas. (Sin embargo, Smullyan (1995, pp. 107–108), usa conjuntos de fórmulas en secuencias en lugar de secuencias de fórmulas. En consecuencia, los tres pares de reglas estructurales llamadas &# 34;adelgazamiento", "contracción" e "intercambio" no son necesarios).

El símbolo ' ⊢ ⊢ {displaystyle vdash } "se conoce a menudo como el "cambio voluminoso", "página derecha", "página de confirmación" o "símbolo de confirmación". A menudo se lee, sugerentemente, como "siields", "prueba" o "entails".

Propiedades

Efectos de insertar y quitar proposiciones

Dado que cada fórmula en el antecedente (el lado izquierdo) debe ser verdadera para concluir la verdad de al menos una fórmula en el sucedente (el lado derecho), agregar fórmulas a cualquier lado da como resultado un secuente más débil, mientras que eliminarlas de cualquier lado da uno más fuerte. Esta es una de las ventajas de la simetría que se deriva del uso de la semántica disyuntiva en el lado derecho del símbolo de aserción, mientras que la semántica conjuntiva se mantiene en el lado izquierdo.

Consecuencias de listas vacías de fórmulas

En el caso extremo donde la lista de fórmulas de antecedente de un consecuente está vacía, el consecuente es incondicional. Esto difiere de la afirmación incondicional simple porque el número de consecuentes es arbitrario, no necesariamente un consecuente único. Así, por ejemplo, ' ⊢ B₁, B₂ ' significa que B₁, o B₂, o ambos deben ser verdaderos. Una lista de fórmulas de antecedentes vacía es equivalente a "siempre verdadero" proposición, llamada "verum", denotada "⊤". (Ver T (símbolo).)

En el caso extremo en el que la lista de fórmulas consecuentes de un consecuente está vacía, la regla sigue siendo que al menos un término de la derecha sea verdadero, lo cual es claramente imposible. Esto se indica con el mensaje 'siempre falso' proposición, llamada "falsum", denotada "⊥". Como la consecuencia es falsa, al menos uno de los antecedentes debe ser falso. Así, por ejemplo, ' A₁, A₂ ⊢ ' significa que al menos uno de los antecedentes A₁ y A₂ debe ser falso.

Uno ve aquí nuevamente una simetría debido a la semántica disyuntiva en el lado derecho. Si el lado izquierdo está vacío, entonces una o más proposiciones del lado derecho deben ser verdaderas. Si el lado derecho está vacío, entonces una o más de las proposiciones del lado izquierdo deben ser falsas.

El caso doblemente extremo ' ⊢ ', donde tanto la lista de fórmulas de antecedente como la de consecuente están vacías es "no satisfactoria". En este caso, el significado del secuente es efectivamente ' ⊤ ⊢ ⊥ '. Esto es equivalente al secuente ' ⊢ ⊥ ', que claramente no puede ser válido.

Ejemplos

Un secuente de la forma ' ⊢ α, β ', para las fórmulas lógicas α y β, significa que α es verdadera o β es verdadera (o ambas). Pero eso no significa que α sea una tautología o que β sea una tautología. Para aclarar esto, considere el ejemplo ' ⊢ B ∨ A, C ∨ ¬A '. Este es un consecuente válido porque B ∨ A es verdadero o C ∨ ¬A es verdadero. Pero ninguna de estas expresiones es una tautología aisladamente. Es la disyunción de estas dos expresiones lo que es una tautología.

Del mismo modo, un secuente de la forma ' α, β ⊢ ', para las fórmulas lógicas α y β, significa que α es falso o β es falso. Pero eso no significa que α sea una contradicción o que β sea una contradicción. Para aclarar esto, considere el ejemplo ' B ∧ A, C ∧ ¬A ⊢ '. Este es un consecuente válido porque B ∧ A es falso o C ∧ ¬A es falso. Pero ninguna de estas expresiones es una contradicción aisladamente. Es la conjunción de estas dos expresiones lo que es una contradicción.

Reglas

La mayoría de los sistemas de demostración ofrecen formas de deducir una secuencia de otra. Estas reglas de inferencia se escriben con una lista de secuencias arriba y abajo de una línea. Esta regla indica que si todo lo que está arriba de la línea es verdadero, también lo es todo lo que está debajo de la línea.

Una regla típica es:

.. ,α α ⊢ ⊢ .. .. ⊢ ⊢ α α .. ⊢ ⊢ .. {displaystyle {frac {Gammaalpha vdash Sigma qquad Gamma vdash alpha ¿Qué?

Esto indica que si podemos deducir eso .. ,α α {displaystyle Gammaalpha } rendimientos .. {displaystyle Sigma }, y eso .. {displaystyle "Gamma" rendimientos α α {displaystyle alpha }, entonces también podemos deducir que .. {displaystyle "Gamma" rendimientos .. {displaystyle Sigma }. (Ver también el conjunto completo de reglas de inferencia de cálculo secuencial.)

Interpretación

Historia del significado de las afirmaciones secuenciales

El símbolo de aserción en sequents originalmente significaba exactamente lo mismo que el operador de implicación. Pero con el tiempo, su significado ha cambiado para significar demostrabilidad dentro de una teoría en lugar de verdad semántica en todos los modelos.

En 1934, Gentzen no definió el símbolo de afirmación ' ⊢ ' en un consecuente para significar demostrabilidad. Lo definió para que significara exactamente lo mismo que el operador de implicación ' ⇒ '. Usando ' → ' en lugar de ' ⊢ ' y ' ⊃ ' en lugar de ' ⇒ ', escribió: "El secuente A₁,..., A_μ → B₁,..., B_ν significa, en cuanto a contenido, exactamente lo mismo que la fórmula (A₁ &... & A_μ) ⊃ (B₁ ∨... ∨ B_ν)". (Gentzen empleó el símbolo de la flecha hacia la derecha entre los antecedentes y los consecuentes de los secuentes. Empleó el símbolo ' ⊃ ' para el operador de implicación lógica).

En 1939, Hilbert y Bernays afirmaron igualmente que un secuente tiene el mismo significado que la correspondiente fórmula de implicación.

En 1944, Alonzo Church enfatizó que las afirmaciones posteriores de Gentzen no significaban demostrabilidad.

"El empleo del teorema de deducción como regla primitiva o derivada no debe confundirse con el uso de Sequenzen por Gentzen. Para la flecha de Gentzen, →, no es comparable a nuestra notación sintáctica, ⊢, pero pertenece a su lenguaje objeto (como está claro del hecho de que las expresiones que la contienen aparecen como premisos y conclusiones en las aplicaciones de sus reglas de inferencia)."

Numerosas publicaciones posteriores a esta época han afirmado que el símbolo de aserción en las secuencias significa demostrabilidad dentro de la teoría donde se formulan las secuencias. Curry en 1963, Lemmon en 1965 y Huth y Ryan en 2004 afirman que el símbolo de afirmación secuencial significa demostrabilidad. Sin embargo, Ben-Ari (2012, p. 69) afirma que el símbolo de aserción en las secuencias del sistema Gentzen, que denota como ' ⇒ ', es parte del lenguaje objeto, no del metalenguaje.

Según Prawitz (1965): "Los cálculos de secuentes pueden entenderse como metacálculos para la relación de deducibilidad en los correspondientes sistemas de deducción natural." Y además: "Una demostración en un cálculo de secuencias puede considerarse como una instrucción sobre cómo construir una deducción natural correspondiente." En otras palabras, el símbolo de afirmación es parte del lenguaje objeto para el cálculo secuente, que es una especie de metacálculo, pero al mismo tiempo significa deducibilidad en un sistema de deducción natural subyacente.

Significado intuitivo

Un secuente es una declaración formalizada de demostrabilidad que se usa con frecuencia cuando se especifican cálculos para la deducción. En el cálculo secuente, el nombre secuente se utiliza para el constructo, que puede considerarse como un tipo específico de juicio, característico de este sistema de deducción.

El significado intuitivo del secuente .. ⊢ ⊢ .. {displaystyle Gamma vdash Sigma } es que bajo la asunción de cúmulo la conclusión de la Autoridad es provable. Clásicamente, las fórmulas de la izquierda del torntil se pueden interpretar conjuntivamente mientras que las fórmulas de la derecha pueden considerarse como una disyunción. Esto significa que, cuando todas las fórmulas en la mantención de la luminaria, entonces al menos una fórmula en la ega también tiene que ser verdad. Si el aspirante está vacío, esto se interpreta como falsedad, es decir. .. ⊢ ⊢ {displaystyle Gamma vdash } significa que el calibre demuestra falsidad y por lo tanto es inconsistente. Por otro lado se supone que un antecedente vacío es verdad, es decir, ⊢ ⊢ .. {displaystyle vdash Sigma } significa que la OPS sigue sin ninguna asunción, es decir, siempre es verdad (como una disyunción). Un secuente de esta forma, con lumina vacía, se conoce como una afirmación lógica.

Por supuesto, otras explicaciones intuitivas son posibles, que son clásicamente equivalentes. Por ejemplo, .. ⊢ ⊢ .. {displaystyle Gamma vdash Sigma } se puede leer como afirmando que no puede ser el caso de que cada fórmula en Dimension es verdadera y cada fórmula en la eva es falsa (esto está relacionado con las interpretaciones de doble negación de la lógica intuitionista clásica, como el teorema de Glivenko).

En cualquier caso, estas lecturas intuitivas son solo pedagógicas. Dado que las pruebas formales en la teoría de la prueba son puramente sintácticas, el significado de (la derivación de) un consecuente solo viene dado por las propiedades del cálculo que proporciona las reglas reales de inferencia.

Basando cualquier contradicción en la definición técnicamente precisa arriba podemos describir los secunts en su forma lógica introductoria. .. {displaystyle "Gamma" representa un conjunto de suposiciones que iniciamos nuestro proceso lógico con, por ejemplo, "Sócrates es un hombre" y "Todos los hombres son mortales". El .. {displaystyle Sigma } representa una conclusión lógica que sigue en estos locales. Por ejemplo "Sócrates es mortal" sigue de una formalización razonable de los puntos anteriores y podríamos esperar verlo en el .. {displaystyle Sigma } del lado del torniquete. En este sentido, ⊢ ⊢ {displaystyle vdash } significa el proceso de razonamiento, o "antes" en inglés.

Variaciones

La noción general de secuente presentada aquí se puede especializar de varias formas. Se dice que un consecuente es un consecuente intuicionista si hay como máximo una fórmula en el sucedente (aunque también son posibles los cálculos multisucedentes para la lógica intuicionista). Más precisamente, la restricción del cálculo de secuentes generales a secuentes de fórmula de un solo sucedente, con las mismas reglas de inferencia que para los secuentes generales, constituye un cálculo de secuentes intuicionista. (Este cálculo secuencial restringido se denota LJ).

Del mismo modo, se pueden obtener cálculos para la lógica intuicionista dual (un tipo de lógica paraconsistente) al requerir que los secuentes sean singulares en el antecedente.

En muchos casos, también se supone que los secuentes consisten en conjuntos múltiples o conjuntos en lugar de secuencias. Por lo tanto, uno ignora el orden o incluso el número de ocurrencias de las fórmulas. Para la lógica proposicional clásica esto no genera ningún problema, ya que las conclusiones que uno puede sacar de una colección de premisas no dependen de estos datos. En lógica subestructural, sin embargo, esto puede llegar a ser muy importante.

Los sistemas de deducción natural usan afirmaciones condicionales de una sola consecuencia, pero por lo general no usan los mismos conjuntos de reglas de inferencia que introdujo Gentzen en 1934. En particular, los sistemas de deducción natural tabulares, que son muy convenientes para la demostración práctica de teoremas en proposiciones. cálculo y cálculo de predicados fueron aplicados por Suppes (1957) harvtxt error: no target: CITEREFSuppes1957 (ayuda) y Lemmon (1965) para la enseñanza de la lógica introductoria en los libros de texto.

Etimología

Históricamente, Gerhard Gentzen introdujo las secuencias para especificar su famoso cálculo de secuencias. En su publicación alemana usó la palabra "Sequenz". Sin embargo, en inglés, la palabra "secuencia" ya se usa como traducción al alemán "Folge" y aparece con bastante frecuencia en matemáticas. El término "secuente" entonces se ha creado en busca de una traducción alternativa de la expresión alemana.

Kleene hace el siguiente comentario sobre la traducción al inglés: "Gentzen dice 'Sequenz', que traducimos como 'sequent', porque ya hemos usado 'secuencia' para cualquier sucesión de objetos, donde el alemán es 'Folge'."