The elementary theory of the recursively enumerable degrees is not \(\aleph _ 0\)-categorical
type: Item
instance of: scholarly article
title: The elementary theory of the recursively enumerable degrees is not \(\aleph _ 0\)-categorical
zbMATH Open document ID: 0559.03027
DOI: 10.1016/0001-8708(84)90028-8
published in: Advances in Mathematics
publication date: 1984-01-01T00:00:00Z
review text: By this paper the authors give the negative answer to the question: ''Is Th(\({\mathcal R})\), the elementary theory of the ordering of the recursively enumerable degrees, \(\aleph_ 0\)-categorical?'' For proving this result, the authors first specify a sequence of finite lattices \({\mathcal P}_ n\) (n\(\geq 0)\) generated by three elements, and then show that all these lattices \({\mathcal P}_ n\) can be embedded (as lattices) into \({\mathcal R}\), the partially ordered set of r.e. degrees. Thus, Th(\({\mathcal R})\) has infinitely many distinct 3-types, and from this the above negative answer follows. The proof of the embedding of \({\mathcal P}_ n\) into \({\mathcal R}\) is very delicate.
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03C35
Mathematics Subject Classification ID: 03D25
zbMATH DE Number: 3891344
zbMATH Keywords: partially ordered set of r.e. degrees
author: Manuel Lerman
author: Richard A. Shore
author: Robert I. Soare
MaRDI profile type: Publication
full work available at URL: 0001-8708(84)90028-8
OpenAlex ID: W2091246156
cites work: Lower Bounds for Pairs of Recursively Enumerable Degrees
cites work: Q5670617
cites work: Not every finite lattice is embeddable in the recursively enumerable degrees
cites work: Q4044555
cites work: Sublattices of the Recursively Enumerable Degrees
cites work: A minimal pair of recursively enumerable degrees
description: scientific article; zbMATH DE number 3891344