Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



A uniformly, extremely nonextensional formula of arithmetic with many undecidable fixed points in many theories

Author: Robert A. Di Paola
Journal: Proc. Amer. Math. Soc. 91 (1984), 291-297
MSC: Primary 03G25; Secondary 03F30
MathSciNet review: 740189
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: It is proved that there is a single unary formula $ F$ of Peano arithmetic PA and a fixed infinite set $ \mathcal{E}$ of fixed points $ \phi $ of $ F$ in PA with the following property. Let $ T$ be any recursively enumerable, $ \Sigma _1^0$-sound extension of PA. Then (i) almost all $ \phi $ in $ \mathcal{E}$ are undecidable in $ T$, and (ii) for all such $ \phi $ and all equivalence relations $ E$ satisfying reasonable conditions and refining provable equivalence in $ T$ (but not depending on $ \phi $ or $ T$) there is a sentence $ \psi $ equivalent to $ \phi $ via $ E$ which is not a fixed point of $ F$ in $ T$. The theorem furnishes an extreme instance of the difficulties encountered in trying to introduce quantification theory into the diagonalizable algebras of Magari, and yet preserve a central theorem about these structures, the De Jongh-Sambin fixed point theorem. The construction is designed for further applications.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03G25, 03F30

Retrieve articles in all journals with MSC: 03G25, 03F30

Additional Information

Article copyright: © Copyright 1984 American Mathematical Society