Section 4.1 Sets
239
Although it is interesting and perhaps surprising to learn that there are
uncountable sets, we are usually concerned with countable sets. A computer, of
course, can manage only finite sets. In the rest of this chapter, we too, limit our
attention to finite sets and various ways to count their elements.
exeRciSeS 4.1
1. Let S = {2, 5, 17, 27}. Which of the following expressions are true?
a. 5 [ S
b. 2 + 5 [ S
c. [ [ S
d. S [ S
2. Let B = {x 0 x [ ℚ and −1 < x < 2}. Which of the following expressions are true?
a. 0 [ B
b. −1 [ B
c. −0.84 [ B
d. "2 [ B
3. How many different sets are described here? What are they?
{2, 3, 4}
[
{x 0 x is the first letter of cat, bat, or apple}
{x 0 x is the first letter of cat, bat, and apple}
{x 0 x [ ℕ and 2 ≤ x ≤ 4}
{2, a, 3, b, 4, c}
{a, b, c}
{3, 4, 2}
4. How many different sets are described here? What are they?
{x 0 x = F(n) ` n [ {5, 6, 7}} [F(n) is a Fibonacci number]
{x 0 x 0 24} [x divides 24]
{1, 2, 3, 4}
{5, 8, 13}
{x 0 x [ ℕ ` 0 < x ≤ 4}
{x 0 x [ φ(5)} [φ(n) is the Euler phi function]
{12, 2, 6, 24, 8, 3, 1, 4}
{x 0 x is a digit in the decimal equivalent of the Roman numeral MCCXXXIV}
S e c t i o n 4 . 1 review
tecHniQueS
• Describe sets by a list of elements and by a
characterizing property.
• Prove that one set is a subset of another.
• Find the power set of a set.
• Check that the required properties for a binary or
unary operation are satisfied.
• Form new sets by taking the union, intersection,
complement, and cross product of sets.
• Prove set identities by showing set inclusion in
each direction or using the basic set identities.
• Demonstrate the denumerability of certain sets.
• Use the Cantor diagonalization method to prove
that certain sets are uncountable.
main iDeaS
• Sets are unordered collections of objects that can
be related (equal sets, subsets, etc.) or combined
(union, intersection, etc.).
• Certain standard sets have their own notation.
• The power set of a set with n elements has 2
n
elements.
• Basic set identities exist (in dual pairs) and can be
used to prove other set identities; once an identity is
proved in this manner, its dual is also true.
• Countable sets can be enumerated, and uncountable
sets exist.
W
W
239
Although it is interesting and perhaps surprising to learn that there are
uncountable sets, we are usually concerned with countable sets. A computer, of
course, can manage only finite sets. In the rest of this chapter, we too, limit our
attention to finite sets and various ways to count their elements.
exeRciSeS 4.1
1. Let S = {2, 5, 17, 27}. Which of the following expressions are true?
a. 5 [ S
b. 2 + 5 [ S
c. [ [ S
d. S [ S
2. Let B = {x 0 x [ ℚ and −1 < x < 2}. Which of the following expressions are true?
a. 0 [ B
b. −1 [ B
c. −0.84 [ B
d. "2 [ B
3. How many different sets are described here? What are they?
{2, 3, 4}
[
{x 0 x is the first letter of cat, bat, or apple}
{x 0 x is the first letter of cat, bat, and apple}
{x 0 x [ ℕ and 2 ≤ x ≤ 4}
{2, a, 3, b, 4, c}
{a, b, c}
{3, 4, 2}
4. How many different sets are described here? What are they?
{x 0 x = F(n) ` n [ {5, 6, 7}} [F(n) is a Fibonacci number]
{x 0 x 0 24} [x divides 24]
{1, 2, 3, 4}
{5, 8, 13}
{x 0 x [ ℕ ` 0 < x ≤ 4}
{x 0 x [ φ(5)} [φ(n) is the Euler phi function]
{12, 2, 6, 24, 8, 3, 1, 4}
{x 0 x is a digit in the decimal equivalent of the Roman numeral MCCXXXIV}
S e c t i o n 4 . 1 review
tecHniQueS
• Describe sets by a list of elements and by a
characterizing property.
• Prove that one set is a subset of another.
• Find the power set of a set.
• Check that the required properties for a binary or
unary operation are satisfied.
• Form new sets by taking the union, intersection,
complement, and cross product of sets.
• Prove set identities by showing set inclusion in
each direction or using the basic set identities.
• Demonstrate the denumerability of certain sets.
• Use the Cantor diagonalization method to prove
that certain sets are uncountable.
main iDeaS
• Sets are unordered collections of objects that can
be related (equal sets, subsets, etc.) or combined
(union, intersection, etc.).
• Certain standard sets have their own notation.
• The power set of a set with n elements has 2
n
elements.
• Basic set identities exist (in dual pairs) and can be
used to prove other set identities; once an identity is
proved in this manner, its dual is also true.
• Countable sets can be enumerated, and uncountable
sets exist.
W
W