Computability Theory

Degrees of Unsolvability 137

Applying this lemma twice, we see that whenever A ≡

T

B, then A

0

≡

1

B

0

, and con-

sequently A

0

≡

T

B

0

. This fact allows us to make a jump operation on degrees.

Definition: For a degree a, define its jump a

0

to be the degree [A

0

], where A is any set

chosen from the degree a. (The preceding lemma tells us that the degree a

0

does not

depend on which set A is chosen from a.)

Because [A] < [A

0

], we can conclude that on the degrees,

a < a

0

< a

00

< a

000

< · · ·

for any degree a. Again, we see that there is no largest degree.

Earlier, we defined 0

0

to be the degree of K. Now, we are saying that 0

0

is the degree

of the jump of a computable set. There ...