224
Sets, Combinatorics, and Probability
It is convenient to name certain standard sets so that we can refer to them
easily. We will use
ℕ = set of all nonnegative integers (note that 0 [ ℕ)
ℤ = set of all integers
ℚ = set of all rational numbers
ℝ = set of all real numbers
ℂ = set of all complex numbers
Sometimes we will also want to talk about the set with no elements (the empty set,
or null set), denoted by [ or { }. For example, if S = {x 0 x [ ℕ and x < 0}, then
S = [. Note that [, the set with no elements, is not the same as {[}, which is a
set with a single element where the single element is the empty set.
PraCtiCe 3 Describe each set.
a. A = {x 0 x [ ℕ and (4y)(y [ {2, 3, 4, 5} S x ≥ y)}
b. B = {x 0 (E y)(E z)( y [ {1, 2} and z [ {2, 3} and x = y + z)}
■
PraCtiCe 4 Complete the definition: A is a subset of B if
(4x)(x [ A S __________ )
■
Relationships Between Sets
For A = {2, 3, 5, 12} and B = {2, 3, 4, 5, 9, 12}, every member of A is also a
member of B. When this happens, A is said to be a subset of B.
example 2
Suppose that a set A is described as
A = {x 0 (E y)(y [ {0, 1, 2} and x = y
3
)}
Because y is not a free variable here, this is still of the form A = {x 0 P(x)}. The
members of A can be found by letting y assume each of the values 0, 1, and 2 and
then taking the cube of each such value. Therefore A = {0, 1, 8}. For
B = {x 0 x [ ℕ and (E y)(y [ ℕ and x ≤ y)}
choosing y = 0 gives x = 0; choosing y = 1 gives x = 0 or 1; choosing y = 2 gives
x = 0, 1, or 2; and so on. In other words, B consists of all nonnegative integers
that are less than or equal to some nonnegative integer, which means that B = ℕ.
For the set
C = {x 0 x [ ℕ and (4y)(y [ ℕ S x ≤ y)}
0 is the only nonnegative integer that is less than or equal to every nonnegative
integer, so C = {0}.