La lógica matemática es el estudio de la lógica formal dentro de las matemáticas . Las subáreas principales incluyen la teoría de modelos , la teoría de la prueba , la teoría de conjuntos y la teoría de la recursión (también conocida como teoría de la computabilidad). La investigación en lógica matemática generalmente 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 los 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 fines 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, recibió forma gracias al programa de David Hilbert para demostrar la consistencia de las teorías fundamentales. Los resultados de Kurt Gödel , Gerhard Gentzen y otros proporcionaron una resolución parcial del programa y aclararon las cuestiones involucradas en la demostración de la consistencia. El trabajo en teoría de conjuntos mostró 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 en 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 pueda desarrollar toda la matemática.
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, a veces 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 de otros campos de las matemáticas, no siempre son nítidas. El teorema de incompletitud de Gödel marca no solo un hito en la teoría de la recursión y la teoría de la demostración, sino que también ha dado lugar al teorema de Löb en la lógica modal. El método de forzamiento se emplea en la teoría de conjuntos, la teoría de modelos y la teoría de la recursión, 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 no suele considerarse 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 topos , 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 en el curso del siglo XIX con la ayuda de una notación artificial y un método rigurosamente deductivo. [4] Antes de esta aparición, 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ñados de un vigoroso debate sobre los fundamentos de las matemáticas.
Las teorías de la lógica se desarrollaron en muchas culturas a lo largo de la historia, incluidas China , India , Grecia y el mundo islámico . Los métodos griegos, en particular la lógica aristotélica (o lógica de términos) que se encuentra en el Organon , encontraron una amplia aplicación y aceptación en la ciencia y las matemáticas occidentales durante milenios. [6] Los estoicos , especialmente Crisipo , comenzaron el desarrollo de la lógica de predicados . En la Europa del siglo XVIII, los matemáticos filósofos, incluidos Leibniz y Lambert , habían intentado tratar las operaciones de la lógica formal de una manera 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 , extendió la doctrina aristotélica tradicional de la lógica 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 algebrizació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 , publicada en 1879, una obra que generalmente se considera que marca un punto de inflexión en la historia de la lógica. Sin embargo, el trabajo de Frege permaneció en la oscuridad hasta que Bertrand Russell comenzó a promoverlo cerca del cambio de siglo. La notación bidimensional que desarrolló Frege nunca fue ampliamente adoptada y no se utiliza en textos contemporáneos.
Entre 1890 y 1905, Ernst Schröder publicó Vorlesungen über die Algebra der Logik en tres volúmenes. Esta obra resumía y ampliaba el trabajo de Boole, De Morgan y Peirce y era una referencia exhaustiva sobre la lógica simbólica tal como se entendía a finales del siglo XIX.
La preocupación de que las matemáticas no se habían 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 se refiere a la teoría de los números naturales . Giuseppe Peano [9] publicó un conjunto de axiomas para la 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ó teoremas inaccesibles en el sistema de Peano, incluyendo la unicidad del conjunto de números naturales (hasta el isomorfismo) y las definiciones recursivas de adición y multiplicación a partir de la función sucesora y la inducción matemática.
A mediados del siglo XIX, se conocieron los fallos de los axiomas de Euclides para la geometría. [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 dados por sentados por Euclides no eran de hecho demostrables a partir de sus axiomas. Entre estos se encuentra el teorema de que una línea contiene al menos dos puntos, o que los círculos del mismo radio cuyos centros están separados por ese radio deben intersecarse. Hilbert [13] desarrolló un conjunto completo de axiomas para la geometría , basándose en el trabajo previo 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 línea real . Esto resultaría ser un área importante de investigación en la primera mitad del siglo XX.
El siglo XIX fue testigo de grandes avances en la teoría del análisis real , incluidas las teorías de convergencia de funciones y las series de Fourier . Matemáticos como Karl Weierstrass comenzaron a construir funciones que ampliaban la intuición, como las funciones continuas no diferenciables en ninguna parte . Las concepciones anteriores de una función como regla para el cálculo, o un gráfico 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 permaneció 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, una definición que todavía se emplea en textos contemporáneos. [16]
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 los naturales tienen cardinalidades diferentes. [17] Durante los siguientes veinte años, Cantor desarrolló una teoría de números transfinitos en una serie de publicaciones. En 1891, publicó una nueva prueba de la incontabilidad de los números reales que introdujo el argumento 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 cada conjunto podía estar bien ordenado , pero no pudo producir una prueba para este resultado, dejándolo como un problema abierto en 1895. [18]
En las primeras décadas del siglo XX, las principales áreas de estudio eran 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 eran inconsistentes y buscaran pruebas de su consistencia.
En 1900, Hilbert planteó una famosa lista de 23 problemas para el siglo siguiente. Los dos primeros de ellos eran resolver la hipótesis del continuo y demostrar 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 los números enteros tiene una solución. El trabajo posterior para resolver estos problemas dio forma a 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 todo conjunto podía 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 provocó un acalorado debate e investigación entre los matemáticos y los pioneros de la teoría de conjuntos. La crítica inmediata del 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 las paradojas descubiertas recientemente en la teoría de conjuntos ingenua . Cesare Burali-Forti [21] fue el primero en enunciar 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 . Esta obra seminal 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 fundacional para las matemáticas. [24]
Fraenkel [25] demostró que el axioma de elección no puede probarse a partir de los axiomas de la teoría de conjuntos de Zermelo con urelementos . Trabajos posteriores de Paul Cohen [26] demostraron que no es necesaria la adición de urelementos y que el axioma de elección es indemostrable en ZF. La prueba de Cohen desarrolló el método de forzar , 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 las formalizaciones de primer orden de la teoría de conjuntos, y que implica que cualquier formalización de ese tipo tiene un modelo contable . Este hecho contraintuitivo se conoció como la paradoja de Skolem .
En su tesis doctoral, Kurt Gödel demostró el teorema de completitud , que establece una correspondencia entre la sintaxis y la semántica en la 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 afines , que demostraba la incompletitud (en un sentido diferente de la palabra) de todas las teorías de primer orden suficientemente fuertes y eficaces. Este resultado, conocido como el teorema de incompletitud de Gödel , establece severas limitaciones a los fundamentos axiomáticos de las matemáticas, asestando un duro golpe al programa de Hilbert. Mostró la imposibilidad de proporcionar una prueba de consistencia 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 ningún sistema axiomático 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 se pueden formalizar 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 teóricos de 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 matemáticos destacados colaboró 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 la presentación rigurosa y los fundamentos de la teoría de conjuntos. La terminología acuñada en estos textos, como las palabras biyección , inyección y sobreyección , y los fundamentos de la teoría de conjuntos que empleaban los textos, fueron ampliamente adoptados en toda la matemática.
El estudio de la computabilidad llegó a conocerse como teoría de la recursión o teoría de la computabilidad , porque las formalizaciones tempranas 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 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 en 1931, Gödel carecía de un concepto riguroso de un sistema formal efectivo; inmediatamente se dio cuenta de que las nuevas definiciones de computabilidad podían usarse para este propósito, lo que le permitió enunciar los teoremas de incompletitud en generalidad que solo podía implicarse en el artículo original.
En la década de 1940, Stephen Cole Kleene y Emil Leon Post obtuvieron numerosos resultados en la teoría de la recursión . Kleene [35] introdujo los conceptos de computabilidad relativa, prefigurados por Turing, [36] y la jerarquía aritmética . Posteriormente, Kleene generalizó la teoría de la recursión a los 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 trata de conceptos matemáticos expresados mediante sistemas lógicos formales . Estos sistemas, aunque difieren en muchos detalles, comparten la propiedad común de considerar solo 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 debido a sus deseables propiedades de teoría de pruebas. [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 implica 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) mostró 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 fundacionales 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 la consecuencia lógica en la 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 compacidad apareció por primera vez como un lema en la prueba de Gödel del teorema de completitud, y pasaron muchos años antes de que los lógicos comprendieran su significado y comenzaran a aplicarlo de manera rutinaria. Dice que un conjunto de oraciones tiene un modelo si y solo si cada subconjunto finito tiene un modelo, o en otras palabras, que un conjunto inconsistente de fórmulas debe tener un subconjunto inconsistente finito. Los teoremas de completitud y compacidad permiten un análisis sofisticado de la consecuencia lógica 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 las 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 un enunciado que es verdadero (en el sentido de que es válido para los números naturales) pero no demostrable dentro de ese sistema lógico (y que de hecho puede fallar en algunos modelos no estándar de aritmética que pueden ser consistentes con el sistema lógico). Por ejemplo, en cada sistema lógico capaz de expresar los axiomas de Peano , el enunciado de Gödel es válido 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 una que pueda 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 axiomático suficientemente fuerte, consistente y efectivo para la aritmética puede probar su propia consistencia, lo que se ha interpretado para demostrar que no se puede alcanzar el programa de Hilbert .
Se estudian muchas lógicas además de la lógica de primer orden, entre ellas las lógicas infinitarias , que permiten que las fórmulas proporcionen una cantidad infinita de información, y las lógicas de orden superior , que incluyen una parte de la teoría de conjuntos directamente en su semántica.
La lógica infinitaria mejor estudiada es . En esta lógica, los cuantificadores solo pueden estar anidados hasta profundidades finitas, como en la lógica de primer orden, pero las fórmulas pueden tener conjunciones y disyunciones finitas o infinitamente numerables dentro de ellas. Así, por ejemplo, es posible decir que un objeto es un número entero utilizando una fórmula como
Las lógicas de orden superior permiten cuantificar no sólo elementos del dominio del discurso , sino también 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 abarquen 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 los 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 de teoría de pruebas.
Otro tipo de lógicas sonlógica de punto fijo que permitedefiniciones inductivas, como la que se escribe 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 la lógica de primer orden en ciertas formas fundamentales, pero no abarca todas las lógicas en general, es decir, no abarca la lógica intuicionista, 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 de Löwenheim-Skolem descendente 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 solo 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 la imposición de la teoría de conjuntos. [39]
La lógica intuicionista fue desarrollada por Heyting para estudiar el programa de intuicionismo de Brouwer, en el que el propio Brouwer evitó la formalización. La lógica intuicionista no incluye específicamente la ley del tercio 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 mostró que se puede recuperar información constructiva a partir de las 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 las lógicas formales. Un ejemplo fundamental es el uso de las álgebras de Boole para representar valores de verdad en la lógica proposicional clásica, y el uso de las álgebras de Heyting para representar valores de verdad en la lógica proposicional intuicionista. Las lógicas más fuertes, 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 axiomatizaciones formales de la teoría de conjuntos. La primera de estas axiomatizaciones , 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, entre ellas la teoría de conjuntos de von Neumann–Bernays–Gödel (NBG), la teoría de conjuntos de Morse–Kelley (MK) y los Nuevos Fundamentos (NF). De estas, ZF, NBG y MK son similares en la descripción de una jerarquía acumulativa de conjuntos. Los Nuevos Fundamentos adoptan un enfoque diferente; permiten 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 recursión generalizada.
Dos enunciados famosos en la teoría de conjuntos son el axioma de elección y la hipótesis del continuo . El axioma de elección, enunciado por primera vez por Zermelo [19], fue demostrado independiente de ZF por Fraenkel [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 la capacidad de hacer tal elección es considerada obvia por algunos, ya que cada conjunto de la colección no está vacío, la falta de una regla general y concreta por 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 puede usarse para descomponer una bola sólida en un número finito de piezas que luego pueden reorganizarse, sin escala, para formar dos bolas sólidas del tamaño original. [40] Este teorema, conocido como la paradoja de Banach-Tarski , es uno de los muchos resultados contraintuitivos del axioma de elección.
La hipótesis del continuo, propuesta por primera vez como conjetura por Cantor, fue incluida por David Hilbert en la lista 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 la hipótesis del continuo debe cumplirse. En 1963, Paul Cohen demostró que la hipótesis del continuo no puede ser probada a partir de los axiomas de la teoría de conjuntos de Zermelo-Fraenkel. [26] Sin embargo, este resultado de independencia no resolvió por completo la cuestión 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 esta línea , 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 grandes cardinales son números cardinales con propiedades particulares tan fuertes que la existencia de tales cardinales no puede probarse en ZFC. La existencia del cardinal grande más pequeño típicamente estudiado, un cardinal inaccesible , ya implica la consistencia de ZFC. A pesar del hecho de que los grandes cardinales tienen una cardinalidad extremadamente alta , su existencia tiene muchas ramificaciones para la estructura de la línea real. La determinabilidad se refiere a la posible existencia de estrategias ganadoras para ciertos 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 en una lógica formal y una firma particulares , 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.
El conjunto de todos los modelos de una teoría particular se denomina 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 cuerpos reales cerrados , un resultado que también demuestra que la teoría del cuerpo de números reales es decidible . [42] También señaló que sus métodos eran igualmente aplicables a cuerpos algebraicamente cerrados de característica arbitraria. Un subcampo moderno que se desarrolla a partir de esto se ocupa de las estructuras o-minimales .
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 isomorfos, 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 número continuo de modelos contables no isomorfos puede tener solo un número contable. La conjetura de Vaught , llamada así por 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 recursión también incluye el estudio de la computabilidad generalizada y la definibilidad. 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 ampliado en gran medida por Kleene y Post en la década de 1940. [44]
La teoría clásica de la recursión se centra en la computabilidad de funciones de los números naturales a los números naturales. Los resultados fundamentales establecen una clase robusta y canónica de funciones computables con numerosas caracterizaciones independientes y equivalentes 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 la red de conjuntos enumerables recursivamente .
La teoría de la recursión generalizada extiende las ideas de la teoría de la recursión 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 α-recursión .
La investigación contemporánea en teoría de la recursión 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 teoría de la recursión pura.
Un subcampo importante de la teoría de la recursión estudia la irresolubilidad algorítmica; un problema de decisión o un problema de función es algorítmicamente irresoluble si no existe un algoritmo computable posible que devuelva la respuesta correcta para todas las entradas legales al problema. Los primeros resultados sobre la irresolubilidad, obtenidos independientemente por Church y Turing en 1936, mostraron que el Entscheidungsproblem es algorítmicamente irresoluble. Turing lo demostró al establecer la irresolubilidad del problema de la detención , un resultado con implicaciones de amplio alcance tanto en la teoría de la recursión como en la ciencia informática.
Existen muchos ejemplos conocidos de problemas indecidibles en las matemáticas ordinarias. Pyotr Novikov demostró en 1955 que el problema de los grupos era irresoluble mediante algoritmos, y W. Boone lo demostró de forma independiente en 1959. Otro ejemplo bien conocido es el problema del castor atareado , desarrollado por Tibor Radó en 1962.
El décimo problema de Hilbert pedía un algoritmo para determinar si una ecuación polinómica multivariante con coeficientes enteros tiene una solución en los 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 demostración es el estudio de las demostraciones formales en varios sistemas de deducción lógica. Estas demostraciones se representan como objetos matemáticos formales, lo que facilita su análisis mediante técnicas matemáticas. Se consideran comúnmente varios sistemas de deducción, incluidos los sistemas de deducción de estilo Hilbert , los sistemas de deducción natural y el cálculo secuencial desarrollado por Gentzen.
El estudio de las matemáticas constructivas , en el contexto de la lógica matemática, incluye el estudio de sistemas de 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]
Como 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, lo que permite que algunas propiedades sobre 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 minería de pruebas por Ulrich Kohlenbach y el estudio de los ordinales teóricos 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 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 " Se ha demostrado que esta teoría es extremadamente fructífera ( 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 la informática está estrechamente relacionado con el estudio de la computabilidad en la lógica matemática. Sin embargo, existe una diferencia de énfasis. Los científicos informáticos a menudo se centran en los lenguajes de programación concretos y 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 comprobación de modelos ). La correspondencia Curry-Howard entre pruebas y programas se relaciona con la teoría de pruebas , 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 desarrollando técnicas para la comprobación automática o incluso el hallazgo de pruebas, como la demostración automatizada de teoremas y la programación lógica .
La teoría de la complejidad descriptiva relaciona la lógica con la complejidad computacional . El primer resultado significativo en esta área, el teorema de Fagin (1974), estableció que NP es precisamente el conjunto de lenguajes expresables por 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 un ejemplo del método axiomático, eran incompletos. El uso de infinitesimales y la propia definición de función se pusieron en tela de juicio 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 sobre conjuntos infinitos arbitrarios también fue objeto de críticas. Leopold Kronecker afirmó en su famosa frase: "Dios hizo los números enteros; todo lo demás es obra del hombre", con lo que apoyó el regreso al estudio de objetos finitos y concretos en matemáticas. Aunque el argumento de Kronecker fue continuado por los constructivistas en el 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 axiomáticos que pudieran utilizarse para formalizar grandes partes 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 consistencia. En el siglo XIX, el principal método para demostrar la consistencia de un conjunto de axiomas era proporcionar un modelo para él. 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 se preguntó si sería posible probar que un sistema de axiomas es consistente analizando la estructura de las posibles pruebas en el sistema y mostrando a través de este análisis que es imposible probar una contradicción. Esta idea condujo al estudio de la teoría de la prueba . Además, Hilbert propuso que el análisis debería ser completamente 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 el 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 se puede establecer 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 finitario aumentado con axiomas de inducción transfinita , y las técnicas que desarrolló para hacerlo fueron seminales 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 la matemática constructiva . El estudio de la matemática constructiva incluye muchos programas diferentes con varias definiciones de constructivo . En el extremo más complaciente, las pruebas en la teoría de conjuntos ZF que no utilizan el axioma de elección son llamadas constructivas por muchos matemáticos. 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, lo que facilita 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 en sí 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, poco comprendida al principio, afirmaba que para que un enunciado matemático fuera verdadero para un matemático, esa persona debe ser capaz de intuir el enunciado, no solo creer en su verdad sino entender la razón de su verdad. Una consecuencia de esta definición de la verdad fue el rechazo de la ley del tercio excluido , pues hay enunciados que, según Brouwer, no se pueden afirmar como verdaderos mientras que sus negaciones tampoco se pueden afirmar como verdaderas. La filosofía de Brouwer fue influyente y la causa de amargas disputas entre matemáticos destacados. Kleene y Kreisel estudiarían más tarde versiones formalizadas de la lógica intuicionista (Brouwer rechazó la formalización y presentó su trabajo en lenguaje natural no formalizado). Con el advenimiento de la interpretación BHK y los modelos de Kripke , el intuicionismo se volvió más fácil de conciliar 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 ücksichtigung neuer Einsichten zur Aufgabe machte. Dabei ist der Umfang des Buches angewachsen, so daß eine Teilung in zwei Bände angezeigt erschien."
Sin duda, Hilbert ya era consciente de la importancia del trabajo de Gödel en 1934. El segundo volumen, de 1939, incluía una forma de la prueba de consistencia de Gentzen para la aritmética."La realización de este plan [de Hilbert para una exposición de la teoría de la prueba para la lógica matemática] ha sufrido un retraso esencial porque, en la fase en que la exposición ya estaba próxima a su conclusión, se produjo un cambio en la situación en el área de la teoría de la prueba debido a la aparición de las obras de Herbrand y Gödel, lo que hizo necesario considerar nuevos puntos de vista. Por ello, el alcance de este libro ha aumentado, de modo que parecía aconsejable dividirlo en dos volúmenes."
{{cite book}}: CS1 maint: location missing publisher (link)Bochenski, Jozef Maria, ed. (1959). Un resumen de lógica matemática . Synthese Library, 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 de la computabilidad y aplicaciones: 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}}: CS1 maint: location missing publisher (link)