Definable properties of the computably enumerable sets
Post started to analyze properties of computably enumerable (c.e.) sets with the intent of finding a property guaranteeing their incompleteness. The authors study this problem for properties definable in the inclusion ordering of c.e. subsets of \(\omega\), \({\mathcal E}= (\{W_n\}_{n\in {\omega}},\subset)\). They introduce two \({\mathcal E}\)-definable properties, \(T(A)\) and \(NL(A)\), relating the \({\mathcal E}\)-structure of a set \(A\) to \(\deg(A)\). The first property \(T(A)\) is proved to guarantee that \(A\) must be complete, but there exists an \(A\) satisfying \(T(A)\) such that \(A\) is promptly simple too. The second property \(NL(A)\) ensures that \(A\) is not low (though \(A\) may be \(\text{low}_2\)). These properties allow the authors to give negative answers to some open questions in this area (for example: ``If \(A\) and \(B\) are both promptly simple and their complements are semi-\(\text{low}_{1.5}\), then are \(A\) and \(B\) automorphic?). The proofs of the definability results are presented by the notion of Lachlan-type games, where we have a contest between the definability player and the automorphism player.
- Automorphisms of the lattice of recursively enumerable sets
- Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
- Automorphisms of the lattice of recursively enumerable sets. Part II: Low sets
- Automorphisms of the lattice of recursively enumerable sets: Orbits
- Automorphisms of the Lattice of Recursively Enumerable Sets: Promptly Simple Sets
- Cappable recursively enumerable degrees and Post's program
- Characterization of Recursively Enumerable Sets with Supersets Effectively Isomorphic to all Recursively Enumerable Sets
- Classes of Recursively Enumerable Sets and Degrees of Unsolvability
- Codable sets and orbits of computably enumerable sets
- Computability and Recursion
- d-simple sets, small sets, and degree classes
- Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets
- Degrees of recursively enumerable sets which have no maximal supersets
- scientific article; zbMATH DE number 194103 (Why is no real title available?)
- scientific article; zbMATH DE number 1163992 (Why is no real title available?)
- scientific article; zbMATH DE number 841085 (Why is no real title available?)
- scientific article; zbMATH DE number 1390017 (Why is no real title available?)
- On some games which are relevant to the theory of recursively enumerable sets
- On the orbits of hyperhypersimple sets
- Post's program and incomplete recursively enumerable sets.
- Recursively enumerable generic sets
- Splitting properties and jump classes
- The dense simple sets are orbit complete with respect to the simple sets
- The translation theorem
- The Δ₃⁰-automorphism method and noninvariant classes of degrees
- There is no fat orbit
- Variations on promptly simple sets
- Orbits of computably enumerable sets: Low sets can avoid an upper cone
- There is no fat orbit
- Definable elements of definable Borel sets
- Duality, non-standard elements, and dynamic properties of r.e. sets
- Computably enumerable sets that are automorphic to low sets
- Definable incompleteness and Friedberg splittings
- scientific article; zbMATH DE number 5000345 (Why is no real title available?)
- scientific article; zbMATH DE number 1531936 (Why is no real title available?)
- scientific article; zbMATH DE number 841085 (Why is no real title available?)
- Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets
- The nonlow computably enumerable degrees are not invariant in \(\mathcal{E}\)
This page was built for publication: Definable properties of the computably enumerable sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1295410)
