Autores, Editores, Burócratas, Administradores
2226
ediciones
sin resumen de edición
De hecho, la demostración de la completud de la lógica de primer orden no es trivial. La prueba más habitual emplea la construcción de Henkin para demostrar que todo conjunto consistente de oraciones tiene un modelo. Que un conjunto de oraciones <math>\Gamma</math> es consistente significa que <math>\Gamma\nvdash A\land\lnot A</math>. Por otra parte, un modelo para <math>\Gamma</math> es una interpretación que hace verdaderas a todas las oraciones en <math>\Gamma</math>. La idea central de la prueba muestra cómo cualquier conjunto consistente <math>\Gamma</math> de oraciones se puede extender a un conjunto <math>\Sigma</math> que es máximamente consistente y que contiene una instancia para cada generalización existencial en <math>\Sigma</math>. A partir de este conjunto es posible construir una interpretación que haga a todas las oraciones en <math>\Sigma</math>, y por tanto en <math>\Gamma</math>, verdaderas. Ver Zalabardo 2002, c. 5 y Hedman 2006, 148-151, para detalles sobre la prueba.
'''Comentario 2.17'''
La compacidad nos dice que si <math>A</math> es consecuencia lógica de un conjunto <math>\Gamma</math> de premisas, entonces <math>A</math> es consecuencia lógica de un subconjunto finito <math>\Gamma^{*}</math> de <math>\Gamma</math>. Si <math>\Gamma</math> es finito, podría suceder que <math>\Gamma=\Gamma^{*}</math>. Ahora bien, si <math>\Gamma</math> es infinito, entonces <math>\Gamma^{*}</math> es más pequeño y, por tanto, hay muchas premisas en <math>\Gamma</math> "prescindibles", es decir, de las que no depende la validez del argumento.
La compacidad de la lógica de primer orden es una consecuencia de las propiedades de completud y corrección. Pues supongamos que <math>\Gamma\vDash A</math>. Por el teorema de completud, sabemos que <math>\Gamma\vdash A</math>. Ahora bien, dado que las demostraciones son finitas, la demostración emplea a lo sumo un número finito de oraciones <math>\Gamma^{*}\subseteq\Gamma</math>, de modo que <math>\Gamma^{*}\vdash A</math>. Por la corrección de nuestro sistema de demostración obtenemos <math>\Gamma^{*}\vDash A</math>.
La compacidad es de alguna manera la cara y la cruz de la lógica de primer orden. Es una consecuencia directa del teorema de completud que es, aparentemente, un aspecto positivo de la lógica de primer orden. La compacidad, sin embargo, impone limitaciones acerca de los conceptos que pueden expresarse en un lenguaje de primer orden, como la idea de finitud, y que juegan un papel importante en teorías matemáticas interesantes (ver 3.1). Este hecho muestra uno de los aspectos más interesantes e intrigantes de la lógica matemática: la proporción inversa que existe entre poder expresivo y capacidad de demostración.
'''Comentario 2.18'''
Una teoría, en términos generales, es un conjunto consistente de oraciones. La construcción de Henkin garantiza que cualquier teoría de un lenguaje de primer orden tiene un modelo (una interpretación donde todas las oraciones de la teoría son verdaderas). Los teoremas de Löwenheim-Skolem se refieren al ''tamaño'' de los modelos, donde el tamaño de un modelo <math>\langle\mathbb{U}, \mathbb{I}\rangle</math> es el tamaño de su universo <math>\mathbb{U}</math>.
Un conjunto es una colección de elementos y como tal tiene un determinado tamaño. Cuando un conjunto es finito, su tamaño viene expresado por un número natural. Sin embargo, ningún número natural expresa el tamaño de un conjunto infinito, pues lo característico de los números naturales es situarse a una distancia finita de 0. La idea de ''cardinal'' es la generalización de la noción de tamaño para conjuntos de cualquier tipo. El cardinal infinito más pequeño es el de los números naturales y suele ser representado como <math>\aleph_0</math> (escribiremos <math>|\mathbb{N}|=\aleph_0</math>). Dos conjuntos tienen el mismo cardinal cuando hay una correspondencia biunívoca entre ellos. En este sentido, el conjunto de los números naturales y el conjunto de los números racionales tienen el mismo tamaño, pero el conjunto de los números reales tiene un tamaño mayor (más sobre cardinales en (Zabalardo 2002, c. 6) y (Hedman 2006, 150-163).
En un lenguaje de primer orden podemos encontrar conjuntos de oraciones que ponen un ''límite por arriba'' al tamaño de sus modelos. Por ejemplo, la oración <math>\forall x\forall y\forall z(x\approx y\lor x\approx z)</math> puede ser verdadera en estructuras que tienen a lo sumo dos elementos. El Teorema de Löwenheim-Skolem ascendente nos dice que un conjunto de oraciones de un lenguaje de primer orden con un modelo infinito no puede poner un límite por arriba a sus modelos. El teorema es una consecuencia directa del Teorema de compacidad (detalles en Zabalardo 2002, 298 y Hedman 2006, 167).
En un lenguaje de primer orden podemos encontrar conjuntos de oraciones que ponen un ''límite por abajo'' al tamaño de sus modelos. Por ejemplo, la oración <math>\exists x\exists y\exists z(((x\not\approx y)\land(x\not\approx z))\land (y\not\approx z))</math> puede ser verdadera en estructuras con al menos tres elementos. La cardinalidad de un lenguaje de primer orden es el tamaño del conjunto de oraciones de ese lenguaje y depende directamente del tamaño del vocabulario no-lógico: si este es contable, la cardinalidad del lenguaje es enumerable, si tiene un cardinal mayor, tal será la cardinalidad del lenguaje. El Teorema de Löwenheim-Skolem descendente nos dice que un conjunto de oraciones de un lenguaje de primer orden no puede poner un límite por abajo a sus modelos mayor que la cardinalidad del lenguaje. Esto significa, por ejemplo, que la teoría axiomática de conjuntos <math>\mathsf{ZF}</math> tiene modelos contables (este hecho es conocido como ''Paradoja de Skolem'', Zabalardo 2002, 294).
La demostración del Teorema de Löwenheim-Skolem descendente tiene cierta complejidad debido principalmente a que envuelve nociones sobre cardinales infinitos. El teorema consiste en un procedimiento para, dado un conjunto de oraciones <math>\Gamma</math> y un modelo <math>\langle\mathbb{U}, \mathbb{I}\rangle</math>, "depurar" el universo de la interpretación sin variar el valor de verdad de las oraciones en <math>\Gamma</math>. El procedimiento requiere mantener la extensión de constantes y funciones, pero tomar únicamente un objeto (un "testigo") de <math>\mathbb{U}</math> para oraciones existencialmente cuantificadas verdaderas en <math>\langle\mathbb{U}, \mathbb{I}\rangle</math> (detalles en Zabalardo 2002, 292 y Hedman 2006, 168-170).
==Representación y axiomatización de la aritmética==
