236
Sets, Combinatorics, and Probability
Countable and Uncountable Sets
In a finite set S, we can always designate one element as the first member, s 1 ,
another element as the second member, s 2 , and so forth. If there are k elements in
the set, then these can be listed in the order we have selected:
s 1 , s 2 , … , s k
This list represents the entire set S. The number of elements in a finite set is the
cardinality of the set, so this would be a set of cardinality k, denoted by 0S 0 = k.
If the set is infinite, we may still be able to select a first element s 1 , a second
element s 2 , and so forth, so that the list
s 1 , s 2 , s 3 , …
represents all elements of the set. Every element of the set will eventually appear
in this list. Such an infinite set is said to be denumerable. Both finite and denumerable sets are countable sets because we can count, or enumerate, all of their
elements. Being countable does not mean that we can state the total number of
elements in the set; rather, it means that we can say, “Here is a first one,” “Here
is a second one,” and so on, through the set. There are, however, infinite sets that
are uncountable. In an uncountable set, the set is so big that there is no way to
count out the elements and get the whole set in the process. Before we prove that
uncountable sets exist, let’s look at some denumerable (countably infinite) sets.
Table 4.1
Method
Comment
Draw a Venn diagram
Not a good plan because no one diagram fits all cases
and it will not prove the general identity.
Establish set inclusion
in each direction
Take an arbitrary member of one side and show it
belongs to the other side, and conversely.
Use already proved
identities
Be sure to match the pattern of the identity you want to
use.
Table 4.1 summarizes the approaches to proving set identities.
exaMple 21
The set ℕ is denumerable.
To prove denumerability, we need only exhibit a counting scheme. For the set
ℕ of nonnegative integers, it is clear that
0, 1, 2, 3, …
is an enumeration that will eventually include every member of the set.
■
Practice 20 Prove that the set of even positive integers is denumerable.
Sets, Combinatorics, and Probability
Countable and Uncountable Sets
In a finite set S, we can always designate one element as the first member, s 1 ,
another element as the second member, s 2 , and so forth. If there are k elements in
the set, then these can be listed in the order we have selected:
s 1 , s 2 , … , s k
This list represents the entire set S. The number of elements in a finite set is the
cardinality of the set, so this would be a set of cardinality k, denoted by 0S 0 = k.
If the set is infinite, we may still be able to select a first element s 1 , a second
element s 2 , and so forth, so that the list
s 1 , s 2 , s 3 , …
represents all elements of the set. Every element of the set will eventually appear
in this list. Such an infinite set is said to be denumerable. Both finite and denumerable sets are countable sets because we can count, or enumerate, all of their
elements. Being countable does not mean that we can state the total number of
elements in the set; rather, it means that we can say, “Here is a first one,” “Here
is a second one,” and so on, through the set. There are, however, infinite sets that
are uncountable. In an uncountable set, the set is so big that there is no way to
count out the elements and get the whole set in the process. Before we prove that
uncountable sets exist, let’s look at some denumerable (countably infinite) sets.
Table 4.1
Method
Comment
Draw a Venn diagram
Not a good plan because no one diagram fits all cases
and it will not prove the general identity.
Establish set inclusion
in each direction
Take an arbitrary member of one side and show it
belongs to the other side, and conversely.
Use already proved
identities
Be sure to match the pattern of the identity you want to
use.
Table 4.1 summarizes the approaches to proving set identities.
exaMple 21
The set ℕ is denumerable.
To prove denumerability, we need only exhibit a counting scheme. For the set
ℕ of nonnegative integers, it is clear that
0, 1, 2, 3, …
is an enumeration that will eventually include every member of the set.
■
Practice 20 Prove that the set of even positive integers is denumerable.