Sets

What is a set?
A set is a unordered collection of “objects”
 People in a class: {Alice, Bob, Chris }
 States in the US: {Alabama, Alaska, Virginia, … }
 Sets can contain non-related elements: {3, a, Virginia}
 All positive numbers less than or equal to 5: {1, 2, 3, 4, 5}

Properties
 Order does not matter
 {1, 2, 3, 4, 5} is equivalent to {3, 5, 2, 4, 1}
 Sets do not have duplicate elements
 Consider the list of students in this class
– It does not make sense to list somebody twice
 Specifying a set
A set “contains” the various “members” or
“elements” that make up the set
If an element a is a member of (or an element of)
a set S, we use then notation a  S
4  {1, 2, 3, 4}
If not, we use the notation a  S
7  {1, 2, 3, 4}
 Often used sets
N = {0, 1, 2, 3, …} is the set of natural numbers
Z = {…, -2, -1, 0, 1, 2, …} is the set of integers
Z+ = {1, 2, 3, …} is the set of positive integers
(a.k.a whole numbers)
 Note that people disagree on the exact definitions of whole
numbers and natural numbers
Q = {p/q | p  Z, q  Z, q ≠ 0} is the set of rational
numbers
 Any number that can be expressed as a fraction of two
integers (where the bottom one is not zero)
R is the set of real numbers
 The universal set
U is the universal set – the set of all of
elements (or the “universe”) from which
given any set is drawn
For the set {-2, 0.4, 2}, U would be the real
numbers
For the set {0, 1, 2}, U could be the N, Z, Q, R
depending on the context
For the set of the vowels of the alphabet, U would
be all the letters of the alphabet
 Venn diagrams
Represents sets graphically
 The box represents the universal set
 Circles represent the set(s)
Consider set S, which is
the set of all vowels in the
alphabet
b c d f
The individual elements U
g
are usually not written h j S
m
in a Venn diagram k l
n p q a e i

r s t
o u
v w x
y z
 Sets of sets
Sets can contain other sets
S = { {1}, {2}, {3} }
T = { {1}, {{2}}, {{{3}}} }
V = { {{1}, {{2}}}, {{{3}}}, { {1}, {{2}},
{{{3}}} } }
V has only 3 elements!
Note that 1 ≠ {1} ≠ {{1}} ≠ {{{1}}}
They are all different
 The Empty Set
If a set has zero elements, it is called the empty (or
null) set
 Written using the symbol 
 Thus,  = { }  VERY IMPORTANT

It can be a element of other sets

 { , 1, 2, 3, x } is a valid set

≠{}
 The first is a set of zero elements
 The second is a set of 1 element

Replace  by { }, and you get: { } ≠ {{ }}

 It’s easier to see that they are not equal that way
 Set Equality, Subsets
Two sets are equal if they have the same elements
 {1, 2, 3, 4, 5} = {5, 4, 3, 2, 1}
 {1, 2, 3, 2, 4, 3, 2, 1} = {4, 3, 2, 1}
 Two sets are not equal if they do not have the same elements
 {1, 2, 3, 4, 5} ≠ {1, 2, 3, 4}

If all the elements of a set S are also elements of a set T, then

S is a subset of T
 If S = {2, 4, 6}, T = {1, 2, 3, 4, 5, 6, 7}, S is a subset of T
 This is specified by S  T meaning that  x (x  S → x  T)

 For any set S, S  S (S S  S)

 For any set S,   S (S   S)
 Proper Subsets
If S is a subset of T, and S is not equal to T, then S
is a proper subset of T
 Can be written as: R  T and R  T
 Let T = {0, 1, 2, 3, 4, 5}
 If S = {1, 2, 3}, S is not equal to T, and S is a subset of T
 A proper subset is written as S  T
 Let Q = {4, 5, 6}. Q is neither a subset or T nor a proper
subset of T
 Set cardinality
The cardinality of a set is the number of elements in
a set, written as |A|

Examples
 Let R = {1, 2, 3, 4, 5}. Then |R| = 5
 || = 0
 Let S = {, {a}, {b}, {a, b}}. Then |S| = 4
 Power Sets
Given S = {0, 1}. All the possible subsets of S?
  (as it is a subset of all sets), {0}, {1}, and {0, 1}
 The power set of S (written as P(S)) is the set of all the subsets of S
 P(S) = { , {0}, {1}, {0,1} }
 Note that |S| = 2 and |P(S)| = 4
Let T = {0, 1, 2}. The P(T) = { , {0}, {1}, {2}, {0,1}, {0,2},
{1,2}, {0,1,2} }
 Note that |T| = 3 and |P(T)| = 8
P() = {  }
 Note that || = 0 and |P()| = 1
If a set has n elements, then the power set will have 2n elements
Set Operations
 Set operations: Union
Formal definition for the union of two sets:
A U B = { x | x  A or x  B }

