Prefacio

Este libro es una introducción a la metalógica, dirigido especialmente a estudiantes de informática y filosofía. “Metalogic” se llama porque es la disciplina la que estudia la lógica misma. La lógica propiamente dicha se ocupa de cánones de inferencia válida, y su versión simbólica o formal presenta estos cánones utilizando lenguajes formales, como los de lógica proposicional y predicado, también conocida como lógica de primer orden. La metalógica investiga las propiedades de estos lenguajes, y de los cánones de inferencia correcta que los utilizan. Estudia temas como cómo dar sentido preciso a las expresiones de estos lenguajes formales, cómo justificar los cánones de inferencia válida, cuáles son las propiedades de diversos sistemas de prueba, incluyendo sus propiedades computacionales. Estas preguntas son importantes e interesantes por derecho propio, porque los lenguajes y sistemas de prueba investigados se aplican en muchas áreas diferentes —en matemáticas, filosofía, informática y lingüística, especialmente— pero también sirven como ejemplos de cómo estudiar los sistemas formales en general. Los lenguajes lógicos que estudiamos aquí no son los únicos que interesan a las personas. Por ejemplo, los lingüistas y filósofos están interesados en lenguajes que son mucho más complicados que los de la lógica proposicional y de primer orden, y los informáticos están interesados en otros tipos de lenguajes en conjunto, como los lenguajes de programación. Y los métodos que discutimos aquí —cómo dar semántica para las lenguas formales, cómo probar resultados sobre las lenguas formales, cómo investigar las propiedades de los lenguajes formales— también son aplicables en esos casos.

Como cualquier disciplina, tanto metalogic tiene un conjunto de resultados o hechos, como un almacén de métodos y técnicas, y este texto abarca ambos. Algunos estudiantes no necesitarán conocer algunos de los resultados que discutimos fuera de este curso, pero necesitarán y utilizarán los métodos que usamos para establecerlos. El teorema de Löwenheim-Skolem, digamos, no suele aparecer en la informática, sino que los métodos que utilizamos para demostrarlo sí. Por otro lado, muchos de los resultados que discutimos sí tienen relevancia para ciertos debates, digamos, en la filosofía de la ciencia y en la metafísica. Es posible que los estudiantes de filosofía no necesiten poder probar estos resultados fuera de este curso, pero sí necesitan entender cuáles son los resultados, y realmente solo entiendes estos resultados si has pensado en las definiciones y pruebas necesarias para establecerlos. Estas son, en parte, las razones por las que los resultados y los métodos tratados en este texto son recomendados de estudio —en algunos casos incluso requeridos— para estudiantes de informática y filosofía.

El material se divide en tres partes. La primera parte se ocupa de la teoría de los conjuntos. La lógica y la metalógica están históricamente conectadas muy estrechamente con lo que se llama los “fundamentos de las matemáticas”. Los fundamentos matemáticos tratan de cómo en última instancia los objetos matemáticos como enteros, racionales, y números reales, funciones, espacios, etc., deben ser entendidos. La teoría de conjuntos proporciona una respuesta (hay otras), por lo que la teoría de conjuntos y la lógica se han estudiado durante mucho tiempo lado a lado. Los conjuntos, las relaciones y las funciones también son omnipresentes en cualquier tipo de investigación formal, no solo en matemáticas sino también en informática y en algunos de los rincones más técnicos de la filosofía. Ciertamente, a los efectos de formular y probar resultados sobre la semántica y la teoría de la prueba de la lógica y el fundamento de la computabilidad es fundamental contar con un lenguaje en el que hacer esto. Por ejemplo, hablaremos de conjuntos de expresiones, relaciones de consecuencia y demostrabilidad, interpretaciones de símbolos predicados (que resultan ser relaciones), funciones computables y diversas relaciones entre y construcciones que utilizan estos. Será bueno tener símbolos abreviados para estos, y pensar en las propiedades generales de los conjuntos, las relaciones y las funciones para poder hacerlo. Si no estás acostumbrado a pensar matemáticamente y a formular pruebas matemáticas, entonces piensa en la primera parte de la teoría de conjuntos como un campo de entrenamiento: se darán todas las definiciones básicas, y vamos a dar pruebas cada vez más complicadas usándolas. Tenga en cuenta que comprender estas pruebas —y poder encontrarlas y formularlas usted mismo— es quizás más importante que comprender los resultados, y especialmente en la primera parte, y especialmente si eres nuevo en el pensamiento matemático, es importante que pienses a través de los ejemplos y problemas.

En la primera parte estableceremos un resultado importante, sin embargo. Este resultado, el teorema de Cantor, se basa en uno de los ejemplos más llamativos de análisis conceptual que se encuentran en cualquier parte de las ciencias, a saber, el análisis de Cantor del infinito. El infinito ha desconcertado a matemáticos y filósofos por igual durante siglos. Nadie sabía cómo pensarlo adecuadamente. Mucha gente incluso pensó que era un error pensarlo en absoluto, que la noción de un objeto infinito o colección infinita en sí misma era incoherente. Cantor convirtió el infinito en un tema con el que podemos trabajar coherentemente, y desarrolló toda una teoría de colecciones infinitas —y números infinitos con los que podemos medir los tamaños de colecciones infinitas— y demostró que hay diferentes niveles de infinito. Esta teoría de los números “transfinitos” es hermosa e intrincada, y no vamos a llegar muy lejos en ella; pero podremos demostrar que hay diferentes niveles de infinito, específicamente, que hay niveles “contables” e “incontables” de infinito. Este resultado tiene aplicaciones importantes, pero también es realmente el tipo de resultado que cualquier matemático, informático o filósofo que se precie debe conocer.

