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)  http://matrix.skku.ac.kr/2018-DM/Ch-1/ 
 DM-Ch-1-Lab  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/2018-DM/Ch-2/
DM-Ch-2-Lab    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 Well-Ordering Property https://youtu.be/areatkjOjcg 

​(DM Ch. 3, Functions, Sequences, and Relations, Lecture Note)  
http://matrix.skku.ac.kr/2018-DM/Ch-3/
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/2018-DM/Ch-4/
DM-Ch-4-Lab   http://math1.skku.ac.kr/home/pub/2654/
    (DM Ch. 4, 동영상강의) 
​DM 이산수학 Ch 4,
...

[References]

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

 

 By  

 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

http://matrix.skku.ac.kr/Cal-Book/part1/CS-Sec-1-3.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

http://blog.naver.com/PostView.nhn?blogId=onlyyeom&logNo=100160308299&parentCategoryNo=37&categoryNo=51&viewDate=&isShowPopularPosts=false&from=postView 

그림입니다.그림입니다.

 

 * 각 책은 하나씩 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, https://ko.wikipedia.org/중국인의 나머지정리

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.

 

Proof 

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.

 

Proof 

[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

 

그림입니다.

 


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

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

 

 




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

.

 



 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.



 

 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

.

 

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

 

 




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