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.

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

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!

- 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:

*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

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

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.

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

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

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

*(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.).*

*This function induces three functions*

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.David Joyner 2007-09-03