×

zbMATH — the first resource for mathematics

Provable fixed points. (English) Zbl 0661.03009
The paper establishes some general conditions under wich a formula A(p) has only provable fixed points in Guaspari-Solovay modal logic of provability R. This result is used to give another proof of Parikh’s theorem: For each natural number \(k\geq 1\) there is an arithmetical sentence A, provable in PA, such that \(\square^ kA\) has a much shorter proof than \(\square^ mA\) for any \(m<k\).
Reviewer: S.Artemov

MSC:
03B45 Modal logic (including the logic of norms)
03F40 Gödel numberings and issues of incompleteness
03F30 First-order arithmetic and fragments
PDF BibTeX XML Cite
Full Text: DOI