Let $D_{tt} $ denote the set of truth-table degrees. A bijection π: $D_{tt} \to \,D_{tt} $ is an automorphism if for all truth-table degrees x and y we have $ \leqslant _{tt} \,y\, \Leftrightarrow \,\pi (x)\, \leqslant _{tt} \,\pi (y)$ . We say an automorphism π is fixed on a cone if there is a degree b such that for all $x \geqslant _{tt} b$ we have π(x) = x. We first prove that for every 2-generic real X we have (...) X' $X' \le _{tt} \,X\, \oplus \,0'$ . We next prove that for every real $X \ge _{tt} \,0'$ there is a real Y such that $Y \oplus 0{\text{'}}\, \equiv _{tt} \,Y{\text{'}} \equiv _{tt} \,X$ . Finally, we use this to demonstrate that every automorphism of the truth-table degrees is fixed on a cone. (shrink)

We show that Sacks' and Shoenfield's analogs of jump inversion fail for both tt- and wtt-reducibilities in a strong way. In particular we show that there is a ${\mathrm{\Delta }}_{2}^{0}$ set B > tt ∅′ such that there is no c.e. set A with A′ ≡ wtt B. We also show that there is a ${\mathrm{\Sigma }}_{2}^{0}$ set C > tt ∅′ such that there is no ${\mathrm{\Delta }}_{2}^{0}$ set D with D′ ≡ wtt C.

This book describes a program of research in computable structure theory. The goal is to find definability conditions corresponding to bounds on complexity which persist under isomorphism. The results apply to familiar kinds of structures (groups, fields, vector spaces, linear orderings Boolean algebras, Abelian p-groups, models of arithmetic). There are many interesting results already, but there are also many natural questions still to be answered. The book is self-contained in that it includes necessary background material from recursion theory (ordinal notations, (...) the hyperarithmetical hierarchy) and model theory (infinitary formulas, consistency properties). (shrink)