A uniformly, extremely nonextensional formula of arithmetic with many undecidable fixed points in many theories
HTML articles powered by AMS MathViewer
- by Robert A. Di Paola PDF
- Proc. Amer. Math. Soc. 91 (1984), 291-297 Request permission
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
- Claudio Bernardi, The fixed-point theorem for diagonalizable algebras, Studia Logica 34 (1975), no. 3, 239–251. The algebraization of the theories which express Theor, III. MR 460110, DOI 10.1007/BF02125226
- Claudio Bernardi, The uniqueness of the fixed-point in every diagonalizable algebra, Studia Logica 35 (1976), no. 4, 335–343. The algebraization of the theories which express Theor, VIII. MR 460115, DOI 10.1007/BF02123401
- Robert A. Di Paola, Some properties of pseudo-complements of recursively enumerable sets, Trans. Amer. Math. Soc. 121 (1966), 296–308. MR 195722, DOI 10.1090/S0002-9947-1966-0195722-9
- Robert A. Di Paola, Some theorems on extensions of arithmetic, J. Symbolic Logic 32 (1967), 180–189. MR 219411, DOI 10.2307/2271655
- S. Feferman, Arithmetization of metamathematics in a general setting, Fund. Math. 49 (1960/61), 35–92. MR 147397, DOI 10.4064/fm-49-1-35-92
- Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
- Roberto Magari, Metodi algebrici in teoria della dimostrazione, Boll. Un. Mat. Ital. (4) 12 (1975), no. 3, 252–261 (Italian). MR 0419184
- Roberto Magari, The diagonalizable algebras, Boll. Un. Mat. Ital. (4) 12 (1975), no. 3, suppl., 117–125 (English, with Italian summary). The algebraization of the theories which express Theor, II; Collection in memory of Enrico Bompiani. MR 0460109
- Giovanni Sambin, An effective fixed-point theorem in intuitionistic diagonalizable algebras, Studia Logica 35 (1976), no. 4, 345–361. The algebraization of the theories which express Theor, IX. MR 460116, DOI 10.1007/BF02123402 C. Smoryński, Fixed point algebras, Bull. Amer. Math. Society (N.S.) 6 (1982), 317-356.
- D. Guaspari and R. M. Solovay, Rosser sentences, Ann. Math. Logic 16 (1979), no. 1, 81–99. MR 530432, DOI 10.1016/0003-4843(79)90017-2
- Alfred Tarski, Undecidable theories, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam, 1953. In collaboration with Andrzej Mostowski and Raphael M. Robinson. MR 0058532
Additional Information
- © Copyright 1984 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 91 (1984), 291-297
- MSC: Primary 03G25; Secondary 03F30
- DOI: https://doi.org/10.1090/S0002-9939-1984-0740189-9
- MathSciNet review: 740189