COMP232

Introduction to Discrete Mathematics

Week 6: Set Theory
Naive Set Theory after Cantor

Definition
A set is an unordered collection defined by its members or
elements.

Definition
The set ∅ = {} with no elements is called the empty set.
The set U that contains all elements under consideration is
called the universal set.

We write:

MyChildren = {x|Person(x) ∧ Parent(I, x)}

Notation

x ∈ A : x is an element of A
x∈/ A ≡ ¬(x ∈ A)
A ⊆ B ≡ [∀x (x ∈ A) → (x ∈ B)]
A = B ≡ (A ⊆ B) ∧ (B ⊆ A)
A ⊂ B : (A ⊆ B) ∧ ¬(A = B)
[∃x x ∈ ∅] : F
[∀x x ∈ U] : T
Let A and B be sets.

Definition
[A = B] ≡ [∀x(x ∈ A) ↔ (x ∈ B)] set equality
A ∪ B = {x | (x ∈ A) ∨ (x ∈ B)} set union
A ∩ B = {x | (x ∈ A) ∧ (x ∈ B)} intersection
A − B = {x | (x ∈ A) ∧ (x 6∈ B)} difference
A = U − A set complement
A, B are disjoint iff A ∩ B = ∅
Venn diagram

A graphical representation of sets. It helps us to visualize the

results of set operations.
A B

11111
00000
00000
11111
00000
11111
00000
11111 B
00000
11111
00000
11111
A 00000
11111
00000
11111
00000
11111
00000
11111 A B
00000
11111
00000
11111

00000
11111
00000
11111
11111
00000
A11111111111111111111
00000000000000000000
00000
11111
00000
11111 B
11111111111111111111
00000000000000000000
00000
11111
00000
11111
00000000000000000000
11111111111111111111
00000
11111
00000
11111 (A B) C
00000000000000000000
11111111111111111111
00000
11111
00000
11111
00000000000000000000
11111111111111111111
00000000000000000000
11111111111111111111
00000000000000000000
11111111111111111111
00000000000000000000
11111111111111111111
C
00000000000000000000
11111111111111111111
00000000000000000000
11111111111111111111
Definition
A set with exactly k distinct elements for some natural number
k is called a finite set and k is its cardinality (more formally
cardinal number). If A is not finite then A is infinite.

We write |A| = k when the cardinality of A is k.

|MyChildren| = 2
Exercise: What can you say about the sets A and B if the
following are true?
1. A ∪ B = A
2. A ∩ B = A
3. A − B = A
4. A ∩ B = B ∩ A
5. A − B = B − A
see below...
Exercise: What can you say about the sets A and B if
A ∪ B = A ? (Give the most general answer possible)
A A⊆B
B B⊆A
C B⊂A
D B=∅
Exercise: What can you say about the sets A and B if
A ∪ B = A ? (Give the most general answer possible)
A
B B⊆A
C
D
Exercise: What can you say about the sets A and B if the
following are true?
A ∩ B = A (Give the most general answer possible)
A A⊆B
B A⊂B
C A=B
D B=U
Exercise: What can you say about the sets A and B if the
following are true?
A ∩ B = A (Give the most general answer possible)
A A⊆B
B
C
D
Exercise: What can you say about the sets A and B if the
following are true?
A − B = A (Give the most general answer possible)
A B=∅
B B=A
C B⊆A
Exercise: What can you say about the sets A and B if the
following are true?
A − B = A (Give the most general answer possible)
A
B
C B⊆A

Note that
B ⊆ A ⇐= B = A
and
B ⊆ A ⇐= B = ∅
Exercise: What can you say about the sets A and B if the
following are true?
A∩B =B∩A
A A⊆B
B B⊆A
C nothing
Exercise: What can you say about the sets A and B if the
following are true?
A∩B =B∩A
A
B
C nothing

Note that elements in sets are unordered, so there can be no

difference in the two intersections.
Exercise: What can you say about the sets A and B if the
following are true?
A − B = B − A (Give the most general answer possible!)

