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] 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, consta de:
- 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 está "satisfecha" con 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 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 κ tal 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 cardenal para cualquier lógica en la que el conjunto 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 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 de modo que si A es cualquier 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 "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" por "tiene un modelo más pequeño que", ya que esto produce una clasificación más detallada. [2]
Ejemplos
- 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 ℵ 0 . 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 la lógica de segundo orden es mayor que el primer cardinal mensurable , si hay un cardinal mensurable. [2] (Y lo mismo ocurre con 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 (suponiendo que exista).
- El número de Löwenheim-Skolem-Tarski de lógica de segundo orden es el supremo de todos los ordinales definibles mediante una fórmula. [3] Corolario 4.7
Notas
- ^ Zhang 2002 página 77
- ^ abc Magidor y Väänänen 2009/2010
- ^ J. Väänänen, Lógica de clasificación y fundamentos de las matemáticas . En Infinity and Truth , Serie de notas de conferencias 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