Prueba de consistencia


Prueba de consistencia

Prueba de consistencia

En lógica matemática, un sistema formal es consistente si no contiene una contradicción, o, en forma más precisa, no existe una proposición φ tal que se puede demostrar o deducir simultáneamente la proposición φ y su contraria ¬φ o no-φ.

Referido a un argumento, la consistencia es la necesidad de que todas las premisas tengan que ser necesariamente y a la vez, como producto, todas verdaderas, para que el argumento, si es consistente, pueda ser válido o no válido. Referido al discurso la consistencia tiene que ver con que las implicaciones lógicas del mismo no sean autocontradictorias.

Una demostración de consistencia (o prueba de consistencia) es una demostración formal de que un sistema formal es consistente. El desarrollo inicial de la teoría de la demostración matemática fue motivado por el deseo de proveer demostraciones de consistencia finita para toda la matemáticas como parte del programa de Hilbert. El programa de Hilbert cumple con las observaciones de Gödel, tal como se expresa en sus dos teoremas de incompletitud de Gödel, de que las teorías de demostración robustas no son capaces de probar su propia consistencia.

A pesar de que es posible demostrar la consistencia mediante teoría de modelos, por lo general se realiza de una manera puramente sintáctica, sin la necesidad de proveer una referencia a algún modelo de la lógica. La eliminación de corte (o en forma equivalente la normalización del cálculo subyacente si es que existe uno) implica la consistencia del cálculo: dado que obviamente no existe prueba de falsedad que sea libre de corte, no existe por lo tanto contradicción en general.

Contenido

Consistencia y completitud

Los principales resultados relacionados con la consistencia y completitud fueron demostrados por Kurt Gödel:

  • El teorema de completitud de Gödel indica que toda teoría de primer orden consistente es completa con respecto al conjunto consistente máximo de las fórmulas que se generan por medio del algoritmo de búsqueda de demostración.
  • Los teoremas de la incompletitud de Gödel indican que las teorías capaces de expresar su propia relación de demostrabilidad y de desarrollar un argumento diagonal son capaces de demostrar su propia consistencia solo si son inconsistentes. Estas teorías, si son consistentes, son denominadas teorías esencialmente incompletas.

Mediante la aplicación de estas ideas, se pueden encontrar cuatro tipos distintos de teorías de primer orden:

  1. Teorías inconsistentes, que no poseen modelos;
  2. Teorías que no pueden analizar su propia relación de demostración, tales como la axiomatización de Tarski de la geometría del punto y la linea, y la aritmética de Presburg. Dado que estas teorías son descriptas en forma satisfactoria por el modelo que se obtiene mediante el teorema de completitud, entonces estos sistemas son completos;
  3. Teorías capaces de analizar su propia consistencia, y que incluyen la negación de la proposición que asevera su propia consistencia. Este tipo de teorías son completas con respecto al modelo que se obtiene a partir del teorema de completitud, pero contienen como teorema la implicancia de una contradicción, en contradicción al hecho de que son consistentes;
  4. Teorías esencialmente incompletas.

En forma adicional, se ha descubierto recientemente que existe un quinto tipo de teoría, las teorías auto verificables, que son lo suficientemente robustas como para analizar su propia relación de demostración, pero son demasiado débiles como para realizar una diagonalización de Gödel, y que por lo tanto pueden demostrar en forma consistente su propia consistencia. Sin embargo, una teoría que demuestra su propia consistencia no permite obtener ninguna información interesante, dado que las teorías inconsistentes también demuestran su propia consistencia.

Fórmulas

Un conjunto de fórmulas Φ en lógica de primer orden es consistente (expresado como ConΦ) si y solo si no existe una fórmula φ tal que \Phi \vdash \phi y \Phi \vdash \lnot\phi. De lo contrario Φ es inconsistente y se expresa IncΦ.

Φ es simplemente consistente si y solo si para ninguna fórmula φ de Φ son tanto φ como la negación de φ teoremas de Φ.

Φ es absolutamente consistente o Post consistente si por lo menos una fórmula de Φ no es un teorema de Φ.

Φ es máximamente consistente si y solo si para toda fórmula φ, si Con \Phi \cup \phi entonces \phi \in \Phi.

Φ se dice contiene testigos si y solo si para cada fórmula de la forma \exist x \phi existe un término t tal que (\exists x \phi \to \phi {t \over x}) \in \Phi. Véase Lógica de primer orden.

Resultados básicos

1. Los siguientes son equivalentes:

(a) IncΦ

(b) Para todo \phi,\; \Phi \vdash \phi.

2. Todo conjunto de fórmulas satisfiable es consistente, un conjunto de fórmulas Φ es satisfiable si y solo si existe un modelo \mathfrak{I} tal que \mathfrak{I} \vDash \Phi .

3. Para todo Φ y φ:

(a) si no  \Phi \vdash \phi, entonces Con \Phi \cup \{\lnot\phi\};

(b) si Con Φ y \Phi \vdash \phi, entonces Con \Phi \cup \{\phi\};

(c) si Con Φ, entonces Con \Phi \cup \{\phi\} o Con \Phi \cup \{\lnot \phi\}.

4. Sea Φ un conjunto de fórmulas consistentes y que poseen testigos. Para todo φ y ψ:

