Following our normal procedure to solve this type of exercise, we start with the definitions.
Definition: “A function f is said to be one-to-one, or an injunction, 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.” Discrete mathematics and its applications By Rosen.
Remark: “We can express that f is one-to-one using quantifiers as ∀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.” Discrete mathematics and its applications By Rosen.
Now, let’s solve the exercise.
Table of Contents
a) f(n)=n−1
To prove that the function is one-to-one, we must use the definition. In this particular case, we will show that f (a) = f (b) implies that a = b for all a and b in the domain of f.
In other words, we will show, using a direct proof, that a-1 = b-1 implies that a = b.
f(a) = a-1
f(b) = b-1
a-1=b-1, adding 1 to both sides,
a=b
Therefore, the function is one-to-one.
b) f(n)=n2 +1
Another useful proof method, studied before, is to find a counterexample.
Suppose a=1 and b=-1. It is trivial to show that f(a)=f(b), however a≠b.
f(1) = 2
f(-1) = 2
Therefore, the function is one-to-one.
c) f(n) = n3
Using the definition, let’s prove that f (a) = f (b) implies that a = b for all a and b in the domain of f.
a3 = b3, applying the cubic root on both sides, we get,
a=b
Therefore, the function is one-to-one.
d) f(n) = ⌈n/2⌉
Following the same approach as in b), let’s find a counterexample.
f(3)=⌈3/2⌉=⌈1.5⌉=2
f(4)= ⌈4/2⌉=⌈2⌉=2
Therefore, the function is not one-to-one.
Related posts: