Recursive functions modulo $\textrm {CO}-r$-maximal sets
HTML articles powered by AMS MathViewer
- by Manuel Lerman PDF
- Trans. Amer. Math. Soc. 148 (1970), 429-444 Request permission
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
-
S. Feferman, D. S. Scott and S. Tennenbaum, Models of arithmetic through function rings, Notices Amer. Math. Soc. 6 (1959), 173. Abstract #556-31.
- 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, DOI 10.2307/2964290
- Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
- A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1โ37. MR 227009, DOI 10.1090/S0002-9947-1968-0227009-1
- Manuel Lerman, Turing degrees and many-one degrees of maximal sets, J. Symbolic Logic 35 (1970), 29โ40. MR 278948, DOI 10.2307/2271152
- Donald A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295โ310. MR 224469, DOI 10.1002/malq.19660120125
- Donald A. Martin, A theorem on hyperhypersimple sets, J. Symbolic Logic 28 (1963), 273โ278. MR 177887, DOI 10.2307/2271305
- Elliott Mendelson, Introduction to mathematical logic, D. Van Nostrand Co., Inc., Princeton, N.J., 1964. MR 0164867
- Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284โ316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1
- Robert W. Robinson, Simplicity of recursively enumerable sets, J. Symbolic Logic 32 (1967), 162โ172. MR 218235, DOI 10.2307/2271653
- Robert W. Robinson, Two theorems on hyperhypersimple sets, Trans. Amer. Math. Soc. 128 (1967), 531โ538. MR 215714, DOI 10.1090/S0002-9947-1967-0215714-1 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.
Additional Information
- © Copyright 1970 American Mathematical Society
- 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