Maggie Johnson                                                                                                            Handout #32

CS103A                     

Functions

 

Key topics:

 

            * Introduction and Definitions

            * Types of Functions

            * The Growth of Functions

                                                                                                                                                           

 

As used in ordinary language, the word function indicates dependence of a varying quantity on another.  If I tell you that your grade in this class is a function of the number of thousands of dollars you pay me, you interpret this to mean that I have a rule for translating a number in thousands into a letter grade.  More generally, suppose two sets of objects are given: set A and set B;  and suppose that with each element of A there is associated a particular element of B.  These three things: the two sets and the correspondence between elements comprise a function.

 

A function f is a mapping from a set D to a set T with the property that for each element d in D, f maps d to a unique element of T, denoted f(d).  Here  D is called the domain of f, and T is called the target or co-domain.  We write f: D -> T. We  also say that f(d) is the image of d under f, and we call the set of all images the range R of f.

 

A mapping might fail to be a function if it is not defined at every element of the domain, or if it maps an element of the domain to two or more elements in the range:

 

To define a function f, we must specify its domain D and a rule for how it operates. 

 

Example 1

 

            Let B be the set of all binary numbers, or equivalently all finite strings of 0's and 1's.  Let N 

be the set of natural numbers expressed in decimal notation.  f, g, h, j are the following functions:

 

                        f(s) = decimal equivalent of s

                        g(s) = number of bits in s

                        h(s) = number of ones in s

                        j(s)  = ones bit of s

 

            If s = 110010 then f(s) = 50, g(s) = 6, h(s) = 3, j(s) = 0.  The range of f, g, h, is N but the         range of j is {0,1}.  Here are two mappings from B to N that are not functions:

 

                        k(s) = the fifth bit in s counting from the left

 

                        l(s) =    1 if s ends with 1

                                    2 if s ends with 0

                                    4 if  s ends with 00

 

                Why do these mappings fail? _________________________________________

 

                Which of the following are functions from N to B where r is an integer?

 

                                m(r) = the number of digits in r                                          ________________

                               

                                n(r) =      0  if r  is even                                                         ________________

                                                1 if r is odd

 

                                o(r) = the string of r ones                                                    ________________

 

                                p(r) =      0 if 2 divides r                                                       ________________

                                                1 if 3 divides r

                                                1 if neither 2 nor 3 divide r

 

Types of Functions

 

A function is said to be onto if its range is equal to its target (as in figure a above, (not b);  and functions f, g, h are onto; j is not if the mapping is from B -> N). Another way of saying this is if for every element (b) of the codomain, there is at least one element (a) in the domain such that f(a) = b.

Two functions are equal if they have the same domain and f(d) = g(d) for every d in D. A function is  one-to-one if it maps distinct elements of the domain to distinct elements of the range.  A formal definition of one-to-one is: if f(x1) = f(x2) then x1 = x2. 

 

a is one-to-one and onto; b is one-to-one but not onto; c is not one-to-one but is onto; d is not a function.  Other terms you may have seen for one-to-one is injective; onto is surjective;  a function that is both is bijective.  Function f above is one-to-one; g is not (g(101) = g(111)); h is not.  Functions f, g, and h are all onto.

 

 

 

Example 2

 

            Define f: Z -> Z with the rule that f(x) = x2  for all x ? Z.  Is f(x) one-to-one?

 

            We must show that for all integers, if f(x1) = f(x2) then x1 = x2. 

            f(x1) = x12; f(x2) = x22 so  we need to see if for all integers:

            if x12 = x22 then x1 = x2.  But this is not true when x1 = -1 and x2 = 1,

            so f(x) is not one-to-one.

 

Consider two functions: successor as applied to integers, and a sqr function.  If we take the output of the successor function and use it as input to the sqr function, the two functions are operating together.  They take as input an integer n, add one to it and then square n+1.  We call this a composition of two functions.

 

Let f be a function from X -> Y and g be a function from Y' -> Z where Y  is a subset of Y'.  A new function  (g o f) is defined by the following rule:  For all x ??X, (g o f)(x) = g(f(x)).  This is called the composition of f and g (f comes first because it acts on x first).

 

Notice in the successor-sqr example that composition is not commutative.

 

Example 3

 

Let g be the function from the set {a,b,c} to itself such that g(a) = b; g(b) = c and g(c) = a.  Let f be a function from the set {a,b,c} to the set {1,2,3} such that f(a) = 3; f(b) = 2; f(c) = 1.  What is the composition of f and g; g and f?

 

            (f o g) is defined by (f o g)(a) = f(g(a)) = f(b) = 2;  (f o g)(b) = f(g(b)) = f(c) = 1; (f o g)(c) =     f(g(c)) = f(a) = 3.

 

            (g o f) is not defined because the co-domain of f is not a subset of the domain of g.

 

 

Example 4

 

            f(x) = 2x + 3; g(x) = 3x +  2.  What is the composition of f and g; g and f?

 

            (f o g)(x) = (f(g(x)) = f(3x+2) = 2(3x+2) + 3 = 6x + 7

            (g o f)(x) = (g(f(x)) = g(2x+3) = 3(2x+3) + 2 = 6x + 11

 

 

The Growth of Functions

 

Now that we have all the definitions out of the way, our main concern is with certain functions, and how these functions behave when we increase the x in f(x).  The functions we are interested in:

 

 

f(x) = 1

f(x) = log x

f(x) = x

f(x) = x log x

f(x) = x2

f(x) = 2x

f(x) = x!

 

Recall that logarithms are defined as follows: If b is a positive real number not equal to 1 and y is a positive real number, then the logarithm to the base b of y (logb y) is the unique real number x such that bx = y.  In other words, logb y = the exponent to which b must be raised in order to obtain y. 

 

Bibliography

 

For additional information on functions, consult Discrete Math textbooks or Calculus textbooks.  The following are excellent references:

 

S. Epp, Discrete Mathematics with Applications, Belmont, CA: Wadsworth, 1990.

 

R. McEliece, R. Ash, C. Ash, Introduction to Discrete Mathematics, New York: Random House,     1989.

 

K. Rosen, Discrete Mathematics and its Applications 4th Ed., New York: McGraw-Hill, 1999.

 

* A reference that specifically addresses the growth of functions:

 

G. Hardy, E. Wright, Introduction to the Theory of Numbers, London: Oxford University Press, 1938.

 

 

Historical Notes

 

The term "function" and the form (x, f(x)) is attributed to Leibniz who used it to refer to several of his mathematical formulas, but the concept of a function was first presented by René Descartes (1596-1650) in his Geometry of 1637.  In this book, he presents the concept of defining an equation in terms of one variable (i.e., as a function of...), and how to graph equations in the Cartesian plane.  The formal definition of a function (as a mapping from domain to target) was first formulated for sets of numbers by Lejeune Dirichlet (1805-1859) in 1837.