Lógica matemática

La lógica matemática es una parte de la lógica y las matemáticas, que consiste en el estudio matemático de la lógica y en la aplicación de este estudio a otras áreas de las matemáticas. La lógica matemática tiene estrechas conexiones con las ciencias de la computación y la lógica filosófica.

La lógica matemática estudia los sistemas formales en relación con el modo en el que codifican nociones intuitivas de objetos matemáticos como conjuntos, números, demostraciones y computación.

La lógica matemática suele dividirse en cuatro subcampos: teoría de modelos, teoría de la demostración, teoría de conjuntos y teoría de la recursión. La investigación en lógica matemática ha jugado un papel fundamental en el estudio de los fundamentos de las matemáticas. Actualmente se usan indiferentemente como sinónimos las expresiones: lógica simbólica (o logística), lógica matemática, lógica teorética y lógica formal.

La lógica matemática no es la «lógica de las matemáticas» sino la «matemática de la lógica». Incluye aquellas partes de la lógica que pueden ser modeladas y estudiadas matemáticamente.

Historia

Siglo XIX

Lógica matemática fue el nombre dado por Giuseppe Peano para esta disciplina. En esencia, es la lógica de Aristóteles, pero desde el punto de vista de una nueva notación, más abstracta, tomada del álgebra.

Previamente ya se hicieron algunos intentos de tratar las operaciones lógicas formales de una manera simbólica por parte de algunos filósofos matemáticos como Leibniz y Lambert, pero su labor permaneció desconocida y aislada.

Fueron George Boole y Augustus De Morgan, a mediados del siglo XIX, quienes primero presentaron un sistema matemático para modelar operaciones lógicas. La lógica tradicional aristotélica fue reformada y completada, obteniendo un instrumento apropiado para investigar sobre los fundamentos de la matemática.

El tradicional desarrollo de la lógica enfatizaba su centro de interés en la forma de argumentar, mientras que la actual lógica matemática lo centra en un estudio combinatorio de los contenidos. Esto se aplica tanto a un nivel sintáctico (por ejemplo, el envío de una cadena de símbolos perteneciente a un lenguaje formal a un programa compilador que lo convierte en una secuencia de instrucciones ejecutables por una máquina), como a un nivel semántico, construyendo modelos apropiados (teoría de modelos).

Lógica simbólica

Leopold Löwenheim (1915) y Thoralf Skolem (1920) formularon el llamado teorema de Löwenheim-Skolem, que afirma que cualquier sistema axiomático basado en la lógica de primer orden no puede controlar la cardinalidad de la estructuras no finitas que satisfacen los axiomas de dicho sistema. Skolem comprendió que este teorema podría aplicarse para las formalizaciones de primer orden de la teoría de conjuntos, sinedo dicha formalización numerable, existiría un modelo numerable para dicha teoría aun cuando la teoría afirma que existen conjuntos no contables. Este resultado contraintuitivo es la conocida paradoja de Skolem.

En su tesis doctoral, Kurt Gödel (1929) demostró el teorema de completitud, que establece una correspondencia entre la sintaxis y la semántica de la lógica de primer orden. Gödel usó dicho teorema de completitud para probar el llamado teorema de comapcidad, demonstrando la naturaleza fintiaria del operador de consecuencia lógica. Estos resultados ayudaron a establecer a la lógica de primer orden como el tipo de lógica dominante en las matemáticas actual.

En 1931, Gödel publicó On Formally Undecidable Propositions of Principia Mathematica and Related Systems, que demostraba la incompletitud (en un sentido diferente del término) de cualquier sistema axiomático suficientemente expresivo, cuyo sistema de axiomas fuera recursivamente enumerable. Este tipo de resultados, conocidos como teorema de incompletitud de Gödel, implica que los sistemas axiomáticos de primer orden tienen severas limitaciones para fundamentar las matemáticas, y supusieron un duro golpe para el llamado programa de Hilbert para la fundamentación de las matemáticas. Uno de los resultados de Gödel estableció que es imposible que pueda formalizarse la consistencia de la artimética una teoría formal en la que se pueda formalizar la propia aritmética. Por otra parte, durante algún tiempo ni Hilbert ni otros de sus colaboradores fueron conscientes de la importancia del trabajo de Gödel para su prentesión de fundamentar las matemáticas mediante el citado "programa de Hilbert".

