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)
never undefined.
We also think of relations as subsets of
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
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.
Previous Page Next Page