« previous section   next section »


3.2 Properties of functions

Definition 3.2.1

We  say that function f : X → Y is a one-to-one mapping, shortly f : X → 1-1Y, if distinct arguments have distinct values, i.e.

if x1 ≠ x2, to f(x1) ≠ f(x2) for arbitrary x1, x2 ∈ X.

We can reword the same property differently in a form of the following condition: for any x1, x2 ∈ X,

if f(x1) = f(x2), then x1= x2 for every x1, x2 ∈ X.

The one-to-one functions are also called injections. The exmple of such function is presented in Fig 3.1.3. Contrary to this, the functions shown in Fig 3.1.4 are not  one-to-one mappings, e.g. the function 3.1.4(b)  takes the same value for all arguments from the interval (0,1].

Please note, that to prove a given function to be an injection we must show that for any pair of elements  x1, x2 of the function's domain, f(x1) has different values than f(x2). However, the proof that a function is not a one-to-one mapping, requires finding just one pair (so called contrexample), which does not fulfill the condition mentioned in the definition.

Question 3.2.1 Which of the functions shown in the example 3.1.1 are injections?

Definition 3.2.2

We say that a function f : X → Y is a mapping onto Y if and only if each element of the set Y is the value of the function, i.e.

for any y ∈ Y there is x ∈ X, such that f(x) = y.

In other words, the function is onto, if the set of its values is the set Y, Im(f) = Y. Such a function we call a surjection and we denote it shortly as f : X → ontoY.

Example 3.2.1

  1. Function g defined by a formulae g(n) = (-1)n for n ∈ N takes as the values he numbers -1, 1 exclusively. Indeed, the value of the function for every even number and zero is 1, and for very odd number is -1. It is therefore the mapping onto the set {-1, 1}, g : N → onto{-1,1}.
    Function g is not an injection, because for example: g(2) = g(4).

  2. Function f: N → P, defined for an arbitrary natural nubmer n as f(n) = 2n, is an example of a one-to-one mapping. If n and m are different natural numbers, than 2n ≠ 2m. Furthermore, this is a mapping onto the set P of even numbers, because for any even number k there is a natural number, that is k/2, such that f(k/2) = k.

  3. Function f : N × N → N, which associates an ordered pair of natural numbers to a natural number, according to the formulae f(n,m) = n + (n+m+1)(n+m)/2, is a one-to-one function onto the set of natural numbers N.

  4. Let r be a relation in R, r = {(x,y) ∈ R × R : y = 2x/(x2 +1)}. This relation is a total function because, each real value a is associated to exactly one real number 2a/(a2 +1). This is not a mapping onto the set of real numbers, since there is no real number which would be associated to a number 4. (If for some x, 2x/(x2 +1) = 4, then we would have 4 x2 + 4 -2x = 0, which is not possible because D=(-2)(-2) - 4*4*4 < 0). To examine the codomain of the function r let us observe that,

-(x2 + 1) ≤ 2x and 2x ≤ x2 + 1

of what we conclude that -1 ≤ 2x/(x2 +1) ≤ 1. Because 2x/(x2 +1) is a continuous funcion, then it takes all the values of the interval [-1, 1].

Remark. Function f: X → Y, which is at the same time  one-to-one mapping  and  onto  Y is called  bijection.


Example 3.2.2

Each natural number can be presented as a sequence of digits in the decimal system,  or octagonal, or binary system. For example  12 = (1100) 2 = (14) 8 = (110) 3. Function bin : N → {0,1}*, which associates each natural number to its representation in a binary system, is a bijection:

  1. Every finite zero-one sequence denotes some natural number, in the following way
                                   (ak, ak-1, ..., a0) 2 = (ak2k + ak-12 k-1+...+ a0 20).

  2. Every natural number n has its unique binary representation. It can be obtained by multiple divisions of the number n by 2, and noting each reminder of the division as a following number of the sought sequnce.  The algorithm below defines the function bin:

begin
   if n=0 then bin(n) := 0 else
      i := 0; while n >0 do ai := n mod 2; n := n div 2; i := i+1 od;
      bin(n) := (ai-1,ai-2,...,a0);
   fi
end

Further down this course we will be interested in some functions that are one-to-one correspondence of a set X onto itself. For example the sequence  p = (3,4,5,6,0,1,2) is a function defined in the set {0,1,2,...,6}, whose values are derrived from the formulae p(i) = (i+3) mod 7 and who fulfill the set {0,1,2,...,6}. Functions of this type are called permutations.

Question 3.2.2 Is  f : N\{0} → N defined by the formulae f(n) = n * ⎣ lg n ⎦ for  n>0 a mapping onto the set of natural numbers ( ⎣ lg n ⎦ denotes the integer part of the 2-based logarithm of n)?

Problem 3.2.1

Design an algorithm which would find a triangular representation of any natural number. 


« previous section   next section »