Concepto de lógica matemática

La lógica matemática estudia los sistemas formales en relación con el modo en el que codifican conceptos intuitivos de objetos matemáticos como conjuntos, números, demostraciones y computación. La lógica estudia las reglas de deducción formales, las capacidades expresivas de los diferentes lenguajes formales y las propiedades metalógicas de los mismos.

En un nivel elemental, la lógica proporciona reglas y técnicas para determinar si es o no válido un argumento dado dentro de un determinado sistema formal. En un nivel avanzado, la lógica matemática se ocupa de la posibilidad de axiomatizar las teorías matemáticas, de clasificar su capacidad expresiva, y desarrollar métodos computacionales útiles en sistemas formales. La teoría de la demostración y la matemática inversa son dos de los razonamientos más recientes de la lógica matemática abstracta. Debe señalarse que la lógica matemática se ocupa de sistemas formales que pueden no ser equivalentes en todos sus aspectos, por lo que la lógica matemática no es método de descubrir verdades del mundo físico real, sino sólo una fuente posible de modelos lógicos aplicables a teorías científicas, muy especialmente a la matemática convencional.

La lógica matemática no se encarga por otra parte del concepto de razonamiento humano general o del proceso creativo de construcción de demostraciones matemáticas mediante argumentos rigurosos pero hechas usando lenguaje informal con algunos signos o diagramas, sino sólo de demostraciones y razonamientos que pueden ser completamente formalizados en todos sus aspectos.

Sistemas lógicos

La lógica matemática se interesa por tres tipos de aspectos de los sistemas lógicos:

• La sintaxis de las lenguajes formales, es decir, las reglas de formación de símbolos interpretables construidos a partir de un determinado alfabeto, y las reglas de inferencia. En concreto el conjunto de teoremas deducibles de un conjunto de axiomas.
• La semántica de las lenguajes formales, es decir, los significados atribuibles a un conjunto de signos, así como el valor de verdad atribuible a algunas de las proposiciones. En general las expresiones de un sistema formal interpretadas en un modelo son ciertas o falsas, por lo que un conjunto de proposiciones que admite un modelo es siempre consistente.
• Los aspectos metalógicos de las lenguas formales, como por ejemplo la completitud, la consistencia, la compacidad o la existencia de modelos de cierto tipo, etc.

Los diferentes tipos de sistemas lógicos pueden ser clasificados en:

• Lógica proposicional (Lógica de orden cero): En ella existe símbolos para variables proposicionales (que pueden ser interpretados informalmente como enunciados que puden ser ciertos o falsos) además de símbolos para diversas conectivas. Estas conectivas permiten formar expresiones complejas a partir de variables proposicionales simples. Un sistema lógico puede incluir diversos tipos de conectivas, entre ellos, la lógica clásica suele hacer uso de los siguientes:

¬ se lee “no”

∧ se lee “y”

∨ se lee “o”

→ se lee “…implica…” o “si,…entonces…,”

↔ se lee “…equivalente con…” o "…si, sólo sí…"

Dentro de la lógica proposicional pueden distinguirse varios tipos, por ejemplo restringiendo las posibilidades de interpretación semántica se obtiene la lógica intuicionista y ampliando la complejidad de las interpretaciones semánticas se obtienen las lógicas modales.

