Lecture 5

Learning Objectives
To use set notations
To apply operations (union, intersection) on sets
To define de Morgan’s Laws for sets
To define relations on sets
To define set partitions
Set Theory
 Set is a collection of objects
 The { } notation for sets
 𝐴 = {𝑥 ∈ 𝑆 | 𝑃 𝑥 }
Which is read “the set of all x in S such that P of x.”

 Example:
X = { x | x is the alphabetical letter of English }
X = {a, b, c, d ,..., x, y, z}
a X b X p X z X
The element of Set
 The objects are called the elements of a
set
 We use  to denote the elements of
a set.
x is an element of the set A

x A x is a member of A

x belongs to A
 The element of Set
 The size of a set is called cardinality.
 The notation of cardinality is | |.
 Example:
X = { x | x is the alphabetical letter of English }
X = { a, b, c, …, x, y, z }

| X | = 26 26 is the size or cardinality of X

Y = {a, b}, Y = 2

Z = {b}, Z = 1 A singleton (a 1-element set)

 The Null Set / Empty Set

 {}
Examples:
1.The set of real numbers x such that x2 = -1.

2.The set of students who are doing Industrial

Training and are in the first semester.
Infinite Sets
 The set of all nonnegative integers
◦ N = {1, 2, 3, …}
◦ N = {0, 1, 2, 3, …} (in Susanna S. Epp)

 The set of all integers Countably infinite

or
◦ Z = {…, -2, -1, 0, 1, 2, …} Countable

 The set of all rational numbers

◦ Q (quotients of integers or “fractions”)

 The set of all real numbers, R Uncountably infinite or Uncountable

Notations of Set

𝐴 ⊆ 𝐵 ⟺ ∀𝑥, 𝑖𝑓 𝑥 ∈ 𝐴 𝑡ℎ𝑒𝑛 𝑥 ∈ 𝐵

𝐴 ⊈ 𝐵 ⟺ ∃𝑥 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑥 ∉ 𝐵

X Y X is contained in Y

X is a subset of Y

X Y Every element of X is also in Y.

Example
1. X = {1, 2, 3, 6, 7}
2. Y = {4, 5, 6, 7, 8}
3. Z = {2, 3, 6, 7}

ZX Z Y
More on Subsets

  N Z Q
Note that the null set is regarded as a subset of every set,
including itself.

N = Natural Numbers = { 1,2,3,…}

Z = Integers = {…,-2, -1, 0, 1, 2,…}
Q = Rational Numbers = { ½, 1/3, …}
R = Real Numbers = { 0.1, 0.1, 3,…}
Example
Let A = {a, b, c} = {b, c, a}. List all subsets
of A.

◦ Ø (the no-element subset)

◦ {a}, {b}, {c} (the 1-element subsets)
◦ {a, b}, {a, c}, {b, c} (the 2-element subsets)
◦ {a, b, c} (the 3-element subset)
 Power Sets
 The set of all subsets of a given set X
( X )
 Example: A = {a, b, c}

