Posted 27
May 2008
OPERATIONS
ON SETS
The unlinked entries have not yet been written. The links below each one connect you to the
relevant sections of Wikipedia.
Subsets and inclusion
Union and intersection
union and intersection
Complement
complement
subtraction
Powerset
powerset
Cartesian
Product
cartesian product
Diagonal
Tuples tuple
For sets A and B, the notation 
refers to the set the
set of elements of A
that are not in B. (See sebuilder notation). Examples:
¨
¨
¨ is the set of nonzero real numbers.
¨ ,
since .
¨ is a meaningless expression, since is not a set.
¨ {1, 3, 5, 6} \ {4, 5, 7} = {1, 3, 6}.
¨ {1, 3, 5, 6} \ {2, 4, 8} = {1, 3, 5, 6}.
Union and intersection
Definition:union
For any sets
A and B, the union AB of A and B is defined by
|
AB={x‖xA∨xB}
|
(0.15)
|
Definition:intersection
For any sets
A and B, intersection A∩B is defined by ,
|
A∩B={x‖xAxB}
|
(0.16)
|
Example
Let A={1,2} and
B={2,3,4}. Then AB={1,2,3,4} and A∩ B={2}. If C={3,4,5}, then A∩C=.
Exercise
What are {1,2,3}{2,3,4,5}
and {1,2,3}∩{2,3,4,5}? Answer: {1,2,3}{2,3,4,5}={1,2,3,4,5}
and {1,2,3}∩{2,3,4,5}={2,3}.
Exercise
What are NZ
and N∩Z? Answer: NZ=Z
and N∩Z=N.
Remark
Union and
intersection mirror the logical
connectives ` ∨' and ` ' of section *. The
connection is by means of the extensions of the predicates
involved. The extension of P∨ Q is the union of the
extensions of P and of Q, and the extension of , PQ is the intersection
of the extensions of P and of Q.
Example
Let
S be a set of
poker chips, each of which is a single color, either red, green or blue. Let R,
G, B be respectively the sets of red, green and blue chips. Then RB is the set
of chips which are either red or blue; the ` ' symbol mirrors the
"or". And R∩B=, since it is false that a chip can be both red and blue.
Warning
Although union corresponds
with " ∨", the set RB of the preceding example could also be
described as "the set
of red chips and blue chips"!
Exercise
Prove that for any sets A and B, A∩ BAB.
Answer: By Definition *, we must show
that if xA∩B, then xAB.
By Definition *
(of intersection), xA∩B implies that xA
and xB.
By Definition *
(of union), if xA, then xA
B.
Exercise
Prove that for any
sets A and B, A∩ BA
and AAB.
Definition:disjoint
If
A and B are sets and A∩ B= then A and B are said to be disjoint.
Exercise
Name three different
subsets of Z that are disjoint from N. Answer: There are of course an
infinite number of answers. Some correct answers are: The set of all negative
integers, the set of all negative even integers, {-1,-2,-3}, {-42}, and the
empty set (which is disjoint from every set).
Exercise
If A and B are
disjoint, must P(A) and P(B) be disjoint?
The universal set and complements
Since we cannot talk
about the set
of all sets, there is no universal way to mirror TRUE as a set. However, in
many situations, all elements are of a particular type.
For example, all the elements in Example * are chips. The set of all elements
of that type
constitutes a single set containing as subsets all the sets under
consideration. Such a set is called a universal set,
and is customarily denoted U .
Given a universal
set, we can define an operation corresponding to ` ¬', as in the following
defintion.
Definition:complement
If A is a set,
Ac is the set of
all elements in U but not in A. Ac is called the complement
of A (note the spelling).
Usage
Ac may be denoted A
‾ or A' in other texts.
Example
The complement of N
in Z is the set of all negative integers.
Definition:set difference
Let A and B be any two sets. The set difference A-B is the set defined by ,
|
A-B={x‖xAx\mathordB}
|
(0.17)
|
Example
Let A={1,2,3} and
B={3,4,5}; then A-B={1,2}.
Exercise
What is Z-N? What is
N-Z? Answer: Z-N is the set of all negative integers. N-Z=.
Fact
f
there is a universal set U , then Ac =U -A.
Usage
A-B is written
A\B in many texts..
Exercise
Let A={1,2,3},
B={2,3,4,5} and C={1,7,8}. Write out the elements of the following sets:
ll@ ll
a) AB f) B-C
b) A∩B g) A∩(BC)
c) BC h) B(A∩C)
d) B∩C i) B(A-C)
e) A-B
Answer: (a) 1,2,3,4,5; (b) 2,3;
(c) 1,2,3,4,5,7,8; (d) none; (e) 1; (f) 2,3,4,5;
(g) 1,2,3; (h) 1,2,3,4,5; (i) 2,3,4,5.
Exercise
State whether each
item in the first column is an element of each set in the second
column. A={1,3,7}, B={1,2,3,4,5}, and the universal set is Z.
rr@ rr
1) 1 1) AB
2) 4 2) A∩B
3) 7 3) A-B
4) -2 4) A-Z
5) 5) Bc
6) {2,4,5} 6) PA
7) {1,3} 7) P(A∩B)
Answer: 1) 1 and 2. 2) 1. 3) 1, 3 and
5. 4) 5. 5) 6 and 7. 6) None. 7) 6 and 7.
Exercise
Explain why the
following statements are true for all sets A and B or give examples
showing they are false for some A and B.
P(A)∩P(B)=P(A∩B)
P(A)P(B)=P(AB)
P(A)-P(B)=P(A-B)
Answer: Proof of (a):
(b) is false; for example, {1,2}P({1}{2})
but {1,2}P{1}P{2}.
(c) is false: for
example, the empty set is an element of any powerset, so it
is an element of P(A-B). Since it is in both P(A) and P(B), it is not in
P(A)-P(B).
Exercise
Show that for any sets A and B included
in a universal set U , if AB=U and A∩B=, then B= Ac .
The
powerset of a set
Definition:powerset
If
A is any set, the
set of all subsets
of A is called the powerset of A and is denoted PA.
Remark
Using setbuilder
notation, PA={X‖XA}.
Example
The powerset of
{1,2} is {,{1},{2},{1,2}}, and the powerset of {1} is {,{1}}.
Fact
he definition of
powerset gives two rules of inference:
|
BA |