Teorema de Löwenheim-Skolem

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

El teorema de Löwenheim-Skolem descendente

Sea ℒ un lenguaje de primer orden de cardinalidad K, donde K es un cardinal infinito. El teorema de Löwenheim-Skolem descendente establece que si ℒ tiene un modelo de cardinalidad K, entonces también tiene al menos un modelo de cardinalidad menor o igual a K. La demostración del teorema emplea el teorema de la existencia de modelos dentro de la demostración de completitud para la lógica de primer orden.

El teorema establece una conexión entre la cardinalidad del lenguaje y la cardinalidad de sus modelos, e impone serias restricciones sobre la representación de estructuras infinitas. Si E es una estructura para un lenguaje ℒ de cardinalidad mayor que la cardinalidad de ℒ, ningún conjunto de oraciones de ℒ podrá representar a E hasta el isomorfismo ya que, según el teorema, cualquier conjunto de oraciones de ℒ que tenga modelos, tendrá algún modelo de cardinalidad menor que la cardinalidad de E; y este modelo no puede ser isomorfo con E.

El teorema de Löwenheim-Skolem descendente es una propiedad clave, junto con el teorema de compacidad, para caracterizar a la lógica de primer orden.

El teorema de Löwenheim-Skolem ascendente

De nuevo, sea ℒ un lenguaje de primer orden de cardinalidad K, donde K es un cardinal infinito. El teorema de Löwenheim-Skolem ascendente establece que si ℒ tiene un modelo de cardinalidad K, entonces también tiene al menos un modelo de cardinalidad mayor o igual a K. La demostración emplea el teorema de compacidad para lenguajes de primer orden.

Este segundo teorema elimina cualquier esperanza de representar cualquier estructura infinita hasta el isomorfismo. Pues si un conjunto de fórmulas de un lenguaje de primer orden ℒ tiene un modelo infinito, entonces tendrá otros de cardinalidad mayor y, por tanto, no isomorfos.

El teorema de Löwenheim, Skolem y Tarski

Si un conjunto de fórmulas de un lenguaje de primer orden ℒ tiene un modelo infinito, entonces tiene un modelo de cada cardinalidad infinita mayor o igual que la cardinalidad de ℒ. Este teorema es un resultado reforzado del teorema de Löwenheim y Skolem, que se puede obtener combinando los otros dos resultados.

Véase también

Notas y referencias

  1. ↑ 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. 
  2. ↑ Shapiro, Stewart. «Classical Logic». En Edward N. Zalta, ed. Stanford Encyclopedia of Philosophy (en inglés) (Winter 2009 Edition).