Metalógica

La metalógica es la rama de la lógica que estudia las propiedades y los componentes de los sistemas formales.^[1] Las propiedades más importantes que se pueden demostrar de los sistemas formales son la consistencia, decidibilidad y completitud.^[2] Ejemplos de teoremas metalógicos importantes son los teoremas de incompletitud de Gödel, el teorema de completitud de Gödel y el teorema de Löwenheim-Skolem. Otra propiedad es la compacidad.

Propiedades metateóricas editar

Mientras la lógica matemática se encarga, entre otras cosas, de construir sistemas lógicos, la metalógica se ocupa de estudiar las propiedades de dichos sistemas. Las propiedades más importantes que se pueden demostrar de los sistemas lógicos son:

Consistencia editar

Esta sección es un extracto de Consistencia (lógica).[editar]

En metalógica, la consistencia o consistencia lógica es la propiedad que tienen los sistemas formales cuando no es posible deducir una contradicción dentro del sistema. Es decir, dado un lenguaje formal y un aparato deductivo (axiomas y reglas de inferencia), no es posible deducir una fórmula y su negación. La existencia de un modelo implica que una teoría lógica es consistente.

Generalizando, la consistencia es una propiedad que pueden tener los conjuntos de fórmulas. Intuitivamente, un conjunto de fórmulas es consistente cuando no es posible deducir una contradicción del mismo. Es decir, dado un lenguaje formal y un aparato deductivo, no es posible demostrar una fórmula y su negación. Equivalentemente, esto se puede expresar diciendo que para ninguna proposición lógica p:

{\mathcal {A}}\vdash p

y

{\mathcal {A}}\vdash \neg p

simultáneamente.

Decidibilidad editar

Esta sección es un extracto de Decidibilidad.[editar]

En metalógica, la decidibilidad es una propiedad de los sistemas formales cuando, para cualquier fórmula en el lenguaje del sistema, existe un método efectivo para determinar si esa fórmula pertenece o no al conjunto de las verdades del sistema. Por ejemplo, la lógica proposicional es decidible, porque existe un algoritmo (la tabla de verdad) que en un número finito de pasos puede decidir si la fórmula es válida o no.

Cuando una fórmula no puede ser probada verdadera ni falsa, se dice que la fórmula es independiente, y que por lo tanto el sistema es no decidible. La única manera de incorporar una fórmula independiente a las verdades del sistema es postulándola como axioma. Dos ejemplos muy importantes de fórmulas independientes son el axioma de elección en la teoría de conjuntos, y el quinto postulado de la geometría euclidiana.

Completitud editar

Esta sección es un extracto de Completitud (lógica).[editar]

En metalógica, la completitud o completitud semántica es la propiedad metateórica que tienen los sistemas formales cuando todas las fórmulas lógicamente válidas (todas las verdades lógicas) del sistema son además teoremas del sistema.^[3] Es decir, cuando el conjunto de las verdades lógicas del sistema es un subconjunto del conjunto de teoremas. En otras palabras, si A es una fórmula cualquiera del lenguaje y S es el sistema formal bajo consideración, entonces se cumple que:

Si

\models _{\mathrm {S} }A

entonces

\vdash _{\mathrm {S} }A

^[3]

Por otra parte, la completitud sintáctica es la propiedad que tienen los sistemas formales cuando, para toda fórmula cerrada del lenguaje del sistema, o bien es un teorema o bien su negación lo es. Esto es, existe una prueba para cada fórmula cerrada o para su negación.

La lógica proposicional y la lógica de primer orden son ambas semánticamente completas, pero no sintácticamente completas. Por ejemplo, en la lógica proposicional, la fórmula p no es un teorema, y tampoco lo es su negación, de modo que eso basta para mostrar que no es sintácticamente completa. No obstante, como ninguna de esas dos fórmulas es una verdad lógica, no afectan a la completitud semántica del sistema.

El segundo teorema de incompletitud de Gödel demuestra que ningún sistema (definido recursivamente) con cierto poder expresivo puede ser a la vez consistente y sintácticamente completo.

