En teoría de modelos , el teorema de Löwenheim-Skolem , enunciado por Leopold Löwenheim en 1915 y plenamente demostrado en 1920 por Thoralf Skolem , establece que si un conjunto de fórmulas cerradas de lógica de primer orden admite un modelo infinito, entonces admite un modelo de cualquier tipo. cardinalidad infinita mayor o igual a la cardinalidad del lenguaje y del conjunto de fórmulas. El resultado se presenta a menudo en forma de dos teoremas : el teorema ascendente de Löwenheim-Skolem y el teorema descendente de Löwenheim-Skolem .
Consideremos que el lenguaje es contable (a menudo es una suposición razonable en particular en el procesamiento de datos y es una suposición hecha en ciertos trabajos de lógica en el procesamiento de datos). El teorema de Löwenheim-Skolem se puede establecer mediante: si una fórmula es satisfactoria, entonces es satisfactoria en el modelo más contable. O de manera más general: si un conjunto (contable) T de fórmulas cerradas es satisfactorio, entonces T lo es en un modelo más contable.
Sea σ una firma para un lenguaje de primer orden que contiene igualdad. Sea κ un cardinal infinito tal que | σ | ≤ κ. Sea M un modelo infinito en la firma σ. Entonces existe un modelo N de cardinalidad κ tal que:
En particular, M y N son entonces elementalmente equivalentes.
Sea σ, κ, M como en la hipótesis del teorema ascendente: | σ | ≤ κ y | M | <κ. Agregue una constante c a a cualquier elemento a del dominio de M y llame a σ + la firma σ aumentada por estas constantes c a . De cualquier M + definido como el modelo M pero donde se interpreta cada constante c tiene el elemento del dominio M . Sea T + el conjunto de fórmulas cerradas verdaderas en M + en el lenguaje de firmas σ + (este es el diagrama elemental de M ).
Consideremos ahora un conjunto E de cardenal y κ constante d i para todos i en E . Luego consideramos la teoría T 'que contiene T + y las fórmulas d i ≠ d j para i ≠ j . Cualquier parte finita T 0 de T ' es satisfactoria: por ejemplo, T 0 admite como modelo el modelo M' , definido como M + en el que las constantes d i se interpretan de modo que las d i que intervienen en T 0 se interpretan por separado elementos; esto es posible ya que T 0 es finito y M infinito. Por el teorema de compacidad , T ' admite un modelo N' cuyo dominio es al menos κ cardinal por definición de T 'que es una extensión elemental de M desde T' contiene el diagrama básico T + de M . Por el teorema de Skolem Löwenheim abajo, existe N '' es una subestructura elemental de N '' y contiene M , por lo que una extensión elemental de M . Sea N el modelo N '' restringido a la firma σ; este es el modelo buscado.
La parte descendente se muestra usando, por ejemplo, el teorema de completitud , o al menos la compleción del lenguaje por testigos de Henkin usado en las versiones modernas de la demostración del teorema de completitud .