228
Sets, Combinatorics, and Probability
Now let S have k + 1 elements and put one of these elements, call it x, aside.
The remaining set has k elements, so by our inductive assumption, its power set has
2
k
elements. Each of these elements is also a member of ℘(S). The only members of
℘(S) not counted by this procedure are those including element x. All the subsets including x can be found by taking all those subsets not including x (of which there are
2
k
) and throwing in the x; thus, there will be 2
k
subsets including x. Altogether, there
are 2
k
subsets without x and 2
k
subsets with x, or 2
k
+ 2
k
= 2 # 2
k
= 2
k+1
subsets.
Therefore, ℘(S) has 2
k+1
elements.
Analogy with the truth tables of Section 1.1 is another way to show that ℘(S)
has 2
n
elements for a set S with n elements. There we had n statement letters and
showed that there were 2
n
true-false combinations among these letters. But we can
also think of each true-false combination as representing a particular subset, with
T indicating membership and F indicating nonmembership in that subset. (For
example, the row of the truth table with all statement letters F corresponds to the
empty set.) Thus, the number of true-false combinations among n statement letters
equals the number of subsets of a set with n elements; both are 2
n
.
Binary and Unary Operations
By itself a set is not very interesting until we do something with its elements. For
example, we can perform several arithmetic operations on elements of the set
ℤ. We might subtract two integers, or we might take the negative of an integer.
Subtraction acts on two integers; it is a binary operation on ℤ. Negation acts on
one integer; it is a unary operation on ℤ.
To see exactly what is involved in a binary operation, let’s look at subtraction
more closely. For any two integers x and y, x − y produces an answer and only one
answer, and that answer is always an integer. Finally, subtraction is performed on
an ordered pair of numbers. For example, 7 − 5 does not produce the same result
as 5 − 7. An ordered pair is denoted by (x, y), where x is the first component of the
ordered pair and y is the second component. Order is important in an ordered pair;
thus, the sets {1, 2} and {2, 1} are equal, but the ordered pairs (1, 2) and (2, 1) are
not. You are probably familiar with ordered pairs used as coordinates to locate a
point in the plane. The point (1, 2) is different from the point (2, 1). Two ordered
pairs (x, y) and (u, v) are equal only when it is the case that x = u and y = v.
■
PraCtiCe 10 Given that (2x − y, x + y) = (7, −1), solve for x and y.
■
PraCtiCe 11 Let S = {3, 4}. List all the ordered pairs (x, y) of elements of S.
We will generalize the properties of subtraction on the integers to define a
binary operation + on a set S. The symbol + is merely a placeholder; in any specific discussion, it will be replaced by the appropriate operation symbol, such as
a subtraction sign.
Sets, Combinatorics, and Probability
Now let S have k + 1 elements and put one of these elements, call it x, aside.
The remaining set has k elements, so by our inductive assumption, its power set has
2
k
elements. Each of these elements is also a member of ℘(S). The only members of
℘(S) not counted by this procedure are those including element x. All the subsets including x can be found by taking all those subsets not including x (of which there are
2
k
) and throwing in the x; thus, there will be 2
k
subsets including x. Altogether, there
are 2
k
subsets without x and 2
k
subsets with x, or 2
k
+ 2
k
= 2 # 2
k
= 2
k+1
subsets.
Therefore, ℘(S) has 2
k+1
elements.
Analogy with the truth tables of Section 1.1 is another way to show that ℘(S)
has 2
n
elements for a set S with n elements. There we had n statement letters and
showed that there were 2
n
true-false combinations among these letters. But we can
also think of each true-false combination as representing a particular subset, with
T indicating membership and F indicating nonmembership in that subset. (For
example, the row of the truth table with all statement letters F corresponds to the
empty set.) Thus, the number of true-false combinations among n statement letters
equals the number of subsets of a set with n elements; both are 2
n
.
Binary and Unary Operations
By itself a set is not very interesting until we do something with its elements. For
example, we can perform several arithmetic operations on elements of the set
ℤ. We might subtract two integers, or we might take the negative of an integer.
Subtraction acts on two integers; it is a binary operation on ℤ. Negation acts on
one integer; it is a unary operation on ℤ.
To see exactly what is involved in a binary operation, let’s look at subtraction
more closely. For any two integers x and y, x − y produces an answer and only one
answer, and that answer is always an integer. Finally, subtraction is performed on
an ordered pair of numbers. For example, 7 − 5 does not produce the same result
as 5 − 7. An ordered pair is denoted by (x, y), where x is the first component of the
ordered pair and y is the second component. Order is important in an ordered pair;
thus, the sets {1, 2} and {2, 1} are equal, but the ordered pairs (1, 2) and (2, 1) are
not. You are probably familiar with ordered pairs used as coordinates to locate a
point in the plane. The point (1, 2) is different from the point (2, 1). Two ordered
pairs (x, y) and (u, v) are equal only when it is the case that x = u and y = v.
■
PraCtiCe 10 Given that (2x − y, x + y) = (7, −1), solve for x and y.
■
PraCtiCe 11 Let S = {3, 4}. List all the ordered pairs (x, y) of elements of S.
We will generalize the properties of subtraction on the integers to define a
binary operation + on a set S. The symbol + is merely a placeholder; in any specific discussion, it will be replaced by the appropriate operation symbol, such as
a subtraction sign.