1

COMP S264F Unit 3:

Set Theory

Dr. Keith Lee

School of Science and Technology
Hong Kong Metropolitan University
 2

Overview
• Set notations
• Equality & Subset
• Venn diagrams
• Finite sets
• Set operators
➢Union, Intersection, Difference, Complement
• Set identities
• Power sets
• Cartesian products
 3

Sets
• A set is a group of distinct objects.
• To describe a set, we can
➢list all its elements (enclosed by a pair of braces); or
➢specify the properties of the objects in the set.

• Examples:
➢Let A be the set of all Computing students born in 2001.
➢Let X be the set of {A, B, C, D}.
➢Let ℤ be the set of all integers.
➢Let ℕ (natural numbers) = {0, 1, 2, 3, …}.
➢EVEN = { x | x  ℤ and (x mod 2 = 0)}.

{ x | … } is the set builder notation, read as the set of all x such that …
 4

Basic terminology
• The objects in a set are also called the elements or members
of the set.

• The notation “x  A” is defined to be the statement

“x is an element of A”, “x is in A”, or “A contains x”.
➢“x  A” means “x is not in A”.

• The set that contains no element is called the empty set, or the
null set, denoted by .

• The universal set is the set containing all objects under

consideration.
 5

Equality & Subset

• Two sets A and B are equal, denoted by A = B, if and only if
they have the same elements (i.e., x (x  A  x  B)).

• E.g., {1, 3, 5} = {3, 5, 1} ?  = {} ?

• A set A is said to be a subset of a set B, denoted by A  B,

if and only if every element of A is also an element of B
(i.e., x (x  A  x  B)).

• E.g., {1, 2}  {3, 1, 2}  ℕ  ℤ

 6

Venn diagrams
Let A and B be sets.
• If A and B are represented as regions in the plane, their
relationships can be represented by a Venn diagram.
• E.g., A  B: A = B:

B A A=B

• Three possible Venn diagrams for A B:

A B A B A B
 7

Equality: Example 1
How to prove A = B?
• Show that A  B and also B  A
• I.e. x (x  A  x  B) and x (x  B  x  A) .

Example 1: Let A = { n | n = 2p for some p  ℤ }, and let B = {m |

m = 2q - 2 for some q  ℤ}. Is A = B?

• Before proving a theorem, it is always good to consider a few

small examples of it.
 8

Equality: Example 1 (cont’)

How to prove A = B?
• Show that A  B and also B  A
• I.e. x (x  A  x  B) and x (x  B  x  A) .

Example 1: Let A = { n | n = 2p for some p  ℤ }, and let B = {m |

m = 2q - 2 for some q  ℤ}. Is A = B?

Proof.
Let x  A. Then, there is an integer p such that x = 2p = 2(p+1) - 2.
As p+1 is also an integer, x  B.

Let y  B. Then, there is an integer q such that y = 2q - 2 = 2(q-1).

As q-1 is also an integer, y  A.

Therefore, A = B.
 9

Equality: Example 2
Example 2: Let A = { n | n = 2p for some p  ℤ }, and
let C = { k | k = 3r + 1 for some r  ℤ}. Is A = C?

Proof. No, we can find a counterexample, as follows:

C contains k = 3(2) + 1 = 7, i.e., 7  C.
To check whether 7  A, we set 7 = 2p.
Then, p = 7/2 = 3.5, which is not an integer.
Thus, 7  A  A  C.
 10

Subsets
Let A = {1, 2, 3}.
True or false?
• A
•
•   S for all sets S.

Let A and B be any two sets. A is a proper subset of B,

denoted by A  B, if and only if A  B and A  B.
True or false?
•
 11

Subsets: Example
ℝ ℤ ℕ
• The set of real numbers is denoted by ℝ.
• E.g., 1.33  ℝ,   ℝ, -2  ℝ, ℕ  ℤ  ℝ.

Example: Let A = {x  ℝ | x > 4}, and let B = {x  ℝ | x2 > 1}.

Prove that A  B.

The proof consists of two parts:

1. A  B
2. A  B. Identify the purple item in B. B A
 12

Subsets: Example
Example: Let A = {x  ℝ | x > 4}, and let B = {x  ℝ | x2 > 1}.
Prove that A  B.
Proof.
First, we show that A  B. For every x  A,
x > 4  x2 > 42 (as x > 0)
= 16
>1
 x  B.

Then, we show that A  B. Consider x = -2.

x2 = (-2)2 = 4 > 1  -2  B .
But, x = -2 ≤ 4  -2  A .

It follows that A  B.
 13

Finite sets
Let S be a set containing exactly n  0 elements.
• We say that S is a finite set.
• The cardinality of S, denoted by |S|, is the number of elements
in S, i.e., n.
An infinite set is a set that is not finite.

Questions: finite or infinite?

• {A, B, C}
• The set of all Computing students who were born in 2001.
• ℕ = {0, 1, 2, …}
• PRIME = the set of prime numbers

What is the cardinality of  ? {} ? {, {} } ?

 14

Set Operators
Let A and B be two sets.
• The union of A and B, denoted by A  B, is the set
{x | x  A or x  B }.
E.g., { 1, 2 }  { 3, 2 } = { 1, 2, 3 }

• The intersection of A and B, denoted by A  B, is the set

{x | x  A and x  B }.
E.g., { 1, 2 }  { 3, 2 } = { 2 }

• The difference of A and B, denoted by A - B, is the set

{x | x  A and x  B }.
E.g., { 1, 2 } - { 3, 2 } = { 1 }

