SECTION 4.1 Basics of Set Theory 189
Number of subsets
= number of subsets of size 0
+ number of subsets of size 1
+ number of subsets of size 2
+ number of subsets of size 3
+ number of subsets of size 4
+ number of subsets of size 5
+ number of subsets of size 6
+ number of subsets of size 7
+ number of subsets of size 8
=Ä 8
0ä
+Ä 8
1ä
+Ä 8
2ä
+Ä 8
3ä
+Ä 8
4ä
+Ä 8
5ä
+Ä 8
6ä
+Ä 8
7ä
+Ä 8
8ä=
∑^8
k=0Ñ
8
ké
= (1 + 1)^8 = 2^8 ,where we have applied the Binomial Theorem.
In general, ifAis any set, we denote by 2A the set of all subsets of
A, often called thepower setofA. (Many authors denote this set by
P(A).) We’ll have more to say about the power set later. At any rate,
we showed above that ifS = { 1 , 2 , 3 , ..., 8 }, then | 2 S| = 2^8. The
obvious generalization is this:
Theorem.LetAbe a finite set with cardinalityn. The 2 Ahas cardi-
nality 2 n. Symbolically,
∣∣
∣∣
∣^2
A∣∣
∣∣
∣ = 2|A|.
Exercises
- Let p be a prime number and define the following subset of the
rational numbersQ:
Q(p) =ßr
s
∈Q| the fractionr
s
is in lowest terms, andpdoesn’t evenly divides™
.