Embeddings into the recursively enumerable degrees
Manuel Lerman · Cambridge University Press eBooks · 1996
Section 1: Introduction One of the most efficient methods for proving that a problem is undecidable is to code a second problem which is known to be undecidable into the given problem; a decision procedure for the original problem would then yield one for the second problem, so no such decision procedure can exist. Turing [1939] noticed that this method succeeds because of an inherent notion of information content , coded by a set of integers in the countable situation. This led him to introduce the relation of relative computability between sets as a way of expressing that the information content contained in one set was sufficient to identify the members of the second set. Post [1944], and Kleene and Post [1954] tried to capture the notion of relative computability algebraically. They noticed that the pre-order relation induced on sets of integers by relative computability gave rise to an equivalence relation, and that the equivalence classes form a poset with least element. This structure, known as the degrees of unsolvability or just the degrees has since been intensively studied, and it is of interest whether the algebraic structure completely captures the notion of information content . This question reduces to the determination of whether the degrees are rigid, i.e., whether this algebraic structure has any non-trivial automorphisms, a question to which a positive result has recently been announced by Cooper. One of the major problems one encounters in trying to produce, or rule out automorphisms of the degrees is that the structure is uncountable.