Further examples
 {1, 2, 3} U {3, 4, 5} = {1, 2, 3, 4, 5}
 {a, b} U {3, 4} = {a, b, 3, 4}
 {1, 2} U  = {1, 2}

Properties of the union operation

A U =A Identity law
A U U=U Domination law
A U A=A Idempotent law
A U B=BUA Commutative law
A U (B U C) = (A U B) U C Associative law
 Set operations: Intersection
Formal definition for the intersection of two sets:
A ∩ B = { x | x  A and x  B }

Examples
 {1, 2, 3} ∩ {3, 4, 5} = {3}
 {a, b} ∩ {3, 4} = 
 {1, 2} ∩  = 

Properties of the intersection operation

A ∩ U= A Identity law
A ∩ = Domination law
A ∩ A=A Idempotent law
A ∩ B=B∩A Commutative law
A ∩ (B ∩ C) = (A ∩ B) ∩ C Associative law
 Disjoint sets
Formal definition for disjoint sets: two sets
are disjoint if their intersection is the empty
set
Further examples
{1, 2, 3} and {3, 4, 5} are not disjoint
{a, b} and {3, 4} are disjoint
{1, 2} and  are disjoint
Their intersection is the empty set
 and  are disjoint!
Their intersection is the empty set
 Set operations: Difference
Formal definition for the difference of two
sets:
A - B = { x | x  A and x  B }
Further examples
{1, 2, 3} - {3, 4, 5} = {1, 2}
{a, b} - {3, 4} = {a, b}
{1, 2} -  = {1, 2}
The difference of any set S with the empty set will be
the set S
 Complement sets
Formal definition for the complement of a
set: A = { x | x  A } = Ac
Or U – A, where U is the universal set

Further examples (assuming U = Z)

{1, 2, 3}c = { …, -2, -1, 0, 4, 5, 6, … }
{a, b}c = Z

Properties of complement sets

(Ac)c = A Complementation law
A U Ac = U Complement law
A ∩ Ac =  Complement law
 Set identities
A = A AU = U
Identity Law Domination law
AU = A A = 
AA = A Idempotent Complement
(Ac)c = A
AA = A Law Law
AB = BA Commutative (AB)c = AcBc
De Morgan’s Law
AB = BA Law (AB)c = AcBc
A(BC) A(BC) =
= (AB)C Associative (AB)(AC)
Distributive Law
A(BC) Law A(BC) =
= (AB)C (AB)(AC)
A(AB) = A Absorption A  Ac = U Complement
A(AB) = A Law A  Ac =  Law
 How to prove a set identity
For example: A∩B=B-(B-A)
Four methods:
Use the basic set identities
Use membership tables
Prove each set is a subset of each other
Use set builder notation and logical equivalences
 Proof by Set Identities
A  B = A - (A - B)
Proof) A - (A - B) = A - (A  Bc)
= A  (A  Bc)c
= A  (Ac  B)
= (A  Ac)  (A  B)
=   (A  B)
=AB
Showing each is a subset of the others
(A  B)c = Ac  Bc
Proof) Want to prove that
(A  B)c  Ac  Bc and (A  B)c  Ac  Bc

x  (A  B)c
 x  (A  B)
  (x  A  B)
  (x  A  x  B)
  (x  A)   (x  B)
xAxB
 x  A c  x  Bc
 x  Ac  Bc
 Examples
Let A, B, and C be sets. Show that:
a) (AUB)  (AUBUC)
b) (A∩B∩C)  (A∩B)
c) (A-B)-C  A-C
d) (A-C) ∩ (C-B) = 
Functions
 Definition of a function
A function takes an element from a set and
maps it to a UNIQUE element in another set

f maps R to Z
Domain R Z Co-domain
f

f(4.3)
4.3 4

Pre-image of 4 Image of 4.3

 More functions

A pre-image The image

Domain Co-domain of 1 of “a”

Alice A “a” 1
Bob B “bb“ 2
Chris C “cccc” 3
Dave D “dd” 4
Emma F “e” 5

A class grade function A string length function

 Even more functions

Range

a 1 “a” 1
e 2 “bb“ 2
i 3 “cccc” 3
o 4 “dd” 4
u 5 “e” 5

Some function… Not a valid function!

Also not a valid function!
 Function arithmetic
Let f1(x) = 2x
Let f2(x) = x2

f1+f2 = (f1+f2)(x) = f1(x)+f2(x) = 2x+x2

f1*f2 = (f1*f2)(x) = f1(x)*f2(x) = 2x*x2 = 2x3

 One-to-one functions
A function is one-to-one if each element in
the co-domain has a unique pre-image

a 1 a 1
e 2 e 2
i 3 i 3
o 4 o 4
5 5

A one-to-one function A function that is

not one-to-one
 More on one-to-one
Injective is synonymous with one-to-one
“A function is injective”
A function is an injection if it is one-to-one

Note that there can a 1

be un-used elements e 2
in the co-domain i 3
o 4
5

