Functions

Definition. A function f from a set X to a set Y is a subset S of the product $X \times Y$ such that if $(x,y_1),
   (x,y_2) \in S$ , then $y_1 = y_2$ .

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

"If $(x,y_1), (x,y_2) \in
   S$ , then $y_1 = y_2$ "

means that there is a unique output for each input.

$f: X \to Y$ 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:

$$(\hbox{range of f}) = \{y \in Y \mid y = f(x) \hbox{ for some } x \in X\}.$$


Example. Consider the following functions:

$$f: \real \to \real \quad\hbox{given by}\quad f(x) = x^2.$$

$$g: \real \to \real^{\ge 0} \quad\hbox{given by}\quad g(x) = x^2.$$

$$h: \real^{\ge 0} \to \real \quad\hbox{given by}\quad h(x) = x^2.$$

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


Example. Suppose I try to define $f: \real \to \real$ by

$$f(x) = (\hbox{an integer bigger than x}).$$

This does not define a function. For example, $f(2.6)$ 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,

$$f(x) = \dfrac{\sqrt{x}}{x - 2}.$$

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

In this situation, the domain is understood to be the largest subset of $\real$ for which f is defined. (This is sometimes called the natural domain of f.) In the case of $f(x) = \dfrac{\sqrt{x}}{x - 2}$ :

Hence, the domain of f is $[0,2) \cup
   (2,+\infty)$ .


Definition. Let X and Y be sets. A function $f: X \to Y$ is:

  1. Injective if for all $x_1, x_2 \in X$ , $f(x_1) = f(x_2)$ implies $x_1 = x_2$ .
  2. Surjective if for all $y \in Y$ , there is an $x \in
   X$ such that $f(x) = y$ .
  3. Bijective if it is injective and surjective.

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

$$g\left(f(s)\right) = s \quad\hbox{for all}\quad s \in S \quad\hbox{and}\quad f\left(g(t)\right) = t \quad\hbox{for all}\quad t \in T.$$

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

You've undoubtedly seen inverses of functions in other courses; for example, the inverse of $f(x) = x^3$ is $f^{-1}(x) = x^{1/3}$ . However, the functions I'm discussing may not have anything to do with numbers, and may not be defined using formulas.


Example. Define $f: \real \to \real$ by $f(x) = \dfrac{x}{x + 1}$ . To find the inverse of f (if there is one), set $y = \dfrac{x}{x + 1}$ . Swap the x's and y's, then solve for y in terms of x:

$$x = \dfrac{y}{y + 1}, \quad x(y + 1) = y, \quad xy + x = y, \quad x = y - xy, \quad x = y(1 - x), \quad y = \dfrac{x}{1 - x}.$$

Thus, $f^{-1}(x) = \dfrac{x}{1 - x}$ . To prove that this works using the definition of an inverse function, do this:

$$f^{-1}\left(f(x)\right) = f^{-1}\left(\dfrac{x}{x + 1}\right) = \dfrac{\dfrac{x}{x + 1}}{1 - \dfrac{x}{x + 1}} = \dfrac{x}{(x + 1) - x} = \dfrac{x}{1} = x,$$

$$f\left(f^{-1}(x)\right) = f\left(\dfrac{x}{1 - x}\right) = \dfrac{\dfrac{x}{1 - x}}{\dfrac{x}{1 - x} + 1} = \dfrac{x}{x + (1 - x)} = \dfrac{x}{1} = x.$$

Recall that the graphs of f and $f^{-1}$ are mirror images across the line $y = x$ :

$$\hbox{\epsfysize=2in \epsffile{functions3.eps}}$$

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 $y = x$ ". 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 $f: S \to T$ be a function. f is invertible if and only if f is both injective and surjective.

Proof. ($\rightarrow$ ) Suppose that f is both injective and surjective. I'll construct the inverse function $f^{-1}: T \to S$ .

Take $t \in T$ . Since f is surjective, there is an element $s \in S$ such that $f(s) = t$ . Moreover, s is unique: If $f(s) = t$ and $f(s') = t$ , then $f(s) = f(s')$ . But f is injective, so $s = s'$ .

Define

$$f^{-1}(t) = s.$$

I have defined a function $f^{-1}: T
   \to S$ . I must show that it is the inverse of f.

Let $s \in S$ . By definition of $f^{-1}$ , to compute $f^{-1}\left(f(s)\right)$ I must find an element $\hbox{Moe} \in S$ such that $f(\hbox{Moe}) = f(s)$ . But this is easy --- just take $\hbox{Moe} = s$ . Thus, $f^{-1}\left(f(s)\right) = s$ .

