Definability in the Turing degrees (Q1075320)

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\).