Intervals and sublattices of the r.e. weak truth table degrees. I: Density
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.]
scientific article; zbMATH DE number 4021123
scientific article