Una de las ideas centrales de la lógica matemática es que uno debe distinguir entre verdad y demostrabilidad .
Podemos asignar valores de verdad (verdadero y falso) a fórmulas lógicas; hacemos esto usando una interpretación de los símbolos lógicos. Si nuestro lenguaje de fórmulas lógicas tiene símbolos constantes como [matemática] 1 [/ matemática] y [matemática] 2 [/ matemática], probablemente asignaríamos el valor numérico 1 a [matemática] 1 [/ matemática] y el valor numérico 2 a [matemáticas] 2 [/ matemáticas], pero no hay nada que nos impida elegir otra interpretación, digamos una que asigne el mismo valor numérico a todos los símbolos constantes.
En la primera interpretación “natural”, la fórmula [matemática] 1 = 2 [/ matemática] sería falsa, pero en la segunda interpretación “tonta” la fórmula [matemática] 1 = 2 [/ matemática] sería verdadera.
- ¿Cuánto tiempo se tarda en forzar por fuerza bruta una contraseña SHA-256 con un Mac Pro y cuánto tiempo con un MacBook Pro (en teoría)?
- ¿Tiene razón Stephen Wolfram al afirmar que los axiomas de la lógica pueden ser arbitrarios?
- ¿Cómo se aplica el análisis matemático a las empresas?
- ¿Cuáles son ejemplos de exceso de apalancamiento en la naturaleza y cómo los corrige?
- ¿Qué significa 'R I' en mi calculadora?
Cuando hablamos de demostrabilidad, hablamos de un sistema lógico que se basa en un conjunto de axiomas (este conjunto puede estar vacío) y una colección de reglas de prueba que nos permiten deducir nuevas fórmulas de las antiguas. Un ejemplo bien conocido de una regla de prueba es modus ponens :
[matemáticas] \ frac {A \ quad A \ Rightarrow B} {B} [/ math]
Si [math] A [/ math] es una fórmula que se puede probar y [math] A \ Rightarrow B [/ math] es una fórmula que se puede probar, entonces la fórmula [math] B [/ math] también puede ser demostrado.
Si tenemos un sistema lógico y una interpretación, nos gustaría mantener lo siguiente:
- Si una fórmula [matemática] A [/ matemática] es demostrable en el sistema lógico, entonces [matemática] A [/ matemática] también es cierta. Esto se llama solidez.
- Si una fórmula [matemáticas] A [/ matemáticas] es cierto, entonces [matemáticas] A [/ matemáticas] También es demostrable en el sistema lógico. Esto se llama integridad.
Afortunadamente, algunos sistemas lógicos con una interpretación estándar son sólidos y completos. Este es el caso de la lógica proposicional estándar (conocida también como lógica booleana).
Sin embargo, el lógico austriaco Kurt Gödel demostró que si tiene un lenguaje de fórmulas y un sistema lógico que sea lo suficientemente rico, entonces un sistema lógico sólido no puede ser completo. En otras palabras, habrá fórmulas que sean verdaderas en cada interpretación pero que no se puedan probar utilizando los axiomas y las reglas de prueba del sistema lógico.
Por “suficientemente rico” queremos decir que el sistema lógico nos permitirá describir pruebas por inducción y definir las llamadas funciones recursivas primitivas sobre los números naturales.
La prueba del famoso resultado de incompletitud de Gödel es bastante larga, pero la idea subyacente es simple, es decir, expresar la declaración
“Soy una fórmula que no se puede probar en este sistema lógico”
como una fórmula lógica Esta fórmula es verdadera si y solo si no se puede probar en el sistema lógico.