2.3. Relations 21 authors to mean “countably infinite,” and by others to mean “finite or countably infinite,” so you often have to rely on context. We will mean the latter, but will try to be explicit. To prove that a set is countably infinite, you must demonstrate it is in bijection with the natural numbers – that is, that you can count the objects of your set 1, 2, 3, 4, . . . , and not miss any. We’ll come back to this in §3.4 for now you can look in the appendices to find Cantor’s proofs that the rationals are countable and the reals are not (§A.3). The rest of the infinite cardinalities are called uncountable, and for our purposes that’s as fine-grained as it gets. The fundamental notions of computability theory live in the world of countable sets, and the only uncountable ones we get to are those which can be approximated in the countable world. 2.3. Relations The following definition is not the most general case, but we’ll start with it. Definition 2.3.1. A relation R(x, y) on a set A is a logical predicate that is true or false of each pair (x, y) ∈ A2, never undefined. We also think of relations as subsets of A2 consisting of the pairs for which the relation is true. For example, in the set A = {1, 2, 3}, the relation consists of {(1, 2), (1, 3), (2, 3)} and the relation ≤ is the union of with {(1, 1), (2, 2), (3, 3)}. Note that the order matters: although 1 2, 2 1, so (2, 1) is not in . The first definition shows you why these are called relations we think of R as being true when the values filled in for x and y have some relationship to each other. The set-theoretic definition is generally more useful, however. More generally, we may define n-ary relations on a set A as log- ical predicates that are true or false of any n-tuple (ordered set of n elements) of A, or alternatively as subsets of An. For n = 1, 2, 3 we refer to these relations as unary, binary, and ternary, respectively. Exercise 2.3.2. Prove the two definitions of relation are equivalent. That is, prove that every logical predicate corresponds to a unique set, and vice-versa.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.