Transcript chap1sec7 - University of Virginia, Department of Computer

Section 1.7: Set Operations
This section will introduce various
operations that we can perform on
sets.
Def: Let A and B be sets. The union of the sets A and B,
denoted by A  B, is the set that contains those elements that
are either in A or in B, or in both. That is,
A  B = { x | x  A  x  B }.
Ex: The union of {1, 3, 5} and {1, 2, 3} is {1, 2, 3, 5}.
Ex: The union of {1, 3, 5} and {2, 4, 6} is {1, 2, 3, 4, 5, 6}.
Ex: Z  N = Z.
Ex: The union of the set of even integers and the set of odd
integers is the set of all integers.
Ex: S   = S for any set S.
Ex: S  A = S if and only if A  S (for any set S).
Theorem: S  A = S if and only if A  S (for any set S).
Proof: Let S be a set [State overall assumption; set up for U.G.].
() Let A be a set such that S  A = S [Assume the hypothesis].
We wish to show that A  S so let x  A. Now we show x  S.
Since x  A, then x  S  A.
But then x  S since S  A = S. So A  S.
() Let A be a set such that A  S [Assume the hypothesis].
We wish to show that S  A = S so we will show that S  A  S
and S  S  A.
First let x  S  A. Then this means that x  S  x  A. If x  S
then surely x  S. If x  A then x  S since A  S. So x  S.
Hence S  A  S because x  S  A  x  S.
Now let y  S. Then y  S  A. So S  S  A.
Def: Let A and B be sets. The intersection of the sets A and B,
denoted by A  B, is the set that contains those elements that
are in both A and B. That is,
A  B = { x | x  A  x  B }.
Ex: The intersection of {1, 3, 5} and {1, 2, 3} is {1, 3}.
Ex: The intersection of {1, 3, 5} and {2, 4, 6} is .
Ex: Z  N = N.
Ex: The intersection of the set of even integers and the set of
odd integers is the empty set.
Ex: S   =  for any set S.
Ex: S  A = A if and only if A  S (for any set S).
Def: The sets A and B are called disjoint if their intersection is
the empty set. That is, A and B are disjoint if A  B = .
Ex: The sets {1, 3, 5} and {1, 2, 3} are not disjoint.
Ex: The sets {1, 3, 5} and {2, 4, 6} are disjoint.
Ex: Z  N = N and N is not the empty set so Z and N are not
disjoint.
Ex: The set of even integers and the set of odd integers are
disjoint sets.
Ex: S and  are disjoint for any set S.
Note that the cardinality of the union of two disjoint sets is the
sum of the original sets’ cardinalities. That is,
|A  B| = |A| + |B| if and only if A  B = .
What if A and B are not disjoint?
Consider the union of two arbitrary sets A and B. If I simply add
the cardinality of A to the cardinality of B in an attempt to find
the cardinality of A  B then I might overcount a few things.
Each member of A gets counted once and each member of B
gets counted once. This is fine if A and B have no common
members. But if A and B do have common members, then each
of them will get counted twice. To remedy this, I can subtract
out the number of elements common to A and B. That is, I can
subtract out the cardinality of A  B.
This observation produces the general formula:
|A  B| = |A| + |B| - |A  B|.
Note that our previous formula (when A  B = ) is simply a
special case of this more general formula (when |A  B| = 0).
Def: Let A and B be sets. The difference of A and B, denoted by
A - B, is the set containing those elements that are in A but not in
B. This is also called the complement of B with respect to A.
A - B = { x | x  A  x  B }.
Ex: The difference of {1, 3, 5} and {1, 2, 3} is {5}.
Ex: The difference of {1, 3, 5} and {2, 4, 6} is {1, 3, 5}.
Ex: Z - N = Z-. This is the set of negative integers.
Ex: The difference of the set of even integers and the set of
odd integers is the set of even integers.
Ex: S -  = S for any set S.
Up to this point, we have allowed a set to have any kind of
members we want. This allows us to talk about such sets as
{Jim, my right shoe, -10, math}.
What we can do to restrict our use of sets is to specify a
universal set U from which other sets we construct must take
their members. This sort of restriction is often useful because
knowing that all members of a set are of the same type can
allow us to do things with a set that we couldn’t otherwise do.
When it is convenient for us, we will introduce such a universal
set to be used with certain sets we will construct.
Ex: Let U = Z. Then we can specify the set of positive
integers as simply { x | x > 0}.
Def: Let U be the universal set. The complement of the set A is
the set containing all elements that are in U but not in A. That is,
the complement of A is U – A.
U – A = { x | x  U  x  A }.
The complement of the set A is often denoted as “A with a bar
over it”. By introducing the universal set U, we can use such an
abbreviated notation in place of U – A. In the slides we will
either stick with U – A or another common notation, A’, to denote
the complement of A. This is mainly due the unavailability of the
symbol “A with a bar over it”.
Ex: {x | x is odd}’ = {x | x is even} if U = Z.
Ex: {x | x is rational}’ = {x | x is irrational} if U = R.
Set Identities
We have a table of set identities just as we had a table of
logical equivalences. This is table 1 on page 89 of the text.
Take a look at this table and compare it to our table for logical
equivalences. You will find them to be strikingly similar. This
is not a coincidence.
Every set operation that we introduced could be expressed in
set builder notation using logic. So it turns out that each one
of these set identities (many of which have already been
presented with the corresponding operations) are direct
results of the corresponding logical equivalences.
This also means we can use membership tables (ala truth
tables), logical equivalences in set builder notation, or the
corresponding rules of set theory to prove each identity.
Ex: Prove the set identity (A  B)’ = A’  B’ which is one of De
Morgan’s Laws.
Proof (using set theory): Recall that to show two sets are
equal, we can show subset inclusion both ways.
((A  B)’  A’  B’ ) Let x  (A  B)’. Then x  A  B. So that
means that x  A and x  B. So x  A’ and x  B’. Then it
follows that x  A’  B’. So we proved (A  B)’  A’  B’.
(A’  B’  (A  B)’ ) Let x  A’  B’. Then x  A’ and x  B’.
So that means that x  A and x  B. Then x  (A  B).
Hence x  (A  B)’. So we proved A’  B’  (A  B)’.
Proof (logic): (A  B)’ = { x | x  A  B } = { x | (x  A  x  B)}
= { x | x  A  x  B } = { x | x  A’  x  B’ } = { x | x  A’  B’ } =
A’  B’.
Preliminaries
• Turn in HW4 (make sure your name is on it)
• Pass back HW3
– average: 76%, adjusted avg: 81.5%, median: 82%
– previous 2 HWs were ~ avg: 86.5%, median: 90%
• Emmanuel graded 1.5: 20ac, 24, and 26 (red)
• Pascal graded the others (green)
• http://www.cs.virginia.edu/~cmt5n/cs202/hw3/
– I will post the grading key later today (not up yet)
Generalized Unions and Intersections
We can generalize our notions of union and intersection to
apply to more than two sets.
Def: The union of a collection of sets {Ai} is the set that
contains those elements that are members of at least one set
in the collection.
Def: The intersection of a collection of sets {Ai} is the set that
contains those elements that are members of all sets in the
collection.
Whenever we generalize a definition, the new definition should
include the old, more specialized definition as a specific case.
As you can verify, the union of two sets is covered properly.
Computer Representations of Sets
Consider a finite universal set U = {a1, a2, …, an}. Hence the
cardinality of the universal set is n. We can represent a set
from this universe by a bit string of length n. We set the ith bit
in the string to a 1 if that element is present in the set and set
it to a zero if that element is not present.
Ex: Let U = {s, e, t}. What set does the bit string 001 represent?
{t} since the only 1 in the string is at the 3rd bit.
How would we represent {s, t}?
101 since only element e is not present.
Note that this representation is maximally efficient. That is,
every bit string of length n corresponds to a set from the
universe U of size n. And every set from a universe of size n
can be represented by one of these bit strings of length n.
We call such a setup a one-to-one correspondence. This
particular one-to-one correspondence turns out to be extremely
useful.
One reason it is useful is because it allows us to use bit
operations to compute corresponding set operations very
efficiently. A bitwise complement corresponds to a set compl.
The second (and more important) reason that it is useful is we
can utilize this representation to provide very simple proofs for
some theorems involving the cardinality of sets.
Theorem: Let S be a finite set with cardinality n. Then |P(S)| = 2n.
Proof: Let S be a finite set with cardinality n.
We wish to show that the number of different subsets of S is 2n.
Recall that we can represent a subset of S by a bit string of
length n where the ith bit in the string indicates whether the ith
element of S is present in the subset or not.
Recall also that every bit string of length n represents a subset
of S. This is a one-to-one correspondence.
So the number of different subsets of S is precisely the same as
the number of different bit strings of length n.
We know that the number of different bit strings of length n is 2n.
Hence the number of different subsets of S is 2n as well.