Definability in the Turing degrees (Q1075320): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:44, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Definability in the Turing degrees |
scientific article |
Statements
Definability in the Turing degrees (English)
0 references
1986
0 references
Suppose that \({\mathcal R}\) is a countable relation on the Turing degrees. Then \({\mathcal R}\) can be defined in \({\mathcal D}\), the Turing degrees with \(\leq_ T\), by a first order formula with finitely many parameters. The parameters are built by means of a notion of forcing in which the conditions are essentially finite. The conditions in the forcing partial specify finite initial segments of the generic reals and impose an infinite constraint on further extensions. This result is applied to show that any elementary function from \({\mathcal D}\) to \({\mathcal D}\) is an automorphism. Other applications are given toward the rigidity question for: By observing that a single jump is all that is needed to meet the relevant dense sets, it is also shown that the recursively enumerable degrees can be defined from finitely many parameters in the structure consisting of the degrees below O' with \(\leq_ T\).
0 references
forcing
0 references
automorphism
0 references
rigidity
0 references
jump
0 references
recursively enumerable degrees
0 references