A one-to-one function
 Onto functions
A function is onto if each element in the co-
domain is an image of some pre-image

a 1 a 1
e 2 e 2
i 3 i 3
o 4 o 4
u 5

An onto function A function that

is not onto
 More on onto
Surjective is synonymous with onto
“A function is surjective”
A function is an surjection if it is onto

Note that there can

be multiply used a 1
elements in the e 2
co-domain i 3
o 4
u

An onto function
 Onto vs. one-to-one
Are the following functions onto, one-to-
one, both, or neither?
a 1 a 1
a 1
b 2 b 2
b 2
c 3 c 3
c 3
4 d 4
4
1-to-1, not onto Both 1-to-1 and onto Not a valid function

a 1 a 1
b 2 b 2
c 3 c 3
d d 4
Onto, not 1-to-1 Neither 1-to-1 nor onto
 Bijections
Consider a function that is
both one-to-one and onto: a 1
b 2
c 3
Such a function is a one-to-one d 4
correspondence, or a bijection
 Identity functions
A function such that the image and the pre-
image are ALWAYS equal

f(x) = 1*x
f(x) = x + 0

The domain and the co-domain must be the

same set
 Inverse functions

Let f(x) = 2*x

R f R

f-1

f(4.3)
4.3 8.6
f-1(8.6)

Then f-1(x) = x/2

 More on inverse functions
Can we define the inverse of the following functions?

a 1 a 1
b 2 b 2
c 3 c 3
4 d

What is f-1(2)? What is f-1(2)?

Not onto! Not 1-to-1!

An inverse function can ONLY be done defined on a

bijection
 Few Examples
f: Z → Z
f(x) = x
f(x) = 2x
f(x) = x+1
f: R → R
f(x) = 2x
f(x) = x2
f(x) = x3
f: R → R+  {0}
f(x) = x2
 Definition of a function
A function takes an element from a set and
maps it to a UNIQUE element in another set

f maps R to Z
Domain R Z Co-domain
f

f(4.3)
4.3 4

Pre-image of 4 Image of 4.3

 Compositions of functions
(f ○ g)(x) = f(g(x))
f○g

A B C
g f

g(a) f(b)

a f(g(a))
b = g(a)

(f ○ g)(a)
 Compositions of functions

Let f(x) = 2x+3 f○g

Let g(x) = 3x+2
R R R
g f

g(1) f(5)
f(g(1))=13
1
g(1)=5

(f ○ g)(1)

f(g(x)) = 2(3x+2)+3 = 6x+7

 Compositions of functions

Does f(g(x)) = g(f(x))?

Let f(x) = 2x+3 Let g(x) = 3x+2

f(g(x)) = 2(3x+2)+3 = 6x+7

g(f(x)) = 3(2x+3)+2 = 6x+11

Not equal!
Function composition is not commutative!
 f(x)=3
Graphs of functions x=1

Let f(x)=2x+1
f(x)=5
x=2
Plot (x, f(x))

This is a plot
of f(x)
 Useful functions
Floor: x means take the greatest integer
less than or equal to the number

Ceiling: x means take the lowest integer

greater than or equal to the number

round(x) =  x+0.5 
 Floor, Ceiling Examples
Find these values

1.1 1
1.1 2
-0.1 -1
-0.1 0
 Ceiling and floor properties
Let n be an integer
(1a) x = n if and only if n ≤ x < n+1
(1b) x = n if and only if n-1 < x ≤ n
(1c) x = n if and only if x-1 < n ≤ x
(1d) x = n if and only if x ≤ n < x+1
(2) x-1 < x ≤ x ≤ x < x+1
(3a) -x = - x
(3b) -x = - x
(4a) x+n = x+n
(4b) x+n = x+n
 Ceiling property proof
Prove rule 4a: x+n = x+n
Where n is an integer
Will use rule 1a: x = n if and only if n ≤ x <
n+1
Direct proof!
Let m = x
Thus, m ≤ x < m+1 (by rule 1a)
Add n to both sides: m+n ≤ x+n < m+n+1
By rule 1a, m+n = x+n
Since m = x, m+n also equals x+n
Thus, x+n = m+n = x+n
 Factorial
Factorial is denoted by n!

n! = n * (n-1) * (n-2) * … * 2 * 1

Thus, 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720

Note that 0! is defined to equal 1

 Proving Function problems
Let f be an invertible function from Y to Z
Let g be an invertible function from X to Y
Show that the inverse of f○g is:
(f○g)-1 = g-1 ○ f-1

(Pf) Thus, we want to show, for all zZ and xX

((f  g)  (g-1  f-1)) (x) = x and ((f-1  g-1)  (g  f)) (z) = z

((f  g)  (g-1  f-1)) (x) = (f  g) ((g-1  f-1)) (x))

= (f  g) (g-1 (f-1(x)))
= (f (g (g-1 (f-1(x)))))
= (f (f-1(x))
=x
The second equality is similar