(a) si  \Phi \vdash \phi, entonces \phi \in \Phi,

(b) o bien \phi \in \Phi o bien \lnot \phi \in \Phi,

(c) (\phi \or \psi) \in \Phi si y solo si \phi \in \Phi o \psi \in \Phi,

(d) si (\phi\to\psi) \in \Phi y \phi \in \Phi , entonces \psi \in \Phi,

(e) \exists x \phi \in \Phi si y solo si existe un término t tal que \phi{t \over x}\in\Phi.


Teorema de Henkin

Sea Φ un conjunto de fórmulas máximamente consistentes con testigos.

Define una relación binaria en el conjunto de términos S  t_0 \sim t_1 \! si y solo si \; t_0 = t_1 \in \Phi; y sea \overline t \! la clase de términos de equivalencia conteniendo t \!; y sea T_{\Phi} := \{ \; \overline t \; |\; t \in T^S \} donde T^S \! es el conjunto de términos basados en el conjunto de símbolo S \!.

Define la estructura S \mathfrak T_{\Phi} sobre  T_{\Phi} \! el término-estructura correspondiente a Φ mediante:

(1) Para el n-ésimo R \in S, R^{\mathfrak T_{\Phi}} \overline {t_0} \ldots \overline {t_{n-1}} si y solo si \; R t_0 \ldots t_{n-1} \in \Phi,

(2) Para el n-ésimo f \in S, f^{\mathfrak T_{\Phi}} (\overline {t_0} \ldots \overline {t_{n-1}}) := \overline {f t_0 \ldots t_{n-1}},

(3) Para c \in S, c^{\mathfrak T_{\Phi}}:= \overline c.

Sea \mathfrak I_{\Phi} := (\mathfrak T_{\Phi},\beta_{\Phi}) el término interpretación asociado con Φ, donde \beta _{\Phi} (x) := \bar x.

(*) \; Para todo φ,\; \mathfrak I_{\Phi} \vDash \phi si y solo si  \; \phi \in \Phi.

Véase también

  • Lógica paraconsistente
  • Equiconsistency
  • Hilbert's second problem
  • Hilbert's program
  • Hilbert's problems
  • Matiyasevich's theorem
  • Emil Post (1920)
  • Łukasiewicz

Referencias

H.D. Ebbinghaus, J. Flum, W. Thomas, Mathematical Logic

Obtenido de "Prueba de consistencia"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • prueba — ► sustantivo femenino 1 Acción y resultado de probar: ■ antes de lavarlo, haz una prueba con un retal a ver si destiñe; nos hizo una prueba del funcionamiento de la máquina. SINÓNIMO demostración 2 Razón, testimonio u otro medio con que se… …   Enciclopedia Universal

  • Consistencia (lógica) — Se ha sugerido que este artículo o sección sea fusionado con Prueba de consistencia (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí. La consistencia lógica es una propiedad que pueden tener los… …   Wikipedia Español

  • prueba — (de probar) 1) f. Acción de probar. 2) Efecto de probar. 3) Razón, argumento, etc., con que se pretende hacer patente la verdad o falsedad de una cosa. 4) Indicio, señal o muestra que se da de una cosa. 5) Ensayo o experiencia de una cosa. 6)… …   Diccionario de motivos de la Lengua Española

  • prueba — (de probar) 1) f. Acción de probar. 2) Efecto de probar. 3) Razón, argumento, etc., con que se pretende hacer patente la verdad o falsedad de una cosa. 4) Indicio, señal o muestra que se da de una cosa. 5) Ensayo o experiencia de una cosa. 6)… …   Diccionario de motivos de la Lengua Española

  • prueba — (de probar) 1) f. Acción de probar. 2) Efecto de probar. 3) Razón, argumento, etc., con que se pretende hacer patente la verdad o falsedad de una cosa. 4) Indicio, señal o muestra que se da de una cosa. 5) Ensayo o experiencia de una cosa. 6)… …   Diccionario de motivos de la Lengua Española

  • prueba — 1. f. Acción y efecto de probar. 2. Razón, argumento, instrumento u otro medio con que se pretende mostrar y hacer patente la verdad o falsedad de algo. 3. Indicio, señal o muestra que se da de algo. 4. Ensayo o experimento que se hace de algo,… …   Diccionario de la lengua española

  • prueba de Moberg — el paciente debe reconocer sin el control de la vista 9 objetos de forma y consistencia diferente. Se utiliza para comprobar la sensibilidad después de una lesión traumática de los nervios periféricos Diccionario ilustrado de Términos Médicos..… …   Diccionario médico

  • consistencia — f Grado de firmeza o de la relativa facilidad para deformarse del hormigуn reciйn mezclado; generalmente se mide por el cono de Abrams y por la prueba de la mesa de sacudidas, en el caso de una lechada o mortero …   Diccionario de Construcción y Arquitectur

  • prueba de asiento — f Procedimiento o mйtodo que se emplea para determinar la consistencia y plasticidad del hormigуn fresco midiendo su descenso o asentamiento …   Diccionario de Construcción y Arquitectur

  • de prueba — ► locución adverbial 1. Con consistencia y firmeza en lo físico y en lo moral. 2. Adecuado para probar el límite de la paciencia de uno …   Enciclopedia Universal