Two Theorems on Truth Table Degrees
R. G. Downey · Proceedings of the American Mathematical Society · 1988
In this article we solve two questions of Odifreddi on the r.e. ${\text {tt}}$-degrees. First we construct an r.e. ${\text {tt}}$-degree with anticupping property. In fact, we construct r.e. ${\text {tt}}$-degrees ${\mathbf {a}},{\mathbf {b}}$ with ${\mathbf {0}} < {\mathbf {a}} < {\mathbf {b}}$ and such that for all (not necessarily r.e.) ${\text {tt}}$-degrees ${\mathbf {c}}$ if ${\mathbf {a}} \cup {\mathbf {c}} \geq {\mathbf {b}}$ then ${\mathbf {a}} \leq {\mathbf {c}}$. This result also has ramifications in, for example, the r.e. ${\text {wtt}}$-degrees. Finally we solve another question of Odifreddi by constructing an r.e. ${\text {tt}}$-degree with no greatest r.e. $m$-degree.