Scribd
Upload
68 views34 pages

Basic Structures Sets, Functions Sequences, and Sums

This document provides an overview of basic set theory concepts including sets, set operations, functions, sequences, and summations. It defines what sets, elements, and membership are. Important sets like the natural numbers, integers, and real numbers are introduced. Set operations like union, intersection, difference, and complement are defined along with properties like identities. Functions, injections, surjections, bijections, and inverse functions are covered. Common sequences like arithmetic and geometric progressions are discussed. Summations, including formulas for sums of integers and geometric series, are presented. The concept of cardinality, countable vs uncountable sets, and aleph null are introduced.

Uploaded by

Vũ Thái Anh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
68 views34 pages

Basic Structures Sets, Functions Sequences, and Sums

This document provides an overview of basic set theory concepts including sets, set operations, functions, sequences, and summations. It defines what sets, elements, and membership are. Important sets like the natural numbers, integers, and real numbers are introduced. Set operations like union, intersection, difference, and complement are defined along with properties like identities. Functions, injections, surjections, bijections, and inverse functions are covered. Common sequences like arithmetic and geometric progressions are discussed. Summations, including formulas for sums of integers and geometric series, are presented. The concept of cardinality, countable vs uncountable sets, and aleph null are introduced.

Uploaded by

Vũ Thái Anh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 34

Chapter 2

Basic Structures
Sets, Functions
Sequences, and Sums
Objectives
 Sets
 Set operations
 Functions
 Sequences
 Summations
 An unordered collection of objects
2.1- Sets
 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

aA : a is an element of the set A // a belongs to A


aA: a is not an element of A

 p  G. Cantor
Q  r  p  Z , 0  q  Z 
 q 
V   a, u , o, i, e
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 (xA  x B)
 A B: the set A is a subset of the set B
A  B if and only if x (xA  x B)
 A  B: A is a proper subset of B
Venn diagram shows that A
A  B if and only if (A  B) ^ (A ≠ B) 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 and B 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),


A  A  ...  A 
AxBxC= 2 n   a , a ,..., a  a  A , i  1, n
1 {(a,1,0),(a,1,1),(a,2,0),(a,2,1),(a,3,0),(a,3,1),
1 2
(b,1,0),(b,1,1),(b,2,0),(b,2,1),(b,3,0),(b,3,1) }
n i i

For example
A=  a, b B=  1, 2,3 , C   0,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 AA=A Idempotent laws
A A Complementation law
AB = B  A AB=B A Commutative laws
A (B C) = (A B) C Associative laws
A (B  C)= (A 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  (AB) = 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 fg, is defined by: (fg)
(x)= f(g(x))

Example:
f:  →, f(x)=x+1
g:→, g(x)= x2
(fg)(x)= f(g(x))= f(x2) = x2+1
(gf)(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  m j  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;
for (int i=1; i<=n; i++) S+= i;
m: Lower limit
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 |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, ZZ, …   0‫א‬

{x| 0 < x < 1}, R,…   20 ‫א‬


Summary
 Sets
 Set operations
 Functions
 Sequences
 Summations
Thanks

You might also like