• Lógica de predicados: Esta no incluye símbolos para variables proposicionales sino que las proposciones más elementales son predicados atómicos (formados a partir de variables interpretables como objetos singulares, relaciones (entre estas frecuentemente se usan = , <, >, etc), funciones matemáticas. Además símbolos para representar variables, relaciones y funciones este tipo de lógicas incluyen cuantificadores. Dentro de la lógica de precidados se pueden distinguir ciertos tipos:
  • Lógica de primer orden que usualmente es finitaria (sólo se admiten proposiciones formadas mediante un número finito de pasos) aunque también existen lógicas infinitarias.
  • Lógica de segundo orden que a su vez pueden ser de diferentes subtipos.

Teorías axiomáticas

Una teoría axiomática está formada por un conjunto de proposiciones expresables en un determinado lenguaje formal y todas las proposiciones deducibles de dichas expresiones mediante las relgas de inferencia posibles en dicho sistema lógico.

El objetivo de las teorías axiomáticas es construir sistemas lógicos que representen las características esenciales de ramas enteras de las matemáticas. Si se selecciona un conjunto más amplio o menos amplio de axiomas el conjunto de teoremas deducibles cambian. El interés de la teoría de modelos es que en un modelo que satisfagan los axiomas de determinada teoría también se satisfacen los teoremas deducibles de dicha teoría. Es decir, si un teorema es deducible en una cierta teoría, entonces ese teorema es universalmente válido en todos los modelos que satisfacen los axiomas. Esto es interesante porque en principio la clase de modelos que satisface una cierta teoría es difícil de conocer, ya que las teorías matemáticas interesantes en general admiten toda clase infinita de modelos no isomorfos, por lo que su clasificación en general resulta difícilmente abordable sin no existe un sistema lógico y un conjunto de axiomas que caracterice los diferentes tipos de modelos.

Áreas

La Mathematics Subject Classification divide la lógica matemática en las siguientes áreas:

• Filosófica y crítica
• Lógica general (que incluye campos como la lógica modal y la lógica borrosa)
• Teoría de modelos
• Teoría de la computabilidad
• Teoría de conjuntos
• Teoría de la demostración y matemática constructiva algebraica]]
• Modelos no-estándar

En algunos casos hay conjunción de intereses con la Informática teórica, pues muchos pioneros de la informática, como Alan Turing, fueron matemáticos y lógicos. Así, el estudio de la semántica de los lenguajes de programación procede de la teoría de modelos, así como también la verificación de programas, y el caso particular de la técnica del model checking. También el isomorfismo de Churry-Howard entre pruebas y programas se corresponde con la teoría de pruebas, donde la lógica intuicionista y la lógica lineal son especialmente significativas.

Algunos sistemas lógicos como el cálculo lambda, y la lógica combinatoria entre otras han devenido, incluso, auténticos lenguajes de programación, creando nuevos paradigmas como son la programación funcional y la programación lógica.

Tipos de sistemas lógicos

Lógica proposicional

La lógica proposicional (o lógica de orden cero) es un lenguaje formal en el que no existen variables ni cuantificación, eso implica que cualquier secuencia de signos que constituya una fórmula bien formada de la lógica proposicional admite una valoración en la proposición es cierta o falsa dependiendo del valor de verdad asignado a las proposiciones que la compongan. En otras palabras en la lógica proposicional cualquier fórmula bien formada define una función proposicional. Por tanto, cualquier sistema lógico basado en la lógica proposicional es decidible y en un número finito de pasos puede determinarse la verdad o falsedad semántica de una proposición. Esto hace que la lógica proposicional sea completa y muy sencilla de caracterizar semánticamente.

Lógica de predicados

La lógica de predicados (o lógica de primer orden) es un lenguaje formal en el que las sentencias bien formadas son producidas por las reglas enunciadas a continuación.

Vocabulario

Un vocabulario es una tupla: $\tau = \langle R_1,R_2,...,R_r,f_1,f_2,...,f_s,c_1,c_2...c_t \rangle$ que consta de:

