abstractmath.org
help with abstract math
Produced by Charles Wells. Home. Website Contents Website Index
Back to Sets beginning
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.
union and intersection
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}.
For any sets
A and B, the union AB of A and B is defined by
AB={x‖xA∨xB}

(0.15) 
For any sets
A and B, intersection A∩B is defined by ,
A∩B={x‖xAxB}

(0.16) 
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=.
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}.
What are NZ
and N∩Z? Answer: NZ=Z
and N∩Z=N.
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.
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.
Although union corresponds
with " ∨", the set RB of the preceding example could also be
described as "the set
of red chips and blue chips"!
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.
Prove that for any
sets A and B, A∩ BA
and AAB.
If
A and B are sets and A∩ B= then A and B are said to be disjoint.
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).
If A and B are
disjoint, must P(A) and P(B) be disjoint?
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.
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).
Ac may be denoted A
‾ or A' in other texts.
The complement of N
in Z is the set of all negative integers.
Let A and B be any two sets. The set difference AB is the set defined by ,
AB={x‖xAx\mathordB} 
(0.17) 
Let A={1,2,3} and
B={3,4,5}; then AB={1,2}.
What is ZN? What is
NZ? Answer: ZN is the set of all negative integers. NZ=.
f
there is a universal set U , then Ac =U A.
AB is written
A\B in many texts..
Let A={1,2,3},
B={2,3,4,5} and C={1,7,8}. Write out the elements of the following sets:
[email protected] ll
a) AB f) BC
b) A∩B g) A∩(BC)
c) BC h) B(A∩C)
d) B∩C i) B(AC)
e) AB
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.
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.
[email protected] rr
1) 1 1) AB
2) 4 2) A∩B
3) 7 3) AB
4) 2 4) AZ
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.
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(AB)
Answer: Proof of (a):
CP(A)∩P(B)
⇔Definitionofintersection CP(A)
and CP(B)
⇔Definitionofpowerset CA
and CB
⇔Definitionofintersection CA∩B
⇔Definitionofpowerset CP(A∩B)

(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(AB). Since it is in both P(A) and P(B), it is not in
P(A)P(B).
Show that for any sets A and B included
in a universal set U , if AB=U and A∩B=, then B= Ac .
If
A is any set, the
set of all subsets
of A is called the powerset of A and is denoted PA.
Using setbuilder
notation, PA={X‖XA}.
The powerset of
{1,2} is {,{1},{2},{1,2}}, and the powerset of {1} is {,{1}}.
he definition of
powerset gives two rules of inference:
BABPA

(0.13) 
and
BPABA

(0.14) 
The empty set is an
element of the powerset
of every set, since it is a subset
of every set.
The empty set is not
an element of every set; for example, it is not an element of {1,2}.
How many elements do
each of the following sets
have?
{1,2,3,{1,2,3}}
{}
{,{}}
Answer: a: 4. b: 0. c: 1. d: 2.
Write the powerset of
{5,6,7}. Answer: {,{5},{6},{7},{5,6},{6,7},{5,7},{5,6,7}}
State whether each
item in the first column is an element of each set in the second
column.
rlcrl a) 1
a) Z
b) 3 b) R
c) π c) {1,3,7}
d) {1,3} d) {xR‖x= x2 }
e) {3,π} e) P(Z)
f) f)
g) Z g) {Z,R}
Answer:

