130 Computability Theory Proof. We use the fact that the union of countably many countable sets is countable. This implies that the union of countably many degrees must be a countable subset of PN . But the union of all degrees is PN , which is uncountable. 6.3 Preordering Relations Suppose that R is any binary relation on a set U (that is, R U × U). As before, we can write xRy to mean that x, y R. Definition: R is a preordering on U if it is reflexive on U and is transitive. Example 1: Turing reducibility T is a preordering on PN . Example 2: Many-one reducibility m is a preordering on PN . Example 3: One-one reducibility 1 is a preordering on PN . mRn m divides n. Then, R is obviously reflexive on U, and transitivity is easy to check. Example 4 : Let U be the set of nonzero integers (positive or negative), and that