Outline

• 3.1 Functions
• 3.2 Sequences and Strings
• 3.3 Relations
• 3.4 Equivalence Relations
• 3.5 Matrices of Relations

2
 3.1 Functions

Credit card numbers typically consist of 13, 15, or 16 digits. For example,
• The first digit 4690 3582 1375 4657 The last digit is
designates the special, it is
system check digit.
• 4: Visa card The following digits specify other
information such as the account
number and the bank number

3
Luhn algorithm - Hans Peter Luhn (1896–1964)

7 Doubling
the value of
the number
in the even
position

Add digits of two-digit numbers

SUM = 8 + 6 + 9 + 0 + 6 + 5 + 7 + 2 + 2 + 3 + 5 + 5 + 8 + 6 + 1 = 73.
The check digit =

4
Definition 3.1.1
Let and be sets.
• A function from to is a subset of the Cartesian product having the
property that for each , there is exactly one with . We sometimes denote
a function f from X to Y as f : X → Y.
• The set X is called the domain of f and the set Y is called the codomain
of f.
• The set

(which is a subset of the codomain Y) is called the range of f .

Example 3.1.2
• The check digit function.
• If we call the check digit function L, we may write
L(469035821375465) = 7 and L(469035827375465) = 4. 5
Example 3.1.3-5
• Is the set f = {(1, a), (2, b), (3, a)}
a function from X = {1, 2, 3} to Y
= {a, b, c}?

• Is the set
{(1, a), (2, a), (3, b)}
a function from X = {1, 2, 3, 4} to
Y = {a, b, c}?

• Is the set {(1, a), (2, b), (3, c), (1,

b)} a function from X = {1, 2, 3}
to Y = {a, b, c}?
6
The graph of a function whose domain and codomain are subsets of the
real numbers is obtained by plotting points in the plane that correspond to
the elements in The domain is contained in the horizontal axis and the
codomain is contained in the vertical axis.

Example 3.1.10
The graph of the function is shown

7
Definition 3.1.11
If is an integer and is a positive integer, we define to be the remainder
when is divided by .
Example 3.1.12-14
• We have
6 mod 2 = 0, 5 mod 1 = 0, 8 mod 12 = 8, 199673 mod 2 = 1.
• The check digit calculated by the Luhn algorithm can be written
[10 − (S mod 10)] mod 10,
where S is the sum used in the intermediate step of the calculation.
• What day of the week will it be 365 days from Wednesday?
8
Example 3.1.15-16
• Hash Functions:
• Pseudorandom Numbers: Linear congruential method requires four
integers:
• The modulus m,
• The multiplier a (2 ≤ a < m),
• The increment c (0 ≤ c < m), and
• A seed s (0 ≤ s < m).
• We then set The sequence of pseudorandom numbers generated,
is given by the formula

Commonly used values are

which generate a sequence of integers before repeating a value.

9
Definition 3.1.17
• The floor of , denoted , is the greatest integer less than or equal to .
• The ceiling of , denoted , is the least integer greater than or equal to

Example 3.1.18-19
• .
• The graphs of the floor (left
graph) and ceiling (right graph)
functions.

10
• if d and are integers, , there exist integers q (quotient) and (remainder)
satisfying

Since ,

Definition 3.2.22
A function from to is said to be one-to-one (or injective) if for all , if then

Example 3.1.23-24
• Is the function from to one-to-one?
• Is the function one-to-one?
11
Example 3.1.27-28
• Prove that the function from the set of positive integers to the set of
positive integers is one-to-one.
• Prove that the function from the set of positive integers to the set of
integers is not one-to-one.
Definition 3.1.29
A function from to is said to be onto (or surjective) if for every , there
exists such that

Example 3.1.30-31
• Is the function f = {(1, a), (2, c), (3, b)} from X = {1, 2, 3} to Y = {a, b,
c} one-to-one or onto Y?
• Is the function f = {(1, b), (3, a), (2, c)} from X = {1, 2, 3} to Y = {a, b, c,
d} onto Y?
12
Example 3.1.32
If a function from X to Y is onto, each
element in Y in its arrow diagram will have
at least one arrow pointing to it

Example 3.1.33-34
• Prove that the function

from the set X of nonzero real numbers to the set Y of positive real
numbers is onto Y.
• Prove that the function from the set X of positive integers to the set Y of
positive integers is not onto Y.

13
Definition 3.1.35
A function that is both one-to-one and onto is called a bijection.
Example 3.1.36-37
• Is the function f = {(1, a), (2, c), (3, b)} from X = {1, 2, 3} to Y = {a, b,
c} bijection Y?
• If f is a bijection from a finite set X to a finite set Y, then |X| = |Y|.
• Suppose that the function f is a bijection from X to Y. It can be shown that
the function {(y, x) | (x, y) ∈ f} is bijection from Y to X. This new
function, denoted , is called inverse.
Example 3.1.38
For the function
},
we have
14
Example 3.1.40
The function is a one-to-one function from the set of all real numbers onto
the set of all positive real numbers. Derive a formula for

