Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Recursive functions modulo $ {\rm CO}-r$-maximal sets

Author: Manuel Lerman
Journal: Trans. Amer. Math. Soc. 148 (1970), 429-444
MSC: Primary 02.70
MathSciNet review: 0265157
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Define the equivalence relation $ { \sim _A}$ on the set of recursive functions of one variable by $ f\sim_A g$ if and only if $ f(x) = g(x)$ for all but finitely many $ x \in \bar A$, where $ \bar A$ is an r-cohesive set, to obtain the structure $ \mathcal{R}/\bar A$. Then the recursive functions modulo such an equivalence relation form a semiring with no zero divisors. It is shown that if A is r-maximal, then the structure obtained above is not a nonstandard model for arithmetic, a result due to Feferman, Scott, and Tennenbaum. Furthermore, if A and B are maximal sets, then a necessary and sufficient condition for $ \mathcal{R}/\bar A$ and $ \mathcal{R}/\bar B$ to be elementarily equivalent is obtained. It is also shown that many different elementary theories can be obtained for $ \mathcal{R}/\bar A$ by proper choice of $ \bar A$.

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

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02.70

Retrieve articles in all journals with MSC: 02.70

Additional Information

Keywords: Nonstandard model for arithmetic, r-cohesive set, r-maximal set, retraceable set, elementary equivalence, many-one degree, Turing degree
Article copyright: © Copyright 1970 American Mathematical Society