ELEMENTARY
SET
THEORY
Applied
Sta+s+cs
and
Compu+ng
Lab
Indian
School
of
Business
Applied
Sta+s+cs
and
Compu+ng
Lab
Learning
Goals
What
is
a
Set?
Set
Theory
notaBons
Venn
Diagrams
Set
operaBons
De
Morgans
Law
CommutaBve,
AssociaBve
&
DistribuBve
Laws
Cardinality
of
a
Set
2
Applied
Sta+s+cs
and
Compu+ng
Lab
Sets
Are
fundamental
objects
through
which
we
can
dene
all
MathemaBcal
concepts.
Hence,
dicult
to
dene
in
terms
of
more
fundamental
objects
We
will
not
aSempt
to
dene
a
Set
here,
rather
we
will
learn
through
informal
deniBons
and
examples
Applied
Sta+s+cs
and
Compu+ng
Lab
Understanding
through
an
Example
Consider
a
Town
X
with
500
households
Look
at
the
properBes
of
the
collecBon
of
all
those
households
that
own
a
car:
315
of
these
own
a
car
250
own
a
house
Sets
Such
well
dened
collecBon
of
disBnct
objects
is
called
a
Set
So
the
collecBon
of
all
those
households
in
town
X
that
own
car
is
a
Set.
Applied
Sta+s+cs
and
Compu+ng
Lab
Each
household
is
dis+nct
(i.e.
one
household
is
dierent
from
the
other)
This
collecBon
is
well
dened
(i.e.
there
is
no
ambiguity
as
to
whether
or
not
a
household
belongs
to
this
collecBon)
Sets:
NotaBons
Set:
{}
Example
A={1,2,3,4,5}
,
B={2,4,6,8,10,12}
Subset:
AB
,
set
A
contains
few
or
all
elements
of
B
AB
,
set
A
contains
few
elements
of
B
Example:
{1,2}{1,2,3,4,5,6}
A
B,
set
A
is
not
a
subset
of
set
B
Belongs
to:
aA,
element
a
belongs
to
set
A
Applied
Sta+s+cs
and
Compu+ng
Lab
5
Sets:
Venn
Diagrams
We
can
assign
names
to
a
set:
Let
A
be
the
set
of
all
households
in
town
X
that
own
a
car
B:
The
set
of
all
households
in
town
X
that
own
a
house
What
is
common
in
the
deniBons
of
A
and
B?
.
in
town
X..
A,B
are
dened
relaBve
to
the
set,
(say
X)
of
all
households
in
town
X
We
call
the
set
X
the
Universal
Set,
the
set
that
contains
all
the
objects
involved
in
the
problem/quesBon
of
interest
Without
a
Universal
Set
we
nd
it
hard
to
understand
the
meaning
of
Well
Dened
Each
member
in
a
set
A
(
or
B,
X)
is
called
an
element
of
A
We
denote
houeshold1(labeled
ash1)
belongs
to
set
B
by
h1
A
6
Applied
Sta+s+cs
and
Compu+ng
Lab
Sets:
Venn
Diagrams
Sets
can
be
pictured
using
Venn
Diagrams
or
Set
Diagrams
Uses
circles
to
represent
sets
Drawn
inside
a
rectangle
that
depicts
the
universal
set
The
posiBons,
overlap
of
these
circles
indicate
the
relaBonships
between
the
sets
concerned
X
Applied
Sta+s+cs
and
Compu+ng
Lab
Set
OperaBons:
Complement
X
A
Grey
area:
- Those
households
in
town
X
that
do
not
own
a
car
- This
is
called
the
Complement
of
the
set
A
- Denoted
by:
Ac,
contains
all
those
elements
in
X
that
do
not
belong
to
set
A
What
is
the
complement
of
the
Universal
Set
X?
- An
empty
set,
a
set
with
no
elements
- Denoted
by
{}
or
- Generally
referred
to
as
the
Null
Set
Applied
Sta+s+cs
and
Compu+ng
Lab
8
Set
OperaBons:
IntersecBon
and
Union
X X
B
Look
at
the
households
in
the
blue
region:
- Clear
that
those
belong
to
either
A
or
B
or
both
- These
households
own
a
Car
or
Own
a
house
or
own
both
a
car
and
a
house
- This
is
called
the
union
of
sets
A
and
B
- Denoted
by:
A
B
,
contains
all
those
elements
that
belong
to
either
set
A
or
set
B
or
both
- AAc
=X
9
What
is
the
overlapping
region?
Or
What
kind
of
households
are
in
that
region?
- Clear
that
these
belong
to
both
A
and
B
- These
households
own
a
Car
and
Own
a
house
- This
is
called
the
intersecBon
of
sets
A
and
B
- Denoted
by:
A
B,
contains
all
those
elements
that
belong
to
both
set
A
and
set
B
- AAc
=
Applied
Sta+s+cs
and
Compu+ng
Lab
Set
OperaBons:
De
Morgans
Law
Combines
the
three
basic
set
operaBons
The
laws
are:
Bc
- (A
B)c
=
Ac
Bc
- (A
B)c
=
Ac
Where
do
we
use
this?
- If
AB
or
AB
are
dicult
to
compute
- Used
to
simplify
set
theory
mathemaBcs
if
possible
Applied
Sta+s+cs
and
Compu+ng
Lab
10
Visuals
from:hSp://guideocom.blogspot.in/2011/08/de-morgans-laws-venn-diagrams-proofs.html
Set
OperaBons:
De
Morgans
Law
Example
Consider
the
following
scenario:
X:
Set
of
all
employees
in
a
company
A:
Set
of
all
employees
in
the
company
whose
monthly
salary
60,000
B:
Set
of
all
women
employees
in
the
company
Try
to
dene
the
set
(AUB)c
Let
us
try
it
the
De
Morgans
way:
Not
so
simple
is
it?
Ac
is
the
set
of
all
employees
in
the
company
whose
monthly
salary
<
60,000
Bc
is
the
set
of
all
male
employees
in
the
company
AcBc
is
the
set
of
all
male
employees
in
the
company
whose
salary
<
60,000
So,
(AUB)c
is
easier
to
dene
using
De
Morgans
Law
Applied
Sta+s+cs
and
Compu+ng
Lab
11
Set
OperaBons:
Laws
Commuta+ve
Law
AB
=
BA
AB
=
BA
Associa+ve
Law
(AB)C
=
A(BC)
(AB)C
=
A(BC)
Distribu+ve
Law
A(BC)
=
(AB)(AC)
A(BC)
=
(AB)(AC)
Addi+onal
Results:
1. 2. 3. 4. 5. 6. AB
BcAc
AB
and
BC
AC
AB
and
BC
AUBC
AB
and
BA
A=B
ABA
If
CA
and
CB
CAB
12
Applied
Sta+s+cs
and
Compu+ng
Lab
Set:
Cardinality
Cardinality:
Number
of
elements
in
the
set
Cardinality
of
a
set
A
is
denoted
as
|A|
Consider
the
set
C
=
{2,4,6,8,10},
|C|=5
We
will
now
state
a
relaBon
that
can
be
quite
useful:
|AUB|=
|A|+|B|-|AB|
(Where
A
&
B
are
nite
sets,
i.e.
each
contains
a
nite
set
of
elements)
Applied
Sta+s+cs
and
Compu+ng
Lab
13
Sets:
Mutually
Exclusive,
CollecBvely
ExhausBve,
ParBBon
Consider
two
sets
A
and
B
where
AB
=
|AUB|=
|A|+|B|
X
Such
sets
are
called
Disjoint/Mutually
Exclusive
Sets
Now,
consider
two
sets
A
and
B
whose
union
must
cover
all
elements
in
the
universal
set
X
,
i.e.
AUB
=
X
Such
sets
are
called
Collec+vely/Mutually
Exhaus+ve
sets
Example:
You
can
buy
,
sell
or
hold
a
parBcular
share
A={buy,hold}
B={sell,hold}
AUB
=
{buy,
sell,
hold}=X
Let
us
now
combine
both
the
ideas
menBoned
above,
if
A
and
B
were
Mutually
Exclusive
and
together
ExhausBve
what
can
we
say
about
the
Universal
Set
X
?
It
can
be
parBBoned
into
two
non-overlapping
sets
(A
and
B)!
Applied
Sta+s+cs
and
Compu+ng
Lab
14
Sets:
Mutually
Exclusive,
CollecBvely
ExhausBve,
ParBBon
(Contd.)
We
can
look
at
a
larger
collecBon
of
Mutually
Exclusive
and
ExhausBve
Sets
that
parBBon
the
Universal
Set
X
into
several
non- overlapping
sets
This
concept
is
captured
in
the
picture
below:
A
B
C
D
X
Applied
Sta+s+cs
and
Compu+ng
Lab
15
Thank
you
Applied
Sta+s+cs
and
Compu+ng
Lab
