Page 142 - Discrete Mathematics and Its Applications

2.1 Sets 121

Showing Two Sets are Equal To show that two sets A and B are equal, show that A ⊆ B
and B ⊆ A.

Sets may have other sets as members. For instance, we have the sets

A ={∅, {a}, {b}, {a, b}} and B ={x | x is a subset of the set {a, b}}.
Note that these two sets are equal, that is, A = B. Also note that {a}∈ A, but a/∈ A.

The Size of a Set

Sets are used extensively in counting problems, and for such applications we need to discuss
the sizes of sets.

DEFINITION 4 Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer,
we say that S is a finite set and that n is the cardinality of S. The cardinality of S is denoted
by |S|.

Remark: The term cardinality comes from the common usage of the term cardinal number as
the size of a finite set.

EXAMPLE 10 Let A be the set of odd positive integers less than 10. Then |A|= 5. ▲

EXAMPLE 11 Let S be the set of letters in the English alphabet. Then |S|= 26. ▲

EXAMPLE 12 Because the null set has no elements, it follows that |∅| = 0. ▲

We will also be interested in sets that are not finite.

DEFINITION 5 A set is said to be infinite if it is not finite.

EXAMPLE 13 The set of positive integers is infinite. ▲

We will extend the notion of cardinality to infinite sets in Section 2.5, a challenging topic
full of surprising results.

Power Sets

Many problems involve testing all combinations of elements of a set to see if they satisfy some
property. To consider all such combinations of elements of a set S, we build a new set that has
as its members all the subsets of S.

DEFINITION 6 Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is
denoted by P(S).