Definability in the Turing degrees
type: Item
instance of: scholarly article
title: Definability in the Turing degrees
zbMATH Open document ID: 0592.03030
author: Theodore A. Slaman
author: W. Hugh Woodin
published in: Illinois Journal of Mathematics
publication date: 1986-01-01T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 3950507
zbMATH Keywords: forcing
zbMATH Keywords: automorphism
zbMATH Keywords: rigidity
zbMATH Keywords: jump
zbMATH Keywords: recursively enumerable degrees
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 3950507