Recursive functions modulo 𝐶𝑂-𝑟-maximal sets

Lerman, Manuel

doi:10.1090/S0002-9947-1970-0265157-X

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

Author: Manuel Lerman
Journal: Trans. Amer. Math. Soc. 148 (1970), 429-444
MSC: Primary 02.70
DOI: https://doi.org/10.1090/S0002-9947-1970-0265157-X
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 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$ .

[1] S. Feferman, D. S. Scott and S. Tennenbaum, Models of arithmetic through function rings, Notices Amer. Math. Soc. 6 (1959), 173. Abstract #556-31.
[2] Richard M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symbolic Logic 23 (1958), 309–316. MR 109125, https://doi.org/10.2307/2964290
[3] Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
[4] A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1–37. MR 227009, https://doi.org/10.1090/S0002-9947-1968-0227009-1
[5] Manuel Lerman, Turing degrees and many-one degrees of maximal sets, J. Symbolic Logic 35 (1970), 29–40. MR 278948, https://doi.org/10.2307/2271152
[6] Donald A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295–310. MR 224469, https://doi.org/10.1002/malq.19660120125
[7] Donald A. Martin, A theorem on hyperhypersimple sets, J. Symbolic Logic 28 (1963), 273–278. MR 177887, https://doi.org/10.2307/2271305
[8] Elliott Mendelson, Introduction to mathematical logic, D. Van Nostrand Co., Inc., Princeton, N.J., 1964. MR 0164867
[9] Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, https://doi.org/10.1090/S0002-9904-1944-08111-1
[10] Robert W. Robinson, Simplicity of recursively enumerable sets, J. Symbolic Logic 32 (1967), 162–172. MR 218235, https://doi.org/10.2307/2271653
[11] Robert W. Robinson, Two theorems on hyperhypersimple sets, Trans. Amer. Math. Soc. 128 (1967), 531–538. MR 215714, https://doi.org/10.1090/S0002-9947-1967-0215714-1
[12] T. Skolem, Über die nicht-charackterisierbarkheit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler aussagen mit ausschliesslich Zahlenvariablen, Fund. Math. 23 (1934), 150-161.