Número de Löwenheim

Smallest cardinal number for which a weak downward Löwenheim–Skolem theorem holds

En lógica matemática, el número de Löwenheim de una lógica abstracta es el número cardinal más pequeño para el cual se cumple un teorema de Löwenheim-Skolem descendente débil . ^[1] Se denominan así en honor a Leopold Löwenheim , quien demostró que existen para una clase muy amplia de lógicas.

Lógica abstracta

Una lógica abstracta, a los efectos de los números de Löwenheim, consiste en:

• Una colección de "frases";
• Una colección de "modelos", a cada uno de los cuales se le asigna una cardinalidad;
• Una relación entre oraciones y modelos que dice que una determinada oración es "satisfecha" por un modelo particular.

El teorema no requiere ninguna propiedad particular de las oraciones o modelos, o de la relación de satisfacción, y pueden no ser las mismas que en la lógica ordinaria de primer orden . Por lo tanto, se aplica a una colección muy amplia de lógicas, incluidas la lógica de primer orden , las lógicas de orden superior y las lógicas infinitarias .

Definición

El número de Löwenheim de una lógica L es el cardinal κ más pequeño tal que si una oración arbitraria de L tiene cualquier modelo, la oración tiene un modelo de cardinalidad no mayor que κ .

Löwenheim demostró la existencia de este cardinal para cualquier lógica en la que la colección de oraciones forma un conjunto , usando el siguiente argumento. Dada tal lógica, para cada oración φ , sea κ _φ la cardinalidad más pequeña de un modelo de φ , si φ tiene algún modelo, y sea κ _φ 0 en caso contrario. Entonces el conjunto de cardinales

{ κ _φ  : φ es una oración en L }

existe por el axioma de reemplazo . El supremo de este conjunto, por construcción, es el número de Löwenheim de L. Este argumento no es constructivo: prueba la existencia del número de Löwenheim, pero no proporciona una forma inmediata de calcularlo.

Extensiones

Se han considerado dos extensiones de la definición: ^[2]

• El número de Löwenheim-Skolem de una lógica abstracta L es el cardinal κ más pequeño tal que si cualquier conjunto de oraciones T ⊆ L tiene un modelo, entonces tiene un modelo de tamaño no mayor que max(| T |, κ ) .
• El número de Löwenheim–Skolem–Tarski de L es el cardinal más pequeño tal que si A es cualquier estructura para L existe una subestructura elemental de A de tamaño no mayor que κ . Esto requiere que la lógica tenga una noción adecuada de "subestructura elemental", por ejemplo, utilizando la definición normal de "estructura" de la lógica de predicados.

Para cualquier lógica para la cual existan números, el número de Löwenheim–Skolem–Tarski no será menor que el número de Löwenheim–Skolem, que a su vez no será menor que el número de Löwenheim.

Tenga en cuenta que a veces se utilizan versiones de estas definiciones que reemplazan "tiene un modelo de tamaño no mayor que" por "tiene un modelo menor que", ya que esto produce una clasificación más precisa. ^[2]

Ejemplos

• El teorema de Löwenheim–Skolem muestra que el número de Löwenheim–Skolem–Tarski de la lógica de primer orden (con signaturas contables) es ℵ ₀ . Esto significa, en particular, que si una oración de lógica de primer orden es satisfacible, entonces la oración es satisfacible en un modelo contable.
• Se sabe que el número de Löwenheim-Skolem de la lógica de segundo orden es mayor que el primer cardinal medible , si hay un cardinal medible. ^[2] (Y lo mismo se aplica a su número de Hanf). Sin embargo, el número de Löwenheim de la lógica universal (fragmento de) de segundo orden es menor que el primer cardinal supercompacto (asumiendo que existe).
• El número de Löwenheim–Skolem–Tarski de la lógica de segundo orden es el supremo de todos los ordinales definibles por una fórmula. ^{[3] Corolario 4.7} ${\displaystyle \Pi _{2}}$

Notas

1. Zhang 2002 página 77
2. Magidor y Väänänen 2009/2010
3. J. Väänänen, Sort logic and foundations of mathematics (Lógica de clasificación y fundamentos de las matemáticas ). En Infinity and Truth (Infinito y verdad) , Lecture Notes Series del Instituto de Ciencias Matemáticas de la Universidad Nacional de Singapur, vol. 25 (2014), World Scientific, págs. 171-186.

Referencias

• Menachem Magidor y Jouko Väänänen . "Sobre los números de Löwenheim-Skolem-Tarski para extensiones de la lógica de primer orden", Informe nº 15 (2009/2010) del Instituto Mittag-Leffler.
• Yi Zhang Lógica y álgebra 2002. ISBN  0-8218-2984-X