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).