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 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**0460110****[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**0460115****[3]**Robert A. Di Paola,*Some properties of pseudo-complements of recursively enumerable sets*, Trans. Amer. Math. Soc.**121**(1966), 296–308. MR**0195722**, 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**0219411****[5]**S. Feferman,*Arithmetization of metamathematics in a general setting*, Fund. Math.**49**(1960/1961), 35–92. MR**0147397****[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**0460116****[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**, 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:
http://dx.doi.org/10.1090/S0002-9939-1984-0740189-9

Article copyright:
© Copyright 1984
American Mathematical Society