a 
b 
c 
d 
e 
f 
g 
a 
Y 
Y 
Y 
Y 
N 
N 
N 
b 
Y 
Y 
Y 
N 
N 
N 
N 
c 
N 
Y 
N 
N 
N 
N 
N 
d 
N 
N 
N 
N 
Y 
N 
N 
e 
N 
N 
N 
N 
N 
N 
N 
f 
N 
N 
N 
N 
Y 
N 
N 
g 
N 
N 
N 
N 
Y 
N 
Y 
In analytic
geometry, one specifies points in the plane by ordered pairs of real numbers,
for example <3,5>. (Most books use round parentheses instead of pointy
ones.) This is not the same as the twoelement set {3,5}, because in
the ordered pair the order matters: <3,5> is not the same as <5,3>.
In the ordered pair
<3,5>, 3 is the first coordinate
and 5 is the second coordinate.
Sometimes, the two coordinates are the same: for example, <4,4> has first
and second coordinates both equal to 4.
An ordered pair in
general need not have its first and second coordinates of the same type.
For example, one might consider ordered pairs whose first coordinate is an integer and whose
second coordinate is a letter of the alphabet, such as <5,`a'> and
<3,`d'>.
The following
specification gives the operational properties of ordered pairs:
An
ordered pair <x,y> is a mathematical object distinct from x and y which
is completely determined by the fact that its first coordinate is x and its
second coordinate is y.
Specification * implies that ordered
pairs are the same if and only if their coordinates are the same:
(<x,y>=<x',y'>)≡(x=x'y=y') 
Thus we have a method:
Method: twoshowTo prove two ordered pairs <x,y>
and <x',y'> are the same, prove that x=x' and y=y'.
Which of these pairs
of ordered
pairs are equal to each other?
<2,3>,
<3,2>.
<3,4>,
<3,2>.
<2,4>,
<4,2>.
Answer: The pairs in (a) are different; the pairs in
(b) and (c) are equal.
discussion In texts
on the foundations of mathematics, an ordered pair <a,b> is often defined
to be the set {{a,b},{a} }. Prove that at least when a and b are numbers this
definition satisfies Specification * (with a suitable
definition of "coordinate"). Answer: Let Sa,b = {{a,b},a }.
Define the first coordinate
of S to be the only number in the set,
and the second coordinate to be the same as the first coordinate if the set
that is an element of S is a singleton;
otherwise the second coordinate
is the element of the set in S that is different from the first coordinate.
Things get sticky if a can be a set
 you have to refer to the "Axiom of Foundation" that in effect
