Determine whether each of these functions from Z to Z is one-to-one

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: