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.