Functions — Read

Basics

Definition: Function

A function $f : A \to B$ source 29 is a mapping of each element of $A$ source 30 to an element of $B$ source 30.

We call $A$ source 32 the domain of $f$ source 32 and $B$ source 32 the codomain of $f$ source 33. The elements of $A$ source 33 are called inputs or arguments of $f$ source 34, and the element of $B$ source 34 that is paired with an argument $x$ source 34 by $f$ source 35 is called the value of $f$ source 35 for argument $x$ source 35, written $f (x)$ source 36.

The range $ran (f)$ source 38 of $f$ source 38 is the subset of the codomain consisting of the values of $f$ source 39 for some argument; $ran (f) = {f (x) : x \in A}$ source 39.

source 28

The diagram in Figure: Function from a three-element domain to a four-element codomain may help to think about functions. The ellipse on the left represents the function's domain; the ellipse on the right represents the function's codomain; and an arrow points from an argument in the domain to the corresponding value in the codomain.

Function from a three-element domain to a four-element codomain

Three domain elements each have exactly one outgoing arrow. All three arrows end at the same codomain element, leaving three codomain elements unused.

Domain: three elements.
Codomain: four elements.
Mapping: three arrows, one from each domain element; one codomain element receives all three arrows and the other three receive none.

source 50

Example: Multiplication on natural numbers

Multiplication takes pairs of natural numbers as inputs and maps them to natural numbers as outputs, so goes from $N \times N$ source 59 (the domain) to $N$ source 60 (the codomain). As it turns out, the range is also $N$ source 61, since every $n \in N$ source 61 is $n \times 1$ source 61.

source 57

Example: Multiplication and square-root mappings

Multiplication is a function because it pairs each input—each pair of natural numbers—with a single output: $\times : N^{2} \to N$ source 66. By contrast, mapping a natural number $n$ source 67 to a real $x$ source 67 such that $x^{2} = n$ source 68 is not functional, since each positive integer $n$ source 68 has two square roots: $\sqrt{n}$ source 69 and $- \sqrt{n}$ source 69. We can make it functional by only returning the positive square root: $\sqrt{} : N \to R$ source 70.

source 64

Example: Student grades and parents

The relation that pairs each student in a class with their final grade is a function—no student can get two different final grades in the same class. The relation that pairs each student in a class with their parents is not a function: students can have zero, or two, or more parents.

source 74

Example: Successor function and its range

Let $f : N \to N$ source 93 be defined such that $f (x) = x + 1$ source 93. This is a definition that specifies $f$ source 94 as a function which takes in natural numbers and outputs natural numbers. It tells us that, given a natural number $x$ source 96, $f$ source 96 will output its successor $x + 1$ source 96. In this case, the codomain $N$ source 97 is not the range of $f$ source 97, since the natural number $0$ source 98 is not the successor of any natural number. The range of $f$ source 99 is the set of all positive integers, $Z^{+}$ source 99.

source 92

Example: Extensionally equal successor functions

Let $g : N \to N$ source 103 be defined such that $g (x) = x + 2 - 1$ source 103. This tells us that $g$ source 104 is a function which takes in natural numbers and outputs natural numbers. Given a natural number $n$ source 105, $g$ source 105 will output the predecessor of the successor of the successor of $x$ source 106, i.e., $x + 1$ source 107.

source 102

Example: Function defined by even and odd cases

