Strong enumeration reducibilities
type: Item
instance of: scholarly article
title: Strong enumeration reducibilities
zbMATH Open document ID: 1110.03028
author: Andrea Sorbi
author: Roland Sh. Omanadze
published in: Archive for Mathematical Logic
publication date: 2006-11-06T00:00:00Z
review text: This paper discusses various enumeration reducibilities, with primary emphasis on \(s\)-reducibility. Let \(L\) denote the structure of \(s\)-degrees below \({\mathbf 0}'_s\) (equivalently, the \(\Sigma_2^0\) \(s\)-degrees). The authors prove that a countable atomless Boolean algebra (and hence any countable distributive lattice) is embeddable in \(L\). On the other hand, they show that \(L\) itself is not distributive by embedding the nondistributive lattice \(N_5\) in it. The authors also prove that \(L\) is upwards dense -- indeed, for any \(s\)-degree \({\mathbf a}<{\mathbf 0}'_s\), every countable partial order is embeddable between \({\mathbf a}\) and \({\mathbf 0}'_s\).
reviewed by: Leon Harkleroad
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 5070977
zbMATH Keywords: \(s\)-reducibility
zbMATH Keywords: \(e\)-reducibility
MaRDI profile type: Publication
full work available at URL: s00153-006-0012-4
OpenAlex ID: W2052087632
cites work: Embedding the diamond in the Σ2 enumeration degrees
cites work: A class of hypersimple incomplete sets
cites work: Q4449350
cites work: Enumeration reducibility and partial degrees
cites work: Partial degrees and the density problem
cites work: Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense
cites work: Enumeration Reducibility Using Bounded Information: Counting Minimal Covers
cites work: Bounding and nonbounding minimal pairs in the enumeration degrees
cites work: Noncappable enumeration degrees below 0e′
cites work: Computably enumerable sets and quasi-reducibility
cites work: Q4726237
cites work: Cupping and noncapping in the r.e. weak truth table and turing degrees
cites work: Reducibility and Completeness for Sets of Integers
cites work: On subcreative sets and S-reducibility
cites work: Semirecursive Sets and Positive Reducibility
cites work: The \(n\)-rea enumeration degrees are dense
cites work: Jumps of quasi-minimal enumeration degrees
cites work: On minimal pairs of enumeration degrees
cites work: Classical recursion theory. The theory of functions and sets of natural numbers
cites work: Classical recursion theory. Vol. II
cites work: Upper semilattice of recursively enumerable sQ-degrees
cites work: Enumeration reducibilities
cites work: Q5573961
cites work: On the degrees less than 0'
cites work: Computational complexity, speedable and levelable sets
cites work: Q4348132
cites work: On restricted forms of enumeration reducibility
cites work: e- and s-degrees
DOI: 10.1007/S00153-006-0012-4
description: scientific article; zbMATH DE number 5070977