CS311 -- Discrete Structures ----Spring 2001
Notes on showing that functions are/are not 1-1 or onto
Definition 1: A function f:A->B is 1-1 (or injective) if
for each y in B there is at most one x in A such that f(x) = y.
Definition 2: A function f:A->B is 1-1 if and only if for every
x and y in A, if f(x) = f(y) then x = y.
Definition 2 is more formal and is the one to use to justify your answers
to problems like, "Is this function 1-1? Justify your answers."
Example 1: Consider f:Z->Z such that f(x) = 2x. This function is 1-1.
Justification: Consider x and y in Z such that f(x) = f(y). This means 2x = 2y.
Dividing by 2 gives: x = y. Thus by the definition of 1-1 (definition 2) this
function is 1-1.
Example 2: Consider f:Z->Z such that f(x) = x2. This function
is not 1-1. Consider y = 4. f(-2) = f(2) = 4 (and 2 not = -2) so this is
not 1-1.
Definition 3: A function f:A->B is onto (or surjective) if
and only if for every y in B there exists at least one x in A such that f(x) = y.
Example 3: Consider the function f:R->R such that f(x) = x+1. This is
onto. To show this, consider any y in R. We need to show there exists an x in R
such that f(x) = y. This means f(x) = x+1 = y which means x = y-1. y-1 is in R
for any y in R so this function is onto.
Example 4: Consider the function: f:Z+->Z+ where f(x) = x+1.
This function is not onto. Consider y = 1. Is there an x in the domain
(Z+) such that f(x) = 1? Since f(x) = x+1; x+1 = 1 means x = 0. But
0 is not in Z+. Therefore this function is not onto.