Tracing and domination in the Turing degrees

We show that if 0′ is c.e. traceable by a, then a is array non-computable. It follows that there is no minimal almost everywhere dominating degree, in the sense of Dobrinen and Simpson (2004) [10]. This answers a question of Simpson and a question of Nies (2009) [22, Problem 8.6.4]. Moreover, it adds a new arrow in Nies (2009) [22, Figure 8.1], which is a diagram depicting the relations of various ‘computational lowness’ properties. Finally, it gives a natural definable property, namely non-minimality, which separates almost everywhere domination from highness.

► If the halting problem is c.e. traceable by another degree, then the latter is array non-computable. ► It follows that there is no minimal almost everywhere dominating degree. ► This answers a question of Simpson and a question of Nies (from his 2009 book). ► It gives a natural property which separates almost everywhere domination from highness.