forbids infinite
chains of the elementof relation. Note: In some texts on foundations, numbers
are defined as sets. We do not take that attitude here, so that the clause
"at least when a and b are numbers" implies that they are not sets.
In order to
generalize the idea of ordered pair to allow more than two coordinates,
we need some notation.
Let
n be an integer,
n≥1. Then n is defined to be the set
{iN‖1≤i≤n} 
3={1,2,3}.
Let m and n be
positive integers. What is m∩n? What is mn?
Answer: m∩n is k, where k is the minimum of m and n, and mn
is l, where l is the maximum of m and n.
A tuple is a
generalization of the concept of ordered pair. A tuple satisfies this
specification:
A tuple of length n, or ntuple, is a mathematical object which
T
has an ith entry for
each in,
and
is distinct from its
entries, and
is completely
determined by specifying the ith entry for every in.
An ordered pair is
the same thing as a 2tuple.
A 3tuple is usually
called an ordered triple.
The usual way of
denoting a tuple is by listing its entries in order inside angle brackets.
<1,3,3,2> is
a tuple of integers. It has
length 4. The integer
3 occurs as an entry in this 4tuple twice, for i=2 and i=3.
Tuples and their coordinates
are often named according to a subscripting convention, by which one refers to
the ith entry by subscripting i to the name of the tuple. For example,
let a=<1,3,3,2>; then a2 =3 and a4 =2. One often makes this convention
clear by saying, "Let a=< ai >in be an ntuple."
Many authors would
use curly brackets here: " { ai }in
." Nevertheless, a is not a set.
Many computer
scientists refer to a tuple
as a "vector". Although this usage is widespread, it is not
desirable; in mathematics, a vector is a geometric object which can be represented
as a tuple, but
is not itself a tuple.
It follows from
Specification *
that two ntuples
are equal if and only if they have the same entries. Formally:
Theorem: tuplteHow to tell if tuples are equalLet a
and b be ntuples. Then
a=b≡in( ai = bi ) 
Which of these pairs
of tuples are equal?
<3,3>,
<3,3,3>.
<2,3>,
<2,3,3>.
<2,3,2>,
<3,2,2>.
Answer: None of them are equal.
For formal
completeness, one also has the concept of the null
tuple (or empty tuple) <>, which has length 0 and no entries, and
a 1tuple, which
has length 1 and one entry.
The index set for the null tuple is the empty
set. There is only one null tuple.
In the context of formal language theory the unique null tuple is often denoted
" Λ" (capital lambda) or sometimes " ε" (small
epsilon). We will use the notation Λ here.
For each tuple, give the integer n for
which it is an ntuple
and also give its second entry.
[email protected] ll
a) <3,4,0> d) << <2,<1,5>>,7>,9>
b) << 3,4>,<1,5>> e) <3,{1,2}>
c) <3,<5,<2,1>>> f) <N,Z,Q,R>
Answer: 1. a) 3,4. b) 2,<1,5>.
c) 2,<5,<2,1>>. d) 2,9. e) 2,{1,2}. f) 4,Z.
[ label:
tupasfuncsec]
Let n be a positive integer, and let
\n={1,2,…,n} 
An ntuple
\a=< a1 ,…, an
> 
in An associates to each element i of \n an element ai of A. This determines a function i‖→ ai with domain \n and codomain
A. Conversely, any such function determines
an ntuple in An by setting its coordinate at i to be its value at i.
When \a A1 × A2 ×…× An , so that different components
are in different sets, this way
of looking at ntuples is more complicated. Every coordinate ai is an element of the union C= A1 A2 … An , so that \a
can be thought of as a function from \n→C. In this case, however, not every
such function is a tuple in A1 × A2 ×…× An : we must impose the additional
requirement that ai Ai .
We sum all this up
in an alternative definition of tuple:
[ label:
tupfuncdef] A tuple in Πi=1 n Ai
is a function
\a:\n→ A1 A2 … An 
with the property that for each i, a(i) Ai .
The tuple
<2,1,3> is the function 1‖→2, 2‖→1, 3‖→
3 (compare Section [permexex] ).
The tuple
<5,5,5,5> is the constant function C5 :{1,2,3,4}→Z.
Write the domain and the graph of these tuples regarded as functions
on the index set.
<2,5,1,3,6>.
<π,5,π1,2>.
<<
3,5>,<8,7>,<5,5>>.
Answer: a) Domain:
{1,2,3,4,5}.
Graph: ({<1,2>,<2,5>,<3,1>,<4,3>,<5,6>)}.
b) Domain: {1,2,3,4}.
Graph: ({<1,π>,<2,5>,<3,π1>, <4,2>)}.
c) Domain: {1,2,3}.
Graph: ({<1,<3,5>>,<2,<8,7>>,<3,<5,5>>)}.
[ label:
reldath] A simple database might have records each of which consists of
the name of a student, the student's student number, and the number of classes
the student takes. Such a record would be a triple <w,x,n>, where w is an
element of the set A* of strings of English
letters and spaces (this notation is introduced formally in Definitions
[listsetdef] and [stringdef] ), x is an element of the set D* of strings
of decimal digits, and nN. This triple corresponds to a function
F:{1,2,3}→ A* × D* ×N with the property that F(1) A* , F(2) D* and F(3)N.
Modeling detabases
this way is the principle behind relational database theory.
[ label:
notatrem] In the case that all the Ai are the same, so that \a An , we now have
the situation that \fs\nA (the set of functions from \n
to A, where \n={1,2,…,n}) and An (the set of ntuples in A) are essentially the
same thing. That is the origin of the notation \fsAB.
The discussion above
suggests that by regarding a tuple as a function set, we can use any set as index set.
In computer science
it is often convenient to start a list at 0 instead of at 1, giving a tuple < a0 , a1 ,…, an >. This is then a tuple
indexed by the set {0,1,…,n} for
some n (so it has n+1 entries!).
[ label:
infseqind] An infinite sequence
of integers is indexed by N+ , so it is an element of \fs
N+ Z.
This is another look
at Example [reldath] . The point of view that a triple < Jones ,
1235551212 ,4> is a function with domain
{1,2,3} has an arbitrary nature: it doesn't matter that the name is first, the
student number second and the number of classes third. What matters is that
Jones is the name, 1235551212 is the student number and 4 is the number of
classes. Thus it would be conceptually better to regard the triple as a function whose domain
is the set { Name , StudentNumber , NumberOfClasses }, with
the property that f( Name ) A* , F( StudentNumber ) D* and F(
NumberOfClasses )N. This eliminates
the spurious ordering of data imposed
by using the set {1,2,3} as domain.
In this context, the
elements of a set such as
{ Name ,
StudentNumber , NumberOfClasses } 
are called the field
names of the database.
[ label:
functupledef] A function T:S→A is
is also called an Stuple or a family of
elements of A indexed by S.
Write each of these functions as tuples.
F:{1,2,3,4,5}→R,
Γ(F)=({<2,5>,<1,5>,<3,3>,<5,1>,<4,17>)}.
F:{1,2,3,4,5}→R,
F(n)=(n+1)π.
x‖→ x2
:{1,2,3,4,5,6}→R.
Answer: a)
<5,5,3,17,1>. b) <2π,3π,4π,5π,6π>. c)
<1,4,9,16,25,36>.
Let A and B be sets.
A×B is the set of all ordered pairs whose first coordinate is
an element of A and whose second coordinate is
an element of B. A×B is called the Cartesian
product of A and B (in that order).
if A={1,2} and
B={2,3,4}, then
A×B= {<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,<2,4>
} 
and
B×A=
{<2,1>,<2,2>,<3,1>,<3,2>,<4,1>,<4,2> } 
Write out the
elements of {1,2}×{a,b}. Answer: <1,a>,<1,b>,<2,a>,<2,b>.
Fact: emptykillsIf A is any set, then A×=×A=.
Prove Theorem .
R×R is often called
the "real plane", since it consists of all ordered pairs of real
numbers, and each ordered pair represents a point in the plane once a
coordinate system is given. Graphs of straight lines and curves are subsets of R×R.
For example, the xaxis is {<x,0>∣xR } and the parabola y= x2 is
{<x,y>∣xRy= x2 }, which could be written {<x, x2
>∣xR
} (recall the discussion in Section *).
For
any set A, the subset
{<a,a>∣aA } of A×A of all pairs whose two coordinates
are the same is called the diagonal of A, denoted ΔA .
Write out the
diagonal of {1,2}×{1,2}. Answer: {<1,1>,<2,2>}.
The diagonal ΔR of
R×R is the 45degree line from lower left to upper right. It is the graph of
the equation y=x.
The notion of
Cartesian product can be generalized to more than two factors using the
idea of tuple.
Let A1 , A2 ,…, An be sets
 in other words, let < Ai >in be an ntuple of sets. Then
