COMP9020
Foundations of Computer Science
Lecture 4: Set Theory
Lecturers: Katie Clinch (LIC)
Paul Hunter
Simon Mackenzie
Course admin: Nicholas Tandiono
Course email: cs9020@cse.unsw.edu.au
Outline
Recap of Key Definitions
Set Equality
Laws of Set Operations
Derived Laws
Two Useful Results
Feedback
1
Outline
Recap of Key Definitions
Set Equality
Laws of Set Operations
Derived Laws
Two Useful Results
Feedback
2
Defining Sets
1 Explicitly list elements
2 Take a subset of an existing set by restricting the elements
3 Build up from existing sets using Set Operations
3
Set Operations
Definition
A ∪ B – union (a or b):
A ∪ B = {x : x ∈ A or x ∈ B}.
A ∩ B – intersection (a and b):
A ∩ B = {x : x ∈ A and x ∈ B}.
Ac – complement (with respect to a universal set U):
Ac = {x : x ∈ U and x /∈ A}.
We say that A,B are disjoint if A ∩ B = ∅
4
Set Operations
Other set operations
Definition
A \ B – set difference, relative complement (a but not b):
A \ B = A ∩ Bc
A⊕B – symmetric difference (a and not b or b and not a; also
known as a or b exclusively; a xor b):
A⊕B = (A \ B) ∪ (B \ A)
5
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A B
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A B
A ∪ B
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A B
A ∩ B
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A
Ac
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A B
A \ B
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A B
A⊕B
6
Outline
Recap of Key Definitions
Set Equality
Laws of Set Operations
Derived Laws
Two Useful Results
Feedback
7
Set Equality
Two sets are equal (A = B) if they contain the same elements
To show equality:
Examine all the elements
Show A ⊆ B and B ⊆ A
Use the Laws of Set Operations
Important!
Venn diagrams can help visualize, but are not rigorous.
8
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \
(B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A
\
(B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B)
\ C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B)
\
C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ̸= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ̸= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B) \ C
9
Examples
Example
Show {3, 2, 1} = (0, 4).
(0, 4) = {1, 2, 3} = {3, 2, 1}.
10
Examples
Example
Show {3, 2, 1} = (0, 4).
(0, 4) = {1, 2, 3} = {3, 2, 1}.
10
Examples
Example
Show {n : n ∈ Z and n2 < 5} = {n : n ∈ Z and |n| ≤ 2}
{n : n ∈ Z and n2 < 5} = {−2,−1, 0, 1, 2}
= {n : n ∈ Z and |n| ≤ 2}
11
Examples
Example
Show {n : n ∈ Z and n2 < 5} = {n : n ∈ Z and |n| ≤ 2}
{n : n ∈ Z and n2 < 5} = {−2,−1, 0, 1, 2}
= {n : n ∈ Z and |n| ≤ 2}
11
Examples
Example
Show {n : n ∈ Z and n2 > 5} = {n : n ∈ Z and |n| > 2}
Show:
For all n ∈ Z, if n2 > 5 then |n| > 2; and
For all n ∈ Z, if |n| > 2 then n2 > 5.
That is, show:
For all n ∈ Z: n2 > 5 if, and only if |n| > 2
12
Examples
Example
Show {n : n ∈ Z and n2 > 5} = {n : n ∈ Z and |n| > 2}
Show:
For all n ∈ Z, if n2 > 5 then |n| > 2; and
For all n ∈ Z, if |n| > 2 then n2 > 5.
That is, show:
For all n ∈ Z: n2 > 5 if, and only if |n| > 2
12
Outline
Recap of Key Definitions
Set Equality
Laws of Set Operations
Derived Laws
Two Useful Results
Feedback
13
Laws of Set Operations
For all sets A, B, C :
Commutativity A ∪ B = B ∪ A
A ∩ B = B ∩ A
Associativity (A ∪ B) ∪ C = A ∪ (B ∪ C )
(A ∩ B) ∩ C = A ∩ (B ∩ C )
Distribution A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )
Identity A ∪ ∅ = A
A ∩ U = A
Complementation A ∪ (Ac) = U
A ∩ (Ac) = ∅
14
Substitution
Because the laws hold for all sets, we can substitute complex
expressions for each set symbol.
Example
Commutativity A ∪ B = B ∪ A
Therefore: (C ∩ D) ∪ (D ⊕ E ) = (D ⊕ E ) ∪ (C ∩ D)
15
Substitution
Because the laws hold for all sets, we can substitute complex
expressions for each set symbol.
Example
Commutativity A ∪ B = B ∪ A
Therefore: (C ∩ D) ∪ (D ⊕ E ) = (D ⊕ E ) ∪ (C ∩ D)
15
Example
Example
Show that for all sets A ∩ (B ∩ C ) = C ∩ (B ∩ A):
A ∩ (B ∩ C ) = (A ∩ B) ∩ C [Associativity]
= C ∩ (A ∩ B) [Commutativity]
= C ∩ (B ∩ A) [Commutativity]
Important!
(Aim to) limit each step to a non-overlapping applications of a
single rule
16
Example
Example
Show that for all sets A ∩ (B ∩ C ) = C ∩ (B ∩ A):
A ∩ (B ∩ C ) = (A ∩ B) ∩ C [Associativity]
= C ∩ (A ∩ B) [Commutativity]
= C ∩ (B ∩ A) [Commutativity]
Important!
(Aim to) limit each step to a non-overlapping applications of a
single rule
16
Outline
Recap of Key Definitions
Set Equality
Laws of Set Operations
Derived Laws
Two Useful Results
Feedback
17
Other useful set laws
The following are all derivable from the previous 10 laws.
Idempotence A ∩ A = A
A ∪ A = A
Double complementation (Ac)c = A
Annihilation A ∩ ∅ = ∅
A ∪ U = U
de Morgan’s Laws (A ∩ B)c = Ac ∪ Bc
(A ∪ B)c = Ac ∩ Bc
18
Example (Idempotence of ∪)
A = A ∪ ∅ (Identity)
= A ∪ (A ∩ Ac) (Complementation)
= (A ∪ A) ∩ (A ∪ Ac) (Distributivity)
= (A ∪ A) ∩ U (Complementation)
= (A ∪ A) (Identity)
19
Example (Idempotence of ∪)
A = A ∪ ∅ (Identity)
= A ∪ (A ∩ Ac) (Complementation)
= (A ∪ A) ∩ (A ∪ Ac) (Distributivity)
= (A ∪ A) ∩ U (Complementation)
= (A ∪ A) (Identity)
19
Example (Idempotence of ∪)
A = A ∪ ∅ (Identity)
= A ∪ (A ∩ Ac) (Complementation)
= (A ∪ A) ∩ (A ∪ Ac) (Distributivity)
= (A ∪ A) ∩ U (Complementation)
= (A ∪ A) (Identity)
19
Example (Idempotence of ∪)
A = A ∪ ∅ (Identity)
= A ∪ (A ∩ Ac) (Complementation)
= (A ∪ A) ∩ (A ∪ Ac) (Distributivity)
= (A ∪ A) ∩ U (Complementation)
= (A ∪ A) (Identity)
19
Example (Idempotence of ∪)
A = A ∪ ∅ (Identity)
= A ∪ (A ∩ Ac) (Complementation)
= (A ∪ A) ∩ (A ∪ Ac) (Distributivity)
= (A ∪ A) ∩ U (Complementation)
= (A ∪ A) (Identity)
19
Outline
Recap of Key Definitions
Set Equality
Laws of Set Operations
Derived Laws
Two Useful Results
Feedback
20
Two useful results
Definition
If A is a set defined using ∩, ∪, ∅ and U , then dual(A) is the
expression obtained by replacing ∩ with ∪ (and vice-versa) and ∅
with U (and vice-versa).
Theorem (Principle of Duality)
If you can prove A1 = A2 using the Laws of Set Operations then
you can prove dual(A1) = dual(A2)
Example
Absorption law: A ∪ (A ∩ B) = A
Dual: A ∩ (A ∪ B) = A
21
Application (Idempotence of ∩)
Recall Idempotence of ∪:
A = A ∪ ∅ (Identity)
= A ∪ (A ∩ Ac) (Complementation)
= (A ∪ A) ∩ (A ∪ Ac) (Distributivity)
= (A ∪ A) ∩ U (Complementation)
= (A ∪ A) (Identity)
22
Application (Idempotence of ∩)
Invoke the dual laws!
A = A ∩ U (Identity)
= A ∩ (A ∪ Ac) (Complementation)
= (A ∩ A) ∪ (A ∩ Ac) (Distributivity)
= (A ∩ A) ∪ ∅ (Complementation)
= (A ∩ A) (Identity)
22
Two useful results
Theorem (Uniqueness of complement)
A ∩ B = ∅ and A ∪ B = U if, and only if, B = Ac .
Proof (Only if).
B = B ∩ U (Identity)
= B ∩ (A ∪ Ac) (Complement)
= (B ∩ A) ∪ (B ∩ Ac) (Distributivity)
= (A ∩ B) ∪ (Ac ∩ B) (Commutativity)
= ∅ ∪ (Ac ∩ B) (Given)
= (A ∩ Ac) ∪ (Ac ∩ B) (Complement)
= (Ac ∩ A) ∪ (Ac ∩ B) (Commutativity)
= Ac ∩ (A ∪ B) (Distributivity)
= Ac ∩ U (Given)
= Ac (Identity)
23
Two useful results
Theorem (Uniqueness of complement)
A ∩ B = ∅ and A ∪ B = U if, and only if, B = Ac .
Proof (Only if).
B = B ∩ U (Identity)
= B ∩ (A ∪ Ac) (Complement)
= (B ∩ A) ∪ (B ∩ Ac) (Distributivity)
= (A ∩ B) ∪ (Ac ∩ B) (Commutativity)
= ∅ ∪ (Ac ∩ B) (Given)
= (A ∩ Ac) ∪ (Ac ∩ B) (Complement)
= (Ac ∩ A) ∪ (Ac ∩ B) (Commutativity)
= Ac ∩ (A ∪ B) (Distributivity)
= Ac ∩ U (Given)
= Ac (Identity)
23
Application (Double complement)
Take A = X c and B = X :
X c ∩ X = X ∩ X c (Commutativity)
= ∅ (Identity)
X c ∪ X = U (Principle of duality)
By the uniqueness of complement, (X c)c = X .
24
Exercises
Exercises
Show the following for all sets A, B, C :
B ∪ (A ∩ ∅) = B
(C ∪ A) ∩ (B ∪ A) = A ∪ (B ∩ C )
(A ∩ B) ∪ (A ∪ Bc)c = B
Exercises
Give counterexamples to show the following do not hold for all
sets:
A \ (B \ C ) = (A \ B) \ C
(A ∪ B) \ C = A ∪ (B \ C )
(A \ B) ∪ B = A
25
Outline
Recap of Key Definitions
Set Equality
Laws of Set Operations
Derived Laws
Two Useful Results
Feedback
26
Weekly Feedback
We would appreciate any comments/suggestions/requests you
have on this week’s lectures.
https://forms.office.com/r/aHRCGANHiB