2.1 Functions
2.1.1 Elementary Conventions
Definition 2.1 (Function): Let $A$ and $B$ be two sets. A function $f : A \to B$ is a rule which assigns to each element $a \in A$ exactly one element $f(a) \in B$.
Definition 2.2 (Image, Preimage)
: Let $f : A \to B$ be a function. We define the following sets:
Image: The image of $f$ under $C \subset A$ is the set $f(C) = \qty{f(a) : a \in C}$.
Preimage: The preimage of $f$ under $D$ is the set $f^{-1}(D) = \qty{a : f(a) \in D}$.
Example (Image): Let $f: \R \to \R$, $f(x) = x^2$. We have that $f(\mathbb{R}) = [0, \infty)$. To see it, it is clear that $f(\R) \subset [0, \infty)$. For the other inclusion, take any $y \in [0,\infty)$. If we set $x = \sqrt{y}$, then $x^2 = y$. Thus, $y \in f(\R)$ and $[0, \infty) \subset f(\R)$.
Example (Vector valued function): A function $f : A \to \R^k$ assigns to each element $a \in A$ a vector $f(a) \in \mathbb{R}^{k}$. We use the notation $f(a) = \qty(f_1(a), \ldots, f_k(a))$ for the value of $f$ at $a$, where $f_i(a)$, $i = 1, \ldots, k$, are referred to as the coordinate functions of $f$.
To indicate that an element $a$ is assigned to an element $f(a)$ we often use the notation $a \mapsto f(a)$ to define the assignment, i.e. the function. The following definition clarifies some notation for algebraic operations on functions.
Definition 2.3 (Sum, product, quotient)
: Let $f,g : A \to \R$ be two real-valued functions.
Sum: $f + g$ is the function $a \mapsto (f+g)(a) = f(a) + g(a)$.
Product: $fg$ is the function $a \mapsto (fg)(a) = f(a)g(a)$.
Quotient: If $g(a) \neq 0$ $\forall a \in A$, then $f/g$ is the function $a \mapsto (f/g)(a) = f(a) / g(a)$.
If a function takes values in the extended real numbers, we rely on the following definition regarding the infimum and supremum of the image.
Definition 2.4 (Infimum and supremum of image): Let $f: A \to \overline{\R}$ be a function and $E \subset A$. For the image $f(E)$ we use the notation $\inf f(E) = \inf \qty{f(e) : e \in E} = \inf_{e \in E} f(e)$ and $\sup f(E) = \sup \qty{f(e) : e \in E} = \sup_{e \in E} f(e)$.
2.1.2 Invertible Mappings
Definition 2.5 (Surjective, injective, bijective)
: Let $f: A \to B$ be a function.
Surjective: $f$ is called surjective, if $f(A) = B$.
Injective: $f$ is called injective, if $a \neq a_2 \implies f(a_1) \neq f(a_2)$.
Bijective: $f$ is called bijective if it is surjective and injective.
Example (Surjection): Let $f : \R \to [0, \infty)$, $f(x) = x^2$. We already know that $f$ is surjective. However, it is not injective, since for $x_1 = -1$ and $x_2 = 1$, $f(x_1) = f(x_2) = 1$. This shows that $x \mapsto x^2$ is not bijective.
Definition 2.6 (Restriction): Let $f: A \to B$ be a function and $E \subset A$. The restriction of $f$ to $E$ is the function $f \vert_E : E \to B$ given by $f \vert_E (a) = f(a)$ for any $a \in E$.
Example (Restriction): The function $f : \R \to [0, \infty)$, $f(x) = x^2$ is not bijective. However, its restriction to $[0, \infty)$ is.
Definition 2.7 (Composition): Let $f: A \to B$ and $g: B \to C$ be two functions. The composition $g \circ f$ or $g(f)$ is defined pointwise, i.e. $(g \circ f)(a) = g(f)(a) = g(f(a))$. Thus, $g \circ f: A \to C$.
Definition 2.8 (Inverse): Let $f : A \to B$ be a function. A function $g: B \to A$ is called an inverse of $f$ if $g(f(a)) = a$ $\forall a \in A$ and $f(g(b)) = b$ $\forall b \in B$. If $f$ has an inverse it is called invertible.
A characterization of invertible functions is given by the notions of surjectivity and injectivity. This is summarized in the following result.
Proposition 2.9 (Invertible iff bijection): Let $f: A \to B$ be a function. Then $f$ is bijective if and only if it is invertible.
Example (Exponential function): Let $f(x) = e^x$, $x \in \R$, i.e. $f$ is the natural exponential function. One can show that $f : \R \to (0, \infty)$ is bijective where the inverse is given by the natural logarithm $\log(y) : (0,\infty) \to \R$.
Example (Trigonometric functions): The trigonometric functions $\sin : \R \to \R$ and $\cos : \R \to \R$ are clearly not bijective. However, $\sin \vert_{[-\pi/2, \pi/2]} : [-\pi/2, \pi/2] \to [-1,1]$ and $\cos \vert_{[0,\pi]} : [0, \pi] \to [-1,1]$ are bijective with inverse $\arcsin: [-1,1] \to [-\pi/2, \pi/2]$ and $\arccos : [-1, 1] \to [0, \pi]$, respectively. As a further example, the cotangent $\cot: (0, \pi) \to \R$, $\cot(\theta) = \frac{\cos(\theta)}{\sin(\theta)}$, is bijective with inverse $\arccot: \R \to (0, \pi)$.
2.1.3 Set Operations for Image and Preimage
Proposition 2.10 (Set operations for image and preimage)
: Let $f: A \to B$ be a function. Let $B_{*} \subset B$. Then $f^{-1}(B_{*}^c) = f^{-1}(B_{*})^c$.
Let $I$ and $J$ be some sets and $A_i \subset A$, $i \in I$, and $B_j \subset B$, $j \in J$, be collections of sets from $A$ and $B$ respectively. Then
- $f(\bigcup_{i \in I} A_i) = \bigcup_{i \in I} f(A_i)$
- $f^{-1}(\bigcup_{j \in J} B_j) = \bigcup_{j \in J} f^{-1}(B_j)$
- $f^{-1}(\bigcap_{j \in J} B_j) = \bigcap_{j \in J} f^{-1}(B_j)$
2.1.4 Polar Coordinate Representation
Introduce the set $U = \qty{(\rho, \theta) \in \R^2 : \rho > 0, 0<\theta<2\pi} = (0,\infty) \times (0,2\pi)$. Define the function $T(\rho, \theta) = (\rho \cos(\theta), \rho \sin(\theta))$, $(\rho, \theta) \in U$. Clearly, $T(U) \subset \R^2$. The identification $x = \rho \cos(\theta)$ and $y = \rho \sin(\theta)$ is known as a polar coordinate representation of the point $(x,y) \in \R^2$. Define $V = R^2 \ ([0,\infty) \times {0})$.
Proposition 2.11 (Bijection of polar coordinates): The mapping $T: U \to V$ is bijective.
Notice that for any point $s = (x,0)$, $x \geq 0$, $s \notin T(U)$. In particular, $T: U \to \R^2$ can not be bijective.
2.1.5 Monotonic Function
Definition 2.12 (Increasing, decreasing, monotonic)
: Let $f: I \to \R$, $I \subset \R$ be a function.
Increasing, decreasing: $f$ is called increasing, resp. decreasing, if $x_1 \leq x_2 \implies f(x_1) \leq f(x_2)$, resp. $x_1 \leq x_2 \implies f(x_1) \geq f(x_2)$.
Strictly increasing, decreasing: $f$ is called strictly increasing, resp. strictly decreasing, if $x_1 < x_2 \implies f(x_1) < f(x_2)$, resp. $x_1 < x_2 \implies f(x_1) > f(x_2)$.
Monotonic: $f$ is called monotonic, resp. strictly monotonic, if it is either increasing or decreasing, resp. strictly increasing or decreasing.
Proposition 2.13 (Strict monotonicity and inverse): Let $f : I \to \R$, $I \subset \R$ be a strictly monotonic function. Then, $f: I \to f(I)$ is a bijection. Further, if $f$ is strictly increasing, resp. strictly decreasing, on $I$, then an inverse of $f$ is strictly increasing, resp. strictly decreasing, on $f(I)$.
Example (Strict monotonicity and inverse): Let $f:[0,\infty) \to [0,\infty)$, $f(x) = x^2$. We know that $f([0,\infty)) = [0,\infty)$. Further, if $x_1 < x_2$, then $f(x_1) < x_1^2 < x_2^2 = f(x_2)$. Thus, $f$ is strictly increasing and therefore we know that $f$ has an inverse $f^{-1}:[0,\infty) \to [0,\infty)$ which is also strictly increasing. In this case, we know that $f^{-1}(y) = \sqrt{y}$ is the unique inverse of $f$, since $y = x^2$ has only one non-negative solution.
Proposition 2.14 (Monotonicity and derivatives)
: Let $a,b \in \R$ and $f: (a,b) \to \R$ be a function that is differentiable on $(a,b)$. That is, the derivative $f'$ of $f$ exists on $(a,b)$. Then:
- $f'(x) \geq 0$ $\forall x \in (a,b)$ implies $f \vert_{(a,b)}$ is increasing
- $f'(x) \gt 0$ $\forall x \in (a,b)$ implies $f \vert_{(a,b)}$ is strictly increasing
- $f'(x) \leq 0$ $\forall x \in (a,b)$ implies $f \vert_{(a,b)}$ is decreasing
- $f'(x) \lt 0$ $\forall x \in (a,b)$ implies $f \vert_{(a,b)}$ is strictly decreasing
2.2 Cardinality of Sets
2.2.1 Cardinality
Definition 2.15 (Finite and infinte sets): Let $A$ be a set. $A$ is said to be finite if it contains a finite number of elements. Otherwise, if the number of elements $A$ is not finite, $A$ is referred to as infinite.
Example (Infinite sets): The sets $\N$, $\Z$, $\Q$, $\R$ and $\C$ are all infinite.
Definition 2.16 (Cardinality equality): Let $A$ and $B$ be two arbitrary sets. $A$ and $B$ are said to have the same cardinality, $\# A = \# B$, if and only if there exists a bijection $f: A \to B$.
Example (Cardinality of finite sets): If $A$ and $B$ are finite, then $\# A = \# B$ precisely means that $A$ and $B$ have the same number of elements. In particular $\# \varnothing = 0$.
Definition 2.17 (Cardinality order): Let $A$ and $B$ be two sets and $C \subset B$. If there exists a bijection $g: A \to C$ we write $\# A \leq \# B$. If there exists a bijection $g: A \to C$ but no bijection $f : A \to B$, we write $\# A < \# B$.
Example (Cardinality of subsets): Let $A$ and $B$ with $A \subset B$, then $\# A \leq \# B$. This is because the identity map $g: A \to A$, $g(a) = a$, is a bijection.
Proposition 2.18 (Cardinality relations): We have that $\#\N = \#\Z = \#\Q$, $\#\R > \#\N$ and that any interval $I \subset \R$ is s.t. $\# I > \#\N$.
2.2.2 Countability
Definition 2.19 (Countable and uncountable sets): Let $A$ be a set. If $\#A \leq \#\N$, then $A$ is countable, otherwise it is uncountable.
Proposition 2.20 (Countably infinite sets): Let $A$ be a set. If $A$ is countable but not finite, then $\# A = \#\N$ and $A$ is said to be countably infinite.
2.2.3 Cardinality of Set Operations
Proposition 2.21 (Union of countable sets): Let $\qty{A_i : i \in \N }$ be a collection of sets s.t. for any $i \in \N$, $A_i$ is countable. Then the union $\bigcup_{i \in \N} A_i$ is countable as well.
Proposition 2.22 (Cartesian product of countable sets): Let $A_i$, $i = 1, \ldots, n$, be countable sets. Then, their Cartesian product $\bigtimes_{i=1}^n A_i$ is countable.
2.2.4 Heine-Borel Theorem
Theorem 2.23 (Heine-Borel theorem for intervals): Let $[a,b]$, $a,b \in R$, $a < b$, be any closed interval. Let $I$ be some countable set and assume that there exists a family of open intervals $(a_i, b_i)$, $a_i, b_i \in \R$, $i \in I$, s.t. $[a,b] \subset \bigcup_{i \in I} (a_i, b_i)$. Then, there exists $N \in \N$ and $i_1, \ldots, i_N \in I$ s.t. $[a,b] \subset \bigcup_{j=1}^N (a_{i_j}, b_{i_j})$.
The latter result shows that any closed interval on the real line which is covered by a countable collection of open intervals can be covered by a finite sub-collection.
2.3 Open and Closed Sets in Real Coordinate Spaces
2.3.1 Euclidean Norm
Definition 2.24 (Euclidean norm): Let $\vb{x} \in \R^k$, $\vb{x} = (x_1, \ldots, x_k)$. The Euclidean norm of $\vb{x}$ is given by $\norm{\vb{x}} = \sqrt{x_1^2 + \ldots + x_k^2}$.
$\norm{ \vb{x} - \vb{y} }$ gives the Euclidean distance between two points $\vb{x}, \vb{y} \in \mathbb{R}^k$.
Example (Euclidean norm in one dimension): If $k = 1$, then we write $\norm{x} = \abs{x}$, where the function $x \mapsto \abs{x}$ maps $x \in \mathbb{R}$ to its absolute value $\sqrt{x^2} = \abs{x} \in [0, \infty)$.
For the next proposition, we use the notation $\vb{0}$ for the vector in $\mathbb{R}^k$, $k \in \N$, with all of its coordinates equal to zero.
Proposition 2.25 (Properties of the Euclidean norm)
: For any $\vb{x}, \vb{y} \in \R^k$, the Euclidean norm satisfies:
- $\norm{\vb{x}} \geq 0$
- $\norm{\vb{x}} = 0 \iff \vb{x} = \vb{0}$
- $\norm{\lambda \vb{x}} = \lambda \norm{\vb{x}}$ for any $\lambda \in \R$
- $\norm{\vb{x} - \vb{y}} = \norm{\vb{y} - \vb{x}}$
- $\norm{\vb{x} + \vb{y}} \leq \norm{\vb{x}} + \norm{\vb{y}}$, the triangular inequality
- $\norm{\vb{x} - \vb{y}} \geq \abs{\norm{\vb{x}} - \norm{\vb{y}}}$, the reverse triangular inequality
2.3.2 Open and Closed Balls and Boundedness
Definition 2.26 (Open and closed balls): The open, resp. closed, ball of radius $r > 0$ with center $\vb{y} \in \R^k$ is $B_r(\vb{y}) = \qty{\vb{x} \in \R^k : \norm{\vb{y} - \vb{x}} < r}$, resp. $B_r[\vb{y}] = \qty{\vb{x} \in \R^k : \norm{\vb{y} - \vb{x}} \leq r}$.
Definition 2.27 (Open set): A set $U \subset \R^k$ is called open if for any point $\vb{x} \in U$ there exists an $\epsilon > 0$ s.t. $B_{\epsilon}(\vb{x}) \subset U$.
Example (Intersection of open sets is open): Let $U_1$, $U_2$ be two open subsets of $\R^k$. By definition, for an arbitrary $x \in U_1 \cap U_2$ there exist $B_{\epsilon_1}(\vb{x})$ and $B_{\epsilon_2}(\vb{x})$ s.t. $B_{\epsilon_1}(\vb{x}) \subset U_1$ and $B_{\epsilon_2}(\vb{x})$. Set $\epsilon = \min\qty{\epsilon_1, \epsilon_2}$ and we obtain $B_{\epsilon}(\vb{x}) \subset U_1 \cap U_2$. Hence, $U_1 \cap U_2$ is open.
Example (Open interval is an open set): Let $a,b \in \R$, $a < b$ s.t. $(a,b)$ is an open interval. Let $x \in (a,b)$. Note that $\abs{x-a} = x-a$ and $\abs{x-b} = b-x$. Let $\epsilon < \min\qty{x-a, b-x}$ and take any $y \in (x-\epsilon, x+\epsilon) = B_{\epsilon}(x)$. We have $\abs{x-y} < \epsilon$ and thus $x-y \leq \abs{x-y} < \epsilon < x-a$ and $y-x \leq \abs{x-y} < \epsilon < b-x$. Hence $a < y < b$ and $y \in (a,b)$ and $B_{\epsilon}(x) \subset (a,b)$.
Example (Open ball is an open set): Let $B_r(\vb{y}) \subset \R^k$ and $\vb{x} \in B_r(\vb{y})$ be an arbitrary point. Set $\delta = \norm{\vb{x} - \vb{y}}$. By definition of $B_r(\vb{y})$ we have $\delta < r$. Let $\epsilon = r-\delta$. For any $\vb{z} \in B_{\epsilon}(\vb{x})$ we have by the triangle inequality $\norm{ \vb{z} - \vb{y} } \leq \norm{ \vb{z} - \vb{x} } + \norm{ \vb{x} - \vb{y} } < \epsilon + \delta = r$. Hence $B_{\epsilon}(\vb{x}) \subset B_r(\vb{y})$.
Definition 2.28 (Closed set): A set $V \subset \R^k$ is said to be closed if $V^c$ is open.
Definition 2.29 (Bounded set): A set $A \subset \R^k$ is said to be bounded if there exists an $r>0$ and $\vb{y} \in A$ s.t. $A \subset B_r[\vb{y}]$.
Definition 2.30 (Bounded function): Let $f: A \to \overline{\R}$ and $E \subset A$. THe function $f$ is said to be bounded on $E$ if thre exists a $0 \leq M < \infty$ s.t. $\abs{f(a)} \leq M$ for any $a \in E$.
2.3.3 Open Set Characterization of Continuity
Continuous functions on Euclidean spaces are characterized in terms of open sets.
Definition 2.31 (Continuous function on Euclidean spaces): A function $f: \R^m \to \R^k$ is continuous if for any open set $U \subset \R^k$ the preimage $f^{-1}(U)$ is open in $\R^m$.
Example (Continuity of the identity function): Let $f : \R \to \R$, $f(x) = x$. Take any open set $U \subset \R$. Then $f^{-1}(U) = U$. Hence, $f^{-1}(U)$ is an open subset of $\R$ and $f$ is continuous.
In terms of functions defined on subsets of Euclidean spaces $\R^m$, continuity is characterized as follows.
Proposition 2.32 (Generalized notion of continuity): Let $E \subset \R^m$, $E \neq \varnothing$. A function $f : E \to \R^k$ is continuous iff for any open set $U \subset \R^k$ we have $f^{-1}(U) \in \qty{G \cap E : G \text{ open in } \R^m}$.
Another characterization of continuity, known as the sequence criterion for continuous functions, will be introduced in the next chapter.