Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-22T14:13:04.940Z Has data issue: false hasContentIssue false
  • English
  • Français

Definable Encodings in the Computably Enumerable Sets

Published online by Cambridge University Press:  15 January 2014

Peter A. Cholak  and
Leo A. Harrington
Peter A. Cholak
Affiliation:
Department of Mathematics, University Of Notre Dame, Notre Dame, IN 46556-5683, USA E-mail: [email protected]
Leo A. Harrington
Affiliation:
Department of Mathematics, University Of California, Berkeley, CA 94720-3840, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

The purpose of this communication is to announce some recent results on the computably enumerable sets. There are two disjoint sets of results; the first involves invariant classes and the second involves automorphisms of the computably enumerable sets. What these results have in common is that the guts of the proofs of these theorems uses a new form of definable coding for the computably enumerable sets.

We will work in the structure of the computably enumerable sets. The language is just inclusion, ⊆. This structure is called ε.

All sets will be computably enumerable non-computable sets and all degrees will be computably enumerable and non-computable, unless otherwise noted. Our notation and definitions are standard and follow Soare [1987]; however we will warm up with some definitions and notation issues so the reader need not consult Soare [1987]. Some historical remarks follow in Section 2.1 and throughout Section 3.

We will also consider the quotient structure ε modulo the ideal of finite sets, ε*. ε* is a definable quotient structure of ε since “Χ is finite” is definable in ε; “Χ is finite” iff all subsets of Χ are computable (it takes a little computability theory to show if Χ is infinite then Χ has an infinite non-computable subset). We use A* to denote the equivalent class of A under the ideal of finite sets.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 6 , Issue 2 , June 2000 , pp. 185 - 196
Copyright
Copyright © Association for Symbolic Logic 2000

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.)

References

REFERENCES

Cholak, Peter [1994], Notes on 3 theorems by Leo Harrington, handwritten notes.Google Scholar
Cholak, Peter [1995], Automorphisms of the lattice of recursively enumerable sets, Memoirs of the American Mathematical Society, vol. 113, no. 541, pp. viii +151.CrossRefGoogle Scholar
Cholak, Peter, Downey, Rod, and Harrington, Leo A. [n.d.], Automorphisms of the computably enumerable sets: -completeness, in preparation.Google Scholar
Cholak, Peter and Harrington, Leo A. [n.d.a], -automorphisms of the computably enumerable sets, in preparation.Google Scholar
Cholak, Peter and Harrington, Leo A. [n.d.b], Definable encodings in the computably enumerable sets, submitted, draft available.Google Scholar
Downey, Rod and Harrington, Leo A. [1996], There is no fat orbit, Annals of Pure and Applied Logic, vol. 80, no. 3, pp. 277–289.Google Scholar
Harrington, Leo A. [1983], The undecidability of the lattice of recursively enumerable sets, handwritten notes.Google Scholar
Harrington, Leo A. and Nies, André [1998], Coding in the partial order of enumerable sets, Advances in Mathematics, vol. 133, no. 1, pp. 133–162.Google Scholar
Harrington, Leo A. and Soare, Robert I. [1996a], Definability, automorphisms, and dynamic properties of computably enumerable sets, this BULLETIN, vol. 2, no. 2, pp. 199–213.Google Scholar
Harrington, Leo A. and Soare, Robert I. [1996b], The -automorphism method and noninvariant classes of degrees, Journal of the American Mathematical Society, vol. 9, no. 3, pp. 617–666.CrossRefGoogle Scholar
Herrmann, Eberhard [1984], The undecidability of the elementary theory of the lattice of recursively enumerable sets, Frege conference (Schwerin, 1984), Akademie-Verlag, Berlin, pp. 66–72.Google Scholar
Herrmann, Eberhard [1989], Automorphisms of the lattice of recursively enumerable sets and hyperhypersimple sets, Logic, methodology and philosophy of science, VIII (Moscow, 1987), North-Holland, Amsterdam, pp. 179–190.Google Scholar
Lachlan, Alistair H. [1968a], Degrees of recursively enumerable sets which have no maximal supersets, THIS JOURNAL, vol. 33, pp. 431–443.Google Scholar
Lachlan, Alistair H. [1968b], On the lattice of recursively enumerable sets, Transactions of the American Mathematical Society, vol. 130, pp. 1–37.Google Scholar
Lerman, Manuel, Shore, Richard A., and Soare, Robert I. [1978], r-maximal major subsets, Israel Journal of Mathematics, vol. 31, no. 1, pp. 1–18.Google Scholar
Lerman, Manuel and Soare, Robert I. [1980], d-simple sets, small sets, and degree classes, Pacific Journal of Mathematics, vol. 87, no. 1, pp. 135–155.Google Scholar
Maass, W. [1983], Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets, Transactions of the American Mathematical Society, vol. 279, pp. 311–336.Google Scholar
Maass, W. [1984], On the orbit of hyperhypersimple sets, THIS JOURNAL, vol. 49, pp. 51–62.Google Scholar
Maass, W., Shore, Richard A., and Stob, M. [1981], Splitting properties and jump classes, Israel Journal of Mathematics, vol. 39, pp. 210–224.CrossRefGoogle Scholar
Martin, D. A. [1966], Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 12, pp. 295–310.CrossRefGoogle Scholar
Remmel, J. B. [1989], Recursive Boolean algebras, Handbook of Boolean algebras, vol. 3, North-Holland, Amsterdam, pp. 1097–1165.Google Scholar
Shoenfield, Joseph R. [1976], Degrees of classes of recursively enumerable sets, THIS JOURNAL, vol. 41, pp. 695–696.Google Scholar
Soare, Robert I. [1974], Automorphisms of the lattice of recursively enumerable sets I: maximal sets, Annals of Mathematics, vol. 100, pp. 80–120.Google Scholar
Soare, Robert I. [1987], Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Omega Series, Springer-Verlag, Heidelberg.Google Scholar
Wald, Kevin [1999], Automorphism and noninvariant properties of the computably enumerable sets, Ph.D. thesis , University of Chicago.Google Scholar