# Functions

The type of function we will run across here most frequently is a permutation'', defined precisely later, which is roughly speaking a rule which mixes up and swaps around the elements of a finite set.

Let and be sets.

Definition 4.1.1   : A function from to is a rule which associates to each element exactly one element . We will use the following notation and terminology for this:

A function is also called a map, mapping, or transformation. We call the domain of , the codomain (or range) of , and the set

the image of f.

A wonderful tool for learning about permutations is the Rubik's cube. Erno Rubik was born during World War II in Budapest, Hungary. Far from being a mathematician, Rubik was a Professor at the Academy of Applied Arts and Design, teaching interior design. In the mid 1970's, he patented a cube-shaped mechanical puzzle that has since captured the imagination of millions of people worldwide, the Rubik's Cube. Those of you who have a Rubik's cube or similar puzzle have met permutations before. The moves are permutations!

Example 4.1.2
• One typical example for us will be when is the set of all 54 facets of the Rubik's cube and is a rule for associating to each facet some other facet determined by a Rubik's cube move. This example will be discussed in more detail later (see §4.8.2 below).
• If is any natural number, recall from §1.4.5 that we let denote the number of natural numbers less than or equal to which have no prime factor in common with . The function is Euler's phi function. We have , , , ... .

• If is any natural number, let denote the number of prime numbers less than or equal to . The function is simply called the function. We have , , , ... . Though the rough asymptotic behaviour of is known, there are still many unsolved problems regarding . For example, the following problem is still unsolved.

Question: Is there such that (i.e., ii there always a prime between any two consecutive squares)?

• Let denote the map which sends an integer to its residue . This mod function'' maps an infinite set to a finite set.

• Let denote any sequence of complex numbers. We may regard this sequence as a function by , .

The Cartesian product of two sets , is the set of pairs of elements taken from these sets:

An element of is simply a list of two things, the first one from and the second one from . This construction of a new set from two given sets is named for the French philosopher René Descartes (March 1596-February 1650) whose work, La géométrie, includes his application of algebra to geometry.

Example 4.1.3   If denotes the set of all real numbers then the Cartesian product is simply the set of all pairs or real numbers. In other words, this is the Cartesian plane we are all familiar with from high school.

More generally, we may repeat this process and take the Cartesian product of the set of real numbers with itself times (where is any integer) to get ( times). This -fold Cartesian product is denoted more conveniently by . An element of the set is simply a list of real numbers. Such a list will be called a vector or an -vector to be specific.

Sometimes it is convenient to picture'' a function as the set of its values inside the Cartesian product . The graph of a function is the subset

Not every subset of is the graph of some function from to .

Definition 4.1.4   Let and be two functions. We can compose them to get another function, the composition, denoted :

If this definition seems backwards'' to you, note we are not writing but .

Definition 4.1.5   If the image of the function is all of , i.e., if , then we call surjective (or onto", or say  is a surjection"). Equivalently, a function from to is surjective if every is the image of some under .

For example, the map defined by , for any real number , is surjective. Another example, let be the set of all 54 facets of the Rubik's cube. Let be the map which sends a facet to the facet which is diametrically opposite (for instance, the upward center facet would be mapped to the downward center facet). This function is also surjective.

Definition 4.1.6   : A function is called injective (or one-to-one" or say  is an injection") if each element belonging to the image is the image of exactly one in .

In other words, is an injection if the condition (for some ) always forces .

Question: Suppose that . Is there an injective function ? Explain.

Definition 4.1.7   A function is called a bijection if it is both injective and surjective.

Equivalently, a bijection from to is a function for which each is the image of exactly one .

Definition 4.1.8   A set is called countable if there exists a bijection to the set of integers .

Example 4.1.9 (a)   The set of all odd integers is countable since the map defined by is a bijection.

(b) Recall the set of all rational numbers is denoted by . The set of all rational numbers within the unit interval is countable since you can define as follows: , , , , , , , , and so on. (There are terms of the form , where is relatively prime to and denotes the Euler -function.).

Example 4.1.10   Let C be the cube in 3-space having vertices at the points . We shall also (to use a notation which will be used more later) denote these by dbl, dfl, dbr, ubl, dfr, ufl, ubr, ufr, resp. Let be the set of the 8 vertices of , let be the set of the edges of , and let be the set of the faces of . Let be the rotation of a point by degrees about the line passing through the points , . Note that is a function which sends the cube onto itself.

This function induces three functions

where is the function which sends to its image under (which is again in ), for . Each is a bijection. For example, and .

Suppose is a bijection. Define to be the rule which associates to the element ,

This rule defines a function . This function satisfies , for all , and , for all . In other words, the composition sends each element of to itself, and sends each element of to itself.

Definition 4.1.11   The function constructed above is called the inverse function of .

Exercise 4.1.12   Label the vertices and the facets as in Example 4.1.10 and describe and explicitly by filling out the tables

Exercise 4.1.13   Suppose that . Is there a surjective function ? Explain.

Exercise 4.1.14   Suppose that . Show that a function is surjective if and only if it is injective.

Exercise 4.1.15   If , , are functions, is ? In other words, if , , , is the value of at equal to the value of at ?

David Joyner 2007-09-03