Löb's theorem

Löb's theorem In mathematical logic, Löb's theorem states that in Peano arithmetic (PA) (or any formal system including PA), for any formula P, if it is provable in PA that "if P is provable in PA then P is true", then P is provable in PA. If Prov(P) means that the formula P is provable, we may express this more formally as If {displaystyle PA,vdash ,{{rm {Prov}}(P)rightarrow P}} então {displaystyle PA,vdash ,P} An immediate corollary (the contrapositive) of Löb's theorem is that, if P is not provable in PA, então "if P is provable in PA, then P is true" is not provable in PA. Por exemplo, "Se {displaystyle 1+1=3} is provable in PA, então {displaystyle 1+1=3} " is not provable in PA.[Nota 1] Löb's theorem is named for Martin Hugo Löb, who formulated it in 1955. It is related to Curry's paradox.

Conteúdo 1 Löb's theorem in provability logic 2 Modal proof of Löb's theorem 2.1 Modal formulas 2.2 Modal fixed points 2.3 Modal rules of inference 2.4 Proof of Löb's theorem 3 Exemplos 4 Conversar: Löb's theorem implies the existence of modal fixed points 5 Notas 6 Citações 7 Referências 8 External links Löb's theorem in provability logic Provability logic abstracts away from the details of encodings used in Gödel's incompleteness theorems by expressing the provability of {estilo de exibição phi } in the given system in the language of modal logic, by means of the modality {displaystyle Box phi } .

Then we can formalize Löb's theorem by the axiom {displaystyle Box (Box Prightarrow P)rightarrow Box P,} known as axiom GL, for Gödel–Löb. This is sometimes formalized by means of an inference rule that infers {estilo de exibição P} a partir de {displaystyle Box Prightarrow P.} The provability logic GL that results from taking the modal logic K4 (or K, since the axiom schema 4, {displaystyle Box Arightarrow Box Box A} , then becomes redundant) and adding the above axiom GL is the most intensely investigated system in provability logic.

Modal proof of Löb's theorem Löb's theorem can be proved within modal logic using only some basic rules about the provability operator (the K4 system) plus the existence of modal fixed points.

Modal formulas We will assume the following grammar for formulas: Se {estilo de exibição X} is a propositional variable, então {estilo de exibição X} is a formula. Se {estilo de exibição K} is a propositional constant, então {estilo de exibição K} is a formula. Se {estilo de exibição A} is a formula, então {displaystyle Box A} is a formula. Se {estilo de exibição A} e {estilo de exibição B} are formulas, then so are {displaystyle neg A} , {displaystyle Arightarrow B} , {displaystyle Awedge B} , {displaystyle Avee B} , e {displaystyle Aleftrightarrow B} A modal sentence is a modal formula that contains no propositional variables. We use {displaystyle vdash A} to mean {estilo de exibição A} is a theorem.

Modal fixed points If {estilo de exibição F(X)} is a modal formula with only one propositional variable {estilo de exibição X} , then a modal fixed point of {estilo de exibição F(X)} is a sentence {displaystyle Psi } de tal modo que {displaystyle vdash Psi leftrightarrow F(Box Psi )} We will assume the existence of such fixed points for every modal formula with one free variable. This is of course not an obvious thing to assume, but if we interpret {displaystyle Box } as provability in Peano Arithmetic, then the existence of modal fixed points follows from the diagonal lemma.

