Multi-Page Printing

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