Teorema de Löwenheim-Skolem

ImprimirCitar

Existencia y cardinalidad de modelos de teorías lógicas

En la lógica matemática, el teorema Löwenheim - Skolem es un teorema sobre la existencia y la cardinalidad de los modelos, llamados así por Leopold Löwenheim y Thoralf Skolem.

La formulación precisa se da a continuación. Implica que si una teoría de primer orden contable tiene un modelo infinito, entonces para cada número cardinal infinito κ tiene un modelo de tamaño κ , y que no hay de primer orden La teoría con un modelo infinito puede tener un modelo único hasta el isomorfismo. Como consecuencia, las teorías de primer orden no pueden controlar la cardinalidad de sus modelos infinitos.

El teorema (descendente) de Löwenheim-Skolem es una de las dos propiedades clave, junto con el teorema de compacidad, que se usan en el teorema de Lindström para caracterizar la lógica de primer orden. En general, el teorema de Löwenheim-Skolem no se mantiene en lógicas más fuertes, como la lógica de segundo orden.

Theorem

Ilustración del teorema de Löwenheim–Skolem

En su forma general, el Teorema de Löwenheim-Skolem establece que para cada firma σ, cada estructura σ infinita M y todo número cardinal infinito $κ \geq | σ |$ , existe un σ-estructura N tal que $| N | = κ$ y tal que

si $κ ANTERIOR M Silencio$ entonces N es una subestructura elemental M;
si $κ \sqrt\geqn \sqrt\geq M Silencio$ entonces N es una extensión elemental M.

El teorema a menudo se divide en dos partes correspondientes a los dos casos anteriores. La parte del teorema que afirma que una estructura tiene subestructuras elementales de todas las cardinalidades infinitas más pequeñas se conoce como Teorema de Löwenheim-Skolem hacia abajo. La parte del teorema que afirma que una estructura tiene extensiones elementales de todas las cardinalidades mayores se conoce como el teorema de Löwenheim-Skolem hacia arriba.

Discusión

A continuación elaboramos el concepto general de firmas y estructuras.

Conceptos

Firmas

Una firma consiste en un conjunto de símbolos de función S_func, un conjunto de símbolos de relación S_rel, y una función $operatorname {ar}:S_{operatorname {func} }cup S_{operatorname {rel} }rightarrow mathbb {N} _{0}$ representando la aridad de los símbolos de función y relación. (Un símbolo de función nullaria se llama símbolo constante.) En el contexto de la lógica de primer orden, una firma se llama a veces un lenguaje. Se llama contable si el conjunto de símbolos de función y relación en él es contable, y en general la cardinalidad de una firma es la cardinalidad del conjunto de todos los símbolos que contiene.

Una teoría de primer orden consta de una firma fija y un conjunto fijo de oraciones (fórmulas sin variables libres) en esa firma. Las teorías a menudo se especifican dando una lista de axiomas que generan la teoría, o dando una estructura y considerando que la teoría consiste en las oraciones satisfechas por la estructura.

Estructuras / Modelos

Dada una firma σ, una σ-estructura M es una interpretación concreta de los símbolos en σ. Consiste en un conjunto subyacente (a menudo también indicado por "M") junto con una interpretación de los símbolos de función y relación de σ. Una interpretación de un símbolo constante de σ en M es simplemente un elemento de M. Más generalmente, una interpretación de un símbolo de función n-ary f es una función de Mⁿ a M. De manera similar, una interpretación de un símbolo de relación R es una relación n-aria en M, es decir, un subconjunto de Mⁿ.

Se obtiene una subestructura de una estructura σ M tomando un subconjunto N de M que es cerrado bajo las interpretaciones de todos los símbolos de función en σ (por lo tanto, incluye las interpretaciones de todos los símbolos constantes en σ), y luego restringiendo las interpretaciones de los símbolos de relación a N. Una subestructura elemental es un caso muy especial de esto; en particular, una subestructura elemental satisface exactamente las mismas oraciones de primer orden que la estructura original (su extensión elemental).

Consecuencias

La declaración dada en la introducción sigue inmediatamente al tomar M como un modelo infinito de la teoría. La prueba de la parte superior del teorema también muestra que una teoría con modelos finitos arbitrariamente grandes debe tener un modelo infinito; a veces esto se considera parte del teorema.

