Transcript A B

2
THE NATURE OF
SETS
Copyright © Cengage Learning. All rights reserved.
2.4
Finite and Infinite Sets
Copyright © Cengage Learning. All rights reserved.
Infinite Sets
3
Infinite Sets
Certain sets, such as
and
A = {1000, 2000, 3000, . . .}, have a common property. We
call these infinite sets. If the cardinality of a set is 0 or a
counting number, we say the set is finite. Otherwise, we
say it is infinite. We can also say that a set is finite if it has
a cardinality less than some counting number, even though
we may not know its precise cardinality.
4
Example 1 – Finding a one-to-one correspondence
Which of the following sets can be placed into a one-to-one
correspondence?
K = {3, 4}, L = {4}, M = {3}, N = {three}, P = {
},
Q = {t, h, r, e}
Solution:
Notice that
L = {4} P = {
M = {3}
Q=
}
{t,h,r,e}
N = {three}
5
Example 1 – Solution
cont’d
We see that L, M, and N all have the same cardinality, and
using that knowledge we see that any pair of them can be
placed into a one-to-one correspondence; we write
L M, L N, and M N.
We also see that P and Q can be placed into a one-to-one
correspondence.
6
Infinite set
In the late 18th century, Georg Cantor assigned a cardinal
Number (pronounced “aleph-naught”) to the set of
counting numbers. That is, is the cardinality of the set of
counting numbers
= {1, 2, 3, 4, . . .}
The set
E = {2, 4, 6, 8, . . .}
also has cardinality , since it can be put into a one-to-one
correspondence with set :
= {1, 2, 3, 4, . . ., n, . . .}
E = {2, 4, 6, 8, . . ., 2n, . . .}
7
Infinite set
Notice that all elements of E are elements of the set ,
and that E  . In such a case, we say that E is a proper
subset of . Cantor used this property as a defining
property for infinite sets.
8
Example 2 – Infinite set
Show that the set of integers
= {. . . , –3, –2, –1, 0, 1, 2, 3, . . .} is infinite.
Solution:
We can show that the set of integers can be placed into a
one-to-one correspondence with the set of counting
numbers:
= {1, 2, 3, 4, 5, 6, 7, . . . , 2n, 2n + 1, . . .}
= {0, +1, –1, +2, –2, +3, –3, . . . ,+n,
Since is a proper subset of
integers is infinite.
–n, . . .}
, we see that the set of
9
Infinite set
If a set is finite or if it has cardinality , we say that the set
is countable. Thus, both the set of counting numbers and
the set of integers are countable.
A set that is not countable is said to be uncountable.
In the example 2 we have seen that and are countable.
10
Example 3 – Show that rationals are countable
Show that the set of rational numbers is countable.
Solution:
First, consider the positive rational numbers and arrange
them in rows so that all the numbers with denominators of
1 are written in row 1, those with denominator 2 are written
in row 2, and so on.
Notice that some numbers are highlighted because those
numbers, when reduced, are found somewhere else in the
list.
11
Example 3 – Solution
cont’d
We see that every nonnegative rational number will appear
on this list. For example, 103/879 will appear in row 103
and column 879.
To set up a one-to-one correspondence between the set of
nonnegative rationals and the set of counting numbers, we
follow the path shown in next figure.
12
Example 3 – Solution
cont’d
13
Example 3 – Solution
cont’d
Now we set up the one-to-one correspondence:
(we skip
list),
because it is equal to
and is already in our
What we have shown is that the set of positive rational
numbers has cardinality . Finally, we use the method
shown in Example 2; that is, we let each negative number
follow its positive counterpart, so we can extend this
correspondence to include all negative rational numbers.
Thus, the set of all rational numbers has cardinality and
is therefore countable.
14
Example 4 – Show that reals are uncountable
Show that the set of real numbers is uncountable.
Solution:
In order to prove that the set of real numbers is
uncountable, we note that every set is either countable or
uncountable.
We will assume that the set is countable, and then we will
arrive at a contradiction. This contradiction, in turn, leads
us to the conclusion that our assumption is incorrect, thus
establishing that the set is uncountable. This process is
called proof by contradiction.
15
Example 4 – Solution
cont’d
Let’s suppose that is countable. Then, there is some
one-to-one correspondence between and , say:
Now, if we assume that there is a one-to-one
correspondence between and , then every decimal
number is in the above list.
16
Example 4 – Solution
cont’d
To show this is not possible, we construct a new decimal
as follows. The first digit of this new decimal is any digit
different from the first digit of the entry corresponding to the
first correspondence. (That is, anything other than 2 using
the above-listed correspondence).
The second digit is any digit different from the second digit
of the entry corresponding to the second correspondence
(4 in this example).
Do the same for all the numbers in the one-to-one
correspondence.
17
Example 4 – Solution
cont’d
Because of the way we have constructed this new number,
it is not on the list. But we began by assuming that all
numbers are on the list (i.e., that all decimal numbers are
part of the one-to-one correspondence).
Since both these statements cannot be true, the original
assumption has led to a contradiction. This forces us to
accept the only possible alternative to the original
assumption.
That is, it is not possible to set up a one-to-one
correspondence between and , which means that is
uncountable.
18
Infinite set
It can also be shown that the irrational numbers (real
numbers that are not rational) are uncountable.
Furthermore, the set {x | a  x  b}, where a and b are any
real numbers, is also uncountable.
19
Cartesian Product of Sets
20
Cartesian Product of Sets
There is an operation of sets called the Cartesian product
that provides a way of generating new sets when given the
elements of two sets. Suppose we have the sets
A = {a, b, c}
and
B = {1, 2}
The Cartesian product of sets A and B, denoted by A  B,
is the set of all ordered pairs (x, y) where x  A and y  B.
For this example,
A  B = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}
Notice that A  B  B  A.
21
Example 5 – Cardinality of a Cartesian product
How many elements are in the Cartesian product of the
given sets?
a. A = {Frank, George, Hazel} and
B = {Alfie, Bogie, Calvin, Doug, Ernie}
b. C = {U.S. Senators} and
D = {U.S. President, U.S. Vice President,
Secretary of State}.
22
Example 5(a) – Solution
cont’d
One of the ways to find a Cartesian product is to represent
the sets as an array.
Since a Cartesian product can be arranged as a
rectangular array, we see that the number of elements is
the product of the number of elements in the sets.
That is, since |A| = 3 and |B| = 5,
we see |A  B| = 3  5 = 15.
23
Example 5(b) – Solution
cont’d
We are looking for |C  D|, but we see it is not practical to
form the rectangular array because | C| = 100 and |D| = 3.
We still can visualize the size of the array even without
writing it out, so we conclude
|C  D| = |C|  |D| = 100  3 = 300
24
Cartesian Product of Sets
25
Example 6 – Classify as finite or infinite
Classify each of the sets as finite or infinite.
a. Set of people on Earth
b. Set of license plates that can be issued using three
letters followed by three numerals
c. Set of drops of water in all the oceans of the world
Solution:
a. We do not know the size of this set, but we do know that
there are fewer than 10 billion people on Earth. If the
cardinality of a set is less than a finite number (and 10
billion is finite), then it must be a finite set.
26
Example 6 – Solution
cont’d
b. We can use the fundamental counting principle to
calculate the number of possible license plates:
26  26  26  10  10  10 = 17,576,000
Note that each “26” counts the number of letters of the
alphabet, and each “10” counts the number of numerals
in each position. Since this is a particular number, we
see that this set of license plates is finite.
c. There is a finite number of drops that make up an ounce,
and there are a certain number of ounces in a gallon,
and a certain number of gallons in a cubic foot.
27
Example 6 – Solution
cont’d
The earth will fit entirely inside a cube of a certain size,
and if this cube were filled with water, it would contain a
finite number of gallons.
The number of drops of water in all the oceans of the
world is certainly less than this number, and hence the
set is finite.
28