Coding in the partial order of enumerable sets
From MaRDI portal
This paper first develops techniques for coding into \(\mathcal E\), the partial order of recursively enumerable sets. The authors then use this machinery to prove that true arithmetic can be interpreted in \(\text{Th} (\mathcal E)\) and that the class of quasimaximal sets is definable in \(\mathcal E\). Other results are that no infinite linear order can be coded without parameters into \(\mathcal E\) and that when \(p\neq q\), the partial order on \(\Sigma^0_p\) sets is not elementarily equivalent to that on \(\Sigma^0_q\) sets.
Recommendations
Cites work
- Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
- Classes of Recursively Enumerable Sets and Degrees of Unsolvability
- Definability in the Turing degrees
- Effectively dense Boolean algebras and their applications
- scientific article; zbMATH DE number 194103 (Why is no real title available?)
- scientific article; zbMATH DE number 6318 (Why is no real title available?)
- scientific article; zbMATH DE number 841091 (Why is no real title available?)
- Hyperarithmetical Index Sets in Recursion Theory
- Interpretability and Definability in the Recursively Enumerable Degrees
- Intervals of the Lattice of Computably Enumerable Sets and Effective Boolean Algebras
- Post's program and incomplete recursively enumerable sets.
- The elementary theory of recursively enumerable sets
- The first order properties of products of algebraic systems
- The last question on recursively enumerable m-degrees
- The Theory of the Degrees below 0 ′
- Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
Cited in
(23)- Coding a family of sets
- Boolean pairs formed by the \(\Delta_ n^ 0\)-sets
- Interpreting \(\mathbb{N}\) in the computably enumerable weak truth table degrees
- Atomless r-maximal sets
- On propositional coding techniques for the distinguishability of objects in finite sets
- A coding theorem for enumerable output machines
- Coding into Ramsey sets
- Effectively inseparable Boolean algebras in lattices of sentences
- Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces
- On the lattices of effectively open sets
- Coding over a measurable cardinal
- scientific article; zbMATH DE number 4160713 (Why is no real title available?)
- Interpreting true arithmetic in the _2⁰-enumeration degrees
- scientific article; zbMATH DE number 5521857 (Why is no real title available?)
- scientific article; zbMATH DE number 3920534 (Why is no real title available?)
- PARAMETER DEFINABILITY IN THE RECURSIVELY ENUMERABLE DEGREES
- Effectively dense Boolean algebras and their applications
- Definable Encodings in the Computably Enumerable Sets
- Isomorphisms of splits of computably enumerable sets
- ON THE DEFINABILITY OF THE DOUBLE JUMP IN THE COMPUTABLY ENUMERABLE SETS
- On unordered codes
- Computably enumerable sets and related issues
- A coding of the countable linear orderings
This page was built for publication: Coding in the partial order of enumerable sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1380333)