A1 × A2 ×…× An is the set
{< a1 , a2 ,…,
an >∣in( ai Ai ) } 
(0.18) 
of all ntuples whose ith coordinate
lies in Ai .
The set R×Z×R has triples
as elements; it contains as an element the ordered
triple <π,2,3>, but not, for example, <2,π,3>.
Observe that R×N×R,
(R×N)×R and R×(N×R) are three different sets; in fact, any
two of them are disjoint.
Of course, in an obvious sense they all represent the same data.
Consider the set
D={<m,n>‖m
divides n} 
where m and n are of type integer. Thus <3,6>, <3,6> and
<5,0> are elements of D but not <3,5>. D is not a Cartesian
product, although it is a (proper) subset of the
cartesian product Z×Z. The point is that a pair in A×B can have any element of
A as its first coordinate
and any element of B as its second coordinate, regardless of what the first
coordinate is. In D what the second coordinate is depends on what the first
coordinate is.
A set such as D is a
relation, a
concept discussed later.
Exercises
through give "facts" which may or may not be correct for all sets A, B and C.
State whether each "fact" is true for all sets A, B and C, or false
for some sets A, B or C, and for those that are not true for all sets, give
examples of sets
for which they are false.
A×A=A. Answer: This is false for any nonempty set A because
the elements of A×A are pairs of elements of A, and an ordered pair is distinct
from its coordinates
(see *).
(The last statement implies that in fact for nonempty A, A×A and A have no
elements in common.) The statement A×A=A is true if A=.
A×B=B×A. Answer: False
if A and B are both nonempty.
A(B×C)=(AB)×(A
C). Answer: False for nonempty A (and some other cases as well).
A∩(B×C)=(A∩B)×(A∩C).
A×(B×C)=(A×B)×C.
P(A×B)=P(A)×P(B). Answer: A=B= is an example that makes it false, since P(×) but the only element of P()×P() is <,>.
The statements in
problems through are true for all sets A, B and C,
except that in some cases some of the sets A, B and C have to be nonempty if
the statement is to be true for all other sets named. Amend the statement
in each case so that it is true.
For
all sets A, B and
C, A×C=B×CA=B. Answer: "For all sets A and
B and all nonempty sets C, …"
For all sets A and B, A×B=B×AA=B. Answer: "For all nonempty
sets A and B…"
For
all sets A, B and
C, AB(A×C)(B×C).
Answer: Correct as it stands.
The
dmfuncs.m package contains the command CartesianProduct, which gives the
Cartesian product of a sequence of sets. For example,
CartesianProduct[{1,2},{a,b,c},{x,y}]
produces
{{1, a, x}, {1, a, y}, {1, b, x}, {1, b, y}, {1, c, x}, {1, c, y},
{2, a, x}, {2, a, y}, {2, b, x}, {2, b, y}, {2, c, x}, {2, c, y}}
Mathematica The
command CartesianProduct mentioned in * works on any
lists, not just sets
(see *,
page pageref).
Write a precise description of the result given when CartesianProduct is
applied to a sequence of lists, some of which contain repeated entries.
If all the sets in a Cartesian
product are the same, exponential notation is also used. Thus A2 =A×A, A3 =A×A×A,
and in general
An =A×A×…×A 
( n times). These are called Cartesian powers
of A; in particular, A2 is the Cartesian square
of A. This notation is extended to 0 and 1 by setting A0 ={<>} (the singleton set
containing the null tuple
as an element) and A1 =A.
Let A={1,2} and
B={3,4,5}. Write all the elements of each set:
[email protected] ll
a) A0 f) B×A
b) A1 g) A×A×B
c) A2 h) A×(A×B)
d) A3 i) (A×B)A
e) A×B j) (A×B)∩A
Answer:
ll (a) Λ
(b) 1,2
(c) <1,1>,<1,2>,<2,1>,<2,2>
(d) <1,1,1>,<1,1,2>,<1,2,1>,<1,2,2>,
<2,1,1>,<2,1,2>,<2,2,1>,<2,2,2>
(e) <1,3>,<1,4>,<1,5>,<2,3>,<2,4>,<2,5>
(f) <3,1>,<3,2>,<4,1>,<4,2>,<5,1>,<5,2>
(g)
<1,1,3>,<1,1,4>,<1,1,5>,<1,2,3>,<1,2,4>,<1,2,5>,
<2,1,3>,<2,1,4>,<2,1,5>,<2,2,3>,<2,2,4>,<2,2,5>
(h)
<1,<1,3>>,<1,<1,4>>,<1,<1,5>>,<1,<2,3>>,
<1,<2,4>>,<1,<2,5>>,<2,<1,3>>,<2,<1,4>>,
<2,<1,5>>,<2,<2,3>>,<2,<2,4>>,<2,<2,5>>
(i) <1,3>,<1,4>,<1,5>,<2,3>,<2,4>,<2,5>,1,2
(j)
For each pair of
numbers <m,n>{1,2,3,4,5,6,7}×{1,2,3,4,5,6,7},
state whether item m in the first column is an element of the set in item n of the
second column. A={1,3,7}, B={1,2,3,4,5}.
[email protected] ll
1. <3,5> 1. A×A
2. <3,3> 2. A3
3. <3,3,5> 3. A×B
4. {<3,5>,<7,5> } 4. B×A
5. <{3,7},{3,5}> 5. P(A×B)
6. 6. PA×PB
7. <1,7,7> 7. B2
Answer:
cccccccc 1 2 3 4 5 6 7
1 N N Y N N N Y
2 Y N Y Y N N Y
3 N N N N N N N
4 N N N N Y N N
5 N N N N N Y N
6 N N N N Y N N
7 N Y N N N N N