Going the other way, let $t \in T$ . By definition of $f^{-1}$ , to compute $f\left(f^{-1}(t)\right)$ I find an element $s \in S$ such that $f(s) = t$ . Then $f^{-1}(t) = s$ , so

$$f\left(f^{-1}(t)\right) = f(s) = t.$$

Therefore, $f^{-1}$ really is the inverse of f.

($\leftarrow$ ) Suppose f has an inverse $f^{-1}: T \to S$ . I must show f is injective and surjective.

To show that f is surjective, take $t
   \in T$ . Then $f\left(f^{-1}(t)\right) = t$ , so I've found an element of S --- namely $f^{-1}(t)$ --- which f maps to t. Therefore, f is surjective.

To show that f is injective, suppose $s_1, s_2 \in S$ and $f(s_1) = f(s_2)$ . Then

$$f^{-1}\left(f(s_1)\right) = f^{-1}\left(f(s_2)\right), \quad\hbox{so}\quad s_1 = s_2.$$

Therefore, f is injective.


Example. (a) $f: \real \to \real$ given by $f(x) = x^2$ is neither injective nor surjective.

It is not injective, since $f(-3) =
   9$ and $f(3) = 9$ : Different inputs may give the same output.

It is not surjective, since there is no $x \in \real$ such that $f(x) = -1$ .

(b) $f: \real \to \real^{\ge 0}$ given by $f(x) = x^2$ is not injective, but it is surjective.

It is not injective, since $f(-3) =
   9$ and $f(3) = 9$ : Different inputs may give the same output.

It is surjective, since if $y \ge 0$ , $\sqrt{y}$ is defined, and

$$f(\sqrt{y}) = (\sqrt{y})^2 = y.\quad\halmos$$

(c) $f: \real^{\ge 0} \to \real^{\ge
   0}$ given by $f(x) = x^2$ is injective and surjective.

It is injective, since if $f(x_1) =
   f(x_2)$ , then $x_1^2 = x_2^2$ . But in this case, $x_1, x_2 \ge 0$ , so $x_1 = x_2$ by taking square roots.

It is surjective, since if $y \ge
   0$ , $\sqrt{y}$ is defined, and

$$f(\sqrt{y}) = (\sqrt{y})^2 = y.\quad\halmos$$

Notice that in this example, the same "rule" --- $f(x) = x^2$ --- 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 $f: \real \to \real$ given by $f(x) =
   \dfrac{x + 1}{x}$ is injective.

Suppose $x_1, x_2 \in \real$ and $f(x_1) = f(x_2)$ . I must prove that $x_1 = x_2$ .

$f(x_1) = f(x_2)$ means that $\dfrac{x_1 + 1}{x_1} = \dfrac{x_2 + 1}{x_2}$ . Clearing denominators and doing some algebra, I get

$$x_2(x_1 + 1) = x_1(x_2 + 1), \quad x_2x_1 + x_2 = x_1x_2 + x_1, \quad x_1 = x_2.$$

Therefore, f is injective.


Example. Define $f: \real \to \real$ by $f(x) = 5x - 7$ .

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

Suppose $f(a) = f(b)$ . Then $5a
   - 7 = 5b - 7$ , so $5a = 5b$ , and hence $a = b$ . Therefore, f is injective.

Suppose $y \in \real$ . I must find x such that $f(x) = y$ . I want $5x - 7 =
   y$ . Working backwards, I find that $x = \dfrac{1}{5}(y + 7)$ . Verify that it works:

$$f\left(\dfrac{1}{5}(y + 7)\right) = 5\cdot \dfrac{1}{5}(y + 7) - 7 = (y + 7) - 7 = y.$$

This proves that f is surjective.

(b) Prove that f is injective and surjective by showing that f has an inverse $f^{-1}$ .

Define $f^{-1}(x) = \dfrac{1}{5}(x +
   7)$ . I'll prove that this is the inverse of f:

$$f(f^{-1}(x)) = f\left(\dfrac{1}{5}(x + 7)\right) = 5\cdot \dfrac{1}{5}(x + 7) - 7 = (x + 7) - 7 = x,$$

$$f^{-1}(f(x)) = f^{-1}(5x - 7) = \dfrac{1}{5}\left((5x - 7) + 7\right) = \dfrac{1}{5}\cdot 5x = x.$$

