Coding in the partial order of enumerable sets (Q1380333): Difference between revisions

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.