3.1: Naïvely

Estamos en un punto de nuestras exploraciones donde hemos establecido un sistema deductivo particular, consistente en los axiomas lógicos y reglas de inferencia que planteamos en el último capítulo. El Teorema de la Solidez demostró que nuestro sistema deductivo preserva la verdad, en el sentido de que si hay una deducción\(\phi\) de\(\Sigma\), entonces\(\phi\) es cierto en cualquier modelo de\(\Sigma\). El Teorema de la Completitud, primer gran resultado de este capítulo, nos da lo contrario al Teorema de la Solidez. Entonces, cuando se combinen los dos resultados, tendremos esta equivalencia:

\[\Sigma \models \phi \: \text{if and only if} \: \Sigma \vdash \phi.\]

Ya hemos hecho un gran punto sobre el hecho de que nos gustaría estar seguros de que si nuestro sistema deductivo nos permite probar una declaración, nos gustaría que esa afirmación fuera cierta. Ciertamente, el contenido del Teorema de la Solidez es exactamente eso. Si\(\vdash \phi\), si hay una deducción\(\phi\) de solo los axiomas lógicos sin ningún supuesto adicional, entonces lo sabemos\(\models \phi\), así\(\phi\) es cierto en cada estructura con cada función de asignación. En la medida en que la práctica matemática informal de las pruebas cotidianas esté modelada por nuestro sistema formal de deducción, podemos estar seguros de que las cosas que probamos matemáticamente son ciertas.

Si la vida fuera duraznos y crema, también nos gustaría saber que podemos probar cualquier cosa que sea verdad. El Teorema de la Completitud es el resultado que afirma que nuestro sistema deductivo es así de fuerte. Entonces estarías tentado a concluir que, por ejemplo, somos capaces de probar cualquier afirmación de lógica de primer orden que sea una verdadera afirmación sobre los números naturales.

Desafortunadamente, esta conclusión se basa en una interpretación errónea de la afirmación del Teorema de la Completitud. Lo que probaremos es que nuestro sistema deductivo está completo, en el sentido de esta definición.

Definición 3.1.1. Se dice que un sistema deductivo que consiste en una colección de axiomas lógicos\(\Lambda\) y una colección de reglas de inferencia es completo si por cada conjunto de axiomas no lógicos\(\Sigma\) y cada\(\mathcal{L}\) fórmula\(\phi\),

\[\text{If} \: \Sigma \models \phi, \: \text{then} \: \Sigma \vdash \phi.\]

Lo que esto dice es que si\(\phi\) es una\(\mathcal{L}\) -fórmula que es cierta en cada modelo de\(\Sigma\), entonces habrá una deducción de\(\Sigma\) de\(\phi\). Entonces nuestra capacidad de demostrar\(\phi\) depende de\(\phi\) ser ciertos en cada modelo de\(\Sigma\). Así, si queremos poder utilizar\(\Sigma\) para probar cada afirmación verdadera sobre los números naturales, tenemos que ser capaces de encontrar un conjunto de axiomas no lógicos\(\Sigma\) tal que\(\Sigma \models \phi\) si y sólo si\(\phi\) es una declaración verdadera sobre los números naturales. Tendremos mucho más que decir sobre ese problema en los Capítulos 4, 5, 6 y 7.

La segunda parte del capítulo se refiere al teorema de la compacidad y a los teoremas de Löwenheim-Skolem. Utilizaremos estos resultados para investigar diversos tipos de estructuras matemáticas, incluyendo estructuras que son bastante sorprendentes.

En cierto sentido, hemos pasado mucho tiempo en los primeros capítulos de este libro desarrollando mucho vocabulario y estableciendo algunos resultados básicos. Ahora nos arremangaremos y obtendremos un par de teoremas que valen la pena. Es momento de comenzar a mostrar algo de la belleza y el poder, así como las limitaciones, de la lógica de primer orden.