Recursive functions modulo $\textrm {CO}-r$-maximal sets
HTML articles powered by AMS MathViewer
- by Manuel Lerman
- Trans. Amer. Math. Soc. 148 (1970), 429-444
- DOI: https://doi.org/10.1090/S0002-9947-1970-0265157-X
- PDF | 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.
Bibliographic 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