La lógica matemática es el estudio de la lógica formal dentro de las matemáticas . Las principales subáreas incluyen la teoría de modelos , la teoría de la prueba , la teoría de conjuntos y la teoría de la recursividad (también conocida como teoría de la computabilidad). La investigación en lógica matemática comúnmente aborda las propiedades matemáticas de los sistemas formales de lógica, como su poder expresivo o deductivo. Sin embargo, también puede incluir usos de la lógica para caracterizar el razonamiento matemático correcto o para establecer fundamentos de las matemáticas .
Desde sus inicios, la lógica matemática ha contribuido y ha sido motivada por el estudio de los fundamentos de las matemáticas. Este estudio comenzó a finales del siglo XIX con el desarrollo de marcos axiomáticos para la geometría , la aritmética y el análisis . A principios del siglo XX, fue moldeado por el programa de David Hilbert para demostrar la coherencia de las teorías fundamentales. Los resultados de Kurt Gödel , Gerhard Gentzen y otros proporcionaron una resolución parcial al programa y aclararon los problemas involucrados en la prueba de coherencia. El trabajo en teoría de conjuntos demostró que casi todas las matemáticas ordinarias pueden formalizarse en términos de conjuntos, aunque hay algunos teoremas que no pueden demostrarse en sistemas de axiomas comunes para la teoría de conjuntos. El trabajo contemporáneo sobre los fundamentos de las matemáticas a menudo se centra en establecer qué partes de las matemáticas pueden formalizarse en sistemas formales particulares (como en las matemáticas inversas ) en lugar de tratar de encontrar teorías en las que se puedan desarrollar todas las matemáticas.
El Manual de Lógica Matemática [1] de 1977 hace una división aproximada de la lógica matemática contemporánea en cuatro áreas:
Además, en ocasiones el campo de la teoría de la complejidad computacional también se incluye como parte de la lógica matemática. [2] Cada área tiene un enfoque distinto, aunque muchas técnicas y resultados se comparten entre múltiples áreas. Las fronteras entre estos campos y las líneas que separan la lógica matemática y otros campos de las matemáticas no siempre son claras. El teorema de incompletitud de Gödel marca no sólo un hito en la teoría de la recursividad y la teoría de la prueba, sino que también ha llevado al teorema de Löb en la lógica modal. El método de forzado se emplea en la teoría de conjuntos, la teoría de modelos y la teoría de la recursividad, así como en el estudio de las matemáticas intuicionistas.
El campo matemático de la teoría de categorías utiliza muchos métodos axiomáticos formales e incluye el estudio de la lógica categórica , pero la teoría de categorías normalmente no se considera un subcampo de la lógica matemática. Debido a su aplicabilidad en diversos campos de las matemáticas, matemáticos como Saunders Mac Lane han propuesto la teoría de categorías como un sistema fundamental para las matemáticas, independiente de la teoría de conjuntos. Estos fundamentos utilizan toposes , que se asemejan a modelos generalizados de teoría de conjuntos que pueden emplear lógica clásica o no clásica.
La lógica matemática surgió a mediados del siglo XIX como un subcampo de las matemáticas, reflejando la confluencia de dos tradiciones: la lógica filosófica formal y las matemáticas. [3] "La lógica matemática, también llamada 'logística', 'lógica simbólica', ' álgebra de la lógica ' y, más recientemente, simplemente 'lógica formal', es el conjunto de teorías lógicas elaboradas a lo largo del último siglo XIX . Century con la ayuda de una notación artificial y un método rigurosamente deductivo." [4] Antes de este surgimiento, la lógica se estudiaba con la retórica , con los cálculos , [5] a través del silogismo , y con la filosofía . La primera mitad del siglo XX vio una explosión de resultados fundamentales, acompañada de un vigoroso debate sobre los fundamentos de las matemáticas.
Las teorías de la lógica se desarrollaron en muchas culturas de la historia, incluidas China , India , Grecia y el mundo islámico . Los métodos griegos, particularmente la lógica aristotélica (o el término lógica) tal como se encuentra en el Organon , encontraron amplia aplicación y aceptación en la ciencia y las matemáticas occidentales durante milenios. [6] Los estoicos , especialmente Crisipo , iniciaron el desarrollo de la lógica de predicados . En la Europa del siglo XVIII, matemáticos filosóficos, entre ellos Leibniz y Lambert , habían intentado tratar las operaciones de la lógica formal de forma simbólica o algebraica , pero sus trabajos permanecieron aislados y poco conocidos.
A mediados del siglo XIX, George Boole y luego Augustus De Morgan presentaron tratamientos matemáticos sistemáticos de la lógica. Su trabajo, basado en el trabajo de algebristas como George Peacock , amplió la doctrina aristotélica tradicional de la lógica hasta convertirla en un marco suficiente para el estudio de los fundamentos de las matemáticas . [7] En 1847 , Vatroslav Bertić realizó un trabajo sustancial sobre la algebraización de la lógica, independientemente de Boole. [8] Charles Sanders Peirce se basó más tarde en el trabajo de Boole para desarrollar un sistema lógico para relaciones y cuantificadores, que publicó en varios artículos entre 1870 y 1885.
Gottlob Frege presentó un desarrollo independiente de la lógica con cuantificadores en su Begriffsschrift , publicado en 1879, una obra generalmente considerada como un punto de inflexión en la historia de la lógica. Sin embargo, el trabajo de Frege permaneció oscuro hasta que Bertrand Russell comenzó a promoverlo hacia el cambio de siglo. La notación bidimensional que desarrolló Frege nunca fue adoptada ampliamente y no se utiliza en los textos contemporáneos.
De 1890 a 1905, Ernst Schröder publicó Vorlesungen über die Algebra der Logik en tres volúmenes. Este trabajo resumió y amplió el trabajo de Boole, De Morgan y Peirce, y fue una referencia integral a la lógica simbólica tal como se entendía a finales del siglo XIX.
La preocupación por que las matemáticas no se hubieran construido sobre una base adecuada condujo al desarrollo de sistemas axiomáticos para áreas fundamentales de las matemáticas como la aritmética, el análisis y la geometría.
En lógica, el término aritmética hace referencia a la teoría de los números naturales . Giuseppe Peano [9] publicó un conjunto de axiomas para aritmética que llegó a llevar su nombre ( Axiomas de Peano ), utilizando una variación del sistema lógico de Boole y Schröder pero añadiendo cuantificadores. Peano desconocía el trabajo de Frege en ese momento. Casi al mismo tiempo, Richard Dedekind demostró que los números naturales se caracterizan únicamente por sus propiedades de inducción . Dedekind propuso una caracterización diferente, que carecía del carácter lógico formal de los axiomas de Peano. [10] El trabajo de Dedekind, sin embargo, demostró que los teoremas eran inaccesibles en el sistema de Peano, incluida la unicidad del conjunto de números naturales (hasta el isomorfismo) y las definiciones recursivas de suma y multiplicación a partir de la función sucesora y la inducción matemática.
A mediados del siglo XIX, se conocieron los defectos de los axiomas geométricos de Euclides. [11] Además de la independencia del postulado de las paralelas , establecido por Nikolai Lobachevsky en 1826, [12] los matemáticos descubrieron que ciertos teoremas que Euclides daba por sentados no eran en realidad demostrables a partir de sus axiomas. Entre ellos está el teorema de que una línea contiene al menos dos puntos, o que círculos del mismo radio cuyos centros están separados por ese radio deben cruzarse. Hilbert [13] desarrolló un conjunto completo de axiomas para la geometría , basándose en trabajos anteriores de Pasch. [14] El éxito en la axiomatización de la geometría motivó a Hilbert a buscar axiomatizaciones completas de otras áreas de las matemáticas, como los números naturales y la recta real . Esta resultaría ser un área importante de investigación en la primera mitad del siglo XX.
El siglo XIX vio grandes avances en la teoría del análisis real , incluidas las teorías de la convergencia de funciones y las series de Fourier . Matemáticos como Karl Weierstrass comenzaron a construir funciones que ampliaban la intuición, como funciones continuas no diferenciables en ninguna parte . Las concepciones anteriores de una función como regla de cálculo, o una gráfica suave, ya no eran adecuadas. Weierstrass comenzó a defender la aritmetización del análisis , que buscaba axiomatizar el análisis utilizando propiedades de los números naturales. La definición moderna (ε, δ) de funciones límite y continuas ya fue desarrollada por Bolzano en 1817, [15] pero seguía siendo relativamente desconocida.Cauchy en 1821 definió la continuidad en términos de infinitesimales (ver Cours d'Analyse, página 34). En 1858, Dedekind propuso una definición de los números reales en términos de cortes de Dedekind de números racionales, definición todavía empleada en los textos contemporáneos. [dieciséis]
Georg Cantor desarrolló los conceptos fundamentales de la teoría de conjuntos infinitos. Sus primeros resultados desarrollaron la teoría de la cardinalidad y demostraron que los números reales y naturales tienen cardinalidades diferentes. [17] Durante los siguientes veinte años, Cantor desarrolló una teoría de los números transfinitos en una serie de publicaciones. En 1891, publicó una nueva prueba de la incontable de los números reales que introducía el argumento de la diagonal , y utilizó este método para demostrar el teorema de Cantor de que ningún conjunto puede tener la misma cardinalidad que su conjunto potencia . Cantor creía que todo conjunto podía estar bien ordenado , pero no pudo presentar una prueba de este resultado, dejándolo como un problema abierto en 1895. [18]
En las primeras décadas del siglo XX, las principales áreas de estudio fueron la teoría de conjuntos y la lógica formal. El descubrimiento de paradojas en la teoría informal de conjuntos hizo que algunos se preguntaran si las matemáticas en sí mismas son inconsistentes y buscaran pruebas de coherencia.
En 1900, Hilbert formuló una famosa lista de 23 problemas para el próximo siglo. Los dos primeros debían resolver la hipótesis del continuo y probar la consistencia de la aritmética elemental, respectivamente; el décimo era producir un método que pudiera decidir si una ecuación polinómica multivariante sobre números enteros tiene solución. El trabajo posterior para resolver estos problemas moldeó la dirección de la lógica matemática, al igual que el esfuerzo por resolver el Entscheidungsproblem de Hilbert , planteado en 1928. Este problema requería un procedimiento que decidiera, dado un enunciado matemático formalizado, si el enunciado es verdadero o falso.
Ernst Zermelo demostró que cada conjunto puede estar bien ordenado , un resultado que Georg Cantor no había podido obtener. [19] Para lograr la prueba, Zermelo introdujo el axioma de elección , que generó acalorados debates e investigaciones entre los matemáticos y los pioneros de la teoría de conjuntos. La crítica inmediata al método llevó a Zermelo a publicar una segunda exposición de su resultado, abordando directamente las críticas a su prueba. [20] Este artículo condujo a la aceptación general del axioma de elección en la comunidad matemática.
El escepticismo sobre el axioma de elección se vio reforzado por paradojas recientemente descubiertas en la ingenua teoría de conjuntos . Cesare Burali-Forti [21] fue el primero en plantear una paradoja: la paradoja de Burali-Forti muestra que la colección de todos los números ordinales no puede formar un conjunto. Muy poco después, Bertrand Russell descubrió la paradoja de Russell en 1901, y Jules Richard descubrió la paradoja de Richard . [22]
Zermelo proporcionó el primer conjunto de axiomas para la teoría de conjuntos. [23] Estos axiomas, junto con el axioma adicional de reemplazo propuesto por Abraham Fraenkel , ahora se denominan teoría de conjuntos de Zermelo-Fraenkel (ZF). Los axiomas de Zermelo incorporaron el principio de limitación de tamaño para evitar la paradoja de Russell.
En 1910 se publicó el primer volumen de Principia Mathematica de Russell y Alfred North Whitehead . Este trabajo fundamental desarrolló la teoría de funciones y cardinalidad en un marco completamente formal de teoría de tipos , que Russell y Whitehead desarrollaron en un esfuerzo por evitar las paradojas. Principia Mathematica se considera una de las obras más influyentes del siglo XX, aunque el marco de la teoría de tipos no resultó popular como teoría fundamental de las matemáticas. [24]
Fraenkel [25] demostró que el axioma de elección no puede demostrarse a partir de los axiomas de la teoría de conjuntos de Zermelo con urelementos . Un trabajo posterior de Paul Cohen [26] demostró que no es necesaria la adición de urelementos y que el axioma de elección no es demostrable en ZF. La prueba de Cohen desarrolló el método del forzamiento , que ahora es una herramienta importante para establecer resultados de independencia en la teoría de conjuntos. [27]
Leopold Löwenheim [28] y Thoralf Skolem [29] obtuvieron el teorema de Löwenheim-Skolem , que dice que la lógica de primer orden no puede controlar las cardinalidades de estructuras infinitas. Skolem se dio cuenta de que este teorema se aplicaría a formalizaciones de primer orden de la teoría de conjuntos, y que implica que cualquier formalización de este tipo tiene un modelo contable . Este hecho contradictorio se conoció como la paradoja de Skolem .
En su tesis doctoral, Kurt Gödel demostró el teorema de completitud , que establece una correspondencia entre sintaxis y semántica en lógica de primer orden. [30] Gödel utilizó el teorema de completitud para demostrar el teorema de compacidad , demostrando la naturaleza finita de la consecuencia lógica de primer orden . Estos resultados ayudaron a establecer la lógica de primer orden como la lógica dominante utilizada por los matemáticos.
En 1931, Gödel publicó Sobre las proposiciones formalmente indecidibles de los Principia Mathematica y sistemas relacionados , que demostraba lo incompleto (en un significado diferente de la palabra) de todas las teorías de primer orden suficientemente fuertes y efectivas. Este resultado, conocido como teorema de incompletitud de Gödel , establece severas limitaciones a los fundamentos axiomáticos de las matemáticas, asestando un fuerte golpe al programa de Hilbert. Mostró la imposibilidad de proporcionar una prueba de coherencia de la aritmética dentro de cualquier teoría formal de la aritmética. Hilbert, sin embargo, no reconoció la importancia del teorema de incompletitud durante algún tiempo. [a]
El teorema de Gödel muestra que no se puede obtener una prueba de consistencia de cualquier sistema de axiomas suficientemente fuerte y efectivo en el sistema mismo, si el sistema es consistente, ni en ningún sistema más débil. Esto deja abierta la posibilidad de pruebas de consistencia que no pueden formalizarse dentro del sistema que consideran. Gentzen demostró la consistencia de la aritmética utilizando un sistema finitista junto con un principio de inducción transfinita . [31] El resultado de Gentzen introdujo las ideas de eliminación de cortes y ordinales de la teoría de la prueba , que se convirtieron en herramientas clave en la teoría de la prueba. Gödel dio una prueba de consistencia diferente, que reduce la consistencia de la aritmética clásica a la de la aritmética intuicionista en tipos superiores. [32]
El primer libro de texto sobre lógica simbólica para el profano fue escrito por Lewis Carroll , [33] autor de Las aventuras de Alicia en el país de las maravillas , en 1896. [34]
Alfred Tarski desarrolló los fundamentos de la teoría de modelos .
A partir de 1935, un grupo de destacados matemáticos colaboraron bajo el seudónimo de Nicolas Bourbaki para publicar Éléments de mathématique , una serie de textos enciclopédicos de matemáticas. Estos textos, escritos en un estilo austero y axiomático, enfatizaban una presentación rigurosa y fundamentos de teoría de conjuntos. La terminología acuñada por estos textos, como las palabras biyección , inyección y sobreyección , y los fundamentos de la teoría de conjuntos que emplearon los textos, fueron ampliamente adoptados en todas las matemáticas.
El estudio de la computabilidad llegó a conocerse como teoría de la recursividad o teoría de la computabilidad , porque las primeras formalizaciones de Gödel y Kleene se basaban en definiciones recursivas de funciones. [b] Cuando se demostró que estas definiciones eran equivalentes a la formalización de Turing que involucraba las máquinas de Turing , quedó claro que se había descubierto un nuevo concepto, la función computable , y que esta definición era lo suficientemente sólida como para admitir numerosas caracterizaciones independientes. En su trabajo sobre los teoremas de incompletitud de 1931, Gödel carecía de un concepto riguroso de sistema formal eficaz; Inmediatamente se dio cuenta de que las nuevas definiciones de computabilidad podrían usarse para este propósito, permitiéndole enunciar los teoremas de incompletitud en general que solo podían estar implícitos en el artículo original.
Stephen Cole Kleene y Emil Leon Post obtuvieron numerosos resultados en la teoría de la recursión en la década de 1940 . Kleene [35] introdujo los conceptos de computabilidad relativa, presagiados por Turing, [36] y la jerarquía aritmética . Más tarde, Kleene generalizó la teoría de la recursión a funcionales de orden superior. Kleene y Georg Kreisel estudiaron versiones formales de las matemáticas intuicionistas, particularmente en el contexto de la teoría de la prueba.
En esencia, la lógica matemática se ocupa de conceptos matemáticos expresados mediante sistemas lógicos formales . Estos sistemas, aunque difieren en muchos detalles, comparten la propiedad común de considerar sólo expresiones en un lenguaje formal fijo . Los sistemas de lógica proposicional y lógica de primer orden son los más estudiados en la actualidad, debido a su aplicabilidad a los fundamentos de las matemáticas y a sus deseables propiedades teóricas de prueba. [c] También se estudian lógicas clásicas más fuertes, como la lógica de segundo orden o la lógica infinitaria , junto con lógicas no clásicas como la lógica intuicionista .
La lógica de primer orden es un sistema formal particular de lógica . Su sintaxis involucra sólo expresiones finitas como fórmulas bien formadas , mientras que su semántica se caracteriza por la limitación de todos los cuantificadores a un dominio fijo del discurso .
Los primeros resultados de la lógica formal establecieron limitaciones de la lógica de primer orden. El teorema de Löwenheim-Skolem (1919) demostró que si un conjunto de oraciones en un lenguaje contable de primer orden tiene un modelo infinito, entonces tiene al menos un modelo de cada cardinalidad infinita. Esto demuestra que es imposible que un conjunto de axiomas de primer orden caracterice los números naturales, los números reales o cualquier otra estructura infinita hasta el isomorfismo . Como el objetivo de los primeros estudios fundamentales era producir teorías axiomáticas para todas las partes de las matemáticas, esta limitación era particularmente marcada.
El teorema de completitud de Gödel estableció la equivalencia entre las definiciones semánticas y sintácticas de consecuencia lógica en lógica de primer orden. [30] Muestra que si una oración particular es verdadera en cada modelo que satisface un conjunto particular de axiomas, entonces debe haber una deducción finita de la oración a partir de los axiomas. El teorema de la compacidad apareció por primera vez como un lema en la demostración del teorema de completitud de Gödel, y pasaron muchos años antes de que los lógicos captaran su importancia y comenzaran a aplicarlo de forma rutinaria. Dice que un conjunto de oraciones tiene un modelo si y sólo si cada subconjunto finito tiene un modelo, o en otras palabras, que un conjunto inconsistente de fórmulas debe tener un subconjunto finito inconsistente. Los teoremas de completitud y compacidad permiten un análisis sofisticado de las consecuencias lógicas en la lógica de primer orden y el desarrollo de la teoría de modelos , y son una razón clave para la prominencia de la lógica de primer orden en matemáticas.
Los teoremas de incompletitud de Gödel establecen límites adicionales a las axiomatizaciones de primer orden. [37] El primer teorema de incompletitud establece que para cualquier sistema lógico consistente, efectivamente dado (definido a continuación) que sea capaz de interpretar la aritmética, existe una afirmación que es verdadera (en el sentido de que es válida para los números naturales) pero no demostrable. dentro de ese sistema lógico (y que de hecho puede fallar en algunos modelos de aritmética no estándar que pueden ser consistentes con el sistema lógico). Por ejemplo, en todo sistema lógico capaz de expresar los axiomas de Peano , la oración de Gödel es válida para los números naturales pero no puede demostrarse.
Aquí se dice que un sistema lógico está efectivamente dado si es posible decidir, dada cualquier fórmula en el lenguaje del sistema, si la fórmula es un axioma, y uno que puede expresar los axiomas de Peano se llama "suficientemente fuerte". Cuando se aplica a la lógica de primer orden, el primer teorema de incompletitud implica que cualquier teoría de primer orden suficientemente fuerte, consistente y efectiva tiene modelos que no son elementalmente equivalentes , una limitación más fuerte que la establecida por el teorema de Löwenheim-Skolem. El segundo teorema de incompletitud establece que ningún sistema de axiomas aritmético suficientemente fuerte, consistente y eficaz puede demostrar su propia coherencia, lo que se ha interpretado en el sentido de que muestra que no se puede alcanzar el programa de Hilbert .
Se estudian muchas lógicas además de la lógica de primer orden. Estos incluyen lógicas infinitas , que permiten que las fórmulas proporcionen una cantidad infinita de información, y lógicas de orden superior , que incluyen una parte de la teoría de conjuntos directamente en su semántica.
La lógica infinita mejor estudiada es . En esta lógica, los cuantificadores sólo pueden anidarse en profundidades finitas, como en la lógica de primer orden, pero las fórmulas pueden tener conjunciones y disyunciones finitas o infinitas contablemente dentro de ellas. Así, por ejemplo, es posible decir que un objeto es un número entero usando una fórmula como
La lógica de orden superior permite la cuantificación no sólo de elementos del dominio del discurso , sino también de subconjuntos del dominio del discurso, conjuntos de dichos subconjuntos y otros objetos de tipo superior. La semántica se define de modo que, en lugar de tener un dominio separado para cada cuantificador de tipo superior, los cuantificadores abarcan todos los objetos del tipo apropiado. Las lógicas estudiadas antes del desarrollo de la lógica de primer orden, por ejemplo la lógica de Frege, tenían aspectos de teoría de conjuntos similares. Aunque las lógicas de orden superior son más expresivas y permiten axiomatizaciones completas de estructuras como los números naturales, no satisfacen análogos de los teoremas de completitud y compacidad de la lógica de primer orden y, por lo tanto, son menos susceptibles de análisis teóricos de prueba.
Otro tipo de lógicas sonLógicas de punto fijo que permitendefiniciones inductivas, como las que se escriben parafunciones recursivas primitivas.
Se puede definir formalmente una extensión de la lógica de primer orden, una noción que abarca todas las lógicas de esta sección porque se comportan como lógica de primer orden en ciertos aspectos fundamentales, pero que no abarca todas las lógicas en general; por ejemplo, no abarca la lógica intuicionista, lógica modal o difusa .
El teorema de Lindström implica que la única extensión de la lógica de primer orden que satisface tanto el teorema de compacidad como el teorema descendente de Löwenheim-Skolem es la lógica de primer orden.
Las lógicas modales incluyen operadores modales adicionales, como un operador que establece que una fórmula particular no sólo es verdadera, sino necesariamente verdadera. Aunque la lógica modal no se utiliza a menudo para axiomatizar las matemáticas, se ha utilizado para estudiar las propiedades de la demostrabilidad de primer orden [38] y el forzamiento de la teoría de conjuntos. [39]
Heyting desarrolló la lógica intuicionista para estudiar el programa de intuicionismo de Brouwer, en el que el propio Brouwer evitaba la formalización. La lógica intuicionista específicamente no incluye la ley del tercero excluido , que establece que cada oración es verdadera o su negación es verdadera. El trabajo de Kleene con la teoría de la prueba de la lógica intuicionista demostró que se puede recuperar información constructiva a partir de pruebas intuicionistas. Por ejemplo, cualquier función demostrablemente total en aritmética intuicionista es computable ; esto no es cierto en las teorías clásicas de la aritmética como la aritmética de Peano .
La lógica algebraica utiliza los métodos del álgebra abstracta para estudiar la semántica de la lógica formal. Un ejemplo fundamental es el uso de álgebras booleanas para representar valores de verdad en la lógica proposicional clásica y el uso de álgebras de Heyting para representar valores de verdad en la lógica proposicional intuicionista. Las lógicas más sólidas, como la lógica de primer orden y la lógica de orden superior, se estudian utilizando estructuras algebraicas más complicadas, como las álgebras cilíndricas .
La teoría de conjuntos es el estudio de los conjuntos , que son colecciones abstractas de objetos. Muchas de las nociones básicas, como los números ordinales y cardinales, fueron desarrolladas informalmente por Cantor antes de que se desarrollaran las axiomatizaciones formales de la teoría de conjuntos. La primera axiomatización de este tipo , debida a Zermelo, [23] se amplió ligeramente para convertirse en la teoría de conjuntos de Zermelo-Fraenkel (ZF), que ahora es la teoría fundamental más utilizada para las matemáticas.
Se han propuesto otras formalizaciones de la teoría de conjuntos, incluida la teoría de conjuntos de von Neumann-Bernays-Gödel (NBG), la teoría de conjuntos de Morse-Kelley (MK) y New Foundations (NF). De estos, ZF, NBG y MK son similares al describir una jerarquía acumulativa de conjuntos. New Foundations adopta un enfoque diferente; permite objetos como el conjunto de todos los conjuntos a costa de restricciones en sus axiomas de existencia de conjuntos. El sistema de la teoría de conjuntos de Kripke-Platek está estrechamente relacionado con la teoría de la recursividad generalizada.
Dos declaraciones famosas en la teoría de conjuntos son el axioma de elección y la hipótesis del continuo . Fraenkel demostró que el axioma de elección, enunciado por primera vez por Zermelo [19], es independiente de ZF, [25] pero ha llegado a ser ampliamente aceptado por los matemáticos. Afirma que dada una colección de conjuntos no vacíos hay un único conjunto C que contiene exactamente un elemento de cada conjunto de la colección. Se dice que el conjunto C "elige" un elemento de cada conjunto de la colección. Si bien algunos consideran obvia la capacidad de hacer tal elección, dado que cada conjunto de la colección no está vacío, la falta de una regla general y concreta mediante la cual se pueda hacer la elección hace que el axioma no sea constructivo. Stefan Banach y Alfred Tarski demostraron que el axioma de elección se puede utilizar para descomponer una bola sólida en un número finito de piezas que luego se pueden reorganizar, sin escala, para formar dos bolas sólidas del tamaño original. [40] Este teorema, conocido como paradoja de Banach-Tarski , es uno de los muchos resultados contrarios a la intuición del axioma de elección.
La hipótesis del continuo, propuesta por primera vez como una conjetura por Cantor, fue incluida por David Hilbert como uno de sus 23 problemas en 1900. Gödel demostró que la hipótesis del continuo no puede ser refutada a partir de los axiomas de la teoría de conjuntos de Zermelo-Fraenkel (con o sin el axioma de elección), desarrollando el universo construible de la teoría de conjuntos en el que debe mantenerse la hipótesis del continuo. En 1963, Paul Cohen demostró que la hipótesis del continuo no puede probarse a partir de los axiomas de la teoría de conjuntos de Zermelo-Fraenkel. [26] Sin embargo, este resultado de independencia no resolvió completamente la pregunta de Hilbert, ya que es posible que nuevos axiomas para la teoría de conjuntos puedan resolver la hipótesis. W. Hugh Woodin ha realizado trabajos recientes en este sentido , aunque su importancia aún no está clara. [41]
La investigación contemporánea en teoría de conjuntos incluye el estudio de los grandes cardinales y la determinabilidad . Los cardinales grandes son números cardinales con propiedades particulares tan fuertes que la existencia de tales cardinales no se puede demostrar en ZFC. La existencia del cardenal grande más pequeño típicamente estudiado, un cardenal inaccesible , ya implica la consistencia de ZFC. A pesar de que los cardenales grandes tienen una cardinalidad extremadamente alta , su existencia tiene muchas ramificaciones para la estructura de la línea real. La determinación se refiere a la posible existencia de estrategias ganadoras para determinados juegos de dos jugadores (se dice que los juegos están determinados ). La existencia de estas estrategias implica propiedades estructurales de la línea real y otros espacios polacos .
La teoría de modelos estudia los modelos de varias teorías formales. Aquí una teoría es un conjunto de fórmulas con una lógica y firma formal particular , mientras que un modelo es una estructura que da una interpretación concreta de la teoría. La teoría de modelos está estrechamente relacionada con el álgebra universal y la geometría algebraica , aunque los métodos de la teoría de modelos se centran más en consideraciones lógicas que en esos campos.
Al conjunto de todos los modelos de una teoría particular se le llama clase elemental ; La teoría de modelos clásica busca determinar las propiedades de los modelos en una clase elemental particular, o determinar si ciertas clases de estructuras forman clases elementales.
El método de eliminación de cuantificadores se puede utilizar para demostrar que los conjuntos definibles en teorías particulares no pueden ser demasiado complicados. Tarski estableció la eliminación de cuantificadores para campos reales cerrados , un resultado que también muestra que la teoría del campo de números reales es decidible . [42] También señaló que sus métodos eran igualmente aplicables a campos algebraicamente cerrados de característica arbitraria. Un subcampo moderno que se desarrolla a partir de esto se ocupa de las estructuras mínimas .
El teorema de categoricidad de Morley , demostrado por Michael D. Morley , [43] establece que si una teoría de primer orden en un lenguaje contable es categórica en alguna cardinalidad incontable, es decir, todos los modelos de esta cardinalidad son isomórficos, entonces es categórica en todas las cardinalidades incontables. .
Una consecuencia trivial de la hipótesis del continuo es que una teoría completa con menos de un continuo de muchos modelos contables no isomórficos sólo puede tener muchos contables. La conjetura de Vaught , que lleva el nombre de Robert Lawson Vaught , dice que esto es cierto incluso independientemente de la hipótesis del continuo. Se han establecido muchos casos especiales de esta conjetura.
La teoría de la recursión , también llamada teoría de la computabilidad , estudia las propiedades de las funciones computables y los grados de Turing , que dividen las funciones no computables en conjuntos que tienen el mismo nivel de incomputabilidad. La teoría de la recursividad también incluye el estudio de la computabilidad y definibilidad generalizadas. La teoría de la recursión surgió del trabajo de Rózsa Péter , Alonzo Church y Alan Turing en la década de 1930, que fue ampliada en gran medida por Kleene y Post en la década de 1940. [44]
La teoría de la recursividad clásica se centra en la computabilidad de funciones desde los números naturales hasta los números naturales. Los resultados fundamentales establecen una clase canónica y robusta de funciones computables con numerosas caracterizaciones equivalentes e independientes utilizando máquinas de Turing , cálculo λ y otros sistemas. Los resultados más avanzados se refieren a la estructura de los grados de Turing y al entramado de conjuntos recursivamente enumerables .
La teoría de la recursividad generalizada extiende las ideas de la teoría de la recursividad a cálculos que ya no son necesariamente finitos. Incluye el estudio de la computabilidad en tipos superiores, así como áreas como la teoría hiperaritmética y la teoría de la recursividad α .
La investigación contemporánea en teoría de la recursividad incluye el estudio de aplicaciones como la aleatoriedad algorítmica , la teoría de modelos computables y las matemáticas inversas , así como nuevos resultados en la teoría de la recursividad pura.
Un subcampo importante de la teoría de la recursividad estudia la insolubilidad algorítmica; un problema de decisión o un problema de función no tiene solución algorítmica si no existe un algoritmo computable posible que devuelva la respuesta correcta para todas las entradas legales del problema. Los primeros resultados sobre la insolubilidad, obtenidos de forma independiente por Church y Turing en 1936, mostraron que el Entscheidungsproblem es algorítmicamente irresoluble. Turing demostró esto al establecer la insolubilidad del problema de la detención , un resultado con implicaciones de largo alcance tanto en la teoría de la recursión como en la informática.
Hay muchos ejemplos conocidos de problemas indecidibles de las matemáticas ordinarias. Pyotr Novikov en 1955 y de forma independiente W. Boone en 1959 demostraron que el problema verbal para grupos no tenía solución algorítmica. El problema del castor ocupado , desarrollado por Tibor Radó en 1962, es otro ejemplo bien conocido.
El décimo problema de Hilbert pedía un algoritmo para determinar si una ecuación polinómica multivariada con coeficientes enteros tiene una solución en números enteros. Julia Robinson , Martin Davis y Hilary Putnam lograron avances parciales . La insolubilidad algorítmica del problema fue demostrada por Yuri Matiyasevich en 1970. [45]
La teoría de la prueba es el estudio de pruebas formales en varios sistemas de deducción lógica. Estas pruebas se representan como objetos matemáticos formales, facilitando su análisis mediante técnicas matemáticas. Comúnmente se consideran varios sistemas de deducción, incluidos los sistemas de deducción estilo Hilbert , los sistemas de deducción natural y el cálculo secuente desarrollado por Gentzen.
El estudio de las matemáticas constructivas , en el contexto de la lógica matemática, incluye el estudio de sistemas en lógica no clásica como la lógica intuicionista, así como el estudio de sistemas predicativos . Uno de los primeros defensores del predicativismo fue Hermann Weyl , quien demostró que es posible desarrollar una gran parte del análisis real utilizando únicamente métodos predicativos. [46]
Debido a que las pruebas son completamente finitas, mientras que la verdad en una estructura no lo es, es común que el trabajo en matemáticas constructivas enfatice la demostrabilidad. La relación entre la demostrabilidad en sistemas clásicos (o no constructivos) y la demostrabilidad en sistemas intuicionistas (o constructivos, respectivamente) es de particular interés. Resultados como la traducción negativa de Gödel-Gentzen muestran que es posible incorporar (o traducir ) la lógica clásica en la lógica intuicionista, permitiendo que algunas propiedades de las pruebas intuicionistas se transfieran nuevamente a las pruebas clásicas.
Los desarrollos recientes en la teoría de la prueba incluyen el estudio de la extracción de pruebas por Ulrich Kohlenbach y el estudio de los ordinales de la teoría de la prueba por Michael Rathjen.
"La lógica matemática se ha aplicado con éxito no sólo a las matemáticas y sus fundamentos ( G. Frege , B. Russell , D. Hilbert , P. Bernays , H. Scholz , R. Carnap , S. Lesniewski , T. Skolem ), sino también a la física (R. Carnap, A. Dittrich, B. Russell, CE Shannon , AN Whitehead , H. Reichenbach , P. Fevrier), a la biología ( JH Woodger , A. Tarski ), a la psicología ( FB Fitch , CG Hempel ) , al derecho y la moral ( K. Menger , U. Klug, P. Oppenheim), a la economía ( J. Neumann , O. Morgenstern ), a las cuestiones prácticas ( EC Berkeley , E. Stamm) e incluso a la metafísica (J. [Jan] Salamucha, H. Scholz, JM Bochenski ) Sus aplicaciones a la historia de la lógica han demostrado ser extremadamente fructíferas ( J. Lukasiewicz , H. Scholz, B. Mates , A. Becker, E. Moody , J. Salamucha, K . Duerr, Z. Jordan, P. Boehner , JM Bochenski, S. [Stanislaw] T. Schayer, D. Ingalls )." [47] "También se han hecho aplicaciones a la teología (F. Drewnowski, J. Salamucha, I. Thomas)". [47]
El estudio de la teoría de la computabilidad en informática está estrechamente relacionado con el estudio de la computabilidad en lógica matemática. Sin embargo, hay una diferencia de énfasis. Los científicos informáticos a menudo se centran en lenguajes de programación concretos y en la computabilidad factible , mientras que los investigadores en lógica matemática a menudo se centran en la computabilidad como concepto teórico y en la no computabilidad.
La teoría de la semántica de los lenguajes de programación está relacionada con la teoría de modelos , al igual que la verificación de programas (en particular, la verificación de modelos ). La correspondencia Curry-Howard entre pruebas y programas se relaciona con la teoría de la prueba , especialmente con la lógica intuicionista . Los cálculos formales como el cálculo lambda y la lógica combinatoria se estudian ahora como lenguajes de programación idealizados .
La informática también contribuye a las matemáticas mediante el desarrollo de técnicas para la verificación automática o incluso la búsqueda de pruebas, como la demostración automatizada de teoremas y la programación lógica .
La teoría descriptiva de la complejidad relaciona la lógica con la complejidad computacional . El primer resultado significativo en esta área, el teorema de Fagin (1974) estableció que la NP es precisamente el conjunto de lenguajes expresables mediante oraciones de lógica existencial de segundo orden .
En el siglo XIX, los matemáticos se dieron cuenta de las lagunas e inconsistencias lógicas en su campo. Se demostró que los axiomas de Euclides para la geometría, que se habían enseñado durante siglos como ejemplo del método axiomático, estaban incompletos. El uso de infinitesimales y la definición misma de función se pusieron en duda en el análisis, a medida que se descubrieron ejemplos patológicos como la función continua no diferenciable en ninguna parte de Weierstrass.
El estudio de Cantor de conjuntos infinitos arbitrarios también generó críticas. Leopold Kronecker afirmó la famosa frase: "Dios hizo los números enteros; todo lo demás es obra del hombre", respaldando un retorno al estudio de objetos finitos y concretos en matemáticas. Aunque el argumento de Kronecker fue defendido por los constructivistas del siglo XX, la comunidad matemática en su conjunto los rechazó. David Hilbert argumentó a favor del estudio del infinito, diciendo: "Nadie nos expulsará del Paraíso que Cantor ha creado".
Los matemáticos comenzaron a buscar sistemas de axiomas que pudieran usarse para formalizar gran parte de las matemáticas. Además de eliminar la ambigüedad de términos previamente ingenuos como función, se esperaba que esta axiomatización permitiera pruebas de coherencia. En el siglo XIX, el principal método para demostrar la coherencia de un conjunto de axiomas era proporcionar un modelo para ello. Así, por ejemplo, se puede demostrar que la geometría no euclidiana es consistente definiendo punto como un punto en una esfera fija y línea como un círculo máximo en la esfera. La estructura resultante, un modelo de geometría elíptica , satisface los axiomas de la geometría plana excepto el postulado de las paralelas.
Con el desarrollo de la lógica formal, Hilbert preguntó si sería posible probar que un sistema de axiomas es consistente analizando la estructura de posibles pruebas en el sistema y mostrando a través de este análisis que es imposible probar una contradicción. Esta idea llevó al estudio de la teoría de la prueba . Además, Hilbert propuso que el análisis debería ser enteramente concreto, utilizando el término finitario para referirse a los métodos que permitiría pero sin definirlos con precisión. Este proyecto, conocido como programa de Hilbert , se vio seriamente afectado por los teoremas de incompletitud de Gödel, que muestran que la consistencia de las teorías formales de la aritmética no puede establecerse utilizando métodos formalizables en esas teorías. Gentzen demostró que es posible producir una prueba de la consistencia de la aritmética en un sistema finito aumentado con axiomas de inducción transfinita , y las técnicas que desarrolló para hacerlo fueron fundamentales en la teoría de la prueba.
Un segundo hilo conductor en la historia de los fundamentos de las matemáticas involucra la lógica no clásica y las matemáticas constructivas . El estudio de las matemáticas constructivas incluye muchos programas diferentes con varias definiciones de constructiva . En el extremo más complaciente, muchos matemáticos consideran constructivas las demostraciones en la teoría de conjuntos ZF que no utilizan el axioma de elección. Las versiones más limitadas del constructivismo se limitan a los números naturales , las funciones de teoría de números y los conjuntos de números naturales (que pueden usarse para representar números reales, facilitando el estudio del análisis matemático ). Una idea común es que se debe conocer un medio concreto para calcular los valores de la función antes de que se pueda decir que la función misma existe.
A principios del siglo XX, Luitzen Egbertus Jan Brouwer fundó el intuicionismo como parte de la filosofía de las matemáticas . Esta filosofía, mal entendida al principio, afirmaba que para que un enunciado matemático sea verdadero para un matemático, esa persona debe ser capaz de intuir el enunciado, no sólo de creer en su verdad sino de comprender la razón de su verdad. Una consecuencia de esta definición de verdad fue el rechazo de la ley del tercero excluido , pues hay afirmaciones que, según Brouwer, no se pueden afirmar como verdaderas mientras que sus negaciones tampoco se pueden afirmar como verdaderas. La filosofía de Brouwer fue influyente y fue causa de amargas disputas entre matemáticos destacados. Más tarde, Kleene y Kreisel estudiarían versiones formalizadas de la lógica intuicionista (Brouwer rechazó la formalización y presentó su trabajo en un lenguaje natural no formalizado). Con el advenimiento de la interpretación de BHK y los modelos de Kripke , el intuicionismo se volvió más fácil de reconciliar con las matemáticas clásicas .
Traducción:"Die Ausführung dieses Vorhabens hat eine wesentliche Verzögerung dadurch erfahren, daß in einem Stadium, in dem die Darstellung schon ihrem Abschuß nahe war, durch das Erscheinen der Arbeiten von Herbrand und von Gödel eine veränderte Situation im Gebiet der Beweistheorie entstand, welche die Berück seguridad nueva Einsichten zur Aufgabe machte. Dabei ist der Umfang des Buches angewachsen, so daß eine Teilung in zwei Bände angezeigt erschien."
Ciertamente, Hilbert era consciente de la importancia del trabajo de Gödel en 1934. El segundo volumen de 1939 incluía una forma de prueba de consistencia para aritmética de Gentzen."La ejecución de este plan [de Hilbert para una exposición sobre la teoría de la prueba para la lógica matemática] experimentó un retraso esencial porque, en el momento en que la exposición ya estaba cerca de su conclusión, se produjo una situación alterada en el campo de la teoría de la prueba. debido a la aparición de obras de Herbrand y Gödel, que exigieron la consideración de nuevas ideas. Así, el alcance de este libro ha crecido, de modo que parecía aconsejable dividirlo en dos volúmenes."
{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )Bochenski, Józef María, ed. (1959). Un resumen de la lógica matemática . Biblioteca de síntesis, vol. 1. Traducido por Otto Bird. Dordrecht : Springer . doi :10.1007/978-94-017-0592-9. ISBN 9789048183296.
Cantor, Georg (1874). "Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen" (PDF) . Journal für die Reine und Angewandte Mathematik . 1874 (77): 258–262. doi :10.1515/crll.1874.77.258. S2CID 199545885.Carroll, Lewis (1896). Lógica simbólica. Reimpresiones del legado de Kessinger. ISBN 9781163444955.
Soare, Robert Irving (22 de diciembre de 2011). "Teoría y aplicaciones de la computabilidad: el arte de la computabilidad clásica" (PDF) . Departamento de Matemáticas . Universidad de Chicago . Consultado el 23 de agosto de 2017 .Swineshead, Richard (1498). Calculations Suiseth Anglici (en lituano). Papie: Per Franciscum Gyrardengum.
{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )