Chapter 3  Functions, Sequences and Relations

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

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    f = { (1, a), (2, b), (3, a) }  (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 a 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.

* 각 책은 하나씩 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

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.

One-to-One functions (Injective)

 Definition  1.21 one-to-one (injective)  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

is one-to-one      If      then    .                               ■

 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 .

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

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]