Coding in the partial order of enumerable sets (Q1380333): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q588764 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Leon Harkleroad / rank | |||
Normal rank |
Revision as of 05:45, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Coding in the partial order of enumerable sets |
scientific article |
Statements
Coding in the partial order of enumerable sets (English)
0 references
31 March 1998
0 references
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.
0 references
enumerable sets
0 references
coding
0 references
definability
0 references
true arithmetic
0 references
quasimaximal sets
0 references