Section 4.1 Sets
223
PraCtiCe 1 Describe each of the following sets by listing its elements.
a. {x 0 x is an integer and 3 < x ≤ 7}
b. {x 0 x is a month with exactly 30 days}
c. {x 0 x is the capital of the United States}
■
PraCtiCe 2 Describe each of the following sets by giving a characterizing property.
a. {1, 4, 9, 16}
b. {the butcher, the baker, the candlestick maker}
c. {2, 3, 5, 7, 11, 13, 17, …}
■
Two sets are equal if they contain the same elements. (In a definition, “if”
really means “if and only if”; thus two sets are equal if and only if they contain
the same elements.) Using predicate logic notation,
A = B means (4x)[(x [ A S x [ B) ` (x [ B S x [ A)]
In describing a particular set, we have to identify its elements. For a finite set (one
with n elements for some nonnegative integer n), we might do this by simply listing
all the elements, as in set A of Example 1. Although it is impossible to list all elements of an infinite set (one that is not finite), for some infinite sets we can indicate
a pattern for listing elements indefinitely. Thus, we might write {2, 4, 6, …} to
express the set S of all positive even integers. (Although this is a common practice, the danger exists that the reader will not see the pattern that the writer has in
mind.) S can also be defined recursively by giving an explicit member of S and then
describing other members of S in terms of already known members. For example,
1. 2 [ S
2. If n [ S, then (n + 2) [ S
But the clearest way to describe this particular set S is to describe the
characterizing property of the set elements in words and write
S = {x 0 x is a positive even integer}
read as “the set of all x such that x is a positive even integer.”
We’ve now given three ways to describe a set:
1. List (or partially list) its elements.
2. Use recursion to describe how to generate the set elements.
3. Describe a property P that characterizes the set elements.
Later in this section we’ll see that there are sets for which the first approach won’t
work; often the second approach is difficult to use. The third method is usually
the best choice.
The notation for a set S whose elements are characterized as having property
P is {x 0 P(x)}. Property P here is a unary predicate; this term was introduced in
Chapter 1. For any given x, P(x) is either true or false. In fact, the formal logic
notation of Chapter 1 again comes to the rescue to clarify what we mean by a
characterizing property of a set’s elements:
S = {x 0 P(x)} means (4x)[(x [ S S P(x)) ` (P(x) S x [ S )]
In words, every element of S has property P and everything that has property P
is an element of S.
223
PraCtiCe 1 Describe each of the following sets by listing its elements.
a. {x 0 x is an integer and 3 < x ≤ 7}
b. {x 0 x is a month with exactly 30 days}
c. {x 0 x is the capital of the United States}
■
PraCtiCe 2 Describe each of the following sets by giving a characterizing property.
a. {1, 4, 9, 16}
b. {the butcher, the baker, the candlestick maker}
c. {2, 3, 5, 7, 11, 13, 17, …}
■
Two sets are equal if they contain the same elements. (In a definition, “if”
really means “if and only if”; thus two sets are equal if and only if they contain
the same elements.) Using predicate logic notation,
A = B means (4x)[(x [ A S x [ B) ` (x [ B S x [ A)]
In describing a particular set, we have to identify its elements. For a finite set (one
with n elements for some nonnegative integer n), we might do this by simply listing
all the elements, as in set A of Example 1. Although it is impossible to list all elements of an infinite set (one that is not finite), for some infinite sets we can indicate
a pattern for listing elements indefinitely. Thus, we might write {2, 4, 6, …} to
express the set S of all positive even integers. (Although this is a common practice, the danger exists that the reader will not see the pattern that the writer has in
mind.) S can also be defined recursively by giving an explicit member of S and then
describing other members of S in terms of already known members. For example,
1. 2 [ S
2. If n [ S, then (n + 2) [ S
But the clearest way to describe this particular set S is to describe the
characterizing property of the set elements in words and write
S = {x 0 x is a positive even integer}
read as “the set of all x such that x is a positive even integer.”
We’ve now given three ways to describe a set:
1. List (or partially list) its elements.
2. Use recursion to describe how to generate the set elements.
3. Describe a property P that characterizes the set elements.
Later in this section we’ll see that there are sets for which the first approach won’t
work; often the second approach is difficult to use. The third method is usually
the best choice.
The notation for a set S whose elements are characterized as having property
P is {x 0 P(x)}. Property P here is a unary predicate; this term was introduced in
Chapter 1. For any given x, P(x) is either true or false. In fact, the formal logic
notation of Chapter 1 again comes to the rescue to clarify what we mean by a
characterizing property of a set’s elements:
S = {x 0 P(x)} means (4x)[(x [ S S P(x)) ` (P(x) S x [ S )]
In words, every element of S has property P and everything that has property P
is an element of S.