• The complement of a set A (with respect to a fixed universal set U),

denoted by 𝐀 ഥ , is the set U - A.
ഥ = { 2, 3, 5 }.
E.g., U = { 1, 2, 3, 4, 5 }, A = { 1, 4 }. Then, A
 15

Venn diagram of Set Operators

Let A and B be two sets.
• A  B: • A  B:

A B
A B

• A - B: ഥ = U - A:
•𝐀

U
A B
A
 16

Set Identities - 1
Identity Name

Identity laws

Domination laws

Idempotent laws

Complementation law
 17

Set Identities - 2
Identity Name
Commutative
laws
Associative
laws

Distributive
laws

De Morgan’s
laws
 18

Empty

Proving Set Identities

A 
•A=A

Proof.
It is obvious that A  A  .

If x  A  , then (x  A) or (x  )  (x  A) or false  x  A .
Thus, A    A.

Therefore, A   = A.
 19

Proving Set Identities U

(cont’) A
•AU=A

Proof.
It is obvious that A  U  A.

If x  A, then x  A  (x  A) and (x  U)  x  A  U .
Thus, A  A  U .

Therefore, A  U = A.
 20

Empty
Proving Set Identities
(cont’) A 
•A=

Proof.
It is obvious that A    .

As   X for any set X. Thus,   A   .

Therefore, A   =  .
 21

Another useful set identity

•

Proof.
xA-B
 (x  A) and (x  __
B)
 (x  A) and
__
(x  B).
 x  A  B.

Therefore, .
 22

Proving Subset: Example 1

Theorem 1. A  B  B .

Proof.
We need to prove x (x  A  B )  x  B .
Assume x  A  B .
Then, x  A and x  B (Definition of  )
 x  B (p and q  p)
 23

Proving Subset: Example 2

Theorem 2. If A  B, then A  B  B.

Proof.
By Theorem 1, A  B  B.

Thus, it remains to prove:

If A  B, then x ((x B)  (x  A  B)).

Assume A  B.
Then, x (x  B  x  A) (Definition of  )
 x (x  B  ((x  A)  (x  B))) (p  p  q)
 x (x  B  (x  A  B)) (x  A  B  x  A or x  B)
 24

Proving Subset: Example 3

Theorem 3. A  B if and only if A  B = A.

Proof.
We first prove that if A  B, then A  B = A.
Assume A  B.
It is obvious that A  B  A.

If x  A, then (x  A) and (x  B) (as A  B)  x  A  B.

Thus, A  A  B.

Therefore, A  B = A.
 25

Proving Subset: Example 3 (con’t)

Theorem 3. A  B if and only if A  B = A.

Proof (cont’).
Next, we prove that if A  B = A, then A  B.
Assume A  B = A.
xA
 x  A  B (as A  B = A)
 (x  A) and (x  B)
 xB
Thus, A  B.

The theorem follows.

 26

Power Sets
• The power set of a set S, denoted by P(S), is the set of all subsets
of S.
• That means, for any element x of P(S), x  S.
E.g.,
• P( {0, 1, 2} ) = {, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}}

• |{0, 1, 2}| = 3; |P({0, 1, 2})| = 8.

• What is the power set of the empty set?

• In general, if |S| = n, then |P(S)| = ?

 27

Size of power set

Theorem. For any set S with n elements, |P(S)| = 2n.
Proof. We can prove by induction on the number of elements.
Base case. When n = 1, let S = {a}. Then P(S) = {, {a}}.
Thus, |P(S)| = 2 = 21 = 2n.
Inductive step. Assume that if a set S’ contains k elements for
some k, then |P(S’)| = 2k.
Consider the case where |S| = k + 1.
Let x be an element of S and denote S’ = S - {x}.

Consider each subset A of S’.

• A is also a subset of S. A A{x}
• A  {x} gives another distinct subset of S.
Thus, S has twice as many subsets as S’, and
|P(S)| = 2 x |P(S’)| = 2 x 2k = 2k+1.
 28

Power Sets: Example

Prove that P(A  B) = P(A)  P(B).

Proof.
x  P(A)  P(B)
 x  P(A) and x  P(B)
 x  A and x  B
 xAB
 x  P(A  B)

Therefore, P(A  B) = P(A)  P(B).

 29

Cartesian Products
• Ordering is important: An ordered n-tuple (a1, a2, …, an) is
the ordered collection that has a1 as the first element, a2 as
its second element, …, and an as the n-th element.

NB. The set {a1, a2, …, an} does not carry any ordering.

• Let A and B be sets. The Cartesian product of A and B,

denoted by A x B, is the set of all 2-tuples (a, b) where
a  A and b  B.
E.g., {a,b} x {c,d} = { (a,c), (a,d), (b,c), (b,d) }.
• The Cartesian product of the sets A1, A2, …, An, denoted
by A1 x A2 x … x An, is the set
{ (a1, a2, …, an) | a1  A1 and a2  A2 and … and an  An}
 30

Cartesian Products: Questions

Assume that A contains n elements and B contains m elements.

• How many elements does A x B contain?

• AxB=BxA?

• Suppose A x B is equal to the empty set.

What can you conclude?
 31

Cartesian Products: Questions (cont’)

Let A be a set of n elements.

• How many elements does P(A) x P(A) contain?

By definition, P(A) x P(A) = { (X, Y) | X  A, Y  A }.

• How many elements are in the set

{ (X, Y) | X  A, Y  A, X  Y =  } ?