A note on the diagonalizable algebras of PA and ZF

DOI10.1016/0168-0072(93)90202-OMaRDI QIDQ685077zbMATH OpenOpenAlexFDO

Authors V. Yu. Shavrukov

Publication date 22 September 1993

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(93)90202-o

zbMATH Keywords

complexity measurediagonalizable algebraLindenbaum sentence algebraPAprovability predicateprovably recursive functionsZF

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Gödel numberings and issues of incompleteness (03F40) Other algebras related to logic (03G25)

Review text

If a formal theory \(T\) is strong enough to formalize its own syntax, then the diagonalizable algebra of \(T\) is defined to be the Lindenbaum sentence algebra of \(T\) endowed with a unary operator \(\square\) induced by the Gödel provability predicate of \(T\). The paper under review shows that the diagonalizable algebras of PA and ZF, as well as those of many other pairs of theories differing considerably in strength, are not isomorphic. The proof exploits the difference between the collections of provably recursive functions of the two theories and utilizes the existence of nonspeedable recursive functions.

Recommendations

• Undecidability in diagonalizable algebras
• scientific article; zbMATH DE number 219032
• Topological structure of diagonalizable algebras and corresponding logical properties of theories
• On the autological character of diagonalizable algebras
• The finite inseparability of the first-order theory of diagonalisable algebras

Cites work

• A Machine-Independent Theory of the Complexity of Recursive Functions
• Calculating self-referential statements
• Deduction-preserving "Recursive Isomorphisms" between theories
• Fixed point algebras
• scientific article; zbMATH DE number 3547370 (Why is no real title available?)
• scientific article; zbMATH DE number 219032 (Why is no real title available?)
• Self-reference and modal logic

Cited in

(8)

• Topological structure of diagonalizable algebras and corresponding logical properties of theories
• On a strengthening of the non-isomorphism theorem for provability algebras
• scientific article; zbMATH DE number 109549 (Why is no real title available?)
• Undecidability in diagonalizable algebras
• Interpretability over peano arithmetic
• ON SHAVRUKOV’S NON-ISOMORPHISM THEOREM FOR DIAGONALIZABLE ALGEBRAS
• Notes on my scientific life
• The finite inseparability of the first-order theory of diagonalisable algebras

This page was built for publication: A note on the diagonalizable algebras of PA and ZF

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685077)