Coding in the partial order of enumerable sets
type: Item
instance of: scholarly article
title: Coding in the partial order of enumerable sets
zbMATH Open document ID: 0890.03016
author: André Nies
author: Leo Harrington
published in: Advances in Mathematics
publication date: 1998-03-31T00:00:00Z
review text: This paper first develops techniques for coding into \(\mathcal E\), the partial order of recursively enumerable sets. The authors then use this machinery to prove that true arithmetic can be interpreted in \(\text{Th} (\mathcal E)\) and that the class of quasimaximal sets is definable in \(\mathcal E\). Other results are that no infinite linear order can be coded without parameters into \(\mathcal E\) and that when \(p\neq q\), the partial order on \(\Sigma^0_p\) sets is not elementarily equivalent to that on \(\Sigma^0_q\) sets.
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D35
zbMATH DE Number: 1123533
zbMATH Keywords: enumerable sets
zbMATH Keywords: coding
zbMATH Keywords: definability
zbMATH Keywords: true arithmetic
zbMATH Keywords: quasimaximal sets
reviewed by: Leon Harkleroad
MaRDI profile type: Publication
full work available at URL: aima.1997.1687
OpenAlex ID: W1991182213
cites work: The first order properties of products of algebraic systems
cites work: Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
cites work: Post's program and incomplete recursively enumerable sets.
cites work: The elementary theory of recursively enumerable sets
cites work: Hyperarithmetical Index Sets in Recursion Theory
cites work: Classes of Recursively Enumerable Sets and Degrees of Unsolvability
cites work: The last question on recursively enumerable \(m\)-degrees
cites work: Q4863247
cites work: Intervals of the Lattice of Computably Enumerable Sets and Effective Boolean Algebras
cites work: Effectively dense Boolean algebras and their applications
cites work: Interpretability and Definability in the Recursively Enumerable Degrees
cites work: Q4712236
cites work: The Theory of the Degrees below 0 ′
cites work: Definability in the Turing degrees
cites work: Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
cites work: Q4040892
DOI: 10.1006/AIMA.1997.1687
description: scientific article; zbMATH DE number 1123533