The Language of relations and

functions
Mathematics is a language. —Josiah
Willard Gibbs (1839–1903)
 Relation
Let A and B be sets. A relation R from A to B is a subset
of A X B. Given an ordered pair (x, y) in A X B, x is
related to y by R, written x R y, if, and only if, (x, y) is
in R.
• The set A is called the domain of R and the set B is
called its co-domain.
• The notation for a relation R may be written
symbolically as follows:
x R y means that (x, y)  R.
• The notation x R y means that x is not related to y by R:
x R y means that (x, y)  R.
 A relation as a Subset

Let A = {1, 2} and B = {1, 2, 3} and define a relation R from

A to B as follows:
Given any (x, y) A X B,
x y
(x, y) R means that is an integer.
2
1. State explicitly which ordered pairs are in A X B and
which are in R.
1
2. Is 1 R 3? Is 2 R 3? Is 2 R 2? 1
2 2
3

3. What are the domain and co-domain of R?

Domain co-doamin
 Functions

A function f from a set X to a set Y, denoted f : X Y, is a relation

from X, the domain of f, to Y, the co-domain of f, that satisfies two
properties:
(1) every element in X is related to some element in Y, and
(2) no element in X is related to more than one element in Y.
Thus, given any element x in X, there is a unique element in Y that is
related to x by f. If we call this element y, then we say that “f sends x
to y” or “f maps x to y” and write f : x y.
The unique element to which f sends x is denoted
f (x) and is called f of x, or
the output of f for the input x, or
the value of f at x, or
the image of x under f.
The set of all values of f taken together is called the
range of f or the image of X under f.
range of f = image of X under f = {y  Y | y = f (x), for
some x in X}.

Given an element y in Y, there may exist elements in X

with y as their image. When x is an element such that
f (x) = y, then x is called a preimage of y or an inverse
image of y. The set of all inverse images of y is called the
inverse image of y.

the inverse image of y = {x  X | f (x) = y}.

 Arrow diagrams

This arrow diagram does define a function because:

1. Every element of X has an arrow that points to an element
in Y.
2. No element of X has two arrows that point to two different
elements of Y.

1 a

b
2
c
3
d
 Let X = {a, b, c} and Y = {1, 2, 3, 4}. Define a function f from X
to Y by the arrow diagram given below.
1. Write the domain and co-domain of f.
2. Find f (a), f (b), and f (c).
3. What is the range of f?
4. Is c an inverse image of 2? Is b an inverse image of 3?
5. Find the inverse images of 2, 4, and 1.
6. Represent f as a set of ordered pairs.

1
a 2
b 3
c 4
 Theorem: Test for Function Equality

If F : X Y and G : X Y are functions,

then F = G if, and only if,
F (x) = G (x) for every x  X.
 Proof
Suppose F : X Y and G : X Y are functions; that is, F and G are
relations from X to Y that satisfy the two additional function
properties.
Then F and G are subsets of X x Y, and for (x, y) to be in F means
that y is the unique element related to x by F, which we denote as
F (x). Similarly, for (x, y) to be in G means that y is the unique
element related to x by G, which we denote as G (x).
Now suppose that F (x) = G (x) for every x  X. Then if x is any
element of X,
(x, y)  F y = F (x) y = G (x) (x, y)  G [because F(x) = G(x)].

So F and G consist of exactly the same elements and hence F = G.

Conversely, if F = G, then for every x  X,

y = F(x) (x, y)  F (x, y)  G y = G(x) [because F and G consist of exactly the same elements]
Thus, since both F(x) and G(x) equal y, we have that
F(x) = G(x).
Let J = {0, 1, 2}, and define functions f and g from J to J as
follows: For every x in J,
f ( x)  ( x 2  x  1) mod 3 g ( x)  ( x  2) 2 mod 3

Does f = g?

x f ( x)  ( x 2  x  1) mod 3 g ( x)  ( x  2) 2 mod 3
0 1 mod 3=1 4 mod 3 =1
1 3 mod 3=0 9 mod 3 =0
2 7 mod 3=1 16 mod 3 =1

Yes, f=g
 The Identity Function on a Set

Given a set X, define a function I(x) from X to X

by
I (x) = x for each x in X.

The function I is called the identity function on

X because it sends each element of X to
the element that is identical to it.
 Sequences

The formal definition of sequences specifies that an infinite

sequence is a function defined on the set of integers that are
greater than or equal to a particular integer. For example, the
sequence denoted

1 1 1 (1) n
1, , , ,..., ,...
2 3 4 n 1
Send each integer n≥0, to
(1) n
f ( n) 
n 1
A Function Defined on a Power Set

F : P({a, b}) Z nonnegative

0
{}
1
{a}
2
{b}
3
{a, b}
.
.
.
 Logarithms and Logarithmic Functions

Let b be a positive real number with b ≠ 1. For each positive

real number x, the logarithm with base b of x, written logb x ,
is the exponent to which b must be raised to obtain x.
Symbolically:
log b x  y  b y  x
The logarithmic function with base b is the function from R to
R that takes each positive real number x to logb x
 The Hamming Distance Function

Let S n be the set of all string of length n.

Define a function H : S n  S n  Z as follows: For each pair
nonnegative

of strings ( s, t ) S nS n

H (s, t) = the number of positions in which s and t have

different values.
H(11111,00000)=5
H(11000,00000)=2
 (n-place) Boolean function

An (n-place) Boolean function f is a function whose domain is

