Hostname: page-component-848d4c4894-x24gv Total loading time: 0 Render date: 2024-05-08T18:50:27.928Z Has data issue: false hasContentIssue false
  • English
  • Français

A universal embedding property of the RETs

Published online by Cambridge University Press:  12 March 2014

Anil Nerode  and
Alfred B. Manaster
Anil Nerode
Affiliation:
Cornell University
Alfred B. Manaster
Affiliation:
University of California, San Diego
Get access Rights & Permissions [Opens in a new window]

Extract

Recursive equivalence types are an effective or recursive analogue of cardinal numbers. They were introduced by Dekker in the early 1950's. The richness of various theories related to the recursive equivalence types is demonstrated in this paper by showing that the theory of any countable relational structure can be embedded in or interpreted in these theories. A more complete summary is presented in the last paragraph of this section.

Let E = {0,1, 2, …} be the natural numbers. If α ⊆ E, β ⊆ E, and there is a 1-1 partial recursive function f such that the image under f of α is β, α and β are called recursively equivalent (see [3]). The recursive equivalence type or RET of α, denoted 〈α〉, is the class of all β recursively equivalent to α. Addition of RETs is defined by 〈α〉 + 〈β〉 = 〈{2x ∣ x ∈ α} ∪ 〈{2x + 1 ∣ x ∈ β}〉. The partial ordering ≤ is defined on the RETs by A ≤ B iff (EC)(A + C = B). An RET, X, is called an isol if X ≠ X + 1 or, equivalently, if no representative of X is recursively equivalent to a proper subset of itself. The isols are thus the recursive analogue of the Dedekind-finite cardinals.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 35 , Issue 1 , March 1970 , pp. 51 - 59
Copyright
Copyright © Association for Symbolic Logic 1970

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

The authors wish to acknowledge the partial support of the National Science Foundation through grants GP-8732 and GP-9055. They would also like to acknowledge valuable conversations with Erik Ellentuck on the research reported here.

References

[1] Bradford, R., Cardinal addition and the axiom of choice, Ph.D. thesis, University of California, Berkeley, Calif., 1965.Google Scholar
[2] Bradford, R., Undecidability of the theory of Dedekind cardinal addition, Axiomatic set theory, Proceedings of Symposia in Pure Mathematics, vol. 13, American Mathematical Society, Providence, R.I. (to appear).Google Scholar
[3] Dekker, J. C. E. and Myhill, J., Recursive equivalence types, University of California Publications in Mathematics (new series), vol. 3, no. 3 (1960), pp. 67–214.Google Scholar
[4] Manaster, A. B., Higher-order indecomposable isols, Ph.D. thesis, Cornell University, Ithaca, N.Y., 1965.Google Scholar
[5] Manaster, A. B., Higher-order indecomposable isols, Transactions of the American Mathematical Society, vol. 125 (1966), pp. 363–383.CrossRefGoogle Scholar
[6] Myhill, J., Elementary properties of the group of isolic integers, Mathematische Zeitschrift, vol. 78 (1962), pp. 126–130.CrossRefGoogle Scholar
[7] Nerode, A., Arithmetically isolated sets and nonstandard models, Recursive function theory, Proceedings of Symposia in Pure Mathematics, vol. 5, American Mathematical Society, Providence, R.I., 1962, pp. 105–116.CrossRefGoogle Scholar
[8] Nerode, A., Additive relations among recursive equivalence types, Mathematische Annalen, vol. 159 (1965), pp. 329–343.CrossRefGoogle Scholar
[9] Rabin, M., A simple method for undecidability proofs and some applications, Logic, methodology, and philosophy of science, ed. by Bar-Hillel, Y., Proceedings of the 1964 International Congress, North-Holland, Amsterdam, 1965, pp. 58–68.Google Scholar