Therefore, $f^{-1}$ 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 $f: \real \to \real$ by $f(x) = x^2(x - 1)$ . f is not injective, since $f(0) = 0$ and $f(1) = 0$ .

The graph suggests that f is surjective. To say that every $y \in \real$ 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).

$$\hbox{\epsfysize=1.75in \epsffile{functions1.eps}}$$

To prove that f is surjective, take $y \in \real$ . I must find $x \in \real$ such that $f(x) =
   y$ , i.e. such that $x^2(x - 1) = y$ .

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.

$$\lim_{x\to +\infty} x^2(x - 1) = +\infty \quad\hbox{and}\quad \lim_{x\to -\infty} x^2(x - 1) = -\infty.$$

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

$$f(x_1) < y \quad\hbox{and}\quad f(x_2) > y.$$

But f is continuous --- it's a polynomial --- so by the Intermediate Value Theorem, there is a point c such that $x_1 < c < x_2$ and $f(c) = y$ . 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

$$f(x) = \cases{x + 1 & if $x < 0$ \cr x^2 & if $x \ge 0$ \cr}.$$

Prove that f is surjective, but not injective.

$$\hbox{\epsfysize=1.75in \epsffile{functions2.eps}}$$

Let $y \in \real$ . If $y <
   0$ , then $y - 1 < -1 < 0$ , so

$$f(y - 1) = (y - 1) + 1 = y.$$

If $y \ge 0$ , then $\sqrt{y}$ is defined and $\sqrt{y} \ge 0$ , so

$$f(\sqrt{y}) = (\sqrt{y})^2 = y.$$

This proves that f is surjective.

However,

$$f\left(-\dfrac{3}{4}\right) = -\dfrac{3}{4} + 1 = \dfrac{1}{4} \quad\hbox{and}\quad f\left(\dfrac{1}{2}\right) = \left(\dfrac{1}{2}\right)^2 = \dfrac{1}{4}.$$

Hence, f is not injective.


Example. Consider the function $f: \real^2 \to \real^2$ defined by

$$f(x,y) = (4x - 3y, 2x + y).$$

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

First, I'll show that f is injective. Suppose $f(x_1,y_1) = f(x_2,y_2)$ . I want to show that $(x_1,y_1) = (x_2,y_2)$ .

$f(x_1,y_1) = f(x_2,y_2)$ means

$$(4x_1 - 3y_1, 2x_1 + y_1) = (4x_2 - 3y_2, 2x_2 + y_2).$$

Equate corresponding components:

$$4x_1 - 3y_1 = 4x_2 - 3y_2, \quad 2x_1 + y_1 = 2x_2 + y_2.$$

Rewrite the equations:

$$4(x_1 - x_2) = 3(y_1 - y_2), \quad 2(x_1 - x_2) = -(y_1 - y_2).$$

The second of these equations gives $y_1 - y_2 = -2(x_1 - x_2)$ . Substitute this into the first equation:

$$4(x_1 - x_2) = 3\cdot (-2)(x_1 - x_2), \quad 4(x_1 - x_2) = -6(x_1 - x_2), \quad 10(x_1 - x_2) = 0, \quad x_1 - x_2 = 0, \quad x_1 = x_2.$$

Plugging this into $y_1 - y_2 =
   -2(x_1 - x_2)$ gives $y_1 - y_2 = 0$ , so $y_1 = y_2$ . Therefore, $(x_1,y_1) = (x_2,y_2)$ , and f is injective.

To show f is surjective, I take a point $(a,b) \in \real^2$ , the codomain. I must find $(x,y)$ such that $f(x,y) = (a,b)$ .

I want

$$(4x - 3y, 2x + y) = (a,b).$$

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

$$4x - 3y = a, \quad 2x + y = b.$$

The second equation gives $y = b -
   2x$ , so plugging this into the first equation yields

$$4x - 3(b - 2x) = a, \quad 10x - 3b = a, \quad x = 0.1a + 0.3b.$$

Plugging this back into $y = b -
   2x$ gives

$$y = b - 2(0.1a + 0.3b) = -0.2a + 0.4b.$$

Now check that this works:

$$f(0.1a + 0.3b, -0.2a + 0.4b) = \left(4(0.1a + 0.3b) - 3(-0.2a + 0.4b), 2(0.1a + 0.3b) + (-0.2a + 0.4b)\right) = (a,b).$$

Therefore, f is surjective.

(b) Show that f is injective and surjective by constructing an inverse $f^{-1}$ .

