Chapter 3   Functions, Sequences and Relations

원본 그림의 이름: CLP0000ec300017.bmp
원본 그림의 크기: 가로 468pixel, 세로 206pixel

Chapter 3  Functions, Sequences and Relations


원본 그림의 이름: CLP0000ec300018.bmp
원본 그림의 크기: 가로 135pixel, 세로 203pixel

​(DM Ch. 1, Sets and Logic, Lecture Note) 
 DM-Ch-1-Lab   (Use Chrome browser, not IE)
    (DM Ch. 1, 동영상강의) 
Discrete Math 이산수학 Ch 0 Introduction 
Discrete Math 이산수학 Ch 1, 1.1, 1.2 Propositions 
Discrete Math 이산수학 Ch 1, 1.3, 1.4 Rules of Inference 
Discrete Math 이산수학 Ch 1, 1.5, 1.6 Nested Quantifiers

​(DM Ch. 2, Proofs, Lecture Note)
     (DM Ch. 2, 동영상강의) 
​DM Ch 2 Lecture 1 Sec 2.1, 2.2 2.2 More Methods of Proof Problem
​DM Ch 2 Lecture 2 Sec 2.4, 2.5 Math Induction and Well-Ordering Property 

​(DM Ch. 3, Functions, Sequences, and Relations, Lecture Note)
     (DM Ch. 3, 동영상강의) 
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 1 
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 2
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 3


Ch 4, Algorithms, Lecture Note
    (DM Ch. 4, 동영상강의) 
​DM 이산수학 Ch 4,


1. Discrete Math - 7th Edition , Richard Johnsonbaugh, Pearson

원본 그림의 이름: CLP0000ec300017.bmp
원본 그림의 크기: 가로 468pixel, 세로 206pixel

원본 그림의 이름: CLP0000ec300019.bmp
원본 그림의 크기: 가로 139pixel, 세로 32pixel  3.1. Functions


 Definition 1.1


  and  are nonempty sets.

      is a function from  to   =  maps  to 

        is the domain (정의역) of  and  is the co-domain (공변역) 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 pre-image 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



 The domain is the set of all .

 The co-domain is the set of all . (Assume the time is restricted to .)

 The range is the set of all .


 Example  1.3


 The set

  (ordered-pair 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  unique element  in        .


 Example  1.4

But the following is not a function:

 The set

 (1.2)                              ordered-pair 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

  ordered-pair 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 non-negative real numbers, in ordered-pair notation, we would have

 Range (f) = the set of all non-negative real numbers.



Graph of a function

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?



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. first-class 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,중국인의 나머지정리

If  and  are integers, , there exist integers  (quotient) and  (remainder) satisfying

,   .

Dividing by , we obtain


Since ,


Compute the quotient  as . Having computed the quotient , we computed the remainder as


The notation  for the remainder.



 One-to-One functions (Injective)

Definition  1.21

one-to-one (injunctive)  function


         A function is said to be injective if it is one-to-one.


A function  from  to  is one-to-one using quantifiers as

or equivalently


      is one-to-one             .

                                 .        ■

 Example  1.22





 Example  1.23




 Example  1.25

one-to-one function,      Not one-to-one function



 Example  1.26


 Prove that the function

 from the set of positive integer to the set of positive integer is one-to-one.



Show that        .


Therefore  is one-to-one.                                                      ■

 (In words, a function is not one-to-one 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 one-to-one.



[Show that f,  such that .]


Therefore  is not one-to-one.                                                  ■



 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





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 one-to-one and onto from  to .

is a one-to-one 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 .




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 .


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

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




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


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


is the sum(or sigma) notation.

The formalism


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 .



● 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







 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 , .





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 .



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



 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



 on  is symmetric

  ,       .


 For example,  and .

Example  3.11


Relation  on  defined by  if , .



  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



 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 , .



,  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 .



 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.




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



 on  is reflexive, symmetric and transitive.

 Thus,  is an equivalence relation.



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 .




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 .


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.


 Example  5.4


 Matrix of the relation

 on  relative to the ordering  is


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 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.5


 Let  be a relation from  to  defined by


 Let  be a relation from  to  defined by




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



Copyright @ 2018 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).