Computability Theory

Degrees of Unsolvability 127

In addition, ≡

T

has a property that ≤

T

lacks: it is symmetric:

Whenever A ≡

T

B then B ≡

T

A.

In summary, the relation ≡

T

is reflexive on PN, transitive, and symmetric. Such rela-

tions are called equivalence relations on PN.

6.2 Equivalence Relations

Suppose that E is a binary relation on some set U (that is, E ⊆ U × U). In place of

hx, yi ∈ E,

we will write simply xEy.

Definition:

(i) E is said to be reflexive on U if xEx for every x in U.

(ii) E is said to be symmetric if whenever xEy then also yEx.

(iii) E is said to be transitive if whenever both xEy and yEz then also xEz.

(iv) E is said to be an equivalence relation on U if it