Modal rules of inference In addition to the existence of modal fixed points, we assume the following rules of inference for the provability operator {displaystyle Box } , known as Hilbert–Bernays provability conditions: (necessitation) A partir de {displaystyle vdash A} conclude {displaystyle vdash Box A} : Informalmente, this says that if A is a theorem, then it is provable. (internal necessitation) {displaystyle vdash Box Arightarrow Box Box A} : If A is provable, then it is provable that it is provable. (box distributivity) {displaystyle vdash Box (Arightarrow B)rightarrow (Box Arightarrow Box B)} : This rule allows you to do modus ponens inside the provability operator. If it is provable that A implies B, and A is provable, then B is provable. Proof of Löb's theorem Assume that there is a modal sentence {estilo de exibição P} de tal modo que {displaystyle vdash Box Prightarrow P} . A grosso modo, it is a theorem that if {estilo de exibição P} é comprovável, then it is, in fact true. This is a claim of soundness. From the existence of modal fixed points for every formula (em particular, a fórmula {displaystyle Xrightarrow P} ) it follows there exists a sentence {displaystyle Psi } de tal modo que {displaystyle vdash Psi leftrightarrow (Box Psi rightarrow P)} . A partir de 2, segue que {displaystyle vdash Psi rightarrow (Box Psi rightarrow P)} . From the necessitation rule, segue que {displaystyle vdash Box (Psi rightarrow (Box Psi rightarrow P))} . A partir de 4 and the box distributivity rule, segue que {displaystyle vdash Box Psi rightarrow Box (Box Psi rightarrow P)} . Applying the box distributivity rule with {displaystyle A=Box Psi } e {displaystyle B=P} gives us {displaystyle vdash Box (Box Psi rightarrow P)rightarrow (Box Box Psi rightarrow Box P)} . A partir de 5 e 6, segue que {displaystyle vdash Box Psi rightarrow (Box Box Psi rightarrow Box P)} . From the internal necessitation rule, segue que {displaystyle vdash Box Psi rightarrow Box Box Psi } . A partir de 7 e 8, segue que {displaystyle vdash Box Psi rightarrow Box P} . A partir de 1 e 9, segue que {displaystyle vdash Box Psi rightarrow P} . A partir de 2, segue que {estilo de exibição vdash (Box Psi rightarrow P)rightarrow Psi } . A partir de 10 e 11, segue que {displaystyle vdash Psi } A partir de 12 and the necessitation rule, segue que {displaystyle vdash Box Psi } . A partir de 13 e 10, segue que {displaystyle vdash P} . Examples An immediate corollary of Löb's theorem is that, if P is not provable in PA, então "if P is provable in PA, then P is true" is not provable in PA. Given we know PA is consistent (but PA does not know PA is consistent), here are some simple examples: "Se {displaystyle 1+1=3} is provable in PA, então {displaystyle 1+1=3} " is not provable in PA, Como {displaystyle 1+1=3} is not provable in PA (as it is false). "Se {displaystyle 1+1=2} is provable in PA, então {displaystyle 1+1=2} " is provable in PA, as is any statement of the form "If X, então {displaystyle 1+1=2} ". "If the strengthened finite Ramsey theorem is provable in PA, then the strengthened finite Ramsey theorem is true" is not provable in PA, Como "The strengthened finite Ramsey theorem is true" is not provable in PA (despite being true).

In Doxastic logic, Löb's theorem shows that any system classified as a reflexive "type 4" reasoner must also be "modest": such a reasoner can never believe "my belief in P would imply that P is true", without first believing that P is true.[1] Gödel's second incompleteness theorem follows from Löb's theorem by substituting the false statement {displaystyle bot } for P.

Conversar: Löb's theorem implies the existence of modal fixed points Not only does the existence of modal fixed points imply Löb's theorem, but the converse is valid, também. When Löb's theorem is given as an axiom (schema), the existence of a fixed point (up to provable equivalence) {displaystyle pleftrightarrow A(p)} for any formula A(p) modalized in p can be derived.[2] Thus in normal modal logic, Löb's axiom is equivalent to the conjunction of the axiom schema 4, {estilo de exibição (Box Arightarrow Box Box A)} , and the existence of modal fixed points.

Notes ^ Unless PA is inconsistent (in which case every statement is provable, Incluindo {displaystyle 1+1=3} ). Citations ^ Smullyan, Raymond M., (1986) Logicians who reason about themselves, Proceedings of the 1986 conference on Theoretical aspects of reasoning about knowledge, Monterey (CA), Morgan Kaufmann Publishers Inc., San Francisco (CA), pp. 341-352 ^ Per Lindström (Junho 2006). "Note on Some Fixed Point Constructions in Provability Logic". Journal of Philosophical Logic. 35 (3): 225–230. doi:10.1007/s10992-005-9013-8. S2CID 11038803. References Boolos, George S. (1995). The Logic of Provability. Cambridge University Press. ISBN 978-0-521-48325-4. Löb, Martinho (1955), "Solution of a Problem of Leon Henkin", Journal of Symbolic Logic, 20 (2): 115-118, doi:10.2307/2266895, JSTOR 2266895 Hinman, P. (2005). Fundamentos de lógica matemática. A K Peters. ISBN 978-1-56881-262-5. Verbrugge, Rineke (L.C.) (1 Janeiro 2016). "Provability Logic". The Stanford Encyclopedia of Philosophy. Recuperado 6 abril 2016. External links Löb's theorem at PlanetMath The Cartoon Guide to Löb’s Theorem by Eliezer Yudkowsky Categories: Mathematical logicModal logicTheorems in the foundations of mathematicsMetatheoremsProvability logicMathematical axioms

Se você quiser conhecer outros artigos semelhantes a Löb's theorem você pode visitar a categoria Mathematical logic.

Ir para cima

Usamos cookies próprios e de terceiros para melhorar a experiência do usuário Mais informação