Número de Löwenheim - Löwenheim number

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 que se cumple un teorema de Löwenheim-Skolem descendente débil . Llevan el nombre de 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 "oraciones";
• 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 en particular.

El teorema no requiere propiedades particulares de las oraciones o modelos, o de la relación de satisfacción, y es posible que no sean 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, incluida la lógica de primer orden , la lógica de orden superior y la lógica infinita .

Definición

El número de Löwenheim de una lógica L es el κ cardinal más pequeño, de modo que si una oración arbitraria de L tiene algún 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 forme un conjunto , utilizando 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 cardenales

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

existe por el axioma de reemplazo . El extremo superior de este conjunto, por construcción, es el número 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:

• El número de Löwenheim-Skolem de una lógica abstracta L es el κ cardinal más pequeño, de modo 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, de modo que si A es una estructura para L, hay 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 una "estructura" de la lógica de predicados.

Para cualquier lógica para la que 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" con "tiene un modelo más pequeño que", ya que esto produce una clasificación más detallada.

Ejemplos de

• El teorema de Löwenheim-Skolem muestra que el número de Löwenheim-Skolem-Tarski de lógica de primer orden (con firmas contables) es ℵ ₀ . Esto significa, en particular, que si una oración de lógica de primer orden es satisfactoria, entonces la oración es satisfactoria en un modelo contable.
• Se sabe que el número de Löwenheim-Skolem de lógica de segundo orden es mayor que el primer cardinal mensurable , si hay un cardinal mensurable. (Y lo mismo vale para su número 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).

Notas

Referencias

• Menachem Magidor y Jouko Väänänen . " Sobre los números de Löwenheim-Skolem-Tarski para extensiones de 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