En lógica matemática , el teorema de Löb establece que en la aritmética de Peano (PA) (o cualquier sistema formal que incluya PA), para cualquier fórmula P , si se puede demostrar en PA que "si P es demostrable en PA, entonces P es verdadero", entonces P es demostrable en PA. Más formalmente, si Prov ( P ) significa que la fórmula P es demostrable, entonces
o
Un corolario inmediato (el contrapositivo ) del teorema de Löb es que, si P no es demostrable en PA, entonces "si P es demostrable en PA, entonces P es verdadero" no es demostrable en PA. Por ejemplo, "Si es demostrable en PA, entonces "no es demostrable en PA. [nota 1]
El teorema de Löb lleva el nombre de Martin Hugo Löb , quien lo formuló en 1955.
El teorema de Löb en lógica de probabilidad
La lógica de probabilidad se abstrae de los detalles de las codificaciones utilizadas en los teoremas de incompletitud de Gödel al expresar la probabilidad deen el sistema dado en el lenguaje de la lógica modal , mediante la modalidad.
Entonces podemos formalizar el teorema de Löb mediante el axioma
conocido como axioma GL, para Gödel – Löb. Esto a veces se formaliza mediante una regla de inferencia que infiere
de
La lógica de probabilidad GL que resulta de tomar la lógica modal K4 (o K , ya que el esquema de axioma 4 ,, luego se vuelve redundante) y agregar el axioma GL anterior es el sistema más intensamente investigado en lógica de probabilidad.
Demostración modal del teorema de Löb
El teorema de Löb se puede demostrar dentro de la lógica modal utilizando solo algunas reglas básicas sobre el operador de probabilidad (el sistema K4) más la existencia de puntos fijos modales.
Fórmulas modales
Asumiremos la siguiente gramática para fórmulas:
- Si es una variable proposicional , entonces es una fórmula.
- Si es una constante proposicional, entonces es una fórmula.
- Si es una fórmula, entonces es una fórmula.
- Si y son fórmulas, entonces también lo son , , , , y
Una oración modal es una fórmula modal que no contiene variables proposicionales. Usamos significar es un teorema.
Puntos fijos modales
Si es una fórmula modal con una sola variable proposicional , entonces un punto fijo modal de es una oración tal que
Supondremos la existencia de tales puntos fijos para cada fórmula modal con una variable libre. Por supuesto, esto no es algo obvio de asumir, pero si interpretamoscomo demostrabilidad en la aritmética de Peano, la existencia de puntos fijos modales se sigue del lema diagonal .
Reglas modales de inferencia
Además de la existencia de puntos fijos modales, asumimos las siguientes reglas de inferencia para el operador de probabilidad , conocidas como condiciones de demostrabilidad de Hilbert-Bernays :
- (necesidad) De concluir : Informalmente, esto dice que si A es un teorema, entonces es demostrable.
- (necesidad interna) : Si A es demostrable, entonces es demostrable que es demostrable.
- (distributividad de caja) : Esta regla le permite hacer modus ponens dentro del operador de demostrabilidad. Si es demostrable que A implica B, y A es demostrable, entonces B es demostrable.
Prueba del teorema de Löb
- Suponga que hay una oración modal tal que .
En términos generales, es un teorema que sies demostrable, entonces es, de hecho, cierto.
Este es un reclamo de solidez . - De la existencia de puntos fijos modales para cada fórmula (en particular, la fórmula ) se sigue que existe una oración tal que .
- De 2, se sigue que .
- De la regla de la necesidad se sigue que .
- De 4 y la regla de la distributividad de caja, se sigue que .
- Aplicando la regla de distributividad de caja con y Nos da .
- De 5 y 6, se sigue que .
- De la regla de necesidad interna se deduce que .
- De 7 y 8, se sigue que .
- De 1 y 9, se sigue que .
- De 2, se sigue que .
- De 10 y 11, se deduce que
- De 12 y la regla de la necesidad, se sigue que .
- De 13 y 10, se deduce que .
Ejemplos de
Un corolario inmediato del teorema de Löb es que, si P no es demostrable en PA, entonces "si P es demostrable en PA, entonces P es verdadero" no es demostrable en PA. Dado que sabemos que PA es consistente (pero PA no sabe que PA es consistente), aquí hay algunos ejemplos simples:
- "Si es demostrable en PA, entonces "no se puede demostrar en PA, ya que no es demostrable en PA (ya que es falso).
- "Si es demostrable en PA, entonces "es demostrable en PA, al igual que cualquier declaración de la forma" Si X, entonces ".
- "Si el teorema de Ramsey finito reforzado es demostrable en PA, entonces el teorema de Ramsey finito reforzado es verdadero" no se puede demostrar en PA, ya que "El teorema de Ramsey finito reforzado es verdadero" no se puede demostrar en PA (a pesar de ser cierto).
En la lógica doxástica , el teorema de Löb muestra que cualquier sistema clasificado como un razonador reflexivo de " tipo 4 " también debe ser " modesto ": tal razonador nunca puede creer que "mi creencia en P implicaría que P es verdadero", sin primero creer que P es verdad. [1]
El segundo teorema de incompletitud de Gödel se deriva del teorema de Löb sustituyendo el enunciado falso para P .
Inverso: el teorema de Löb implica la existencia de puntos fijos modales
La existencia de puntos fijos modales no solo implica el teorema de Löb, sino que lo contrario también es válido. Cuando el teorema de Löb se da como un axioma (esquema), la existencia de un punto fijo (hasta equivalencia demostrable)para cualquier fórmula A ( p ) modalizada en p se puede derivar. [2] Así, en la lógica modal normal , el axioma de Löb es equivalente a la conjunción del esquema del axioma 4 ,y la existencia de puntos fijos modales.
Notas
- ^ A menos que PA sea inconsistente (en cuyo caso cada declaración es demostrable, incluyendo).
Citas
- ^ Smullyan, Raymond M. , (1986) Lógicos que razonan sobre sí mismos , Actas de la conferencia de 1986 sobre aspectos teóricos del razonamiento sobre el conocimiento, Monterey (CA), Morgan Kaufmann Publishers Inc., San Francisco (CA), págs. 341- 352
- ^ Per Lindström (junio de 2006). "Nota sobre algunas construcciones de punto fijo en lógica de probabilidad". Revista de lógica filosófica . 35 (3): 225–230. doi : 10.1007 / s10992-005-9013-8 .
Referencias
- Boolos, George S. (1995). La lógica de la demostrabilidad . Prensa de la Universidad de Cambridge. ISBN 978-0-521-48325-4.
- Löb, Martin (1955), "Solución de un problema de Leon Henkin", Journal of Symbolic Logic , 20 (2): 115-118, JSTOR 2266895
- Hinman, P. (2005). Fundamentos de Lógica Matemática . AK Peters. ISBN 978-1-56881-262-5.
- Verbrugge, Rineke (LC) (1 de enero de 2016). "Lógica de demostrabilidad" . La Enciclopedia de Filosofía de Stanford . Consultado el 6 de abril de 2016 .