Metalógica

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda

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]

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: y simultáneamente.

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]

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    entonces  [3]

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 semánticamente completo.

Por otra parte, la completitud sintáctica es la propiedad que tienen los sistemas formales cuando, para toda fórmula 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 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.

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 de fórmulas, entonces existe una derivación de A a partir de . En símbolos:

Si    entonces  [4]

Compacidad[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 de un lenguaje L, si todo subconjunto finito de es satisfacible, entonces 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]

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.

El primer teorema de incompletitud afirma que, bajo ciertas condiciones, ninguna teoría matemática formal capaz de describir los números naturales y la aritmética con suficiente expresividad, es a la vez consistente y completa. Es decir, si los axiomas de dicha teoría no se contradicen entre sí, entonces existen enunciados que no se pueden probar ni refutar a partir de ellos. En particular, la conclusión del teorema se aplica siempre que la teoría aritmética en cuestión sea recursiva, esto es, una teoría en la que el proceso de deducción se pueda llevar a cabo mediante un algoritmo.

La prueba del teorema es totalmente explícita y en ella se construye una fórmula, denotada habitualmente G en honor a Gödel, para la que dada una demostración de la misma, se puede construir una refutación, y viceversa. Sin embargo, la interpretación natural de dicha sentencia en términos de números naturales es verdadera.[5]

El segundo teorema de incompletitud es un caso particular del primero: afirma que una de las sentencias indecidibles de dicha teoría es aquella que «afirma» la consistencia de la misma. Es decir, que si el sistema de axiomas en cuestión es consistente, no es posible demostrarlo mediante dichos axiomas.

Los teoremas de incompletitud de Gödel son uno de los grandes avances de la lógica matemática, y supusieron —según la mayoría de la comunidad matemática— una respuesta negativa al segundo problema de Hilbert.[5]​ Los teoremas implican que los sistemas axiomáticos de primer orden tienen severas limitaciones para fundamentar las matemáticas, y supusieron un duro golpe para el llamado programa de Hilbert para la fundamentación de las matemáticas. Por otra parte, durante algún tiempo ni Hilbert ni otros de sus colaboradores fueron conscientes de la importancia del trabajo de Gödel para su programa.

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.[3]​ 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.[3]​ Thoralf Skolem demostró una segunda versión del teorema en 1919.[3]​ 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]

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 demostracion 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 fintiaria del operador de consecuencia lógica. Estos resultados ayudaron a establecer a la lógica de primer orden como el tipo de lógica dominante en las matemáticas actual.

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

Otros resultados[editar]

  • Demostración de la consistencia de la lógica proposicional veritativo-funcional (Emil Post 1920)
  • Demostración de la completitud semántica de la lógica proposicional veritativo-funcional (Paul Bernays 1918, Emil Post 1920)
  • Demostración de la decidibilidad de la lógica proposicional veritativo funcional (Emil Post 1920)
  • Demostración de la consistencia de la lógica de primer orden monádica (Leopold Löwenheim 1915)
  • Demostración de la completitud semántica de la lógica de primer orden monádica (Leopold Löwenheim 1915)
  • Demostración de la decidibilidad de la lógica de primer orden monádica (Leopold Löwenheim 1915)
  • Demostración de la consistencia de la lógica de primer orden (David Hilbert y Wilhelm Ackermann 1928)
  • Demostración de la 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]

  1. Shapiro, Stewart. «metalógica». The Oxford Companion to Philosophy. Oxford University Press. Consultado el 6 de octubre de 2009. 
  2. Padilla Gálvez, Jesús. (1995). Sobre metalógica. Un análisis histórico en torno a 1931. Arbor, 150, pp. 73-90.
  3. a b c d e Hunter, Geoffrey (1971). «Sección 46.1». Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press.  Error en la cita: Etiqueta <ref> no válida; el nombre «Hunter» está definido varias veces con contenidos diferentes
  4. Hunter, Geoffrey (1971). «Sección 46.2». Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press. 
  5. a b Véase la parte dedicada a Gödel en la introducción de Hofstadter, 1989.
  6. Shapiro, Stewart. «Classical Logic». En Edward N. Zalta. Stanford Encyclopedia of Philosophy (en inglés) (Winter 2009 Edition).