Introduction

Properties of Sets

COMP9020 24T2 - Week 5 Lecture 1

Set Theory

Sebastian Sequoiah-Grayson - CSE UNSW

Sebastian Sequoiah-Grayson - CSE UNSW COMP9020 24T2 - Week 5 Lecture 1 Set Theory
 Sets, Subsets, and Proper Subsets
Introduction
Set Operations
Properties of Sets
The Null Set and Partitions on Sets

A = {x ∈ S | P(x)}
A = {x ∈ S : Px}
A is the set of all x in S such that P of x/x is P

A ⊆ B ↔ ∀x(x ∈ A → x ∈ B)
A ⊈ B ↔ ∃x(x ∈ A ∧ x ∈
/ B)
A ⊂ B ↔ (A ⊆ B ∧ ∃x(x ∈ B ∧ x ∈
/ A))
A = B ↔ (A ⊆ B ∧ B ⊆ A)
Given these bi-conditionals, proving one side is sufficient for
establishing the other. ˆ∼ ∼ˆ

Sebastian Sequoiah-Grayson - CSE UNSW COMP9020 24T2 - Week 5 Lecture 1 Set Theory
 Sets, Subsets, and Proper Subsets
Introduction
Set Operations
Properties of Sets
The Null Set and Partitions on Sets

Given:
A = {m ∈ Z : m = 2a for some integer a}
B = {n ∈ Z : n = 2b − 2 for some integer b}
A = B?
▶ Choose arbitrary x ∈ A
▶ By definition of A, there is an integer a s.t. x = 2a
▶ Let b = a + 1
▶ b is an integer
▶ 2b − 2 = 2(a + 1) − 2 = 2a + 2 − 2 = 2a = x
▶ Choose arbitrary x ∈ B
▶ By definition of B, there is an integer b s.t. x = 2b − 2
▶ Let a = b − 1
▶ A is an integer
▶ 2a = 2(b − 1) = 2b − 2 = x
Sebastian Sequoiah-Grayson - CSE UNSW COMP9020 24T2 - Week 5 Lecture 1 Set Theory
 Sets, Subsets, and Proper Subsets
Introduction
Set Operations
Properties of Sets
The Null Set and Partitions on Sets

Where A and B are the subsets of a “universal set” U:

A ∪ B = {x ∈ U : x ∈ A ∨ x ∈ B}
A ∩ B = {x ∈ U : x ∈ A ∧ x ∈ B}
B − A = {x ∈ U : x ∈ B ∧ x ∈
/ A}
Ac = {x ∈ U : x ∈
/ A}
n
[
Ai = {x ∈ U : x ∈ Ai for at least one i = 0, 1, 2, . . . , n}
i=0
n
\
Ai = {x ∈ U : x ∈ Ai for all i = 0, 1, 2, . . . , n}
i=0

Sebastian Sequoiah-Grayson - CSE UNSW COMP9020 24T2 - Week 5 Lecture 1 Set Theory
 Sets, Subsets, and Proper Subsets
Introduction
Set Operations
Properties of Sets
The Null Set and Partitions on Sets

The empty set or null set is the set with no elements. It is

denoted by either ‘{ }’ or ‘∅’, but NOT BOTH!

{∅} =
̸ ∅

How many empty sets are there? Why? ˆ∼ ∼ˆ

A and B are disjoint iff A ∩ B = ∅

Ai and Aj are mutually or pairwise disjoint iff Ai ∩ Aj = ∅ ,
when i ̸= j
A set of non-empty sets {A1 , a2 , A3 , . . .} is a partition on a set A
iff :
A is the union of all Ai , and
A1 , A2 , A3 , . . . are pairwise disjoint.
The power set of A, ‘P(A)’, is the set of all subsets of A

Sebastian Sequoiah-Grayson - CSE UNSW COMP9020 24T2 - Week 5 Lecture 1 Set Theory
 Introduction Procedural Properties
Properties of Sets Set Identities

A ∩ B ⊆ A and A ∩ B ⊆ B
A ⊆ A ∪ B and B ⊆ A ∪ B
((A ⊆ B) ∧ (B ⊆ C )) → A ⊆ C
X ∪ Y = {x : x ∈ X or x ∈ Y }
x ∈ X ∪ Y ↔ (x ∈ X ∨ x ∈ Y )
x ∈ X ∩ Y ↔ (x ∈ X ∧ x ∈ Y )
x ∈ X − Y ↔ (x ∈ X ∧ x ∈
/ Y)
x ∈ Xc ↔ x ∈
/X
⟨x, y ⟩ ∈ X × Y ↔ (x ∈ X ∧ y ∈ Y )

Sebastian Sequoiah-Grayson - CSE UNSW COMP9020 24T2 - Week 5 Lecture 1 Set Theory
 Introduction Procedural Properties
Properties of Sets Set Identities

A ∪ B = B ∪ A and A ∩ B = B ∩ A (Com.)
(A ∪ B) ∪ C = A ∪ (B ∪ C ) and (A ∩ B) ∩ C = A ∩ (B ∩ C ) (Asc.)
A∪(B∩C ) = (A∪B)∩(A∪C ) and A∩(B∪C ) = (A∩B)∪(A∩C ) (Dst.)
A ∪ ∅ = A and A ∩ U = A (Id.)
A ∪ Ac = U and A ∩ Ac = ∅ (Comp.)
(Ac )c = A (DC/DN)
A ∪ A = A and A ∩ A = A (Idem.)
A ∪ U = U and A ∩ ∅ = ∅ (Univ.Bound)
(A ∪ B)c = Ac ∩ B c and (A ∩ B)c = Ac ∪ B c (DeMorg.)
A ∪ (A ∩ B) = A and A ∩ (A ∪ B) = A (Absorb.)
U c = ∅ and ∅c = U (Compl. of U and ∅)
A − B = A ∩ B c (Set Diff.)
Sebastian Sequoiah-Grayson - CSE UNSW COMP9020 24T2 - Week 5 Lecture 1 Set Theory