Section 4.1 Sets
227
example 5
We will prove that {x 0 x [ ℕ and x
2
< 15} = {x 0 x [ ℕ and 2x < 7}.
Let A = {x 0 x [ ℕ and x
2
< 15} and B = {x 0 x [ ℕ and 2x < 7}. To show that
A = B, we show A # B and B # A. For A # B, we must choose an arbitrary
member of A—that is, anything satisfying the characterizing property of A—and
show that it also satisfies the characterizing property of B. Let x [ A. Then x is a
nonnegative integer satisfying the inequality x
2
< 15. The nonnegative integers
with squares less than 15 are 0, 1, 2, and 3, so these integers are the members of A.
The double of each of these nonnegative integers is a number less than 7. Hence,
each member of A is a member of B, and A # B.
Now we show B # A. Any member of B is a nonnegative integer whose
double is less than 7. These numbers are 0, 1, 2, and 3, each of which has a square
less than 15, so B # A.
Sets of Sets
For a set S, we can form a new set whose elements are all of the subsets of S. This
new set is called the powerset of S, ℘(S).
example 6
For S = {0, 1}, ℘(S ) = {[, {0}, {1}, {0, 1}}. Note that the members of the power
set of a set are themselves sets.
For any set S, ℘(S) will always have at least [ and S itself as members, since
[ # S and S # S are always true.
PraCtiCe 8 For A = {1, 2, 3}, what is ℘(A)?
■
In Practice 8, A has 3 elements and ℘(A) has 8 elements. Try finding ℘(S) for
other sets S until you can guess the answer to the following practice problem.
ReminDeR
To find ℘(S), start with [.
Then add sets taking 1 element from S at a time, then
2 elements at a time, then
3 at a time, and so forth.
PraCtiCe 9
If S has n elements, then ℘(S ) has ______ elements. (Does your answer work for
n = 0, too?)
■
There are several ways we can show that for a set S with n elements, ℘(S) will
have 2
n
elements. The following proof uses induction. For the basis step of the
induction, we let n = 0. The only set with 0 elements is [. The only subset of [
is [, so ℘([) = {[}, a set with 1 = 2
0
elements. We assume that for any set with
k elements, the power set has 2
k
elements.
227
example 5
We will prove that {x 0 x [ ℕ and x
2
< 15} = {x 0 x [ ℕ and 2x < 7}.
Let A = {x 0 x [ ℕ and x
2
< 15} and B = {x 0 x [ ℕ and 2x < 7}. To show that
A = B, we show A # B and B # A. For A # B, we must choose an arbitrary
member of A—that is, anything satisfying the characterizing property of A—and
show that it also satisfies the characterizing property of B. Let x [ A. Then x is a
nonnegative integer satisfying the inequality x
2
< 15. The nonnegative integers
with squares less than 15 are 0, 1, 2, and 3, so these integers are the members of A.
The double of each of these nonnegative integers is a number less than 7. Hence,
each member of A is a member of B, and A # B.
Now we show B # A. Any member of B is a nonnegative integer whose
double is less than 7. These numbers are 0, 1, 2, and 3, each of which has a square
less than 15, so B # A.
Sets of Sets
For a set S, we can form a new set whose elements are all of the subsets of S. This
new set is called the powerset of S, ℘(S).
example 6
For S = {0, 1}, ℘(S ) = {[, {0}, {1}, {0, 1}}. Note that the members of the power
set of a set are themselves sets.
For any set S, ℘(S) will always have at least [ and S itself as members, since
[ # S and S # S are always true.
PraCtiCe 8 For A = {1, 2, 3}, what is ℘(A)?
■
In Practice 8, A has 3 elements and ℘(A) has 8 elements. Try finding ℘(S) for
other sets S until you can guess the answer to the following practice problem.
ReminDeR
To find ℘(S), start with [.
Then add sets taking 1 element from S at a time, then
2 elements at a time, then
3 at a time, and so forth.
PraCtiCe 9
If S has n elements, then ℘(S ) has ______ elements. (Does your answer work for
n = 0, too?)
■
There are several ways we can show that for a set S with n elements, ℘(S) will
have 2
n
elements. The following proof uses induction. For the basis step of the
induction, we let n = 0. The only set with 0 elements is [. The only subset of [
is [, so ℘([) = {[}, a set with 1 = 2
0
elements. We assume that for any set with
k elements, the power set has 2
k
elements.