Otra propiedad metateórica distinta es la completitud semántica fuerte, que dice: si en un sistema formal S, A es una fórmula bien formada cualquiera que es una consecuencia semántica de un conjunto $\Gamma$ de fórmulas, entonces existe una derivación de A a partir de $\Gamma$ . En símbolos:

Si

\Gamma \models _{\mathrm {S} }A

entonces

\Gamma \vdash _{\mathrm {S} }A

^[4]

Compacidad editar

Esta sección es un extracto de Compacidad (lógica).[editar]

En lógica matemática, el teorema de compacidad establece que un conjunto (posiblemente infinito) de fórmulas bien formadas de la lógica de primer orden tiene un modelo si todos sus subconjuntos finitos tienen un modelo. Es decir, para todo conjunto de fórmulas $\Gamma$ de un lenguaje L, si todo subconjunto finito de $\Gamma$ es satisfacible, entonces $\Gamma$ es satisfacible.

La lógica proposicional como la lógica de primer orden satisfacen el teorema de compacidad. Es decir, si de un conjunto de proposiciones se sigue una consecuencia, entonces existe un subconjunto finito de proposiciones de las cuales se sigue la misma conclusión. Análogamente si cada conjunto finito de proposiciones de un conjunto admite un modelo, entonces el conjunto completo admite un modelo. Si bien la lógica de primer orden tiene compacidad en el sentido previamente explicado, otras lógicas "más potentes" como la lógica de segundo orden no tienen la propiedad de compacidad.

Resultados metalógicos importantes editar

Teoremas de incompletitud de Gödel editar

Esta sección es un extracto de Teoremas de incompletitud de Gödel.[editar]

Kurt Gödel a los 19 años de edad, cinco años antes de la demostración de los teoremas.

Los teoremas de incompletitud de Gödel son dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1931. Ambos están relacionados con la existencia de proposiciones indecidibles en ciertas teorías aritméticas.

Teorema de Löwenheim-Skolem editar

Esta sección es un extracto de Teorema de Löwenheim-Skolem.[editar]

En lógica matemática, el teorema de Löwenheim-Skolem o teorema de Löwenheim-Skolem-Tarski es un teorema que establece que si una teoría de primer orden es consistente, entonces tiene al menos un modelo con dominio finito o numerable.^[5] Más precisamente: sea T un subconjunto consistente de un lenguaje de primer orden ℒ (con identidad): si T es finito o numerable, entonces tiene al menos un modelo con dominio finito o numerable.^[6] Esto significa que las teorías de primer orden no pueden controlar la cardinalidad de sus modelos: ninguna teoría consistente puede tener sólo modelos isomórficos.

La primera versión del teorema se debe a Leopold Löwenheim en 1915, aunque su demostración tenía una pequeña laguna.^[5] Thoralf Skolem demostró una segunda versión del teorema en 1919.^[5] Desde entonces han aparecido otras versiones.

Skolem comprendió que este teorema se podría aplicar para las formalizaciones de primer orden de la teoría de conjuntos, siendo dicha formalización numerable, existiría un modelo numerable para dicha teoría aun cuando la teoría afirma que existen conjuntos no contables. Este resultado contraintuitivo es la conocida paradoja de Skolem.

En general el teorema de Löwenheim-Skolem no se sostiene en lógicas más fuertes, como la lógica de segundo orden.

Teorema de completitud de Gödel editar

Esta sección es un extracto de Teorema de completitud de Gödel.[editar]

Fórmula del teorema de completitud de Gödel.

El teorema de completitud de Gödel es un importante teorema de la lógica matemática, que fue demostrado por primera vez por Kurt Gödel en 1929 y que en su forma más conocida establece lo siguiente:

En una lógica de primer orden, toda fórmula que es válida en un sentido lógico es demostrable.

Kurt Gödel

