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 :
Hence, the domain of f is .
Definition. Let X and Y be sets. A function is:
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.
Instead, I'll proceed indirectly.
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.
Copyright 2008 by Bruce Ikenaga