Definition 3.1.41
Let be a function from X to Y and let be a function from Y to Z. The
composition of with , denoted , is the function

from X to Z.
Example 3.1.42-43
Given , a function from , and , a function from to the composition function
from to is the function

15
Example 3.1.45
A store offers 15% off the price of certain items. A coupon is also available
that offers $20 off the price of the same items. The store will honor both
discounts. The function gives the cost with 15% off the price p. The
function gives the cost using the $20 coupon. The composition

gives the cost using first the coupon and then the 15% discount.
The composition

gives the cost using first the 15% discount and then the coupon. We see that
regardless of the price of an item, it is always cheapest to use the discount
first.

16
Definition 3.1.47
A function from to X is called a binary operator on

Example 3.1.47-48
• Let X = {1, 2, . . .}. If we define f (x, y) = x + y, where x, y ∈ X, then f is
a binary operator on X.
• If X is the set of all propositions, ∧, ∨, →, and ↔ are binary operators
on X.
Definition 3.1.50
A function from X to X is called a unary operator on X.
Example 3.1.51-52
• Let U be a universal set. If we define , where X ∈ P(U), then f is a unary
operator on P(U).
• If X is a set of propositions, ¬ is a unary operator on X.
17
 3.2 Sequences and Strings

Blue Taxi Inc. charges $1 for the first mile and

50 cents for each additional mile. The following
table shows the cost of traveling from 1 to 10
miles. In general, the cost of traveling n miles
is 1.00 (the cost of traveling the first mile) plus
0.50 times the number (n − 1) of additional
miles. That is,

18
Definition 3.2.1
A sequence s is a function whose domain D is a subset of integers. The
notation is typically used instead of the more general function notation . The
term is called the index of the sequence. If D is a finite set, we call s a finite
sequence; otherwise, s is an infinite sequence.
Example 3.2.2-3
Consider the sequence:

• If the domain of a sequence s is the (infinite) set of consecutive integers

{k, k + 1, k + 2, . . .} and the index of s is n, we can denote the sequence s
as
19
• A sequence is increasing if for all and in the domain of , if , then .
• A sequence is decreasing if for all and in the domain of , if , then .
• A sequence is nondecreasing if for all and in the domain of , if , then .
• A sequence is nonincreasing if for all and in the domain of , if , then

Definition 3.2.12
Let be a sequence. A subsequence of is a sequence obtained from by
choosing certain terms of in the same order in which they appear in .
Example 3.2.13
The sequence b, c is a subsequence of the sequence a, a, b, c, q.
20
Definition 3.2.17
If is a sequence, we define:
• The sum (or sigma) notation:

• The product notation:

Example 3.2.18
Let a be the sequence defined by . Then

21
Definition 3.2.23
A string over X, where X is a finite set, is a finite sequence of elements from
X.
Example 3.2.24
Let . If we let

we obtain a string over . This string is written baac.

• The string with no elements is called the null string and is denoted λ.
• Let denote the set of all strings over X, including the null string, and
• Let denote the set of all nonnull strings over X.
Example 3.2.25
Let . Some elements in are , and .
22
• The length of a string α is the number of elements in α. The length of α is
denoted |α|.
• If α and β are two strings, the string consisting of α followed by β, written
αβ, is called the concatenation of α and β.
Example 3.2.26
• If and , then and .
• If and , then

Definition 3.2.30
A string β is a substring of the string α if there are strings γ and δ with
α = γβδ.
23
Example 3.2.31
The string β = add is a substring of the string α = aaaddad.
Example 3.2.32-33
• Let . If , let αR denote α written in reverse. For example, if , . Define a
function from to as . Prove that f is a bijection.
• Let . Define a function from to as . Is f one-to-one? Is f onto ?

24
 3.3 Relations

Table 3.3.1 shows which students are

taking which courses.
Definition 3.3.1
A (binary) relation R from a set X to a
set Y is a subset of the Cartesian
product . If , we write and say that x is
related to y. If X = Y, we call R a
(binary) relation on X
25
Example 3.3.2
If we let X = {Bill, Mary, Beth, Dave} and
Y = {CompSci, Math, Art, History}, our
relation R of Table 3.3.1 can be written
R={(Bill, CompSci), (Mary, Math), (Bill,
Art), (Beth, History), (Beth, CompSci),
(Dave, Math)}.

Example 3.3.3
Let X = {2, 3, 4} and Y = {3, 4, 5, 6, 7}. If we define a relation R from X to
Y by (x, y) ∈ R if x divides y, we obtain R = ?