Una teoría se llama categórica si tiene un solo modelo, hasta el isomorfismo. Este término fue introducido por Veblen (1904), y durante algún tiempo los matemáticos esperaban poder poner las matemáticas sobre una base sólida describiendo una teoría categórica de primer orden de alguna versión de la teoría de conjuntos. El teorema de Löwenheim-Skolem asestó un primer golpe a esta esperanza, ya que implica que una teoría de primer orden que tiene un modelo infinito no puede ser categórica. Más tarde, en 1931, la esperanza se hizo añicos por completo por el teorema de incompletitud de Gödel.

Muchas consecuencias del teorema de Löwenheim-Skolem parecían contrarias a la intuición para los lógicos a principios del siglo XX, ya que aún no se entendía la distinción entre propiedades de primer orden y de no primer orden. Una de esas consecuencias es la existencia de innumerables modelos de aritmética verdadera, que satisfacen todos los axiomas de inducción de primer orden pero tienen subconjuntos no inductivos.

Sea N los números naturales y R los reales. Del teorema se deduce que la teoría de (N, +, ×, 0, 1) (la teoría de la verdadera aritmética de primer orden) tiene innumerables modelos, y que la teoría de ( R, +, ×, 0, 1) (la teoría de los campos cerrados reales) tiene un modelo contable. Hay, por supuesto, axiomatizaciones que caracterizan (N, +, ×, 0, 1) y (R, +, ×, 0, 1) hasta el isomorfismo. El teorema de Löwenheim-Skolem muestra que estas axiomatizaciones no pueden ser de primer orden. Por ejemplo, en la teoría de los números reales, la completitud de un orden lineal usado para caracterizar R como un campo ordenado completo, no es una propiedad de primer orden.

Otra consecuencia que se consideró particularmente preocupante es la existencia de un modelo contable de la teoría de conjuntos, que, sin embargo, debe satisfacer la oración que dice que los números reales son incontables. El teorema de Cantor establece que algunos conjuntos son incontables. Esta situación contraria a la intuición se conoció como la paradoja de Skolem; muestra que la noción de contabilidad no es absoluta.

Boceto de prueba

Parte hacia abajo

Para cada primer orden $sigma$ -formula $varphi (y,x_{1},ldotsx_{n}),,$ el axioma de la elección implica la existencia de una función

f_{varphi }:M^{n}to M

tal que, para todos $a_{1},ldotsa_{n}in M$ , o

Mmodels varphi (f_{varphi }(a_{1},dotsa_{n}),a_{1},dotsa_{n})

{displaystyle Mmodels neg exists y,varphi (y,a_{1},dotsa_{n}),.}

Aplicando el axioma de elección de nuevo obtenemos una función de las fórmulas de primer orden $varphi$ tales funciones $f_{varphi },.$

Familia de funciones $f_{varphi }$ da lugar a un operador de preclosure $F$ en el conjunto de poder $M$

{displaystyle F(A)={f_{varphi }(a_{1},dotsa_{n})in Mmid varphi in sigma;,a_{1},dotsa_{n}in A}}

para $Asubseteq M,.$

Iterating $F$ contablemente muchos resultados en un operador de cierre $F^{omega },.$ Tomando un subconjunto arbitrario $Asubseteq M$ tales que $leftvert Arightvert =kappa$ , y habiendo definido $N=F^{omega }(A),,$ uno puede ver que también $leftvert Nrightvert =kappa ,.$ Entonces... $N$ es una subestructura elemental $M$ por la prueba Tarski-Vaught.

El truco utilizado en esta prueba es esencialmente debido a Skolem, que introdujo símbolos de función para las funciones de Skolem $f_{varphi }$ en el lenguaje. También se podría definir el $f_{varphi }$ como funciones parciales $f_{varphi }$ se define si y sólo si ${displaystyle Mmodels exists y,varphi (y,a_{1},dotsa_{n}),.}$ El único punto importante es que $F$ es un operador de preclosure tal que ${displaystyle F(A)}$ contiene una solución para cada fórmula con parámetros $A$ que tiene una solución $M$ y eso

leftvert F(A)rightvert leq leftvert Arightvert +leftvert sigma rightvert +aleph _{0},.

Parte superior