We can also define functions by cases. For instance, we could define $h : N \to N$ source 125 by $h (x) = {\begin{matrix} \frac{x}{2} & if x is even \\ \frac{x + 1}{2} & if x is odd. \end{matrix}$ source 126 Since every natural number is either even or odd, the output of this function will always be a natural number. Just remember that if you define a function by cases, every possible input must fall into exactly one case. In some cases, this will require a proof that the cases are exhaustive and exclusive.

source 123

Kinds of Functions

Definition: Surjective function

A function $f : A \to B$ source 30 is surjective iff $B$ source 30 is also the range of $f$ source 31, i.e., for every $y \in B$ source 31 there is at least one $x \in A$ source 32 such that $f (x) = y$ source 32, or in symbols: $(\forall y \in B) (\exists x \in A) f (x) = y .$ source 33 We call such a function a surjection from $A$ source 36 to $B$ source 36.

source 29

Definition: Injective function

A function $f : A \to B$ source 65 is injective iff for each $y \in B$ source 66 there is at most one $x \in A$ source 66 such that $f (x) = y$ source 66. We call such a function a injection from $A$ source 67 to $B$ source 67.

source 64

Example: Injective and surjective combinations

The constant function $f : N \to N$ source 77 given by $f (x) = 1$ source 77 is neither injective, nor surjective.

The identity function $f : N \to N$ source 80 given by $f (x) = x$ source 80 is both injective and surjective.

The successor function $f : N \to N$ source 83 given by $f (x) = x + 1$ source 83 is injective but not surjective.

The function $f : N \to N$ source 86 defined by: $f (x) = {\begin{matrix} \frac{x}{2} & if x is even \\ \frac{x + 1}{2} & if x is odd. \end{matrix}$ source 87 is surjective, but not injective.

source 76

Definition: Bijection

A function $f : A \to B$ source 113 is bijective iff it is both surjective and injective. We call such a function a bijection from $A$ source 115 to $B$ source 115 (or between $A$ source 115 and $B$ source 115).

source 112

Functions as Relations

Definition: Graph of a function

Let $f : A \to B$ source 24 be a function. The graph of $f$ source 25 is the relation $R_{f} \subseteq A \times B$ source 25 defined by $R_{f} = {⟨ x, y ⟩ : f (x) = y} .$ source 27

source 24

Proposition: Relations that are function graphs

Let $R \subseteq A \times B$ source 43 be such that:

If $R x y$ source 45 and $R x z$ source 45 then $y = z$ source 45; and
for every $x \in A$ source 46 there is some $y \in B$ source 46 such that $⟨ x, y ⟩ \in R$ source 46.

Then $R$ source 49 is the graph of the function $f : A \to B$ source 49 defined by $f (x) = y$ source 50 iff $R x y$ source 50.

source 42

Proof

Suppose there is a $y$ source 54 such that $R x y$ source 54. If there were another $z \neq y$ source 54 such that $R x z$ source 55, the condition on $R$ source 55 would be violated. Hence, if there is a $y$ source 56 such that $R x y$ source 56, this $y$ source 56 is unique, and so $f$ source 56 is well-defined. Obviously, $R_{f} = R$ source 57.

End of proof.

Explanation

Every function $f : A \to B$ source 61 has a graph, i.e., a relation on $A \times B$ source 61 defined by $f (x) = y$ source 62. On the other hand, every relation $R \subseteq A \times B$ source 62 with the properties given in Proposition: Relations that are function graphs is the graph of a function $f : A \to B$ source 64. Because of this close connection between functions and their graphs, we can think of a function simply as its graph. In other words, functions can be identified with certain relations, i.e., with certain sets of tuples. Note, though, that the spirit of this “identification” is as in Philosophical Reflections: it is not a claim about the metaphysics of functions, but an observation that it is convenient to treat functions as certain sets. One reason that this is so convenient, is that we can now consider performing similar operations on functions as we performed on relations (see Operations on Relations). In particular:

Definition: Function restriction and image

Let $f : A \to B$ source 79 be a function with $C \subseteq A$ source 79.

The restriction of $f$ source 81 to $C$ source 81 is the function $f ↾_{C} : C \to B$ source 82 defined by $(f ↾_{C}) (x) = f (x)$ source 83 for all $x \in C$ source 83. In other words, $f ↾_{C} = {⟨ x, y ⟩ \in R_{f} : x \in C}$ source 84.

The application of $f$ source 87 to $C$ source 87 is $f [C] = {f (x) : x \in C}$ source 87. We also call this the image of $C$ source 88 under $f$ source 89.

source 78

Inverses of Functions

Definition: Inverse function

A function $g : B \to A$ source 28 is an inverse of a function $f : A \to B$ source 28 if $f (g (y)) = y$ source 29 and $g (f (x)) = x$ source 29 for all $x \in A$ source 29 and $y \in B$ source 30.

source 27

If $f$ source 33 has an inverse $g$ source 33, we often write $f^{- 1}$ source 33 instead of $g$ source 33.

Explanation

Now we will determine when functions have inverses. A good candidate for an inverse of $f : A \to B$ source 37 is $g : B \to A$ source 37 “defined by” $g (y) = the x such that f (x) = y .$ source 39 But the scare quotes around “defined by” (and “the”) suggest that this is not a definition. At least, it will not always work, with complete generality. For, in order for this definition to specify a function, there has to be one and only one $x$ source 45 such that $f (x) = y$ source 45—the output of $g$ source 46 has to be uniquely specified. Moreover, it has to be specified for every $y \in B$ source 47. If there are $x_{1}$ source 47 and $x_{2} \in A$ source 47 with $x_{1} \neq x_{2}$ source 48 but $f (x_{1}) = f (x_{2})$ source 48, then $g (y)$ source 48 would not be uniquely specified for $y = f (x_{1}) = f (x_{2})$ source 49. And if there is no $x$ source 49 at all such that $f (x) = y$ source 50, then $g (y)$ source 50 is not specified at all. In other words, for $g$ source 51 to be defined, $f$ source 51 must be both injective and surjective.

Let's go slowly. We'll divide the question into two: Given a function $f : A \to B$ source 55, when is there a function $g : B \to A$ source 55 so that $g (f (x)) = x$ source 56? Such a $g$ source 56 “undoes” what $f$ source 56 does, and is called a left inverse of $f$ source 57. Secondly, when is there a function $h : B \to A$ source 58 so that $f (h (y)) = y$ source 58? Such an $h$ source 58 is called a right inverse of $f$ source 59— $f$ source 59 “undoes” what $h$ source 59 does.

Proposition: Injective functions have left inverses

If $f : A \to B$ source 63 is injective, then there is a left inverse $g : B \to A$ source 64 of $f$ source 64 so that $g (f (x)) = x$ source 64 for all $x \in A$ source 64.

source 62

Proof

Suppose that $f : A \to B$ source 69 is injective. Consider a $y \in B$ source 69. If $y \in ran (f)$ source 70, there is an $x \in A$ source 70 so that $f (x) = y$ source 70. Because $f$ source 71 is injective, there is only one such $x \in A$ source 71. Then we can define: $g (y) = x$ source 72, i.e., $g (y)$ source 72 is “the” $x \in A$ source 72 such that $f (x) = y$ source 72. If $y \notin ran (f)$ source 73, we can map it to any $a \in A$ source 73. So, we can pick an $a \in A$ source 74 and define $g : B \to A$ source 74 by: $g (y) = {\begin{matrix} x & if f (x) = y \\ a & if y \notin ran (f) . \end{matrix}$ source 75 It is defined for all $y \in B$ source 81, since for each such $y \in ran (f)$ source 81 there is exactly one $x \in A$ source 82 such that $f (x) = y$ source 82. By definition, if $y = f (x)$ source 83, then $g (y) = x$ source 83, i.e., $g (f (x)) = x$ source 83.

End of proof.

Exercise: A left inverse implies injectivity

Show that if $f : A \to B$ source 87 has a left inverse $g$ source 87, then $f$ source 87 is injective.

source 86

Proposition: Surjective functions have right inverses

If $f : A \to B$ source 92 is surjective, then there is a right inverse $h : B \to A$ source 93 of $f$ source 93 so that $f (h (y)) = y$ source 93 for all $y \in B$ source 94.

source 91

Proof

Suppose that $f : A \to B$ source 98 is surjective. Consider a $y \in B$ source 98. Since $f$ source 99 is surjective, there is an $x_{y} \in A$ source 99 with $f (x_{y}) = y$ source 99. Then we can define: $h (y) = x_{y}$ source 100, i.e., for each $y \in B$ source 100 we choose some $x \in A$ source 101 so that $f (x) = y$ source 101; since $f$ source 101 is surjective there is always at least one to choose from. Note: Since $f$ source 102 is surjective, for every $y \in B$ source 103 the set ${x : f (x) = y}$ source 103 is nonempty. Our definition of $h$ source 104 requires that we choose a single $x$ source 104 from each of these sets. That this is always possible is actually not obvious—the possibility of making these choices is simply assumed as an axiom. In other words, this proposition assumes the so-called Axiom of Choice, an issue we will revisit in the Choice chapter. However, in many specific cases, e.g., when $A = N$ source 109 or is finite, or when $f$ source 109 is bijective, the Axiom of Choice is not required. (In the particular case when $f$ source 110 is bijective, for each $y \in B$ source 110 the set ${x : f (x) = y}$ source 111 has exactly one element, so that there is no choice to make.) By definition, if $x = h (y)$ source 112, then $f (x) = y$ source 113, i.e., for any $y \in B$ source 113, $f (h (y)) = y$ source 113.

End of proof.

Exercise: A right inverse implies surjectivity

Show that if $f : A \to B$ source 117 has a right inverse $h$ source 117, then $f$ source 117 is surjective.

source 116

Proposition: Bijective functions have inverses

If $f : A \to B$ source 128 is bijective, there is a function $f^{- 1} : B \to A$ source 129 so that for all $x \in A$ source 129, $f^{- 1} (f (x)) = x$ source 130 and for all $y \in B$ source 130, $f (f^{- 1} (y)) = y$ source 130.

source 127

Proof

Exercise.

End of proof.

Exercise: Construct the inverse of a bijection

Prove Proposition: Bijective functions have inverses. You have to define $f^{- 1}$ source 139, show that it is a function, and show that it is an inverse of $f$ source 140, i.e., $f^{- 1} (f (x)) = x$ source 140 and $f (f^{- 1} (y)) = y$ source 140 for all $x \in A$ source 141 and $y \in B$ source 141.

source 137

Proposition: Left and right inverses coincide

Show that if $f : A \to B$ source 155 has a left inverse $g$ source 155 and a right inverse $h$ source 156, then $h = g$ source 156.

source 154

Proof

Exercise.

End of proof.

Exercise: Prove left and right inverses coincide

Prove Proposition: Left and right inverses coincide.

source 163

Proposition: Inverses are unique

Every function $f$ source 168 has at most one inverse.

source 167

Proof

Suppose $g$ source 172 and $h$ source 172 are both inverses of $f$ source 172. Then in particular $g$ source 173 is a left inverse of $f$ source 173 and $h$ source 173 is a right inverse. By Proposition: Left and right inverses coincide, $g = h$ source 174.

End of proof.

Composition of Functions

Explanation

We saw in Inverses of Functions that the inverse $f^{- 1}$ source 14 of a bijection $f$ source 14 is itself a function. Another operation on functions is composition: we can define a new function by composing two functions, $f$ source 16 and $g$ source 16, i.e., by first applying $f$ source 17 and then $g$ source 17. Of course, this is only possible if the ranges and domains match, i.e., the range of $f$ source 18 must be a subset of the domain of $g$ source 19. This operation on functions is the analogue of the operation of relative product on relations from Operations on Relations.

A diagram might help to explain the idea of composition. In Figure: Composition of f from A to B and g from B to C, we depict two functions $f : A \to B$ source 24 and $g : B \to C$ source 25 and their composition $(g \circ f)$ source 25. The function $(g \circ f) : A \to C$ source 26 pairs each element of $A$ source 26 with a element of $C$ source 27. We specify which element of $C$ source 27 a element of $A$ source 28 is paired with as follows: given an input $x \in A$ source 28, first apply the function $f$ source 29 to $x$ source 29, which will output some $f (x) = y \in B$ source 29, then apply the function $g$ source 30 to $y$ source 30, which will output some $g (f (x)) = g (y) = z \in C$ source 31.

Composition of f from A to B and g from B to C

Three elements of A map through two elements of B into two of the four elements of C. The first and third A-elements share one intermediate and final value; the second follows the other branch.

Call the three A-elements the first, second, and third A-elements; call the two B-elements B one and B two; and call the four C-elements C one through C four.
Under f, the first and third A-elements share B one as their middle value; the second A-element maps to B two.
Under g, B one maps to C one and B two maps to C two; C three and C four receive no arrow.
The dashed composite arrows therefore send the first and third A-elements to the same element of C, namely C one, while the second A-element goes to C two.

Diagram labels: $g \circ f$ source 34; $f$ source 34; $g$ source 34.

source 33

Definition: Composition

Let $f : A \to B$ source 40 and $g : B \to C$ source 40 be functions. The composition of $f$ source 41 with $g$ source 41 is $g \circ f : A \to C$ source 41, where $(g \circ f) (x) = g (f (x))$ source 42.

source 39

Example: Composing successor and doubling

Consider the functions $f (x) = x + 1$ source 46, and $g (x) = 2 x$ source 46. Since $(g \circ f) (x) = g (f (x))$ source 47, for each input $x$ source 47 you must first take its successor, then multiply the result by two. So their composition is given by $(g \circ f) (x) = 2 (x + 1)$ source 49.

source 45

Exercise: Composition preserves injectivity

Show that if $f : A \to B$ source 53 and $g : B \to C$ source 53 are both injective, then $g \circ f : A \to C$ source 54 is injective.

source 52

Exercise: Composition preserves surjectivity

Show that if $f : A \to B$ source 58 and $g : B \to C$ source 58 are both surjective, then $g \circ f : A \to C$ source 59 is surjective.

source 57

Exercise: Graph of a composite function

Suppose $f : A \to B$ source 63 and $g : B \to C$ source 63. Show that the graph of $g \circ f$ source 64 is $R_{f} ∣ R_{g}$ source 64.

source 62

Partial Functions

Definition: Partial function and its domain

A partial function $f : A ⇀ B$ source 21 is a mapping which assigns to every element of $A$ source 22 at most one element of $B$ source 22. If $f$ source 23 assigns an element of $B$ source 23 to $x \in A$ source 23, we say $f (x)$ source 23 is defined, and otherwise undefined. If $f (x)$ source 24 is defined, we write $f (x) ↓$ source 25, otherwise $f (x) ↑$ source 25. The domain of a partial function $f$ source 26 is the subset of $A$ source 26 where it is defined, i.e., $dom (f) = {x \in A : f (x) ↓}$ source 27.

source 20

Example: Total functions as partial functions

Every function $f : A \to B$ source 31 is also a partial function. Partial functions that are defined everywhere on $A$ source 32—i.e., what we so far have simply called a function—are also called total functions.

source 30

Example: Reciprocal as a partial function

The partial function $f : R ⇀ R$ source 38 given by $f (x) = 1 / x$ source 38 is undefined for $x = 0$ source 39, and defined everywhere else.

source 37

Exercise: Partial inverse of a partial function

Given $f : A ⇀ B$ source 43, define the partial function $g : B ⇀ A$ source 43 by: for any $y \in B$ source 44, if there is a unique $x \in A$ source 44 such that $f (x) = y$ source 45, then $g (y) = x$ source 45; otherwise $g (y) ↑$ source 45. Show that if $f$ source 46 is injective, then $g (f (x)) = x$ source 46 for all $x \in dom (f)$ source 46, and $f (g (y)) = y$ source 47 for all $y \in ran (f)$ source 47.

source 42

Definition: Graph of a partial function

Let $f : A ⇀ B$ source 51 be a partial function. The graph of $f$ source 51 is the relation $R_{f} \subseteq A \times B$ source 52 defined by $R_{f} = {⟨ x, y ⟩ : f (x) = y} .$ source 53

source 50

Proposition: Single-valued relations define partial functions

Suppose $R \subseteq A \times B$ source 59 has the property that whenever $R x y$ source 59 and $R x y'$ source 60 then $y = y'$ source 60. Then $R$ source 60 is the graph of the partial function $f : A ⇀ B$ source 61 defined by: if there is a $y$ source 61 such that $R x y$ source 62, then $f (x) = y$ source 62, otherwise $f (x) ↑$ source 62. If $R$ source 62 is also serial, i.e., for each $x \in A$ source 63 there is a $y \in B$ source 63 such that $R x y$ source 64, then $f$ source 64 is total.

source 58

Proof

Suppose there is a $y$ source 68 such that $R x y$ source 68. If there were another $y' \neq y$ source 68 such that $R x y'$ source 69, the condition on $R$ source 69 would be violated. Hence, if there is a $y$ source 70 such that $R x y$ source 70, that $y$ source 70 is unique, and so $f$ source 71 is well-defined. Obviously, $R_{f} = R$ source 71 and $f$ source 71 is total if $R$ source 72 is serial.

End of proof.

Reading preferences

How to use Read

Basics

Definition: Function

Example: Multiplication on natural numbers

Example: Multiplication and square-root mappings

Example: Student grades and parents

Example: Successor function and its range

Example: Extensionally equal successor functions

Example: Function defined by even and odd cases

Kinds of Functions

Definition: Surjective function

Definition: Injective function

Example: Injective and surjective combinations

Definition: Bijection

Functions as Relations

Definition: Graph of a function

Proposition: Relations that are function graphs

Proof

Definition: Function restriction and image

Inverses of Functions

Definition: Inverse function

Proposition: Injective functions have left inverses

Proof

Exercise: A left inverse implies injectivity

Proposition: Surjective functions have right inverses

Proof

Exercise: A right inverse implies surjectivity

Proposition: Bijective functions have inverses

Proof

Exercise: Construct the inverse of a bijection

Proposition: Left and right inverses coincide

Proof

Exercise: Prove left and right inverses coincide

Proposition: Inverses are unique

Proof

Composition of Functions

Definition: Composition

Example: Composing successor and doubling

Exercise: Composition preserves injectivity

Exercise: Composition preserves surjectivity

Exercise: Graph of a composite function

Partial Functions

Definition: Partial function and its domain

Example: Total functions as partial functions

Example: Reciprocal as a partial function

Exercise: Partial inverse of a partial function

Definition: Graph of a partial function

Proposition: Single-valued relations define partial functions

Proof