La palabra "demostrable" significa que existe una deducción formal de la fórmula. La deducción consiste en una lista finita de pasos en los que cada paso o bien invoca a un axioma o es obtenido a partir de pasos previos mediante una básica regla de inferencia. A partir de dicha deducción, es posible verificar si cada uno de los pasos es correcto mediante un algoritmo (por ejemplo, mediante una computadora o a mano).

Una fórmula es lógicamente válida si es verdadera en todo modelo para el lenguaje utilizado en la fórmula. Para expresar de manera formal el teorema de completitud de Gödel, se debe definir el significado de la palabra modelo en este contexto. Esta es una definición básica en la teoría de modelos.

El teorema de Gödel establece una correspondencia entre la verdad semántica y la probabilidad sintáctica en la lógica de primer orden. Crea un vínculo entre la teoría de modelos que se ocupa de lo que es cierto en diferentes modelos, y la teoría de la demostración que estudia lo que se puede probar formalmente en sistemas formales particulares. Gödel utilizó el teorema de completitud para probar el teorema de compacidad, demostrando la naturaleza finitaria del operador de consecuencia lógica. Estos resultados ayudaron a establecer la lógica de primer orden como el tipo de lógica dominante en las matemáticas actuales.

Fue luego simplificado en 1947, cuando Leon Henkin observó en su tesis de doctorado que la parte difícil de la prueba se puede presentar como el Modelo de Teorema de la Existencia (publicado en 1949). A su vez, la prueba de Henkin fue simplificada por Gisbert Hasenjaeger en 1953.

Otros resultados editar

Consistencia de la lógica proposicional veritativo-funcional (Emil Post 1920)
Completitud semántica de la lógica proposicional veritativo-funcional (Paul Bernays 1918, Emil Post 1920)
Decidibilidad de la lógica proposicional veritativo funcional (Emil Post 1920)
Consistencia de la lógica de primer orden monádica (Leopold Löwenheim 1915)
Completitud semántica de la lógica de primer orden monádica (Leopold Löwenheim 1915)
Decidibilidad de la lógica de primer orden monádica (Leopold Löwenheim 1915)
Consistencia de la lógica de primer orden (David Hilbert y Wilhelm Ackermann 1928)
Indecibilidad de la lógica de primer orden (Entscheidungsproblem, Alonzo Church 1936 y Alan Turing 1936)

Véase también editar

Notas y referencias editar

↑ Shapiro, Stewart. «metalógica». The Oxford Companion to Philosophy. Oxford University Press. Consultado el 6 de octubre de 2009.
↑ Jesús Padilla Gálvez, Jesús. (1995). Sobre metalógica. Un análisis histórico en torno a 1931. Arbor, 150, pp. 73-90.
↑ ^a ^b Hunter, Geoffrey (1971). «Sección 46.1». Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press.
↑ Hunter, Geoffrey (1971). «Sección 46.2». Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press.
↑ ^a ^b ^c Hunter, Geoffrey (1971). «Sección 45.18». Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press.
↑ Shapiro, Stewart. «Classical Logic». En Edward N. Zalta, ed. Stanford Encyclopedia of Philosophy (en inglés) (Winter 2009 Edition).

Datos: Q1366730
Multimedia: Metalogic / Q1366730

[1] Shapiro, Stewart. «metalógica». The Oxford Companion to Philosophy. Oxford University Press. Consultado el 6 de octubre de 2009.

[2] Jesús Padilla Gálvez, Jesús. (1995). Sobre metalógica. Un análisis histórico en torno a 1931. Arbor, 150, pp. 73-90.

[Completitud_(lógica)_Hunter-46-1-3] Hunter, Geoffrey (1971). «Sección 46.1». Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press.

[Completitud_(lógica)_Hunter-46-2-4] Hunter, Geoffrey (1971). «Sección 46.2». Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press.

[Teorema_de_Löwenheim-Skolem_Hunter-45-18-5] Hunter, Geoffrey (1971). «Sección 45.18». Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press.

[6] Shapiro, Stewart. «Classical Logic». En Edward N. Zalta, ed. Stanford Encyclopedia of Philosophy (en inglés) (Winter 2009 Edition).

[1]

[2]

[3]

[4]

[5]

[6]