Intervals and sublattices of the r.e. weak truth table degrees. I: Density
type: Item
instance of: scholarly article
title: Intervals and sublattices of the r.e. weak truth table degrees. I: Density
zbMATH Open document ID: 0628.03031
DOI: 10.1016/0168-0072(89)90005-5
published in: Annals of Pure and Applied Logic
publication date: 1989-01-01T00:00:00Z
review text: In the following \(\underset \tilde{} a,\underset \tilde{} b,..\). denote r.e. wtt- degrees. The paper examines the structure of [\(\underset \tilde{} a,\underset \tilde{} b]\) for \(\underset \tilde{} a<\underset \tilde{} b\). For example, it is shown that for all \(\underset \tilde{} a<\underset \tilde{} b\), we can embed the countable atomless boolean algebra into [\(\underset \tilde{} a,\underset \tilde{} b]\) preserving \(\underset \tilde{} b\) and so the existential theory in the language L(\(\vee,\wedge,1)\) is decidable. Another example is that for all \(\underset \tilde{} a<\underset \tilde{} b\) there exist \(\underset \tilde{} c<\underset \tilde{} d\) with \(\underset \tilde{} c,\underset \tilde{} d\in [\underset \tilde{} a,\underset \tilde{} b]\) such that [\(\underset \tilde{} c,\underset \tilde{} d]\) forms a lattice. [Part II is reviewed below; see Zbl 0628.03032.]
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03D35
zbMATH DE Number: 4021123
zbMATH Keywords: weak truth table
zbMATH Keywords: r.e. wtt-degrees
zbMATH Keywords: countable atomless boolean algebra
author: Rodney G. Downey
MaRDI profile type: Publication
full work available at URL: 0168-0072(89)90005-5
OpenAlex ID: W2048767471
cites work: Lattice embeddings into the recursively enumerable degrees
cites work: On Pairs of Recursively Enumerable Degrees
cites work: Q5187269
cites work: Anti‐Mitotic Recursively Enumerable Sets
cites work: The recursively enumerable degrees have infinitely many one-types
cites work: Minimal pairs and high recursively enumerable degrees
cites work: The Degrees of R.E. Sets Without the Universal Splitting Property
cites work: Localization of a theorem of Ambos-Spies and the strong anti-splitting property
cites work: \(\Delta\)\( ^ 0_ 2\) degrees and transfer theorems
cites work: Intervals and sublattices of the r.e. weak truth table degrees. II: Nonbounding
cites work: T-Degrees, Jump Classes, and Strong Reducibilities
cites work: Classification of degree classes associated with r.e. subspaces
cites work: Structural interactions of the recursively enumerable T- and W-degrees
cites work: Splitting properties of r.e. sets and degrees
cites work: Q3724316
cites work: Pairs without infimum in the recursively enumerable weak truth table degrees
cites work: Reducibility and Completeness for Sets of Integers
cites work: The undecidability of the recursively enumerable degrees
cites work: Q3926563
cites work: Q3905267
cites work: Lower Bounds for Pairs of Recursively Enumerable Degrees
cites work: Q5670617
cites work: A recursively enumerable degree which will not split over all lesser ones
cites work: Bounding minimal pairs
cites work: Decomposition of Recursively Enumerable Degrees
cites work: The weak truth table degrees of recursively enumerable sets
cites work: Strong reducibilities
cites work: Classical recursion theory. Vol. II
cites work: On the degrees less than 0'
cites work: The recursively enumerable degrees are dense
cites work: Q3691658
cites work: The infinite injury priority method
cites work: Q3690802
cites work: Recursively enumerable sets and degrees
cites work: Wtt-degrees and T-degrees of r.e. sets
description: scientific article; zbMATH DE number 4021123