Recursive functions modulo 𝐶𝑂-𝑟-maximal sets

Lerman, Manuel

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

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

Models of arithmetic through function rings

6

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

Über die nicht-charackterisierbarkheit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler aussagen mit ausschliesslich Zahlenvariablen

23