Definability in the enumeration degrees
type: Item
instance of: scholarly article
title: Definability in the enumeration degrees
zbMATH Open document ID: 0906.03043
author: Theodore A. Slaman
author: W. Hugh Woodin
published in: Archive for Mathematical Logic
publication date: 1999-02-04T00:00:00Z
review text: The authors prove the following Coding Theorem for the enumeration degrees \(\mathcal G\): every countable relation on \(\mathcal G\) is uniformly definable from parameters in \(\mathcal G\). It follows that the first-order theory of \(\mathcal G\) is recursively isomorphic to the second-order theory of arithmetic. Further, the authors prove an ``effective version'' of the Coding Theorem, which implies undecidability of the first-order theory of the \(\Sigma_2^0\)-enumeration degrees. Also, the authors pose the following questions: Is the \(\exists\forall\)-theory of \(\mathcal G\) decidable? Is the first-order theory of \(\Sigma_2^0\)-enumeration degrees recursively isomorphic to the first-order theory of arithmetic?
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03F35
zbMATH DE Number: 1158098
zbMATH Keywords: enumeration degrees
zbMATH Keywords: reducibility
zbMATH Keywords: definability
zbMATH Keywords: undecidability
zbMATH Keywords: coding theorem
zbMATH Keywords: recursive isomorphism
zbMATH Keywords: second-order arithmetic
reviewed by: M. M. Arslanov
MaRDI profile type: Publication
full work available at URL: s001530050064
OpenAlex ID: W2095314879
DOI: 10.1007/S001530050064
description: scientific article; zbMATH DE number 1158098