Chapter 3 Functions, Sequences and Relations
(DM Ch. 1, Sets and Logic, Lecture Note) http://matrix.skku.ac.kr/2018DM/Ch1/
DMCh1Lab http://math1.skku.ac.kr/home/pub/2651/ (Use Chrome browser, not IE)
(DM Ch. 1, 동영상강의)
Discrete Math 이산수학 Ch 0 Introduction https://youtu.be/9ahFnOFTWNQ
Discrete Math 이산수학 Ch 1, 1.1, 1.2 Propositions https://youtu.be/QgdKqmCFW2Y
Discrete Math 이산수학 Ch 1, 1.3, 1.4 Rules of Inference https://youtu.be/92siPfThf0M
Discrete Math 이산수학 Ch 1, 1.5, 1.6 Nested Quantifiers https://youtu.be/7M7w9eX5D0Q
(DM Ch. 2, Proofs, Lecture Note) http://matrix.skku.ac.kr/2018DM/Ch2/
DMCh2Lab http://math1.skku.ac.kr/home/pub/2652/
(DM Ch. 2, 동영상강의)
DM Ch 2 Lecture 1 Sec 2.1, 2.2 2.2 More Methods of Proof Problem https://youtu.be/xEMkHb2AkYk
DM Ch 2 Lecture 2 Sec 2.4, 2.5 Math Induction and WellOrdering Property https://youtu.be/areatkjOjcg
(DM Ch. 3, Functions, Sequences, and Relations, Lecture Note) http://matrix.skku.ac.kr/2018DM/Ch3/
http://math1.skku.ac.kr/home/pub/2653/
(DM Ch. 3, 동영상강의)
DM 이산수학 Ch 3, Functions, Sequences, and Relations 1 https://youtu.be/MhM_9ZuGAis
DM 이산수학 Ch 3, Functions, Sequences, and Relations 2 https://youtu.be/ZjAtN9HkZwM
DM 이산수학 Ch 3, Functions, Sequences, and Relations 3 https://youtu.be/Uuwsx2aiEPI
Ch 4, Algorithms, Lecture Notehttp://matrix.skku.ac.kr/2018DM/Ch4/
DMCh4Lab http://math1.skku.ac.kr/home/pub/2654/
(DM Ch. 4, 동영상강의)
DM 이산수학 Ch 4,
...
3.1. Functions
Definition 1.1 

and are nonempty sets.
is a function from to = maps to is the domain (정의역) of and is the codomain (공변역) of . is an assignment of exactly one element of to each element of .
is the unique element of assigned by the function to the element of . is the image of and is a preimage of . The range (치역) or image of is the set of all images of elements of . 
Functions are sometimes mappings or transformations.
maps to
● is a function from to .
● is a subset of .
● The range (치역) or image of under the function is the subset of that consists of the images of the elements of .
● The range (치역) or image of by , so
.
(1.1) function
travel miles per hour for hours
where is the times and is the distance traveled. ■
Example 1.2 

By The domain is the set of all . The codomain is the set of all . (Assume the time is restricted to .) The range is the set of all . 
Example 1.3 

The set f = { (1, a), (2, b), (3, a) } (orderedpair notation) is a function from to . , , . The domain of is . The codomain of is The range of is . 
Arrow diagram. There is exactly one arrow from each element in .
Domain and Range 

Domain of . Codomain of Range of A function assigns to each in a unique element in . 
Example 1.4 
But the following is not a function: 
The set (1.2) orderedpair notation is not a function from to . The elements is not assigned to an element in . 
Example 1.5 
But the following is not a function: 
The set orderedpair notation is not a function from to . The elements is not assigned a unique element in (1 is assigned the values and ). 
Example 1.7 

Let be the function defined by the rule . If and the Codomain is the set of all nonnegative real numbers, in orderedpair notation, we would have
Range (f) = the set of all nonnegative real numbers. 
Graph of a function
http://matrix.skku.ac.kr/CalBook/part1/CSSec13.htm
Let be a function from the set to the set . The graph of the function is the set of ordered pairs .
Definition 1.10 


Example 1.11 


Example 1.12 

What day of the week will it be 365 days from Wednesday? 
Solution
Since , days from Wednesday, it will be one day later, namely Thursday.
Example 1.13 


* 각 책은 하나씩 ISBN이 부여된다. ISBN은 다음과 같이 구성된다.
978  89 (한국)  5460  326 3
(1)GS1 접두어 (2)국가·언어 (3)출판사 (4)항목 (5)확인숫자
출판 국가 또는 언어 번호 출판사 번호, 영어(0), 프랑스어(2), 독일어(3), ...
13자리 ISBN 이 abcdefghijklm일 때, a+3b+c+3d+e+3f+g+3h+i+3j+k+3l+m = 0 (mod 10) ■
Definition 1.16 