( A) = { ,{a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A}

|( A) |= 8
Theorem

|( A) |= 2 | A|
Operations on Sets
 The union of X and Y
◦ The set of all elements in X or Y
X Y
 The intersection of X and Y
◦ The set of all elements in X and Y
X Y
Venn Diagrams

X Y X Y

X Y X Y
 Example

X = {a, b, c, d , e} X Y

Y = {c, d , e, f } a
c
d f
e
b

X  Y = {a, b, c, d , e, f }
X  Y = {c, d , e}
Complement of Y relative to X
 X – Y or X \ Y
 The “set difference”

X Y
{x  X : x  Y }

X −Y X Y Y−X
 Disjoint Sets
 Two sets are disjoint if they don’t intersect
X Y = 

𝐴 = {1,3,5} and B={2,4,6}

1,3,5 ∩{2,4,6}= ∅
 Mutually Disjoint Sets
 For all i, j =1, 2, 3, …
𝐴𝑖 ∩ 𝐴𝑗 = ∅ whenever 𝑖 ≠ 𝑗

𝐴1 = {3,5}, 𝐴2 = 1,4,6 , 𝑎𝑛𝑑 𝐴3 = {2}

 Universal Set

Often we have a universal set U consisting of all elements of

interest.
So every other set of interest is a subset of U.

U
If X  U we write X
The complement 𝑋ത = 𝑋 𝑐 = 𝑈 ∖ 𝑋
of X
=𝑈 − 𝑋
Lemma: de Morgan’s Law for Sets

X Y = X Y

X Y = X Y
Example
1. U = {1, 2, …, 10}
2. X = {1, 2, 3, 4, 5}
3. Y = {2, 4, 6, 8}
Find:

X Y X X −Y

X Y Y Y−X
 Examples of Some Other Sets

X = {x   | x  4} Y = {x   | x = 9}
2

= {all integers  4} = {−3,3}

= {4,5,6,7,...}
 Cardinality of Set Unions
For finite sets X and Y,

| X  Y |=| X | + | Y | − | X  Y |
Relations on Sets
 Let X, Y be sets. A relation between X and
Y is a subset of the Cartesian product
 Let R be the relation from X to Y

R = X  Y = {( x, y ) | x  X , y  Y }

 So a relation is a set of ordered pairs of

the form (x, y), where x є X and y є Y
 Relations on Sets
Let ρ be a relation from x to y, and
( x, y )  
We write,
x y
Read as “x rho y”,
to say that “x is ρ-related to y”
 Example 1
Let R be the relation from X to Y.

X = {a, b, c} Y = {1,2}
R = X  Y = {( x, y ) | x  X , y  Y }
= {( a,1), (a,2), (b,1), (b,2), (c,1), (c,2)}

Any subset of R is a relation from X to Y.

R1 = o
R2 = {( a,1), (b,1), (c,1)}
R3 = {(c,2)} … and 61 more
Example 2:
Let
X = 3,4 Y = 3,4,5,6,7,8,9

If we define a relation R from X to Y by

( x, y )  R if y subtract x is a positive even number.

We obtain

R = (3,9), (4,8), (3,7), (4,6), (3,5), (4,4), (3,3)

The domain of R is 3,4

The range of R is 3,4,5,6,7,8,9
Relation on Sets
 When X = Y, a relation between X and Y is
called a relation on X
X  X = X 2 = {( x, y ) | x, y  X }

 Any subset of X2 is a relation on X2 .

Example 3
X X

Let R be the relation on X x y

X = {2,3,5,7} 2 2
3 3
Define by ( x, y )  R 5 5
if x  y + 1 7 7
Then,
R = ( x, y ) | x  y + 1, x  X , y  X 
= (5,2), (5,3), (7,2), (7,3), (7,5)
 Properties of Relations: reflexive
A A
Let ρ be a relation on X. x y
ρ is reflexive if
1 1
( x, x)   for all x  X
2 2
Example 4:
Let A = {1, 2, 3}
3 3
and ρ be a relation on A defined as
x− y 0
 = (1,1), (2,1), (2,2), (3,1), (3,2), (3,3)
Therefore, ρ is reflexive
 Properties of Relations: symmetric

Let ρ be a relation on X.

ρ is symmetric if ( x, y )    ( y , x )  
Example 5:
Let A = {2, 3}
and ρ be a relation on A defined as
“x ρ y if and only if x + y is odd integer.”

 = (2,3), (3,2)
ρ is symmetric
 Properties of Relations: transitive
 ρ is transitive if for all
x, y , z  X
If ( x, y )   and ( y, z )   , and ( x, z )  
Example 6:
Let A = {1, 3, 4}
and ρ be a relation on A defined as
𝑥
“x ρ y if and only if > 0 ”
𝑦

𝜌 = { 1,1 , 1,3 , 1,4 , 3,1 , 3,3 , 3,4 , 4,1 , 4,3 , 4,4 }

Equivalence Relations
 A relation ρ on a set X is said to be an
equivalence (relation) when it is reflexive,
symmetric and transitive.
 Example 6 is a equivalence relation.
Congruence modulo n
 “a is congruent to b modulo n” when (a – b) is
an integer multiple of n

𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛
𝑎 − 𝑏 = 𝑡𝑛, for some integer t

 Usually we want a and b to be integers

Example 6
X = {1, 2, 3, 4, 5, 6, 7}.
Define ρ on X by x ρ y if x ≡ y (mod 3).
Write down ρ as a set of ordered pairs.

ρ = {(1,1), (1,4), (1,7), (2,2), (2,5), (3,3),

(3,6), (4,1), (4,4), (4,7), (5,2), (5,5), (6,3),
(6,6), (7,1), (7,4), (7,7)}
Congruence modulo n
It can be shown that the relation a ≡ b (mod n) is
always an equivalence relation on Z and its subsets

I. a  a (mod n)
II. a  b (mod n)  b  a (mod n)

III. a  b (mod n)
a  c (mod n)
b  c (mod n)
Applications
 4 o’clock + 12 hours = “1600 hours” = 16 o’clock = 4 o’clock
◦ This is because 4 ≡ 16 (mod 12)

 8 o’clock + 12 hours = “2000 hours” = 20 o’clock = 8 o’clock

◦ This is because 8 ≡ 20 (mod 12)

 Coding theory is based on arithmetic modulo 2

Partitions
 Given an equivalence relation on a set X,
we can partition X by grouping the related
elements together.

 A partition is a set of disjoint, nonempty

subsets of a given set X whose union is X

 Essentially, a partition divides X into

subsets
Example 6 (revisited)

X = {1, 2, 3, 4, 5, 6, 7}.
Define ρ on X by x ρ y if x ≡ y (mod 3). Write down ρ
as a set of ordered pairs.

ρ = {(1,1), (1,4), (1,7), (2,2), (2,5), (3,3), (3,6), (4,1),

(4,4), (4,7), (5,2), (5,5), (6,3), (6,6), (7,1),(7,4),
(7,7)}

Theorem:
Equivalence classes of X given by the relation ρ.

For every equivalence relation there is a

corresponding partition, and vice versa
 Example

2
5
1 4

7
3
6

The partition corresponding to ρ is often denoted by Πρ.

Here: Πρ = {{1,4,7}, {2,5}, {3,6}}

Example
Consider the following collections of
subsets of S = {1, 2, 3, …, 8, 9}:
1. [{1, 3, 5}, {2, 6}, {4, 8, 9}]
2. [{1, 3, 5}, {2, 4, 6, 8}, {5, 7, 9}]
3. [{1, 3, 5}, {2, 4, 6, 8}, {7, 9}]
Which of the above is a partition of S?
THE END