Coding in the partial order of enumerable sets (Q1380333): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:08, 5 March 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