the set of all ordered n-tuples of 0’s and 1’s and whose co-
domain is the set {0, 1}. More formally, the domain of a
Boolean function can be described as the Cartesian product of
n copies of the set {0, 1}, which is denoted {0,1}n .

f : {0,1}n  {0,1}
Consider the three-place Boolean function defined from the set of all 3-tuples of 0’s
and 1’s to {0, 1} as follows: For each triple (x1, x2, x3) of 0’s and 1’s,
f ( x1 , x2 , x3 )  ( x1  x2  x 3 ) mod 2

x1 x2 x3 ( x1  x 2  x3 ) mod 2
1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 1
0 0 1 1
0 0 0 0
 Checking Whether a Function Is Well Defined

f: R R, for each real number x, f (x) is the real

number y such that x 2  y 2  1
1

(1) there is no y that satisfies the given equation for

some values of x
(2) there are two different values of y that satisfy the
equation.
A “function” is not well defined if it fails to satisfy
at least one of the requirements for being a function.
 Functions Acting on Sets
• If f : X Y is a function and A  X and C  Y,
then f (A) = {y  Y | y= f (x) for some x in A}
and f -1(C ) = {xX | f (x)  C}.

f (A) is called the image of A

f -1(C) is called the inverse image of C.
Let X = {1, 2, 3, 4} and Y = {a, b, c, d, e}, and define F : X Y by the
following arrow diagram:

Let A = {1, 4}, C = {a, b}, and D = {c, e}.

a
1 b
2 c
3 d
4
e
F(A) ={b}
F(X) ={a,b,d}
F -1(C)={1,2,4}
F -1(D)={}
 One-to-One, Onto, and Inverse Functions

Let F be a function from a set X to a set Y. F is one-to-

one (or injective) if, and only if, for all elements x1
and x2 in X,
if F ( x )  F ( x ) , then x1  x2 ,
1 2

or, equivalently, if x1  x2 , then F ( x1 )  F ( x2 ) .

Symbolically:
F: X Y is one-to-one x1 , x2  X , if F ( x1 )  F ( x2 )
then x1  x2 .
Let X = {1, 2, 3} and Y = {a, b, c, d}. Define H: X Y as follows: H (1) = c,
H (2) = a, and H (3) = d. Define K: X Y as follows: K (1) = d, K (2) = b, and
K (3) = d. Is either H or K one-to-one?

H
1 a
a 2 b
1 aa
b 3 c
2 d
c
3
d

• H is one-to-one K is not one-to one

 f : R R is defined by the rule f ( x)  4 x  1 , for each
real number x, then f is one-to-one.

Proof: Suppose x1 and x2 are real numbers such that

f ( x1 )  f ( x2 )
[We must show that x1  x 2 ] .

By definition of f, 4 x11  4 x2  1 .
4 x1  4 x2

x1  x2
If the function g: Z Z is defined by the rule g (n)  n 2 , for
all n  Z, then g is not one-to-one.

Counter example:

Let n1  2 and n2  2.

Then by definition of g,
g (n1 )  g (2)  2 2  4
g (n 2 )  g (2)  (2) 2  4 and

Hence g (n1 )  g (n2 ) but n1  n2

and so g is not one-to-one.
 Hash function

A hash function is a function defined from a

larger, possibly infinite, set of data to a smaller
fixed-size set of integers.
• Define a function H, from the set of student ID
numbers to the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10} as follows:
H(n) = n mod 11 for each ID number n.
Mod function in R

> X<-328343419 #Compute the mod X

> Y<-X %% 11; Y
[1] 8
 Cryptographic hash function

1. It is a function from bit strings to bit strings of a fixed

length.
2. It is close to being one-to-one: the probability of
collisions is very small.
3. It is close to being a one-way function: given any bit
string in its range, finding the inverse image of the
string is computationally very difficult.
4. Its values can be quickly computed.
5. A very slight change in an input string results in an
extensive change in the output string.
 Uses of cryptographic functions

• to provide password security.

• for checking the integrity of files. [When a file is
intended to be copied, a cryptographic hash function is
applied to it. The accuracy of a copy is checked by applying
the same hash function]
• in blockchain technology. [To make it impossible to
change the data in any part of a block, each includes a
time stamp plus a hash computed from all the previous
parts of the blockchain].
 onto (or surjective) functions

• Let F be a function from a set X to a set Y. F is onto (or

surjective) if, and only if, given any element y in Y, it is
possible to find an element x in X with the property that
y = F (x).
Symbolically:
F: X Y is onto  y  Y,  x  X such that F (x) = y.
 Identifying Onto Functions Defined on Finite Sets

1
a
2
b
3
c
4
d
5

• F is not onto because b  F(x) for any x in X.

If f : R R is the function defined by the rule f ( x)  4 x  1 for each
real number x , then f is onto.

Proof: Let y R.
[We must show that x in R such that f ( x)  y .]

y 1
Let x
4

Then x is a real number since sums and quotients (other than by 0) of real
numbers are real numbers.
It follows that
 y 1  y 1
f ( x)  f    4  1  y
 4   4 
If the function h : Z Z is defined by the rule
h(n) = 4n-1 for each integer n, then h is not onto.
Counter example:
The co-domain of h is Z and 0  Z. But h(n)  0 for
any integer n.
For if h(n) = 0, then

4n-1 =0 [by definition of h]

4n = 1
n= ¼
¼ is not an integer. Hence there is no integer n for which
f (n) = 0, and thus f is not onto.