A A∩B =∅
B A∩B =U
C A=B
Exercise: What can you say about the sets A and B if the
following are true?
A − B = B − A (Give the most general answer possible!)

A
B
C A=B

Note that
A ∩ B = ∅ =⇒ A = B = ∅
and A ∩ B = U =⇒ A = B = U =⇒ A = B
Set identities
equivalence law
A∪ ∅ =A identity
A∩U=A
A∪U=U domination
A∩ ∅ ∅
=
A∪A=A idempotent
A∩A=A
(A) = A complement
A∪B=B∪A commutative
A∩B=B∩A
(A ∪ B) ∪ C = A ∪ (B ∪ C) associative
(A ∩ B) ∩ C = A ∩ (B ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) distributive
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
(A ∩ B) = A ∪ B de Morgan
(A ∪ B) = A ∩ B
Power Set

Definition
Let A be a set. We call the set of all subsets of A its power set.
P(A) = {X |X ⊆ A}
Example: P({1, 2, 3}) =
{{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
Cartesian Product

Definition
Let A, B be sets. We call the set of ordered pairs of elements of
Aand B its Cartesian product.
AxB = {(a, b)|a ∈ A ∧ b ∈ B}
Example:
{1, 2, 3}x{a, b} = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
Other useful identities

A∪A=U
A∩A= ∅
A−B =A∩B

To show set identities use:

I set builder notation and logical equivalences

I set identities
I membership tables (deprecated: too messy, takes too
much time)
Set Builder Notation

Show that A − B = A ∩ B

LHS
=A−B
= {x|(x ∈ A) ∧ (x ∈
6 B)}
= {x|(x ∈ A) ∧ (x ∈ B)}
=A∩B
RHS
Set identities

Show that A ∪ (B − A) = A ∪ B.

A ∪ (B − A)
= A ∪ (B ∩ A) shown earlier
= (A ∪ B) ∩ (A ∪ A) distributive law
= (A ∪ B) ∩ U by definition
=A∪B identity laws
Set Builder Notation

Show that A ∪ (B − A) = A ∪ B.

A ∪ (B − A)
= {x | (x ∈ A) ∨ (x ∈ B − A)}
= {x | (x ∈ A) ∨ ((x ∈ B) ∧ (x ∈
/ A))}
= {x | ((x ∈ A) ∨ (x ∈ B)) ∧ ((x ∈ A) ∨ (x ∈
/ A))}
= {x | ((x ∈ A) ∨ (x ∈ B)) ∧ T }
= {x | (x ∈ A) ∨ (x ∈ B)}
= {x | x ∈ A ∪ B}
=A∪B
Set Identities

Let A and B be sets. Show that (A ∪ B) − C = (A − C) ∪ (B − C)

RHS
= (A − C) ∪ (B − C)
Let A and B be sets. Show that (A ∪ B) − C = (A − C) ∪ (B − C)

RHS
= (A − C) ∪ (B − C)
= (A ∩ C) ∪ (B ∩ C)
Let A and B be sets. Show that (A ∪ B) − C = (A − C) ∪ (B − C)

RHS
= (A − C) ∪ (B − C)
= (A ∩ C) ∪ (B ∩ C)
= (A ∪ B) ∩ C
Let A and B be sets. Show that (A ∪ B) − C = (A − C) ∪ (B − C)

RHS
= (A − C) ∪ (B − C)
= (A ∩ C) ∪ (B ∩ C)
= (A ∪ B) ∩ C
= (A ∪ B) − C
= LHS
Let A and B be sets. Show that:
A − (B ∪ C) = (A − B) − C
Let A and B be sets. Show that:

A − (B ∪ C) = (A − B) − C

RHS
= (A − B) − C
= (A ∩ B) ∩ C
= A ∩ (B ∩ C) Associative law
= A ∩ (B ∪ C) de Morgan
= A − (B ∪ C)
LHS