26
Example 3.3.4
Let R be the relation on X = {1, 2, 3, 4}
defined by (x, y) ∈ R if x ≤ y, x, y ∈ X. Then
R=?

Definition 3.4.6,9,12
• A relation R on a set X is reflexive if for every .
• A relation R on a set X is symmetric if for all , if , then .
• A relation R on a set X is antisymmetric if for all , if and , then .

27
Example 3.3.7,10,13,16
• The relation R on X = {1, 2, 3, 4} defined by (x, y) ∈ R if x ≤ y, x, y ∈
X, is reflexive.
• The relation R = {(a, a), (b, c), (c, b), (d, d)} on X = {a, b, c, d} is
symmetric.
• The relation R on X = {1, 2, 3, 4} defined by (x, y) ∈R if x ≤ y, x, y ∈X,
is antisymmetric.
• The relation R = {(a, a), (b, c), (c, b), (d, d)} on X = {a, b, c, d} is not
antisymmetric.

Definition 3.3.17
A relation R on a set X is transitive if for all x, y, z ∈ X, if (x, y) and (y, z) ∈
R, then (x, z) ∈ R.
28
Definition 3.3.20
A relation R on a set X is a partial order if R is reflexive, antisymmetric, and
transitive
Example 3.3.21
Since the relation R defined on the positive integers by
(x, y) ∈ R if x divides y.
is reflexive, antisymmetric, and transitive, R is a partial order.
Definition 3.3.23
Let R be a relation from X to Y. The inverse of R, denoted
, is the relation from Y to X defined by

Example 3.3.24
If , then the inverse of this relation is
29
Definition 3.3.24
Let be a relation from X to Y and be a relation from Y to Z. The
composition of and , denoted , is the relation from X to Z defined by

Example 3.3.26
The composition of the relations

and

is

For example, (1, u) ∈ because (1, 2) ∈ and (2, u) ∈ .

30
 3.4 Equivalence Relations

Suppose that we have a set X of 10

balls, each of which is either red, blue,
or green. If we divide the balls into sets
R, B, and G according to color, the
family {R, B, G} is a partition of X.

31
A partition can be used to define a relation.
Theorem 3.4.1
Let be a partition of a set X. Define to mean that for some set S in , both x
and y belong to S. Then R is reflexive, symmetric, and transitive.
Example 3.4.2
Consider the partition of X = {1, 2, 3, 4, 5, 6}. The relation R on X is

Definition 3.4.3
A relation that is reflexive, symmetric, and transitive on a set X is called an
equivalence relation on X.
32
Example 3.4.4
The relation R of Example 3.4.2 with respect to partition
.

Example 3.4.6
The relation R on X = {1, 2, 3, 4} defined by (x, y) ∈ R if x ≤ y, x, y ∈ X, is
R an equivalence relation?
33
Theorem 3.4.8
Let be an equivalence relation on a set . For each , let (In words, [a] is the
set of all elements in X that are related to a.) Then

is a partition of X.

Definition 3.4.9
Let R be an equivalence relation on a set X. The sets [a] defined in Theorem
3.4.8 are called the equivalence classes of X given by the relation R.
Example 3.4.10
Find the equivalence classes of X = {1, 2, 3, 4, 5, 6} give by the equivalence
relation R = {(1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5), (2,
2), (2, 6), (6, 2), (6, 6), (4, 4)}. 34
Example 3.4.12
Find the equivalence classes for the equivalence relation

on .

Example 3.4.14
Let X = {1, 2, . . . , 10}. Define x R y to mean that 3 divides x − y.
• Verify that the relation R is reflexive, symmetric, and transitive. Thus R
is an equivalence relation on X.
• Determine the members of the equivalence classes.
Theorem 3.4.16
Let R be an equivalence relation on a finite set X. If each equivalence class
has r elements, there are |X|/r equivalence classes.
35
 3.5 Matrices of Relations

A matrix is a convenient way to represent a relation R from X to Y.

• We label the rows with the elements of X (in some arbitrary order), and
we label the columns with the elements of Y (again, in some arbitrary
order). We then, set the entry in row x and column y to 1 if x R y and to 0
otherwise.
• This matrix is called the matrix of the relation R (relative to the
orderings of X and Y).

36
Example 3.5.1-2
The matrix of the relation
R = {(1, b), (1, d), (2, c), (3, c), (3, b), (4, a)}
from X = {1, 2, 3, 4} to Y = {a, b, c, d}.
• Relative to the orderings 1, 2, 3, 4 • Relative to the orderings 2, 3, 4, 1
and a, b, c, d: and d, b, a, c:

• Obviously, the matrix of a relation from X to Y is dependent on the

orderings of X and Y.
37
Example 3.5.3
The relation R from {2, 3, 4} to {5, 6, 7, 8}, defined by
if x divides y.
What is the matrix of R relative to the orderings 2, 3, 4 and 5, 6, 7, 8?

38