I actually did the work of constructing the inverse in showing that f was surjective: I showed that if $f(x,y) = (a,b)$ , that

$$(x,y) = (0.1a + 0.3b, -0.2a + 0.4b), \quad\hbox{or}\quad f(0.1a + 0.3b, -0.2a + 0.4b) = (a,b).$$

But the second equation implies that if $f^{-1}$ exists, it should be defined by

$$f^{-1}(a,b) = (0.1a + 0.3b, -0.2a + 0.4b).$$

Now I showed above that

$$f(f^{-1}(a,b)) = f(0.1a + 0.3b, -0.2a + 0.4b) = (a,b).$$

For the other direction,

$$f^{-1}(f(x,y)) = f^{-1}(4x - 3y, 2x + y) = (0.1(4x - 3y) + 0.3(2x + y), -0.2(4x - 3y) + 0.4(2x + y)) = (x,y).$$

This proves that $f^{-1}$ , 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 $f: \real^2 \to \real^2$ defined by

$$f(x,y) = (2x + 4y, -x - 2y).$$

Prove that f is neither injective nor surjective.

$$f(0,0) = (0,0) \quad\hbox{and}\quad f(2,-1) = (0,0).$$

Therefore, f is not injective.

To prove f is not surjective, I must find a point $(a,b) \in \real^2$ which is not an output of f. I'll show that $(1,1)$ is not an output of f. Suppose on the contrary that $f(x,y) = (1,1)$ . Then

$$(2x + 4y, -x - 2y) = (1,1).$$

This gives two equations:

$$2x + 4y = 1, \quad -x - 2y = 1.$$

Multiply the second equation by -2 to obtain $2x + 4y = -2$ . Now I have $2x +
   4y = 1$ and $2x + 4y = -2$ , so $1 = -2$ , a contradiction.

Therefore, there is no such $(x,y)$ , and f is not surjective.


Example. Let $f: \real^2 \to \real^2$ be defined by

$$f(x,y) = (e^x + y, y^3).$$

Is f injective? Is f surjective?

First, I'll show that f is injective. Suppose $f(a,b) = f(c,d)$ . I have to show that $(a,b) = (c,d)$ .

$$\eqalign{f(a,b) &= f(c,d) \cr (e^a + b, b^3) &= (e^c + d, d^3) \cr}$$

Equating the second components, I get $b^3 = d^3$ . By taking cube roots, I get $b = d$ . Equating the first components, I get $e^a + b = e^c + d$ . But $b = d$ , so subtracting $b = d$ I get $e^a = e^c$ . Now taking the log of both sides gives $a = c$ . Thus, $(a,b) =
   (c,d)$ , and f is injective.

I'll show that f is not surjective by showing that there is no input $(x,y)$ which gives $(-1,0)$ as an output. Suppose on the contrary that $f(x,y)
   = (-1,0)$ . Then

$$\eqalign{f(x,y) &= (-1,0) \cr (e^x + y, y^3) &= (-1,0) \cr}$$

Equating the second components gives $y^3 = 0$ , so $y = 0$ . Equating the first components gives $e^x + y = -1$ . But $y = 0$ , so I get $e^x = -1$ . This is impossible, since $e^x$ is always positive. Therefore, f is not surjective.


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

$$(g\circ f)(a) = g(f(a)).$$

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


Example. Define $f: \real \to \real$ by $f(x) = x^3$ and $g: \real \to
   \real$ by $g(x) = x + 1$ . Then

$$(g\circ f)(x) = g(f(x)) = g(x^3) = x^3 + 1,$$

$$(f\circ g)(x) = f(g(x)) = f(x + 1) = (x + 1)^3.\quad\halmos$$


Lemma. Let $f: X \to Y$ and $g: Y \to Z$ be invertible functions. Then $g\circ f$ is invertible, and its inverse is

$$(g\circ f)^{-1} = f^{-1}\circ g^{-1}.$$

Proof. Let $x \in X$ and let $z \in Z$ . Then

$$(f^{-1}\circ g^{-1})\circ(g\circ f)(x) = f^{-1}\left(g^{-1}\left(g\left(f(x)\right)\right)\right) = f^{-1}\left(f(x)\right) = x,$$

$$(g\circ f)\circ(f^{-1}\circ g^{-1})(z) = g\left(f\left(f^{-1}\left(g(z)\right)\right)\right) = g\left(g(z)\right) = z.$$

This proves that $(g\circ f)^{-1} =
   f^{-1}\circ g^{-1}$ .

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.


Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga