Lecture-09

Lecture 9
Function
Topics
● Function Definition
● Domain and Range
● One-to-one and Onto Functions
● One-to-one Correspondence
● Cardinality of Sets
● Countable and Uncountable Sets
Function Definition
Let A and B be nonempty sets. A function f from A to B is an assignment of
exactly one element of B to each element of A. We write f(a) = b if b is the
unique element of B assigned by the function f to the element a of A. If f is a
function from A to B, we write f : A → B.
Abir A
Chanda B
Gopal C
Rihan D
Shyamoli F
Fig : Assignment of grades in a discrete mathematics class

Domain and Range
If f is a function from A to B, we say that A is the domain of f and B is the
codomain of f. If f(a) = b, we say that b is the image of a and a is a
preimage of b. The range, or image, of f is the set of all images of elements
of A. Also, if f is a function from A to B, we say that f maps A to B.
f
a b=f(a)
A B
f
Fig : The function f maps A to B

Examples
EXAMPLE: Let R be the relation with ordered pairs (Abdul, 22), (Bidyut, 24),
(Chanda, 21), (Dayem, 22), (Emon, 24), and (Fahim, 22). Here each pair
consists of a graduate student and this student’s age. Specify a function
determined by this relation.
SOLUTION: If f is a function specified by R, then f(Abdul) = 22, f(Bidyut) = 24

and so on. For domain we take the set {Abdul, Bidyut, Chanda, Dayem,
Emon, Fahim}. We also need to specify the codomain, which needs to
contain all possible ages of the students. Because it is highly likely that all
students are less than 100 years old, we can take the set of positive
integers less than 100 as the codomain.
Definition
Let f1 and f2 be functions from A to R. Then f1+f2 and f1f2 are also functions from A
to R defined for all x ∈ A by
● (f1+f2)(x) = f1(x) + f2(x)
● (f1f2)(x) = f1(x)f2(x)
EXAMPLE: Let f1 and f2 be functions from R to R such that f1(x) = x2 and f2(x) = x −
x2. What are the functions f1 + f2 and f1 f2?
SOLUTION: From the definition of the sum and product of functions, it follows that
➔ (f1+ f2)(x) = f1(x) + f2(x) = x2 + (x − x2 ) = x

➔ ( f1f2)(x) = x2 (x − x2) = x3 − x4 .
Definition
Let f be a function from A to B and let S be a subset of A. The image of S
under the function f is the subset of B that consists of the images of the
elements of S. We denote the image of S by f(S), so
f(S) = {t ∣ ∃s∈S (t = f(s))}.
We also use the shorthand {f(s) ∣ s ∈ S} to denote this set.
EXAMPLE: Let A = {a, b, c, d, e} and B = {1, 2, 3, 4} with f(a) = 2, f(b) = 1, f(c)

= 4, f(d) = 1, and f(e) = 1. The image of the subset S = {b, c, d} is the set f(S)
= {1, 4}.
One-to-one Functions
A function f is said to be one-to-one, or an injection, if and only if f(a) = f(b)
implies that a = b for all a and b in the domain of f.
A function is said to be injective if it is one-to-one.
Contrapositive of the previous implication: A function f is one-to-one if

and only if f(a) ≠ f(b) whenever a ≠ b.
Expressing the previous implication using quantifiers: ∀a∀b( f(a) = f(b)

→ a = b) or equivalently ∀a∀b(a ≠ b → f(a) ≠ f(b)), where the universe of
discourse is the domain of the function.
Examples
EXAMPLE: Determine whether the function f from {a, b, c, d} to {1, 2, 3, 4, 5}
with f(a) = 4, f(b) = 5, f(c) = 1, and f(d) = 3 is one-to-one.
SOLUTION: The function f is one-to-one because f takes on different values

at the four elements of its domain.
Examples
EXAMPLE: Determine whether the function f(x) = x2 from the set of integers to the
set of integers is one-to-one.
SOLUTION: The function f(x) = x2 is not one-to-one because, for instance, f(1) =
f(−1) = 1, but 1 ≠ −1.
EXAMPLE: Determine whether the function f(x) = x + 1 from the set of real
numbers to itself is one-to-one.
SOLUTION: Suppose that x and y are real numbers with f(x) = f(y), so,
f(x) = f(y)
→x+1=y+1
→ x = y.
Hence, f(x) = x + 1 is a one-to-one function from R to R.
Definition
A function f whose domain and codomain are subsets of the set of real
numbers is called increasing if f(x) ≤ f(y), and strictly increasing if
f(x) < f(y), whenever x < y and x and y are in the domain of f. Similarly, f is
called decreasing if f(x) ≥ f(y), and strictly decreasing if f(x) > f(y),
whenever x < y and x and y are in the domain of f. (The word strictly in this
definition indicates a strict inequality.)
Examples
EXAMPLE: The function f(x) = x2 from R+ to R+ is strictly increasing. To see

