Functions

Definition. A function f from a set X to a set Y is a subset S of the product such that if , then .

Instead of writing , you usually write . Thus, when an ordered pair is in S, x is the input to f and y is the corresponding output. The stipulation that

"If , then "

means that there is a unique output for each input.

means that f is a function from X to Y. X is called the domain, and Y is called the codomain. The range of f is the set of all outputs of the function:

Example. Consider the following functions:

These are different functions; they're defined by the same rule, but they have different domains or codomains.

Example. Suppose I try to define by

This does not define a function. For example, could be 3, since 3 is an integer bigger than 2.6. But it could also be 4, or 67, or 101, or .... This "rule" does not produce a {\it unique} output for each input.

Mathematicians say that such a function --- or such an attempted function --- is not well-defined.

Example. ( The "natural domain" of a function) In basic algebra and calculus, functions are often given by rules, without mention of a domain and codomain; for example,

In this context, the codomain is usually understood to be . What about the domain?

In this situation, the domain is understood to be the largest subset of for which f is defined. (This is sometimes called the natural domain of f.) In the case of :

• I must have in order for to be defined.
• I must have in order to avoid division by zero.

Hence, the domain of f is .

Definition. Let X and Y be sets. A function is:

1. Injective if for all , implies .
2. Surjective if for all , there is an such that .
3. Bijective if it is injective and surjective.

Definition. Let S and T be sets, and let be a function from S to T. A function is called the inverse of f if

Not all functions have inverses; if the inverse of f exists, it's denoted . (Despite the crummy notation, " " {\it does not mean " ".)}

You've undoubtedly seen inverses of functions in other courses; for example, the inverse of is . However, the functions I'm discussing may not have anything to do with numbers, and may not be defined using formulas.

Example. Define by . To find the inverse of f (if there is one), set . Swap the x's and y's, then solve for y in terms of x:

Thus, . To prove that this works using the definition of an inverse function, do this:

Recall that the graphs of f and are mirror images across the line :

I'm mentioning this to connect this discussion to things you've already learned. However, you should not make the mistake of equating this special case with the definition. The inverse of a function is not defined by "swapping x's and y's and solving" or "reflecting the graph about ". A function might not involve numbers or formulas, and a function might not have a graph. The inverse of a function is what the definition says it is --- nothing more or less.

The next lemma is very important, and I'll often use it in showing that a given function is bijective.

Lemma. Let S and T be sets, and let be a function. f is invertible if and only if f is both injective and surjective.

Proof. ( ) Suppose that f is both injective and surjective. I'll construct the inverse function .

Take . Since f is surjective, there is an element such that . Moreover, s is unique: If and , then . But f is injective, so .

Define

I have defined a function . I must show that it is the inverse of f.

Let . By definition of , to compute I must find an element such that . But this is easy --- just take . Thus, .

Going the other way, let . By definition of , to compute I find an element such that . Then , so

Therefore, really is the inverse of f.

( ) Suppose f has an inverse . I must show f is injective and surjective.

To show that f is surjective, take . Then , so I've found an element of S --- namely --- which f maps to t. Therefore, f is surjective.

To show that f is injective, suppose and . Then

Therefore, f is injective.

Example. (a) given by is neither injective nor surjective.

It is not injective, since and : Different inputs may give the same output.

It is not surjective, since there is no such that .

(b) given by is not injective, but it is surjective.

It is not injective, since and : Different inputs may give the same output.

It is surjective, since if , is defined, and

(c) given by is injective and surjective.

It is injective, since if , then . But in this case, , so by taking square roots.

It is surjective, since if , is defined, and

Notice that in this example, the same "rule" --- --- was used, but whether the function was injective or surjective changed. {\it The domain and codomain are part of the definition of a function.}

Example. Prove that given by is injective.

Suppose and . I must prove that .

means that . Clearing denominators and doing some algebra, I get

Therefore, f is injective.

