×

zbMATH — the first resource for mathematics

The Lindenbaum fixed point algebra is undecidable. (English) Zbl 0733.03032
The author studies fixed point algebras (fpa’s) in the sense of C. Smoryński [Bull. Am. Math. Soc., New Ser. 6, 317-356 (1982; Zbl 0544.03032)]. These are certain natural Boolean pairs that arise from consideration of natural mappings on the Lindenbaum algebra. R. M. Solovay [Recursion theory, Proc. Symp. Pure Math. 42, 473-486 (1985; Zbl 0573.03030)] showed that the fpa’s associated with the Lindenbaum algebra of r.e. consistent theories containing PA are all recursively isomorphic. Call this the Lindenbaum fixed point algebra. The author proves that the first-order theory of the Lindenbaum fixed point algebra is hereditarily undecidable.

MSC:
03D35 Undecidability and degrees of sets of sentences
03F30 First-order arithmetic and fragments
03G05 Logical aspects of Boolean algebras
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] ?. ?. ?????, ???????? ???????????? ? ?????????????? ??????, ?????, ??????, 1980.
[2] ?. ?. ?????, ?. ?. ??????, ?. ?. ???????? and M. ?. ???????, ???????????? ??????, ?????? ?????????????? ???? 20 (1965), No. 4, pp. 37-108.
[3] F. Montagna, A completeness result for fixed-point algebras, Zeitschrift f?r mathematische Logik und Grundlagen der Mathematik 30 (1984), pp. 525-532. · Zbl 0564.03044
[4] C. Smor?nski, Fixed point algebras, Bulletin (New Series) of the American Mathematical Society 6 (1982), pp. 317-356. · Zbl 0544.03032
[5] C. Smory?ski, The finite inseparability of the first-order theory of diagonnalisable algebras, Studia Logica 41 (1982), pp. 347-349. · Zbl 0542.03024
[6] C. Smory?ski, Self-Reference and Modal Logic, Springer-Verlag, Berlin, 1985.
[7] R. M. Solovay, Infinite fixed-point algebras, in: A. Nerode and R. A. Shore eds., Recursion Theory, Proceedings of Symposia in Pure Mathematics, vol. 42, AMS, Providence, 1985, pp. 473-486. · Zbl 0573.03030
[8] ?. ?. ???????, ??????????? ????????????? ????????? ???????????? ???????? ? ????????? ??????? ???????????? ?????? ???????????? ?????? ????????, ??????? ? ?????? 1 (1962), No. 3, pp. 24-38.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.