Primero, se extiende la firma agregando un nuevo símbolo constante para cada elemento de M. La teoría completa de M para la firma extendida σ' se denomina diagrama elemental de M. En el siguiente paso, uno agrega κ muchos nuevos símbolos constantes a la firma y agrega al diagrama elemental de M las oraciones c ≠ c' para dos nuevos símbolos constantes distintos c y c'. Usando el teorema de la compacidad, la teoría resultante se ve fácilmente como consistente. Dado que sus modelos deben tener cardinalidad al menos κ, la parte inferior de este teorema garantiza la existencia de un modelo N que tiene cardinalidad exactamente κ. Contiene una copia isomórfica de M como subestructura elemental.

En otras lógicas

Aunque el teorema (clásico) de Löwenheim-Skolem está muy relacionado con la lógica de primer orden, las variantes son válidas para otras lógicas. Por ejemplo, cada teoría consistente en lógica de segundo orden tiene un modelo más pequeño que el primer cardinal supercompacto (suponiendo que exista). El tamaño mínimo al que se aplica un teorema de tipo Löwenheim-Skolem (hacia abajo) en una lógica se conoce como el número de Löwenheim y se puede utilizar para caracterizar la fuerza de esa lógica. Además, si vamos más allá de la lógica de primer orden, debemos renunciar a una de estas tres cosas: la compacidad numerable, el teorema de Löwenheim-Skolem hacia abajo o las propiedades de una lógica abstracta.

Notas históricas

Este relato se basa principalmente en Dawson (1993). Para comprender la historia temprana de la teoría de modelos, se debe distinguir entre consistencia sintáctica (no se puede derivar ninguna contradicción utilizando las reglas de deducción para la lógica de primer orden) y satisfacibilidad (hay una modelo). Sorprendentemente, incluso antes de que el teorema de completitud hiciera innecesaria la distinción, el término consistente se usaba unas veces en un sentido y otras en el otro.

El primer resultado significativo en lo que luego se convirtió en la teoría de modelos fue el teorema de Löwenheim en la publicación de Leopold Löwenheim "Über Möglichkeiten im Relativkalkül" (1915):

Para cada firma contable σ, cada uno σ-sentencia que es satisfecha es satisfecha en un modelo contable.

El artículo de Löwenheim en realidad se ocupaba del cálculo de relativos más general de Peirce-Schröder (álgebra de relaciones con cuantificadores). También utilizó las notaciones ahora anticuadas de Ernst Schröder. Para un resumen del artículo en inglés y utilizando notaciones modernas, véase Brady (2000, capítulo 8).

Según el punto de vista histórico recibido, la prueba de Löwenheim era defectuosa porque implícitamente usaba el lema de Kőnig sin demostrarlo, aunque el lema aún no era un resultado publicado en ese momento. En un relato revisionista, Badesa (2004) considera que la prueba de Löwenheim estaba completa.

Skolem (1920) dio una prueba (correcta) usando fórmulas en lo que luego se llamaría forma normal de Skolem y confiando en el axioma de elección:

Cada teoría contable que es satisfecha en un modelo M, es satisfiible en una subestructura contable M.

Skolem (1922) también demostró la siguiente versión más débil sin el axioma de elección:

Cada teoría contable que es satisfecha en un modelo también es satisfecha en un modelo contable.

Skolem (1929) Simplificado Skolem (1920). Finalmente, Anatoly Ivanovich Maltsev (анато́лий ива́но neg Citó una nota de Skolem, según la cual el teorema había sido probado por Alfred Tarski en un seminario en 1928. Por lo tanto, el teorema general a veces se conoce como el teorema löwenheim - Skolem - Tarski . Pero Tarski no recordaba su prueba, y sigue siendo un misterio cómo podría hacerlo sin el teorema de compacidad.

Did you mean:

It is somewhat ironic that Skolem 's name is connected with the upward direction of the theorem as well as with the downward direction:

"Sigo la costumbre de llamar a Corollary 6.1.4 el teorema de Löwenheim-Skolem ascendente. Pero de hecho Skolem ni siquiera lo creyó, porque no creía en la existencia de conjuntos incontables". – Hodges (1993).

"Skolem [...] rechazó el resultado como sin sentido; Tarski [...] respondió muy razonablemente que el punto de vista formalista de Skolem debe considerar el teorema de Löwenheim-Skolem hacia abajo sin sentido como el hacia arriba." – Hodges (1993).

"Legend tiene que Thoralf Skolem, hasta el final de su vida, fue escandalizado por la asociación de su nombre a un resultado de este tipo, que él consideraba un absurdo, conjuntos innegables siendo, para él, ficciones sin existencia real." – Poizat (2000).

Contenido relacionado

Más resultados...