Page 191 - Discrete Mathematics and Its Applications

170 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

43. What are the values of the following products? 44. Express n! using product notation.
10 8
a) i b) i
i = 0 i = 5
c) 100 (−1) i d) 10 2 4
i = 1 i = 1 45. Find j = 0 j!.
Recall that the value of the factorial function at a positive in-
teger n, denoted by n!, is the product of the positive integers
4
from 1 to n, inclusive. Also, we specify that 0!= 1. 46. Find j = 0 j!.

2.5 Cardinality of Sets

Introduction

In Definition 4 of Section 2.1 we defined the cardinality of a finite set as the number of elements
in the set. We use the cardinalities of finite sets to tell us when they have the same size, or when
one is bigger than the other. In this section we extend this notion to infinite sets. That is, we will
define what it means for two infinite sets to have the same cardinality, providing us with a way
to measure the relative sizes of infinite sets.
We will be particularly interested in countably infinite sets, which are sets with the same
cardinality as the set of positive integers. We will establish the surprising result that the set of
rational numbers is countably infinite. We will also provide an example of an uncountable set
when we show that the set of real numbers is not countable.
The concepts developed in this section have important applications to computer science. A
function is called uncomputable if no computer program can be written to find all its values,
even with unlimited time and memory. We will use the concepts in this section to explain why
uncomputable functions exist.
We now define what it means for two sets to have the same size, or cardinality. In Section 2.1,
we discussed the cardinality of finite sets and we defined the size, or cardinality, of such sets. In
Exercise 79 of Section 2.3 we showed that there is a one-to-one correspondence between any
two finite sets with the same number of elements. We use this observation to extend the concept
of cardinality to all sets, both finite and infinite.

DEFINITION 1 The sets A and B have the same cardinality if and only if there is a one-to-one correspondence
from A to B. When A and B have the same cardinality, we write |A|=|B|.

For infinite sets the definition of cardinality provides a relative measure of the sizes of two sets,
rather than a measure of the size of one particular set. We can also define what it means for one
set to have a smaller cardinality than another set.

DEFINITION 2 If there is a one-to-one function from A to B, the cardinality of A is less than or the same as
the cardinality of B and we write |A|≤|B|. Moreover, when |A|≤|B| and A and B have
different cardinality, we say that the cardinality of A is less than the cardinality of B and we
write |A| < |B|.

Countable Sets

We will now split infinite sets into two groups, those with the same cardinality as the set of
natural numbers and those with a different cardinality.