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
DOI:
https://doi.org/10.1090/S0002-9939-1984-0740189-9
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 of Peano arithmetic PA and a fixed infinite set
of fixed points
of
in PA with the following property. Let
be any recursively enumerable,
-sound extension of PA. Then (i) almost all
in
are undecidable in
, and (ii) for all such
and all equivalence relations
satisfying reasonable conditions and refining provable equivalence in
(but not depending on
or
) there is a sentence
equivalent to
via
which is not a fixed point of
in
. 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.
- [1] 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, https://doi.org/10.1007/BF02125226
- [2] 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, https://doi.org/10.1007/BF02123401
- [3] Robert A. Di Paola, Some properties of pseudo-complements of recursively enumerable sets, Trans. Amer. Math. Soc. 121 (1966), 296–308. MR 195722, https://doi.org/10.1090/S0002-9947-1966-0195722-9
- [4] Robert A. Di Paola, Some theorems on extensions of arithmetic, J. Symbolic Logic 32 (1967), 180–189. MR 219411, https://doi.org/10.2307/2271655
- [5] S. Feferman, Arithmetization of metamathematics in a general setting, Fund. Math. 49 (1960/61), 35–92. MR 147397, https://doi.org/10.4064/fm-49-1-35-92
- [6] Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
- [7] Roberto Magari, Metodi algebrici in teoria della dimostrazione, Boll. Un. Mat. Ital. (4) 12 (1975), no. 3, 252–261 (Italian). MR 0419184
- [8] 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
- [9] 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, https://doi.org/10.1007/BF02123402
- [10] C. Smoryński, Fixed point algebras, Bull. Amer. Math. Society (N.S.) 6 (1982), 317-356.
- [11] D. Guaspari and R. M. Solovay, Rosser sentences, Ann. Math. Logic 16 (1979), no. 1, 81–99. MR 530432, https://doi.org/10.1016/0003-4843(79)90017-2
- [12] Alfred Tarski, Undecidable theories, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam, 1953. In collaboration with Andrzej Mostowski and Raphael M. Robinson. MR 0058532
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:
https://doi.org/10.1090/S0002-9939-1984-0740189-9
Article copyright:
© Copyright 1984
American Mathematical Society