this, suppose that x and y are positive real numbers with x < y. Multiplying
both sides of this inequality by x gives x2 < xy. Similarly, multiplying both sides
by y gives xy < y2. Hence, f(x) = x2 < xy < y2 = f(y). However, the function f(x)
= x2 from R to the set of nonnegative real numbers is not strictly increasing
because −1 < 0, but f(−1) = (−1)2 = 1 is not less than f(0) = 02 = 0.
Onto Functions
A function f from A to B is called onto, or a surjection, if and only if for every
element b ∈ B there is an element a ∈ A with f(a) = b. A function f is called
surjective if it is onto.
Fig: An onto Function

Examples
EXAMPLE: Is the function f(x) = x+1 from the set of integers to the set of
integers onto?
SOLUTION: This function is onto, because for every integer y there is an

integer x such that f(x) = y. To see this, note that f(x) = y if and only if x+1 = y,
which holds if and only if x = y−1. (Note that y−1 is also an integer, and so, is
in the domain of f )
EXAMPLE: Is the function f(x) = x2 from the set of integers to the set of
integers onto?
SOLUTION: The function f is not onto because there is no integer x with
x2 = −1, for instance.
One-to-one Correspondence
The function f is a one-to-one correspondence, or a bijection, if it is both
one-to-one and onto. We also say that such a function is bijective.
EXAMPLE: Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f(a) = 4,

f(b) = 2, f(c) = 1, and f(d) = 3. Is f a bijection?
SOLUTION: The function f is one-to-one and onto. It is one-to-one because

no two values in the domain are assigned the same function value. It is onto
because all four elements of the codomain are images of elements in the
domain. Hence, f is a bijection.
Examples
Fig: Examples of different types of correspondences.

Techniques
Suppose that f : A → B.
● To show that f is injective: Show that if f(x) = f(y) for arbitrary x, y ∈ A,
then x = y.
● To show that f is not injective: Find particular elements x, y ∈ A such
that x ≠ y and f(x) = f(y).
● To show that f is surjective: Consider an arbitrary element y ∈ B and
find an element x ∈ A such that f(x) = y.
● To show that f is not surjective: Find a particular y ∈ B such that f(x) ≠
y for all x ∈ A.
Cardinality of Sets
The sets A and B have the same cardinality if and only if there is a one-to-
one correspondence from A to B. When A and B have the same cardinality,
we write |A| = |B|.
In another words, if there is a one-to-one function from A to B, the cardinality

of A is less than or the same as the cardinality of B and we write |A| ≤ |B|.
Moreover, when |A| ≤ |B| and A and B have different cardinality, we say that
the cardinality of A is less than the cardinality of B and we write |A| < |B|.
Countable and Uncountable Sets
A set that is either finite or has the same cardinality as the set of positive
integers is called countable. A set that is not countable is called
uncountable.
When an infinite set S is countable, we denote the cardinality of S by ℵ0

(where ℵ is aleph, the first letter of the Hebrew alphabet). We write |S| = ℵ0
and say that S has cardinality “aleph null.”
Examples
EXAMPLE: Show that the set of odd positive integers is a countable set.
SOLUTION: To show that the set of odd positive integers is countable, we will
exhibit a one-to-one correspondence between this set and the set of positive
integers. Consider the function f(n) = 2n−1 , from Z+ to the set of odd positive
integers.
We show that f is a one-to-one correspondence by showing that it is both

one-to-one and onto. To see that it is one-to-one, suppose that f(n) = f(m).
Then 2n−1 = 2m−1, so n = m. To see that it is onto, suppose that t is an odd
positive integer. Then t is 1 less than an even integer 2k, where k is a natural
number. Hence t = 2k−1 = f(k).
Examples
Please try to understand the examples 4 and 5 from book.
Thank You

Lecture-09

Uploaded by

Copyright:

Available Formats

Lecture-09

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture-09

Uploaded by

Copyright:

Available Formats

Lecture 9

Fig : Assignment of grades in a discrete mathematics class

Fig : The function f maps A to B

SOLUTION: If f is a function specified by R, then f(Abdul) = 22, f(Bidyut) = 24

➔ (f1+ f2)(x) = f1(x) + f2(x) = x2 + (x − x2 ) = x

EXAMPLE: Let A = {a, b, c, d, e} and B = {1, 2, 3, 4} with f(a) = 2, f(b) = 1, f(c)

Contrapositive of the previous implication: A function f is one-to-one if

Expressing the previous implication using quantifiers: ∀a∀b( f(a) = f(b)

SOLUTION: The function f is one-to-one because f takes on different values

EXAMPLE: The function f(x) = x2 from R+ to R+ is strictly increasing. To see

Fig: An onto Function

SOLUTION: This function is onto, because for every integer y there is an

EXAMPLE: Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f(a) = 4,

SOLUTION: The function f is one-to-one and onto. It is one-to-one because

Fig: Examples of different types of correspondences.

In another words, if there is a one-to-one function from A to B, the cardinality

When an infinite set S is countable, we denote the cardinality of S by ℵ0

We show that f is a one-to-one correspondence by showing that it is both

You might also like