Tracing and domination in the Turing degrees

AbstractWe 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