Definitions on Function - الاء المآضي

Definitions on Function




Subjects to be Learned

function
domain, codomain
image
image of set
range
sum of functions
product of functions
one-to-one function (injection)
onto function (surjection)
one-to-one onto function (bijection)
inverse function
composite function
Contents

A function is something that associates each element of a set with an element of another set (which may or may not be the same as the first set). The concept of function appears quite often even in nontechnical contexts. For example, a social security number uniquely identifies the person, the income tax rate varies depending on the income, the final letter grade for a course is often determined by test and exam scores, homeworks and projects, and so on.
In all these cases to each member of a set (social security number, income, tuple of test and exam scores, homeworks and projects) some member of another set (person, tax rate, letter grade, respectively) is assigned.
As you might have noticed, a function is quite like a relation. In fact, formally, we define a function as a special type of binary relation.

Definition (function): A function, denote it by f, from a set A to a set B is a relation from A to B that satisfies
for each element a in A, there is an element b in B such that is in the relation, and
if and are in the relation, then b = c .
The set A in the above definition is called the domain of the function and B its codomain.
Thus, f is a function if it covers the domain (maps every element of the domain) and it is single valued.

The relation given by f between a and b represented by the ordered pair is denoted as f(a) = b , and b is called the image of a under f .
The set of images of the elements of a set S under a function f is called the image of the set S under f, and is denoted by f(S) , that is,
f(S) = { f(a) | a S }, where S is a subset of the domain A of f .
The image of the domain under f is called the range of f .

For properties of function in general click here for optional reading material.

Example: Let f be the function from the set of natural numbers N to N that maps each natural number x to x2 . Then the domain and codomain of this f are N, the image of, say 3, under this function is 9, and its range is the set of squares, i.e. { 0, 1, 4, 9, 16, ....} .

Definition (sum and product): Let f and g be functions from a set A to the set of real numbers R.
Then the sum and the product of f and g are defined as follows:

For all x, ( f + g )(x) = f(x) + g(x) , and
for all x, ( f*g )(x) = f(x)*g(x) ,
where f(x)*g(x) is the product of two real numbers f(x) and g(x).

Example: Let f(x) = 3x + 1 and g(x) = x2 . Then ( f + g )(x) = x2 + 3x + 1 , and ( f*g )(x) = 3x3 + x2

Definition (one-to-one): A function f is said to be one-to-one (injective) , if and only if whenever f(x) = f(y) , x = y .

Example: The function f(x) = x2 from the set of natural numbers N to N is a one-to-one function. Note that f(x) = x2 is not one-to-one if it is from the set of integers(negative as well as non-negative) to N , because for example f(1) = f(-1) = 1 .

Definition (onto): A function f from a set A to a set B is said to be onto(surjective) , if and only if for every element y of B , there is an element x in A such that f(x) = y , that is, f is onto if and only if f( A ) = B .

Example: The function f(x) = 2x from the set of natural numbers N to the set of non-negative even numbers E is an onto function. However, f(x) = 2x from the set of natural numbers N to N is not onto, because, for example, nothing in N can be mapped to 3 by this function.

Definition (bijection): A function is called a bijection , if it is onto and one-to-one.

For properties of surjection, injection and bijection click here for optional reading material.

Example: The function f(x) = 2x from the set of natural numbers N to the set of non-negative even numbers E is one-to-one and onto. Thus it is a bijection.

Every bijection has a function called the inverse function.

These concepts are illustrated in the figure below. In each figure below, the points on the left are in the domain and the ones on the right are in the codomain, and arrows show < x, f(x) > relation.





Definition (inverse): Let f be a bijection from a set A to a set B. Then the function g is called the inverse function of f, and it is denoted by f -1 , if for every element y of B, g(y) = x , where f(x) = y . Note that such an x is unique for each y because f is a bijection.

For example, the rightmost function in the above figure is a bijection and its inverse is obtained by reversing the direction of each arrow.

Example: The inverse function of f(x) = 2x from the set of natural numbers N to the set of non-negative even numbers E is f -1(x) = 1/2 x from E to N . It is also a bijection.

For properties of inverse function click here for optional reading material.

A function is a relation. Therefore one can also talk about composition of functions.

Definition (composite function): Let g be a function from a set A to a set B , and let f be a function from B to a set C . Then the composition of functions f and g , denoted by fg , is the function from A to C that satisfies
fg(x) = f( g(x) ) for all x in A .

Example: Let f(x) = x2 , and g(x) = x + 1 . Then f( g(x) ) = ( x + 1 )2 .

For properties of composite function click here for optional reading material.

الاء الماضي- 1to1correspondence

In mathematics, one-to-one correspondence refers to a situation in which the members of one set (call it A) can be evenly matched with the members of a second set (call it B). Evenly matched means that each member of A is paired with one and only one member of B, each member of B is paired with one and only one member of A, and none of the members from either set are left unpaired. The result is that every member of A is paired with exactly one member of B, and every member of B is paired with exactly one member of A. In terms of ordered pairs (a,b), where a is a member of A and b is a member of B, no two ordered pairs created by this matching process have the same first element and no two have the same second element. When this type of matching can be shown to exist, mathematicians say that "a one-to-one correspondence exists between the sets A and B." Any two sets for which a one-to-one correspondence exists have the same cardinality, that is they have the same number of members. On the other hand, a one-toone correspondence can be shown to exist between any two sets that have the same cardinality, as can easily be seen for finite sets (sets with a specific number of members). For example, given the sets A = and B = a one-toone correspondence can be established by associating the first members of each set, then the second members, then the third, and so on until each member of A is associated with a member of B. Since the two sets have the same number of members no member of either set will be left unpaired. In addition, because the two sets have the same number of members, there is no need to pair one member of A with two different members of B, or vice versa. Thus, a one-to-one correspondence exists. Another method of establishing a one-to-one correspondence between A and B is to define a one-to-one function. For example, using the same sets A and B, the function that associates each member of A with a member in B that is twice as big is such a function. This type of function is called a one-to-one function because it is reversible. In mathematical terminology, its inverse is also a function. It could just as well be defined so it maps each member of B onto a unique member of A by associating with each member of B that member of A that is half its value.

One-to-one functions are particularly useful in determining whether a one-to-one correspondence exists between infinite sets (sets with so many members that there is always another one). For example, let X be the set of all positive integers, X =, (the three dots are intended to indicate that the listing goes on forever), and let Y be the set of odd positive integers Y =. At first glance, it might be thought that the set of odd positive integers
has half as many members as the set of all positive integers. However, every odd positive integer, call it y, can be associated with a unique positive integer, call it x, by the function f(x) = y = (2x-1). On the other hand, every positive integer can be associated with a unique odd positive integer using the inverse function, namely x=(1/2)(y+1).

The function f is a one-to-one function and so a oneto-one correspondence exists between the set of positive integers and the set of odd positive integers, that is, there are just as many odd positive integers as there are positive integers all together. Carrying this notion further, the German mathematician, George Cantor, showed that it is also possible to find a one-to-one correspondence between the integers and the rational numbers (numbers that can be expressed as the ratio of two whole numbers), but that it is not possible to find a one-to-one correspondence between the integers and the real numbers (the real numbers are all of the integers plus all the decimals, both repeating and nonrepeating). In fact, he showed that there are orders of infinity, and invented the transfinite numbers to describe them.