Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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

DOI: http://dx.doi.org/10.1090/S0002-9939-1984-0740189-9
PII: S 0002-9939(1984)0740189-9
Article copyright: © Copyright 1984 American Mathematical Society