Functions¶
Part 3 · Functions · Chapter 2 · Lecture notes, volume 3 (PDF) · Exercises, volume 3 (PDF) · Slides (PDF)
Prerequisites
- From this module, «Binary relations»: binary relations and functions as relations.
Objectives
At the end of this chapter you will be able to:
-
state the definition of function, domain, codomain and image;
-
decide whether a function is surjective, injective or bijective;
-
compute the inverse of a bijection.
1. The concept of function¶
The existence of a variable quantity implies the existence of a relation between two quantities, that is, the dependence of one quantity on another.
- In each case, this relation follows a certain law or formula.
Example 1: Laws/formulas \(\rightarrow\) functions
If a heavy object is dropped from a certain height, the distance traveled by the object varies with time \(t\) according to the formula:
where \(g \approx 9.8\) is the gravitational acceleration constant.
Hence, the time \(t\) is associated with the distance traveled \(s(t)\): \(t \mapsto s(t)\).
Example 2: Laws/formulas \(\rightarrow\) functions
If a unit capital is invested for one year at the annual rate \(i\), with interest paid monthly at a rate \(\frac{i}{12}\), we have:
-
after the first month, a capital equal to:
\[ 1+ \frac{i}{12} \cdot 1= \underbrace{1 + \frac{i}{12}}_{\alpha} \] -
after the second month, a capital equal to:
\[ \underbrace{1 + \frac{i}{12}}_{\alpha} + \frac{i}{12} \underbrace{\left( 1 + \frac{i}{12} \right)}_{\alpha} = \left(1 + \frac{i}{12}\right) \: \left(1 + \frac{i}{12}\right) = \underbrace{\left(1 + \frac{i}{12}\right)^2}_{\beta} \] -
after the third month, a capital equal to:
\[ \underbrace{\left(1 + \frac{i}{12}\right)^2}_{\beta} + \frac{i}{12} \: \underbrace{\left(1 + \frac{i}{12}\right)^2}_{\beta} = \left(1 + \frac{i}{12}\right)^2 \: \left(1 + \frac{i}{12}\right) = \left(1 + \frac{i}{12}\right)^3 \]
Repeating the argument, the capital at the end of the year therefore depends on the rate \(i\) according to the formula:
Hence, the rate \(i\) is associated with the capital \(k(i)\) at the end of the year: \(i \mapsto k(i)\)
-
In each of the previous examples, a real number (input) is associated uniquely with another real number (output). It is precisely the uniqueness of the relation that characterizes a function.
-
In general, the admissible inputs for a given relation (function) are subject to natural restrictions, related to the very nature of the relation.
Example 3: Admissible inputs
-
In the first example the “starting” real number has the meaning of time; imagining that the object is dropped at an initial time \(t = 0\), it is clear that we must restrict ourselves to times \(t \ge 0\).
-
In the second example, clearly we must have \(0 \le i \le 1\), where \(1\) corresponds to a rate of 100%.
2. Definition of function, domain, codomain and image¶
Definition 1: of domain
The set of admissible inputs for a given function is called the domain.
- The expressions independent variable (for a generic input) and dependent variable (for the output) are often used.
Example 4: Other types of relations
Let us consider the set of students of a given course.
-
If \(A\) is the set of students and \(B\) is the set of their names, the relation that associates each student with his or her name is unique (single-valued).
-
In this case neither \(A\) nor \(B\) is a set of numbers, but nevertheless a unique (single-valued) relation between these two sets is well defined.
On the other hand, the converse is not necessarily true: there could be two students with the same name.
Definition 2: of function
Given any two sets \(A\), \(B\), a function \(f\) with domain \(A\) and values in \(B\) (or also “with codomain \(B\)”) is any law that associates with each element of \(A\) one and only one element of \(B\).
-
In the language of the previous chapter, “Binary relations”, the law \(f\) is identified with the set of pairs \((x, f(x))\) with \(x \in A\): a function is thus a binary relation on \(A\) and \(B\) with the functional property, that is, each \(x \in A\) corresponds to one and only one \(y \in B\) with \((x,y)\) in the relation (this is the definition of function given in that chapter).
-
The notation:
\[\begin{equation*} f: A \rightarrow B \end{equation*}\](which reads “\(f\) defined from \(A\) to \(B\)”), indicates the domain and the codomain of the function \(f\).
-
The notation
\[\begin{equation*} f: x \mapsto f(x) \end{equation*}\](which reads “\(f\) maps \(x\) to \(f(x)\)”) indicates how the function \(f\) acts on the elements.
-
The symbol \(f(x)\) denotes the output or the value that the function \(f\) associates with \(x\), and it must not be confused with the symbol \(f\), which denotes the function itself.
Example 5: Notation for functions
For the function
of the previous example we would have:
Definition 3: of equality of two functions
Two functions \(f\) and \(g\) are equal if they have the same domain \(A\), the same codomain \(B\) and if
- A function is therefore not just a “formula”: the domain and the codomain are part of the function. Changing either of them gives a different function, even if the law is the same.
Example 6: equal functions and different functions
Consider the three functions
-
\(f \neq g\): they have the same domain and the same law, but different codomains;
-
\(f \neq h\): they have the same codomain and the same law, but different domains.
-
The notation
\[ y = f (x) \]is also used to indicate that the variable \(y\) is a function of \(x\). In this case \(y\) is the output or the value that \(f\) associates with the input \(x\).
For brevity, sometimes the value of \(f(x)\) is defined directly in terms of \(x\), as for example \(f(x)=x^2+10\).
-
In general, we can think of a function as a black box that associates with each admissible input \(x\) (input) a unique output \(f(x)\) (output):
Definition 4: of image and image of the domain
The output corresponding to \(x\) is called the image of \(x\); the set of possible outputs is called the image of the domain \(A\) under \(f\) and is denoted by the symbol \(f(A)\) or \(\Ima f\).
-
Note that in the notation \(f: A \rightarrow B\), the codomain \(B\) can be larger than the image \(f(A)\), that is, in general we have
\[ f(A) \subseteq B. \] -
If \(f\) is real-valued, we usually write \(f : A \rightarrow \mathbb{R}\) without specifying the actual image of \(f\).
Definition 5: of image of a subset of the domain
Given a function \(f: A \rightarrow B\) and a subset \(A' \subseteq A\), the image of \(A'\) under \(f\) is the set of the outputs produced by the inputs in \(A'\):
-
Taking \(A'=A\) we recover the image of the domain (also called the range of \(f\)), which can therefore be written explicitly as
\[ f(A) = \big\{ b \in B:~~ b = f(a) {\rm ~~for~some~~} a \in A \big\} \subseteq B. \]
Example 7: image of the domain and image of a subset
Consider the function
-
The image of its domain is
\[ f(\mathbb{N}) = \big\{ m \in \mathbb{N}:~~ m = 2\:n {\rm ~~for~some~~} n \in \mathbb{N} \big\}, \]that is, the set of the nonnegative even numbers. In particular \(f(\mathbb{N}) \subsetneq \mathbb{N}\): the codomain is strictly larger than the image.
-
The image of the subset \(A' = \{0,1,2,3\} \subseteq \mathbb{N}\) is instead
\[ f(A') = \{0,2,4,6\}. \]
3. Surjections, injections and bijections¶
Definition 6: of surjection (surjective function)
A function \(f\) is a surjection if the image of its domain coincides with its codomain.
-
If \(f: A \rightarrow B\) is a surjection, we also say that \(f\) maps \(A\) onto \(B\). Note that the word mapping denotes an arbitrary function: it is the preposition onto that expresses surjectivity.
-
Set representation:
Example 8: surjective and non-surjective functions
-
The function \(f(n)=\lfloor \frac{n}{2} \rfloor\) is a surjective function from \(\mathbb{N}\) to \(\mathbb{N}\), since every element of the codomain \(\mathbb{N}\) is the image of some value of the domain.
-
The function \(f(n)= 2\:n\) is not a surjective function from \(\mathbb{N}\) to \(\mathbb{N}\), since no argument of \(f\) produces \(3\) as a value.
-
The function \(f(n)= 2\:n\) is, however, a surjective function from the natural numbers to the even numbers.
Remark 1
Given two finite sets \(A\) and \(B\), and a function \(f: A \rightarrow B\), if \(f\) is surjective then \(|A| \ge |B|\).
Proof
Write \(B = \{b_1, b_2, \dots, b_m\}\), with \(m = |B|\), and for every \(i \in \{1, 2, \dots, m\}\) consider the set of the inputs whose output is \(b_i\):
-
Every \(A_i\) is nonempty: since \(f\) is surjective, every \(b_i\) is the image of at least one element of \(A\), hence \(|A_i| \ge 1\).
-
The sets \(A_1, A_2, \dots, A_m\) are pairwise disjoint: if \(a \in A_i \cap A_j\) then \(b_i = f(a) = b_j\), because \(f\) associates with \(a\) one and only one output, and therefore \(i=j\).
-
Their union is the whole of \(A\): every \(a \in A\) belongs to the set \(A_i\) with \(b_i = f(a)\).
The sets \(A_1, A_2, \dots, A_m\) thus form a partition of \(A\) and, since \(A\) is finite, we count the elements of \(A\) by summing the cardinalities of the blocks:
□
Definition 7: of injection (injective function)
A function \(f\) is an injection if distinct arguments of \(f\) produce distinct values, that is, if \(a \neq b\) implies \(f(a) \neq f(b)\).
- set representation:
Example 9
-
The function \(f(n)= 2\:n\) is an injective function from \(\mathbb{N}\) to \(\mathbb{N}\), since each even number \(b\) is the image under \(f\) of exactly one element of the domain, namely \(n=\frac{b}{2}\)
-
The function \(f(n)=\lfloor \frac{n}{2} \rfloor\) is not an injective function, since the value 1 is obtained from two arguments: \(2\) and \(3\).
- An injection is also called a one-to-one function.
Remark 2
Given two finite sets \(A\) and \(B\), and a function \(f: A \rightarrow B\), if \(f\) is injective then \(|A| \le |B|\).
Proof
Write \(A = \{a_1, a_2, \dots, a_n\}\), with \(n=|A|\), and consider the \(n\) outputs
-
These outputs are all distinct: if \(i \neq j\) then \(a_i \neq a_j\) and, since \(f\) is injective, \(f(a_i) \neq f(a_j)\).
-
Every element of \(f(A)\) appears in the list: by definition of image of the domain, every \(b \in f(A)\) has the form \(b=f(a)\) with \(a \in A\), that is, \(a = a_i\) for some \(i \in \{1, 2, \dots, n\}\).
The list \(f(a_1), f(a_2), \dots, f(a_n)\) therefore enumerates the elements of \(f(A)\) without repetitions, and hence
Finally \(f(A) \subseteq B\) and \(B\) is finite, hence \(|f(A)| \le |B|\). Putting the two relations together we obtain \(|A| \le |B|\). □
The two remarks above are stated for finite sets: the proofs count elements, and counting only makes sense for finite sets. Comparing the “sizes” of two infinite sets requires a different notion of cardinality, which is introduced in the chapter “Cardinality of infinite sets” of Part 2.
Definition 8: of bijection (bijective function or one-to-one correspondence)
A function \(f\) is a bijection if: \((i)\) it is injective and \((ii)\) it is surjective.
- set representation:
Example 10
-
The function \(f(n)= (-1)^n\:\lceil \frac{n}{2} \rceil\) is a bijection from \(\mathbb{N}\) to \(\mathbb{Z}\). The values of the function are:
\[ f(0)=0,~~~f(1)=-1,~~~f(2)=1,~~~f(3)=-2,~~~f(4)=2 \dots \]The function is injective, since no element of \(\mathbb{Z}\) is the image of more than one element of \(\mathbb{N}\). The function is surjective, since all elements of \(\mathbb{Z}\) are images of some element of \(\mathbb{N}\).
-
A bijection is also called a one-to-one correspondence, since it pairs elements of the domain with elements of the codomain.
-
A bijection from a set \(A\) to itself is also called a permutation.
4. Inverse of a bijection¶
- A bijection \(f: A \rightarrow B\) pairs every element of \(A\) with an element of \(B\) and vice versa: the pairing can therefore be followed in the opposite direction as well, from \(B\) to \(A\).
Definition 9: of inverse of a bijection
Given a bijection \(f: A \rightarrow B\), its inverse is the function
-
The definition is well posed, that is, \(f^{-1}\) really is a function, precisely because \(f\) is a bijection: given \(b \in B\),
-
the surjectivity of \(f\) guarantees that there exists at least one \(a \in A\) with \(f(a)=b\);
-
the injectivity of \(f\) guarantees that there exists at most one, because distinct inputs have distinct outputs.
Hence every \(b \in B\) corresponds to one and only one \(a \in A\), as required by the definition of function.
-
-
In other words, if \(f\) applied to the input \(a\) gives the output \(b\), then \(f^{-1}\) applied to \(b\) returns \(a\):
\[ f^{-1}\big(f(a)\big)=a,~~\forall a \in A \qquad {\rm ~~and~~} \qquad f\big(f^{-1}(b)\big)=b,~~\forall b \in B. \]
Here the inverse is defined on the whole codomain \(B\), and therefore both the injectivity and the surjectivity of \(f\) are needed. In the chapter “Inverse functions” we study instead functions of a real variable, and there a function is called invertible when it is only injective: the inverse is built on the image \(f(D)\) and not on the whole codomain, and with respect to the image surjectivity is automatic.
Example 11: inverse of a bijection
Let us go back to the bijection \(f: \mathbb{N} \rightarrow \mathbb{Z}\) of the previous example,
which pairs \(0 \leftrightarrow 0\), \(1 \leftrightarrow -1\), \(2 \leftrightarrow 1\), \(3 \leftrightarrow -2\), \(4 \leftrightarrow 2, \dots\)
Its inverse \(f^{-1}: \mathbb{Z} \rightarrow \mathbb{N}\) is:
Indeed, if \(m \ge 0\), then \(n = 2\:m\) is even and \(f(n)=(-1)^{2m} \lceil m \rceil = m\); if instead \(m<0\), then \(n=-(2\:m+1)=-2\:m-1\) is odd and nonnegative, and
where we used that \(-m-\frac{1}{2}\) has ceiling \(-m\), since \(-m\) is a positive integer.
5. In summary¶
In summary
-
A function \(f: A \to B\) associates one element of \(B\) with each element of \(A\); its image is the set of the values taken.
-
\(f\) is surjective if the image is \(B\), injective if different points have different images, bijective if both.
-
Only a bijection has an inverse, which sends each value back to its preimage.