In , is the floor of . the greatest integer less than or equal to . Symbolically, if is a real number and is an integer, then . “rounds down.”
is the ceiling of . the least integer greater than or equal to . Symbolically, if is a real number and is an integer, then . “rounds up.”

Example 1.17 


Example 1.18 

Shows the graphs of the floor and the ceiling functions. indicates that the point is to be included in the graph, indicates that the point is to be excluded from the graph. 
Floor Function Ceiling Function
Example 1.19 

In 2007, the U.S. firstclass postage rate for retail flat mail up to ounces was cents for the first ounce or fraction thereof and cents for each additional ounce or fraction thereof. The postage as a function of weight is , . The expressioncounts the number of additional ounces beyond , with a fraction counting as one additional ounce. As examples ,

The graph of the function is
The Quotient(Chinese)Remainder Theorem, https://ko.wikipedia.org/중국인의 나머지정리
If and are integers, , there exist integers (quotient) and (remainder) satisfying
, .
Dividing by , we obtain
n/d = q + r/d .
Since ,
n/d = q + r/d  = q
Compute the quotient as . Having computed the quotient , we computed the remainder as
.
The notation for the remainder.
● OnetoOne functions (Injective)
Definition 1.21 
onetoone (injective) function 
A function is said to be injective if it is onetoone. 
A function from to is onetoone using quantifiers as
is onetoone If then . ■
Example 1.22 


Example 1.23 


Example 1.25 
onetoone function, Not onetoone function 

Example 1.26 

Prove that the function
from the set of positive integer to the set of positive integer is onetoone. 
Proof
Show that , .
.
Therefore is onetoone. ■
(In words, a function is not onetoone if there exist and such that and .)
Example 1.27 

Prove that the function
from the set of positive integer to the set of positive integer is not onetoone. 
Proof
[Show that f, such that .]
Therefore is not onetoone. ■
● Onto function (surjective function)
Definition 1.28 

Function from to is onto (surjection) for every element there is an element with . A function is surjective if it is onto. 
Example 1.29 


Example 1.30 


● Bijection
Definition 1.34 
(bijective function) 

,
Example 1.35 
( Example 1.29 ) 
The function
from to is a bijection. 
Example 1.36 

If is a bijection from a finite set to a finite set , then , that is, the sets have the same cardinality and are the same size. For example
is a bijection from to . Both sets have four elements. In effect, counts the elements in : is the first element in ; is the second element in ; and so on. 
● Inverse Function
A function is a onetoone and onto from to .
is a onetoone and onto from to . is inverse function of .
The function is the inverse of function .
Example 1.37 
inverse function 
From the function , we have . 
Example 1.38 
inverse function 
The arrow diagram for a bijection function from to . The arrow diagram for simply by reserving the direction of each arrow. 
Definition 1.40 
composition function 

Example 1.31 
The composition function of and . 

A binary operator on a set associates with each ordered pair of elements in one elements in .
Definition 1.45 
binary operator 
A function : is a binary operator on . 
Example 1.46 


Example 1.47 

If is a set of propositions, , , and are binary operator on . 
A unary operator on a set associates with each single element in one element in .
Definition 1.48 
unary operator 
Function : is a unary operator on . 
Example 1.49 

Let be a universal set. If we define
where , then is a unary operator on . 
Example 1.50 

If is a set of proposition, is a unary operator on . 
Exercises 1, 10, 16, 26, 35, 48, 51, 62, 68, 70, 90, 95, 98, 104
3.2 Sequences and Strings
A sequence is an ordered list.
The domain consists of a set of consecutive integers.
The term denoted or . is the index of the sequence.
Infinite sequence : The domain of the sequence is infinite.
: the initial index of an infinite sequence .
Finite sequence : The domain of the sequence is finite.
: a finite sequence indexed from to
For and are in the domain of the sequence.
, sequence is increasing
, sequence is decreasing
, sequence is nondecreasing
, sequence is nonincreasing
● increasing is replaced by nondecreasing : “” is replaced by “”
● decreasing is replaced by nonincreasing : “” is replaced by “”
Example 2.7 

The sequence , , , , is increasing and nondecreasing. 
Example 2.8 

The sequence , is decreasing and nonincreasing. 
Example 2.9 


A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
Definition 2.11 

Let be a sequence defined for . Let , , be an increasing sequence whose values are in the set . We call the sequence a subsequence of . 
Example 2.13 

The sequence (2.5) , , , , , , is a subsequence of the sequence (2.6) , , , , , , , , , , . Subsequence is obtained from sequence by choosing the first, second, fourth, eight, and so on, terms. 
Definition 2.14 