Example. Define by .

(a) Prove directly that f is injective and surjective.

Suppose . Then , so , and hence . Therefore, f is injective.

Suppose . I must find x such that . I want . Working backwards, I find that . Verify that it works:

This proves that f is surjective.

(b) Prove that f is injective and surjective by showing that f has an inverse .

Define . I'll prove that this is the inverse of f:

Therefore, is the inverse of f. Since f is invertible, it's injective and surjective.

Example. In some cases, it may be difficult to prove that a function is surjective by a direct argument.

Define by . f is not injective, since and .

The graph suggests that f is surjective. To say that every is an output of f means graphically that every horizontal line crosses the graph at least once (whereas injectivity means that every horizontal line crosses that graph at most once).

To prove that f is surjective, take . I must find such that , i.e. such that .

The problem is that finding x in terms of y involves solving a cubic equation. This is possible, but it's easy to change the example to produce a function where solving algebraically is impossible in principle.

It follows from the definition of these infinite limits that there are numbers and such that

But f is continuous --- it's a polynomial --- so by the Intermediate Value Theorem, there is a point c such that and . This proves that f is surjective.

Note, however, that I haven't found c; I've merely shown that such a value c must exist.

Example. Define

Prove that f is surjective, but not injective.

Let . If , then , so

If , then is defined and , so

This proves that f is surjective.

However,

Hence, f is not injective.

Example. Consider the function defined by

(a) Show that f is injective and surjective directly, using the definitions.

First, I'll show that f is injective. Suppose . I want to show that .

means

Equate corresponding components:

Rewrite the equations:

The second of these equations gives . Substitute this into the first equation:

Plugging this into gives , so . Therefore, , and f is injective.

To show f is surjective, I take a point , the codomain. I must find such that .

I want

I'll work backwards from this equation. Equating corresponding components gives

The second equation gives , so plugging this into the first equation yields

Plugging this back into gives

Now check that this works:

Therefore, f is surjective.

(b) Show that f is injective and surjective by constructing an inverse .

I actually did the work of constructing the inverse in showing that f was surjective: I showed that if , that

But the second equation implies that if exists, it should be defined by

Now I showed above that

For the other direction,

This proves that , as defined above, really is the inverse of f. Hence, f is injective and surjective.

Remark. In linear algebra, you learn more efficient ways to show that functions like the one above are bijective.

Example. Consider the function defined by

Prove that f is neither injective nor surjective.

Therefore, f is not injective.

To prove f is not surjective, I must find a point which is not an output of f. I'll show that is not an output of f. Suppose on the contrary that . Then

This gives two equations:

Multiply the second equation by -2 to obtain . Now I have and , so , a contradiction.

Therefore, there is no such , and f is not surjective.

Example. Let be defined by

Is f injective? Is f surjective?

First, I'll show that f is injective. Suppose . I have to show that .

Equating the second components, I get . By taking cube roots, I get . Equating the first components, I get . But , so subtracting I get . Now taking the log of both sides gives . Thus, , and f is injective.

I'll show that f is not surjective by showing that there is no input which gives as an output. Suppose on the contrary that . Then

Equating the second components gives , so . Equating the first components gives . But , so I get . This is impossible, since is always positive. Therefore, f is not surjective.

Definition. Let A, B, and C be sets, and let and be functions. The composite of f and g is the function defined by

I actually used composites earlier --- for example, in defining the inverse of a function. In my opinion, the notation " " looks a lot like multiplication, so (at least when elements are involved) I prefer to write " " instead. However, the composite notation is used often enough that you should be familiar with it.

Example. Define by and by . Then

Lemma. Let and be invertible functions. Then is invertible, and its inverse is

Proof. Let and let . Then

This proves that .

Corollary. The composite of bijective functions is bijective.

Proof. I showed earlier that a function is bijective if and only if it has an inverse, so the corollary follows from the lemma.