2.2. Sets 17
the Cartesian product of n copies of A, we may abbreviate A × A ×
. . . × A as An. A generic ordered n-tuple from An will be written
(x1,x2,...,xn), where xi are all elements of A.
Example 2.2.1. Let A = {x, y} and B = {y, z}. Then A ∪ B =
{x, y, z}, A ∩ B = {y}, A − B = {x}, B − A = {z}, A × B =
{(x, y), (x, z), (y, y), (y, z)}, and P(A) = {∅, {x}, {y}, {x, y}}.
The sets we will use especially are ∅ and N. The former is the
empty set, the set with no elements. The latter is the natural num-
bers, the set {0, 1, 2, 3,...}. In computability, we often use lowercase
omega, ω, to denote the natural numbers, but in these notes we will be
consistent with N. On occasion we may also refer to Z (the integers),
Q (the rational numbers), or R (the real numbers).
We will assume unless otherwise specified that our universe is N;
i.e., all of our sets are subsets of N. When a universe is fixed we
can define complement. The complement of A, denoted A, is all the
elements of N that are not in A; i.e., A = N − A.
Exercise 2.2.2. Convert the list or description of each of the follow-
ing sets into notation using a logical predicate. Assume the domain
of quantification is N.
(i) {2, 4, 6, 8, 10,...}
(ii) {4, 5, 6, 7, 8}
(iii) The set of numbers that are cubes.
(iv) The set of pairs of numbers such that one is twice the other (in
either order).
(v) The intersection of the set of square numbers and the set of
numbers that are divisible by 3.
(vi) [For this and the next two, you’ll need to use ∈ in your logical
predicate.] A ∪ B for sets A and B.
(vii) A ∩ B for sets A and B.
(viii) A − B for sets A and B.
Exercise 2.2.3. For each of the following sets, list (a) the elements
of X, and (b) the elements of P(X).