If is a sequence, we define , read the summation from equals to of sub, is the sum of all the terms , , , . is the expanded form of the sum. is a sequence, we define . read the product from equals to of sub, is the product of all the terms , , , . is the expanded form of the product. 
The formalism
(2.7)
is the sum(or sigma) notation.
The formalism
(2.8)
is the product notation.
In and , is the index, is the lower limit and is the upper limit.
Example 2.15 


Example 2.16 


Example 2.17 
Changing the index and Limits in a Sum 
The sum , replacing the index by , where . 
Example 2.18 

Find a formula for the sequence defined by . 
If is a finite set of integers and is a sequence,
denotes the sum of the elements .
If is a finite set of integers and is a sequence,
denotes the product of the elements .
● A string is a finite sequence of characters.
Definition 2.20 

A string over is a finite sequence of element from , where is a finite set. 
Example 2.21 

Let . If we let , , , , we obtain a string over . This string is written . 
A string is a sequence, order is taken into account.
Repetitions in a string can be specified by superscripts.
The string with no elements is the null string. is null string.
is the set of all strings over , including the .
is the set of all nonnull strings over .
Example 2.22 


is the length of .
is the number of elements in .
Example 2.23 


● and are two strings.
is the concatenation of and .
the string consisting of followed by
Example 2.24 

If and , then , , , . 
Example 2.25 

Let . If we define , where and are strings over , then is a binary operation on . 
● A substring of a string is obtained by selecting some or all consecutive elements of .
Definition 2.26 

A string is a substring of the string if there are strings and with . 
Example 2.27 

The string is a substring of the string since if we take and , we have . Note that is a substring of , is the part of that precedes (in ), and is the part of that follows (in ). 
Exercises 40,45,67,69~73, 83~86, 94,111,117,120,129
3.3 Relations (Skipped section: 2.3)
Definition 3.1 

and
say that is related to . say that is not related to . 
If , we call a (binary) relation on .
: A function from to is a binary operator on .
A (binary) relation from a set to a set
Example 3.3 


Example 3.4 

Let be the relation on defined by if , . Then . 
Figure 3.1 The digraph of the relation of Example 3.4.
● A digraph is represented by two letters
● An informative ways to picture a relation on a set is to draw its digraph.
●
We first draw vertices(dots) to represent the elements of To draw the diagraph of a relation on a set .
If the element is in relation, we draw an arrow (directed edge) from to .
An element of the form in a relation corresponds to a directed edge from to . Such an edge is a loop.
Example 3.5 


Definition 3.6 
reflexive relation 
, A relation on a set is reflexive. 
, The relation on a set is reflexive.
Example 3.7 

The relation on defined by if , . Then . This relation is reflexive. Because for each element , ; , , , The digraph of a reflexive relation has a loop at every vertex. The digraph of this relation has a loop at every vertex. 
By the generalized De Morgan’s laws for logic,
, A relation on is not reflexive.
Example 3.8 

Relation
on is not reflexive. (Because some vertex has no loop.) 
For example, , but .
, but .
Vertices (and ) do not have a loop. The relation is not reflexive.
Definition 3.9 

A relation on is symmetric if (, if , then ). 
Example 3.10 

Relation
on is symmetric , . 
For example, and .
Example 3.11 

Relation on defined by if , . Then . is not symmetric. 
For example, , but .
The digraph of this relation has a directed edge from to .
The digraph of this relation has no directed edge from to .
Definition 3.12 


, and : A relation on a set is antisymmetric
Example 3.13 

A relation on defined by if , . This is antisymmetric , and . 
Example 3.15 


Figure 3.3 The digraph of the relation of Example 3.15.
Example 3.16 

Relation
on is not anti symmetric because both and . In the digraph of this relation there are two directed edges between and . 
Definition 3.17 


, and : A relation on a set is transitive
Example 3.18 

The relation on defined by if , . Then . , and . 
Pairs of Form 순서쌍의 짝

Pairs of Form 순서쌍의 짝



Example 3.19 

The relation
on is not transitive. and . 
No directed edge from to .
Definition 3.20 


Example 3.21 

Since the relation defined on the positive integers by if divides is reflexive, antisymmetric and transitive, is a partial order.

Definition 3.23 

Let be a relation from to . The inverse of , denoted , is the relation from to defined by . 
Example 3.24 


Definition 3.25 

Let be a relation from to . Let be a relation from to . Let be a subset of . is a subset of . Then is the composition of and . And is the relation from to . = { (x, y) : (x, y) in R_1 and (y, z) in R_2 for some y in Y }.
(not . ) 
Example 3.26 


Exercises 12, 13, 21, 23, 24, 32, 37, 48
3.4 Equivalence Relations
A set have balls.
The balls color are red, blue and green.
Let be a partition of .
The next theorem shows that some relation is always reflexive, symmetric and transitive.
Theorem 4.1 

