Definable encodings in the computably enumerable sets

Bulletin of Symbolic Logic 6 (2):185-196 (2000)
  Copy   BIBTEX

Abstract

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. We use A* to denote the equivalent class of A under the ideal of finite sets.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 94,623

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytics

Added to PP
2009-01-28

Downloads
67 (#240,232)

6 months
29 (#130,163)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Extending and interpreting Post’s programme.S. Cooper - 2010 - Annals of Pure and Applied Logic 161 (6):775-788.
Extending and interpreting Post’s programme.S. Barry Cooper - 2010 - Annals of Pure and Applied Logic 161 (6):775-788.

Add more citations

References found in this work

Automorphisms of the lattice of recursively enumerable sets.Peter Cholak - 1995 - Providence, RI: American Mathematical Society.
There is no fat orbit.Rod Downey & Leo Harrington - 1996 - Annals of Pure and Applied Logic 80 (3):277-289.

View all 8 references / Add more references