A
means that a is an element of A.
SET THEORY
Objectives: To remember what sets are and basic operations with sets.
Recall
1. A set
is a
collection of objects called elements.
For
example, "car, apple, pencil" is a well defined set
whose elements are a
car, an apple, and a pencil. This set has three elements.
The set "1,2,3,4,5" has five elements.
1.1 Any set is denoted by capital letters: A, B, C,… There is an empty set (or the null set) denoted by Ø. This is a set that contains no elements.
1.2 Mostly letters
will identify the elements of
a set. Thus
A={a1,
…,an} (a)
means that the set A consists of the elements a1,
…,an.
The roster notation
is a complete or implied
listing of all elements of the set. So A described
by (a) and
B={2,4,6,8,…,40} are examples of roster notation defining sets
with n and
20 elements respectively.
1.3
The set
builder notation is
used when the roster method is cumbersome
or impossible. Thus
for
A={all
positive integers} (b)
the roster method would be impossible since there are
too many
integers to actually list out .
1.4 The
notation aA
means that a is an element of A.
1.5 The notation a
A
indicates non membership of a in
A.
1.6 A subset B of a set A is another set whose elements are also elements of A. All sets under consideration will be subsets of the total set W (also called space or the universal set).
1.7 If a set consists only of n elements, then the total number of its subsets equals 2^n.
1.8 P(A) denotes the set of all subsets of a set A.
Example 1. We
shall denote by fi the faces
of a die. These 6 faces are the elements of
the total set W={f1,f2 ,f3,f4,f5,f6},
hence W has 2^6=64 subsets. Some of
those would be:
Ø, {f1}, {f2},…., {f6},
{f1,f2},….., {f1,f2,f3},
……, W.
Example 2. Suppose a coin is tossed
twice. The
resulting outcomes are four objects: hh, ht, th, tt where hh
is the
abbreviation for the appearance of the head each time the coin is
tossed,
and tt is the abbreviation for the appearance of the tail each
time the
coin is tossed. So the total set is W={hh, ht, th, tt} and then
it has
2^4=16 subsets, such as
A={head shows on
the
first toss} A={hh,
ht}
B={only
one head shows} B={ht,
th}
C={head shows at least once} C={hh,
ht,
th}.
In the first column the sets are represented
by their
properties as in (b), while in the second column they are
expressed in
terms of their elements, as in (a).
A
means
that B is a subset of A.
2.2. ØAAW,
for
any A.
2.3 This relationship called
inclusion has
some properties:
* Transitivity:
AB
and BC,
then AC.
* Reflexivity:
AA;
* Anti symmetry: AB
and
BA
then A=B.
2.4 A=B means
that AB
and BA
and we say A is equal to B.
B)
is also a set whose elements are all
elements of A or B or both, as shown
in the diagram
below.
The set AB
is
defined to be {x|xA
or xB}.
The vertical bar "|" is read "such that"
so this notation is read aloud
as "the set of x such that x belongs to A
or x belongs to B".
Here are some properties of
union.
* Commutative: A+B=B+A
* Associative (A+B)+C=A+(B+C);
* If AB,
then
A+B=B;
* A+A=A;
*
A+Ø=A;
* A+W=W.
B)
is
also a set whose elements are all common elements of both A and B,
as
shown in the diagram below.
The set AB
is
defined to be {x|A
and xB}.
4.1 Here are some
properties of this operation:
* Commutative:
AB=BA
* Associative (AB)C=A(BC);
* Distributive: A(B+C)=AB+AC;
* If AB,
then
AB=A;
* AA=A;
*
AØ=Ø;
* AW=A.
4.2 If two sets were described by the properties
of their
elements as in (b), then their intersection AB is specified by
including
these properties between braces. For example, if W={1,2,3,4,5,6}
and
A={even} and B={less than five}, then
AB={even and less than five} so AB={2,4}.
Recall 5. Two sets are called mutually
exclusive sets (or
disjoint sets) if they
have no common elements,
that is if
AB=Ø.
Several sets A1, A2, ….are mutually
exclusive iff AiAj=Ø
for any
i,j.
Recall 6. A partition
of
a set W is a collection of mutually exclusive subsets
Ai of
W whose union equals W: A1+A2+...An=W and Ai 7.1 From the definition
it follows that:
Example 3
If A={-3, pi, sqrt(2) } and it's obvious
that the universal set W=R, then
Recall 8. De Morgan’s
Laws. See
illustration below.
This law says that if we
replace all sets by their complements,
all union by intersections and all
intersections by union, the identity
is preserved.
Example 4 Let A={a,d,e,g} and B={c,d,f,g}
in the
universe W={a,b,c,d,e,f,g,h,i}. To verify the first of Morgan’s
laws find
each of these two sets independently to find that they are indeed
the
same. First
1. A={1,2,3,4,5},
B={1,2,3}, C={4,5,6}. True or False:
2. Find the set X using the following
information:
3. Find the set X using the
following information:
4. Find the set X using the
following information:
5. Find the element x
from {1,x, 5} 6.
Find
the
element x from {3,4,x, 7}={2,3,4,7}.
7. Find the element x from
{2,x, 11} 8. Find the element x
from {9,2x, 11} 9.
Find the element x from {2,3x,
12} 10.
A={xAj=Ø for any
i,j.
Recall 7. The complement 
of a
set A is a set consisting of all elements of W that are not in A.
* A+=W;
* A=Ø;
consists of those real
numbers that are
not in
A.
A+B={a,c,d,e,f,g} so
={b,h,i}.
={b,c,f,h,i}, {a,b,e,h,i} is 
,
hence
the intersection of the
complements is 
={b,h,i}.
As predicted,
{b,h,i}={b,h,i}!
Exercises
a) 1A
and
1C;
f) B+C=A;
b) 1A
or
1C;
g)AB=C;
c) 1B
and 1C;
h) xA
implies xB;
d) {1,2,3}A;
i) xB
implies xA.
e) {1,3,4}B;
X+{1,2}={1,2,3} and X{2,3}.
X{1,2,3,4}={3,4} and
X{1,3,4,5}.
X{1,2,5,7}={5,7} and
X+{5,7,9}={3,5,7,8,9}.
{x, 5}={5,9}.
{2,3,11,x}.
{7,15}=Ø.
{1,21}={21}.
N,
the remainder from the division of x by 3 is 1 and
x<=16}.
B={yN,
7<=y<14}.
Find
A+B, AB, A-B, B-A (A-B is defined as the
set of all elements that are in A but not in B: A-B=A ).
Notes
on Set
theory