• $r$ símbolos relacionales $R_i$, cada uno de ellos con un número entero $a_i$ asociado, el cual se conoce como la aridad de $R_i$
• $s$ símbolos funcionales $f_j$, cada uno de aridad $b_j$
• $t$ símbolos constantes $c_k$

Una fórmula de primer orden $\varphi$ en el vocabulario $\tau$, es una fórmula de primer orden donde los únicos predicados, funciones y constantes empleados son los especificados por $\tau$.

Lenguajes y estructuras de primer orden

Un lenguaje de primer orden $\mathfrak{L}\,$ es una colección de distintos símbolos clasificados como sigue:

1. El símbolo de igualdad $=\,$; las conectivas $\lor\,$, $\lnot\,$; el cuantificador universal $\forall\,$ y el paréntesis $(\,$, $)\,$.
2. Un conjunto contable de símbolos de variable $\{v_i\}_{i = 0}^\infty\,$.
3. Un conjunto de símbolos de constante $\{c_\alpha\}_{\alpha \in \Alpha}\,$.
4. Un conjunto de símbolos de función $\{f_\beta\}_{\beta \in \Beta}\,$.
5. Un conjunto de símbolos de relación $\{R_\gamma\}_{\gamma \in \Gamma}\,$.

Así, para especificar un orden, generalmente sólo hace falta especificar la colección de símbolos constantes, símbolos de función y símbolos relacionales, dado que el primer conjunto de símbolos es estándar. Los paréntesis tienen como único propósito de agrupar símbolos y no forman parte de la estructura de las funciones y relaciones.

Los símbolos carecen de significado por sí solos. Sin embargo, a este lenguaje podemos dotarlo de una semántica apropiada.

Una $\mathfrak{L}\,$-estructura sobre el lenguaje $\mathfrak{L}\,$, es una tupla consistente en un conjunto no vacío $A\,$, el universo del discurso, junto a:

1. Para cada símbolo constante $c\,$ de $\mathfrak{L}\,$, tenemos un elemento $c^{\mathfrak{A}} \in A\,$.
2. Para cada símbolo de function $n\,$-aria $f\,$ de $\mathfrak{L}\,$, una function $n\,$-aria $f^{\mathfrak{A}} : A^n \longrightarrow A\,$.
3. Para cada símbolo de relación $n\,$-aria $R\,$ de $\mathfrak{L}\,$, una relación $n\,$-aria sobre $A\,$, esto es, un subconjunto $R^{\mathfrak{A}} \subseteq A^n\,$.

A menudo, usaremos la palabra modelo para denotar esta estructura.

Aspectos metalógicos y algorítimicos

Teoría de modelos

La teoría de modelos introducida anteriormente permite atribuir una intepretación semántica a las expresiones purmente formales de los lenguajes formales. Pero además, permiten estudiar en sí mismos los conjuntos de axiomas, su completitud, su consistencia, la independencia de unos de otros y permiten introducir un importante número de cuestiones metalógicas.

Teoría de la demostración

La teoría de la demostración es la rama de la lógica matemática que trata a las demostraciones como objetos matemáticos, facilitando su análisis mediante técnicas matemáticas. Las demostraciones suelen presentarse como estructuras de datos inductivamente definidas que se construyen de acuerdo con los axiomas y reglas de inferencia de los sistemas lógicos. En este sentido, la teoría de la demostración se ocupa de la sintaxis, en contraste con la teoría de modelos, que trata con la semántica. Junto con la teoría de modelos, la teoría de conjuntos axiomática y la teoría de la recursión, la teoría de la demostración es uno de los "cuatro pilares" de los fundamentos de las matemáticas.

Véase también

• Lógica proposicional
• Lógica de primer orden
• Noción primitiva
• Función indicatriz

Referencias

Bibliografía adicional

• Agazzi, Evandro (1986). Lógica simbólica. Herder. ISBN 9788425401305. 

Enlaces externos

• Wikiversidad alberga proyectos de aprendizaje sobre Lógica matemática.Wikiversidad