En la segunda parte pasamos a la lógica de primer orden. Definiremos el lenguaje de la lógica de primer orden y su semántica, es decir, qué son las estructuras de primer orden y cuándo una oración de lógica de primer orden es verdadera en una estructura. Esto nos permitirá hacer dos cosas importantes: (1) Podemos definir, con precisión matemática, cuando una oración es consecuencia lógica de otra. (2) También podemos considerar cómo las relaciones que conforman una estructura de primer orden son descriptas —caracterizadas— por las oraciones que son verdaderas en ellas. Esto en particular nos lleva a una discusión sobre el método axiomático, en el que se utilizan frases de lenguajes de primer orden para caracterizar ciertos tipos de estructuras. La teoría de la prueba nos ocupará a continuación, y consideraremos la versión original del cálculo secuente y deducción natural tal como lo definió Gerhard Gentzen en la década de 1930. (Su instructor puede optar por cubrir solo una, entonces cualquier referencia a “derivaciones” y “demostrabilidad” significará cualquier sistema que elija). La noción semántica de consecuencia y la noción sintáctica de demostrabilidad nos dan dos formas completamente diferentes de precisar la idea de que una oración puede seguir de algunas otras. Los teoremas de solidez e integridad vinculan estas dos caracterizaciones. En particular, probaremos el teorema de integridad de Gödel, que establece que siempre que una oración es una consecuencia semántica de algunas otras, ahí también es demostrable a partir de ellas. Una formulación equivalente es: si una colección de oraciones es consistente —en el sentido de que no se puede probar nada contradictorio a partir de ellas— entonces hay una estructura que las hace verdaderas todas.

La segunda formulación del teorema de integridad es quizás la más sorprendente. Alrededor de la época en que Gödel demostró este resultado (en 1929), el matemático alemán David Hilbert sostuvo la famosa opinión de que la consistencia (es decir, la libertad de la contradicción) es todo lo que requiere la existencia matemática. En otras palabras, siempre que un matemático pueda describir coherentemente una estructura o clase de estructuras, entonces debería tener derecho a creer en la existencia de tales estructuras. En su momento, a muchos les pareció absurda esta idea: solo porque se puede describir una estructura sin contradecirse a sí mismo, seguramente no se deduce que tal estructura realmente exista. Pero eso es exactamente lo que dice el teorema de integridad de Gödel. Además de este aspecto paradójico —y ciertamente filosóficamente intrigante—, el teorema de la completitud también tiene dos aplicaciones importantes que nos permiten probar más resultados sobre la existencia de estructuras que hacen ciertas oraciones dadas. Estos son la compacidad y los teoremas de Löwenheim-Skolem.

En la tercera parte, conectamos la lógica con la computabilidad. Nuevamente, hay una conexión histórica: David Hilbert se había planteado como un problema fundamental de lógica para encontrar un método mecánico que decidiera, de una frase dada de lógica, si tiene una prueba. Tal método existe, por supuesto, para la lógica proposicional: uno solo tiene que verificar todas las tablas de verdad, y como solo hay finitamente muchas de ellas, el método finalmente arroja una respuesta correcta. Un método tan sencillo no es posible para la lógica de primer orden, ya que el número de estructuras posibles es infinito (y las estructuras mismas pueden ser infinitas). Los logísticos estuvieron trabajando para encontrar métodos más ingeniosos durante años. Alonzo Church y Alan Turing finalmente establecieron que no existe tal método. Para ello, fue necesario primero proporcionar una definición precisa de lo que es un método mecánico en general. Si se hubiera propuesto un procedimiento de decisión, presumiblemente se habría reconocido como un método efectivo. Para probar que no existe un método efectivo, hay que definir primero el “método efectivo” y dar una prueba de imposibilidad a partir de esa definición. Esto es lo que hizo Turing: propuso la idea de una máquina Turing ¹ como modelo matemático de lo que un procedimiento mecánico puede, en principio, hacer. Este es otro ejemplo de un análisis conceptual de un concepto informal utilizando maquinaria matemática; y quizás sea del mismo orden de importancia para la informática que el análisis del infinito de Cantor para las matemáticas. Nuestra última gran empresa será la prueba de dos teoremas de imposibilidad: mostraremos que el llamado “problema de detención” no puede ser resuelto por máquinas Turing, y finalmente que el “problema de decisión” de Hilbert (por lógica) tampoco puede.

Este texto es matemático, en el sentido de que discutimos definiciones matemáticas y probamos nuestros resultados matemáticamente. Pero no es matemático en el sentido de que se necesita un amplio conocimiento de fondo matemático. Nada en este texto requiere conocimientos de álgebra, trigonometría o cálculo. Hemos hecho un esfuerzo especial para no requerir tampoco ninguna familiaridad con la forma en que funcionan las matemáticas: de hecho, parte del punto es desarrollar los tipos de habilidades de razonamiento y prueba necesarias para comprender y probar nuestros resultados. La organización del texto sigue la convención matemática, por una razón: estas convenciones se han desarrollado porque la claridad y la precisión son especialmente importantes, y así, por ejemplo, es crítico saber cuándo se afirma algo como conclusión de un argumento, se ofrece como razón para otra cosa, o tiene la intención de introducir un nuevo vocabulario. Entonces seguimos convenciones matemáticas y etiquetamos pasajes como “definiciones” si se utilizan para introducir nueva terminología o símbolos; y como “teoremas”, “proposiciones”, “lemmas” o “corolarios” cuando registramos un resultado o hallazgo. Aparte de estas convenciones, utilizaremos los métodos de prueba lógica que ya pueden ser familiares desde un primer curso lógico, y también haremos un uso extensivo del método de inducción para probar resultados. Dos capítulos del apéndice están dedicados a estos métodos de prueba.