Let be a partition of a set . Define to mean that for some set in , both and belong to . Then is reflexive, symmetric and transitive. 
Proof
Let .
By the definition of partition, belongs to some numbers of .
Thus and is reflexive.
Suppose that .
Then both and belong to some set .
Since both and belong to , and is symmetric.
Finally suppose that and .
Then both and belong to some set and both and belong to some set .
Since belong to exactly one member of , .
Therefore, both and belong to and .
We have shown that is transitive. ■
Example 4.2 

The partition
of . The relation on given by Theorem 4.1 contains the ordered pair , and because is in . The complete relation is . 
Definition 4.3 
equivalence relation 
A relation on is caled an equivalence relation if is reflexive, symmetric, and transitive. Three properties: (1) , . (reflexive) (2) . (symmetric) (3) and . (transitive) 
Example 4.4 
equivalence relation 
Relation is . Relation is an equivalence relation on . is reflexive, symmetric and transitive. 
Figure 4.2 The graph of the relation of Example 4.2
is reflexive ( a loop at every vertex)
is symmetric ( for every directed edge from to , there is a directed edge from to )
is transitive (there is a directed edge from to and a directed edge from to , there is a directed edge from to ).
Example 4.5 
equivalence relation 
Consider the relation
on is reflexive. , is symmetric , are is transitive is reflexive, symmetric and transitive. is an equivalence relation on . 
Example 4.6 
Not an equivalence relation 
The relation on defined by if , is Not an equivalence relation because is not symmetric ( ). But this relation is reflexive and transitive.
(See . )

Example 4.7 
Not an equivalence relation 
The relation
on is Not an equivalence relation is neither reflexive nor transitive. is not reflexive , is not transitive 
Theorem 4.8 
equivalence relation, partition 

Definition 4.9 
equivalence class 

Example 4.10 
equivalence class 

Example 4.13 

Relation
on is reflexive, symmetric and transitive. Thus, is an equivalence relation. 
Solution
The equivalence class containing consists of all such that .
Therefore, .
The equivalence class containing consists of all such that .
Therefore, .
The equivalence class containing consists of all such that .
Therefore, .
The equivalence classes are
, , . ■
Example 4.14 
equivalence relation 
Let . Define to mean that divides . Then is reflexive, symmetric and transitive. is an equivalence relation on . 
Solution
The equivalence classes consists of all with .
.
The equivalence classes consists of all with .
.
The equivalence classes consists of all with .
.
These three sets partition .
, , .
Theorem 4.16 


Exercises 4, 15, 22, 29, 64
3.5 Matrices of Relations
A matrix is a relation from to .
We label the rows with the elements of (in some arbitrary order).
We label the columns with the elements of (in some arbitrary order).
If then set the entry in row and column to .
Otherwise,
This matrix is the matrix of the relation (relative to the orderings of and ).
Example 5.1 


Example 5.2 


Example 5.3 


The matrix of a relation on a set (from to ), we use the same ordering for the rows as we do for the columns.
The matrix of a relation on a set is a square matrix.
A relation on the set is reflexive by examining the matrix of .
The relation is reflexive has ’s on the main diagonal.
The relation is reflexive for all .
A relation on the set is called symmetric by examining the matrix of .
The relation is symmetric for all and , the entry of is equal to the entry of .
The relation is symmetric , for all .
Example 5.4 

Matrix of the relation
on the set = relative to the ordering , , , is

The above relation on the set is not symmetric.
The above relation is not reflexive since (2, 2) is not 1 on the main diagonal.
Example 5.5 

Let be a relation from to defined by . Let be a relation from to defined by . 
Solution
The matrix of relative to the orderings , , and , is
.
The matrix of relative to the orderings , and , , is
.
The product of these matrices
.
Let us interpret .
...
is “almost” the matrix of the relation .
To obtain the matrix of the relation , we need only change all nonzero entries in to . ( 2 > 1)
Thus the matrix of the relation , relative to previously chosen ordering , , and , , is
Theorem 5.6 

Let be a relation from to and be a relation from to . Choose orderings of , and . is the matrix of . is the matrix of with respect to the orderings selected. The matrix of the relation with respect to the ordering selected is obtained by replacing each nonzero term in the matrix product by . 
Example 5.7 

Matrix of the relation
on , relative to the ordering , , , is . .
Whenever is nonzero, then is nonzero. Thus, is transitive. 
Example 5.8 

Matrix of the relation
on , relative to the ordering , , , , is
. The entry in row , column of is nonzero, but the corresponding entry in is zero. Therefore, is not transitive. 
Exercises 1, 4, 8, 11, 14, 16, 19, 25 [End of Ch. 3]
Copyright by SGLee, SKKU sglee@skku.edu
http://matrix.skku.ac.kr/sglee/vita/LeeSG.htm