Chapter 2
Basic Structures
Sets, Functions
Sequences, and Sums
Objectives
Sets
Setoperations
Functions
Sequences
Summations
2.1- Sets
An unordered collection of objects
The objects in a set are called the elements, or members. A
set is said to contain its elements.
Some important sets in discrete mathematics
N = { 0,1,2,3,4,… }
Z = { … , -2,-1,0,1,2,…} Z+ = {0,1,2,…}
R: the set of real numbers
p G. Cantor
Q r p Z , 0 q Z
q
V a, u , o, i, e
aA : a is an element of the set A // a belongs to A
aA: a is not an element of A
Sets…
Definitions:
Finite set: Set has n elements, n is a nonnegative integer
A set is an infinite set if it is not finite
Cardinality of a set |S|: Number of elements of S
: empty set (null set), the set with no element
Two sets are equal they have the same elements
A = B if and only if x (xA x B)
A B: the set A is a subset of the set B
A B if and only if x (xA x B)
A B: A is a proper subset of B
A B if and only if (A B) ^ (A ≠ B) Venn diagram shows that A
is a subset of B
Theorem 1
For every set S ,
i) S ii) S S
Pr oof
i ) (x ) False
So x x x S True
ii) x x S x S True
Power Sets
Given a set S, power set P(S) of S is a
set of all subsets of the set S.
S= { 1,2,3}
P(S)= {Ø,
{1}, {2},{3},
{1,2}, {1,3},{2,3},
{1,2,3}}
Cartesian Products
The ordered n-tuple (a1,a2,…,an) is the ordered
collection that has a1 as its first element, a2 as
its second element, …, and an as its nth element.
Let A andB be sets. The Cartesian product of A
and B, denoted by AxB,
A B a, b a A, b B
For example
A= a, b B= 1, 2, 3
A B a,1, a, 2 , a,3 , b,1, b, 2 , b, 3
Cartesian Products…
The Cartesian product of A1,A2,…,An , denoted
A1xA2x…xAn, is the set of ordered n- tuples
(a1,a2,…,an),
A1 A2 ... An a1 , a2 ,..., an ai Ai , i 1, n
For example
A= a, b B= 1, 2,3 , C 0,1
AxBxC= {(a,1,0),(a,1,1),(a,2,0),(a,2,1),(a,3,0),(a,3,1),
(b,1,0),(b,1,1),(b,2,0),(b,2,1),(b,3,0),(b,3,1) }
2.2- Set Operations
The Union of sets A and B, denoted by A B
A B x x A x B
The difference of A and B, denoted by A-B
A-B= x x A x B
The symmetric difference of A and B, denoted by A B
A B=A B-A B= x ( x A x B ) ( x A B)
Inter sec tion : A B x x A x B
U is the universal set, complement of A is denoted by A
A=U-A= x x A
Set Identities
Identity – See proofs : pages 125, 126 Name
A = A A U = A Identity laws
A U= U A = Domination laws
A A=A AA=A Idempotent laws
A A Complementation law
AB = B A AB=B A Commutative laws
A (B C) = (A B) C A (B C)= (A Associative laws
B) C
A (B C) = (A B) (A C) Distributive laws
A (B C) = (A B) (A C)
A B =A B A B = A B De Morgan laws
A (A B) = A A (AB) = A Absorption
A A =U A A = Complement laws
Generalized Unions and Intersections
n
A1 A2 A3 ... An Ai x x Ai , i 1, 2,..., n
i 1
n
A1 A2 A3 ... An Ai
i 1
x x A1 x A2 x A3 ... x An
Computer Representation of Sets
• Use bit string U={1,2,3,4,5,6,7,8,9,10}
• A= {1,3,5,7,9 } A = “1010101010”
• B= { 1,8,9} B = “1000000110”
Computer Representation of
Sets
A = “1010101010”
B = “1000000110”
A B 10 1010 1010 10 0000 0110=10 1010 1110
A B 1,3,5, 7, 8,9
A B=10 1010 1010 10 0000 0110 10 0000 0010
A B 1,9
2.3. Functions / Mappings /
Transformations…
f: A → B : function f from A to B (or function f maps A to
B)
A: domain of f
B: codomain of f
Functions as sets of ordered pairs
Functions / Mappings /
Transformations…
What are functions?
f: → : f(x) = x2 + 2
f: → : f(x) = 1/(x-1)2 + 5x
f: → : f(x) = (2x+5)/7
f: → : f(x) = (2x+5)2/(7-2x)
Some Important Functions
See Figure 10 – Page 143
Floor function
f: → such that f(x)= x = largest integer
that less than or equal to x, x x
Ceiling function
f: → such that f(x)= x = smallest integer
that greater than or equal to x, x x
One-to-One/ Injective functions
Function f is one-to-one (or
injective) if and only if
a b → f(a) f(b)
for all a and b in the domain of f.
f : → , f(x) = x2
f is not one-to-one
(we have f(-1) = f(1))
Onto Functions
A function f from A to B is called onto, or
surjective, iff
for every element b in B there is an element
a in A with f(a)=b.
f: → , f(m) =m-1
f is onto because y, y=f(m)=m-1, where
m=y+1
One-to-one Correspodent / Bijective
Functions
Function f is a one-to-one
corespondence or a bijection if it is both
one-to-one and onto.
f: {A,B,…,Z} →{65,66,…,90} is a bijection
Inverse Functions
Let f is a bijection from A to B. The inverse function,
denoted by f-1, of f is the function that assigns to an
element b belonging to B the unique element a in A such
that f(a)=b. Hence f-1(b)=a when f(a)=b.
Inverse Functions…
f:→ such that f(x)=x+1
Is f invertible? And if it is, what is its inverse?
Step 1: Show that f is onto
f(y-1)=y for all y
f is onto
Step 2: Show that f is one-to-one
f(a)=a+1= f(b)=b+1 a=b f is one-to-one
f is bijection f is invertible
Step 3: Find inverse function
f(x)= y=x+1 x=f-1(y)
x=y-1 f-1(y)=y-1
Composition of Functions
Let g:A → B, f: B → C
The composition of f and g, denoted by fg, is defined by:
(fg)(x)= f(g(x))
Example:
f: →, f(x)=x+1
g:→, g(x)= x2
(fg)(x)= f(g(x))= f(x2) = x2+1
(gf)(x) = g(f(x)) = g(x+1)= (x+1)2
2.4- Sequences
Sequence : a1, a2, a3,…, an,…
Ex: 1,3,5,8 : Finite sequence
Ex: 1, 1, 2, 3, 5, 8, 13,… : Infinite sequence
A sequence is a function from a subset of
integers to a set S.
an : image of the integer n
ai : a term of the sequence
{an= 1/n}: +→ 1, 1/2, 1/3, 1/4, …
Sequences…
Geometric progression
f(n) = arn a, ar, ar2, ar3, …, arn
Arithmetic progression
f(n) = a + nd a, a+d, a+ 2d, … , a+nd
a: initial term,
r: common ratio, a real number
d: common difference, real number
Do yourself
bn= (-1)n , n>=0 cn= 2(5)n , n>=0
tn= 7-3n, n>=0 an= -1 + 4n, n>=0
Some Useful Sequences
Summations
n
am am 1 am 2 ... an a j j m a j mj n a j
n
j m
// 1 + 2 +3+4+…+n
a : Sequence long sum1 ( int n) // n additions
j : Index of summation { long S=0;
m: Lower limit for (int i=1; i<=n; i++) S+= i;
return S;
n : Upper limit }
// 1 addition, 1 multiplication, 1 division
long sum2 (int n)
{ return ((long)n) * (n+1)/2;
}
See examples 10, 11. Page 154
Summations….
Theorem 1- (Summation of geometric series)
See the proofs in page 155
Some Useful Summation Formulae
See example 15, page 157
Cardinality
Cardinality = number of elements in a set.
The sets A and B have the same cardinality if and only if
there is a one-to-one correspondence from A to B
A set that is either finite or has the same cardinality as
the set of positive integers is called countable.
A set that is not countable is called uncountable.
When a infinite set S is countable, we denote the
cardinality of S is |S|= 0( אaleph null)
For example, ||= 0 אbecause is countable and
infinite but is uncountable and infinite, and we say ||
=2 0א
Examples p.159, 160
sets countable uncountable cardinality
{a, b, …, z}, {x| x5 -3x2 – 11 = 0}, <
…
{0, 2, 4, …, } 0א
N, Z+, Z, Q, ZZ, … 0א
{x| 0 < x < 1}, R,… 20 א
Summary
Sets
Setoperations
Functions
Sequences
Summations
Thanks
