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 x, y E, Suppose that E is a binary relation on some set U (that is, E U × U). In place of we will write simply xEy. Definition: (i) (ii) (iii) (iv) E is said to be reflexive on U if xEx for every x in U. E is said to be symmetric if whenever xEy then also yEx. E is said to be transitive if whenever both xEy and yEz then also xEz. E is said to be an equivalence relation on U if it is reflexive on U, symmetric, and transitive.