Computability Theory

Degrees of Unsolvability 131

and then testing to see if xRy. We need to verify that the verdict is independent of the

particular choices made. Suppose that instead of x and y, we had chosen x

0

∈ a and

y

0

∈ b. What must be shown is that xRy ⇔ x

0

Ry

0

.

Once we see what must be shown, actually showing it is easy. Since x and x

0

are in the

same equivalence class, we have xEx

0

. Similarly yEy

0

. It follows from transitivity that

xEx

0

& yEy

0

and xRy =⇒ x

0

Ry

0

.

Proposition: The relation ≤ is reflexive on U/E, transitive, and antisymmetric.

“Antisymmetric” means that whenever both a ≤ b and b ≤ a then a = b. A rela-

tion that is reflexive on U/E, transitive, and antisymmetric ...