Intro to Probability

2. Functions, Cardinality and Distance

2.1 Functions

2.1.1 Elementary Conventions

Definition 2.1 (Function): Let A\setA and B\setB be two sets. A function f:A→Bf : \setA \to \setB is a rule which assigns to each element a∈Aa \in \setA exactly one element f(a)∈Bf(a) \in \setB.

Let f:A→Bf : \setA \to \setB be a function. We define the following sets.

Definition 2.2 (Image): The image of a function ff under C⊂A\setC \subset \setA is the set f(C)={f(a)∈B | a∈C} f(\setC) = \set{f(a) \in \setB \mid a \in \setC}
Definition 2.3 (Preimage): The preimage of a function ff under D\setD is the set f−1(D)={a∈A | f(a)∈D} f^{-1}(\setD) = \set{a \in \setA \mid f(a) \in \setD}
Example (Image): Let f:R→Rf: \R \to \R, f(x)=x2f(x) = x^2. We have that f(R)=[0,∞)f(\mathbb{R}) = [0, \infty). To see it, it is clear that f(R)⊂[0,∞)f(\R) \subset [0, \infty). For the other inclusion, take any y∈[0,∞)y \in [0,\infty). If we set x=yx = \sqrt{y}, then x2=yx^2 = y. Thus, y∈f(R)y \in f(\R) and [0,∞)⊂f(R)[0, \infty) \subset f(\R).
Example (Vector valued function): A function f:A→Rkf : \setA \to \R^k assigns to each element a∈Aa \in \setA a vector f(a)∈Rkf(a) \in \mathbb{R}^{k}. We use the notation f(a)=(f1(a),…,fk(a))f(a) = (f_1(a), \ldots, f_k(a)) for the value of ff at aa, where fi(a)f_i(a) are referred to as the coordinate functions of ff.

To indicate that an element aa is assigned to an element f(a)f(a) we often use the notation a↦f(a)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.4 (Sum, product, quotient): Let f,g:A→Rf,g : \setA \to \R be two real-valued functions.
  • f+gf + g is the function a↦(f+g)(a)=f(a)+g(a)a \mapsto (f+g)(a) = f(a) + g(a).
  • f⋅gf \cdot g is the function a↦(f⋅g)(a)=f(a)g(a)a \mapsto (f\cdot g)(a) = f(a)g(a).
  • If ∀a∈A:g(a)≠0\forall a \in \setA : g(a) \neq 0, then fg\frac{f}{g} is the function a↦fg(a)=f(a)g(a)a \mapsto \frac{f}{g}(a) = \frac{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.5 (Infimum and supremum of image): Let f:A→R‾f: \setA \to \Rext be a function and C⊂A\setC \subset \setA. For the image f(C)f(\setC) we use the notation inf⁡f(C)=inf⁡{f(c) | c∈C}=inf⁡c∈Cf(c) \inf f(\setC) = \inf \set{f(c) \mid c \in \setC} = \inf_{c \in \setC} f(c) and sup⁡f(C)=sup⁡{f(c) | c∈C}=sup⁡c∈Cf(c) \sup f(\setC) = \sup \set{f(c) \mid c \in \setC} = \sup_{c \in \setC} f(c)

2.1.2 Invertible Mappings

Definition 2.6 (Surjective, injective, bijective): Let f:A→Bf: \setA \to \setB be a function.
  • ff is called surjective, if f(A)=Bf(\setA) = \setB.
  • ff is called injective, if a≠a2  ⟹  f(a1)≠f(a2)a \neq a_2 \implies f(a_1) \neq f(a_2).
  • ff is called bijective if it is surjective and injective.
Example (Surjection): Let f:R→[0,∞)f : \R \to [0, \infty), f(x)=x2f(x) = x^2. We already know that ff is surjective. However, it is not injective, since for x1=−1x_1 = -1 and x2=1x_2 = 1, f(x1)=f(x2)=1f(x_1) = f(x_2) = 1. This shows that x↦x2x \mapsto x^2 is not bijective.
Definition 2.7 (Restriction): Let f:A→Bf: \setA \to \setB be a function and C⊂A\setC \subset \setA. The restriction of ff to C\setC is the function f∣C:C→Bf \vert_{\setC} : \setC \to \setB given by f∣C(a)=f(a)f \vert_{\setC} (a) = f(a) for any a∈Ca \in \setC.
Example (Restriction): The function f:R→[0,∞)f : \R \to [0, \infty), f(x)=x2f(x) = x^2 is not bijective. However, its restriction to [0,∞)[0, \infty) is.
Definition 2.8 (Composition): Let f:A→Bf: \setA \to \setB and g:B→Cg: \setB \to \setC be two functions. The composition g∘fg \circ f or g(f)g(f) is defined pointwise, i.e. (g∘f)(a)=g(f)(a)=g(f(a))(g \circ f)(a) = g(f)(a) = g(f(a)). Thus, g∘f:A→Cg \circ f: A \to C.
Definition 2.9 (Inverse): Let f:A→Bf : \setA \to \setB be a function. A function g:B→Ag: \setB \to \setA is called an inverse of ff if ∀a∈A:g(f(a))=a\forall a \in \setA : g(f(a)) = a and ∀b∈B:f(g(b))=b\forall b \in \setB: f(g(b)) = b. If ff 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.10 (Invertible if and only if bijection): Let f:A→Bf: \setA \to \setB be a function. Then ff is bijective if and only if it is invertible.
Example (Exponential function): Let exp⁡:R→(0,∞)\exp : \R \to (0, \infty) be the natural exponential function. One can show that exp⁡\exp is bijective where the inverse is given by the natural logarithm log⁡:(0,∞)→R\log : (0,\infty) \to \R.
Example (Trigonometric functions): The trigonometric functions sin⁡:R→[−1,1]\sin : \R \to [-1,1] and cos⁡:R→[−1,1]\cos : \R \to [-1,1] are clearly not bijective. However, sin⁡∣[−π/2,π/2]:[−π/2,π/2]→[−1,1]\sin \vert_{[-\pi/2, \pi/2]} : [-\pi/2, \pi/2] \to [-1,1] and cos⁡∣[0,π]:[0,π]→[−1,1]\cos \vert_{[0,\pi]} : [0, \pi] \to [-1,1] are bijective with inverse arcsin⁡:[−1,1]→[−π/2,π/2]\arcsin: [-1,1] \to [-\pi/2, \pi/2] and arccos⁡:[−1,1]→[0,π]\arccos : [-1, 1] \to [0, \pi], respectively. As a further example, the cotangent cot⁡:(0,π)→R\cot: (0, \pi) \to \R, cot⁡(θ)=cos⁡θsin⁡θ\cot(\theta) = \frac{\cos{\theta}}{\sin{\theta}}, is bijective with inverse arccot⁡:R→(0,π)\arccot: \R \to (0, \pi).

2.1.3 Set Operations for Image and Preimage

Let f:A→Bf: \setA \to \setB be a function.

Proposition 2.11 (Complement of preimage): Let D⊂B\setD \subset \setB. Then f−1(Dc)=f−1(D)cf^{-1}(\setD^c) = f^{-1}(\setD)^c.
Proposition 2.12 (Set operations for image and preimage): Let I\setI and J\setJ be some sets and Ai⊂A\setA_i \subset \setA, i∈Ii \in \setI, and Bj⊂B\setB_j \subset \setB, j∈Jj \in \setJ, be collections of sets from A\setA and B\setB respectively. Then
  1. f(⋃i∈IAi)=⋃i∈If(Ai)f(\bigcup_{i \in \setI} \setA_i) = \bigcup_{i \in \setI} f(\setA_i)
  2. f−1(⋃j∈JBj)=⋃j∈Jf−1(Bj)f^{-1}(\bigcup_{j \in \setJ} \setB_j) = \bigcup_{j \in \setJ} f^{-1}(\setB_j)
  3. f−1(⋂j∈JBj)=⋂j∈Jf−1(Bj)f^{-1}(\bigcap_{j \in \setJ} \setB_j) = \bigcap_{j \in \setJ} f^{-1}(\setB_j)

2.1.4 Polar Coordinate Representation

Introduce the set U={(ρ,θ)∈R2 | ρ>0,0<θ<2π}=(0,∞)×(0,2π) \setU = \set{(\rho, \theta) \in \R^2 \mid \rho > 0, 0<\theta<2\pi} = (0,\infty) \times (0,2\pi) Define the function t(ρ,θ)=(ρcos⁡(θ),ρsin⁡(θ)) t(\rho, \theta) = (\rho \cos(\theta), \rho \sin(\theta)) for (ρ,θ)∈U(\rho, \theta) \in \setU. Clearly, t(U)⊂R2t(\setU) \subset \R^2. The identification x=ρcos⁡(θ)x = \rho \cos(\theta) and y=ρsin⁡(θ)y = \rho \sin(\theta) is known as a polar coordinate representation of the point (x,y)∈R2(x,y) \in \R^2. Define V=R2∖([0,∞)×0)\setV = \R^2 \setminus ([0,\infty) \times {0}).

Proposition 2.13 (Bijection of polar coordinates): The mapping t:U→Vt: \setU \to \setV is bijective.

Notice that for any point in s∈{(x,0)⊂R2 | x≥0}s \in \set{(x,0) \subset \R^2 \mid x \geq 0} we have s∉t(U)s \notin t(\setU). In particular, t:U→R2t: \setU \to \R^2 can not be bijective.

2.1.5 Monotonic Function

Definition 2.14 (Increasing, decreasing, monotonic): Let A⊂R\setA \subset \R and f:A→Rf: \setA \to \R be a function.
  • ff is called increasing if x1≤x2  ⟹  f(x1)≤f(x2)x_1 \leq x_2 \implies f(x_1) \leq f(x_2).
  • ff is called decreasing if x1≤x2  ⟹  f(x1)≥f(x2)x_1 \leq x_2 \implies f(x_1) \geq f(x_2).
  • ff is called strictly increasing if x1<x2  ⟹  f(x1)<f(x2)x_1 < x_2 \implies f(x_1) < f(x_2).
  • ff is called strictly decreasing if x1<x2  ⟹  f(x1)>f(x2)x_1 < x_2 \implies f(x_1) > f(x_2).
Note: ff is called monotonic if it is either increasing or decreasing and strictly monotonic if it is either strictly increasing or strictly decreasing.
Proposition 2.15 (Strict monotonicity and inverse): Let A⊂R\setA \subset \R and f:A→Rf: \setA \to \R be a strictly monotonic function. Then, f:A→f(A)f: \setA \to f(\setA) is a bijection.
Note: Further, if ff is strictly increasing, resp. strictly decreasing, on A\setA, then an inverse of ff is strictly increasing, resp. strictly decreasing, on f(A)f(\setA).
Example (Strict monotonicity and inverse): Let f:[0,∞)→[0,∞)f:[0,\infty) \to [0,\infty) with f(x)=x2f(x) = x^2. We know that f([0,∞))=[0,∞)f([0,\infty)) = [0,\infty). Further, if x1<x2x_1 < x_2, then f(x1)<x12<x22=f(x2)f(x_1) < x_1^2 < x_2^2 = f(x_2). Thus, ff is strictly increasing and therefore we know that ff has an inverse f−1:[0,∞)→[0,∞)f^{-1}:[0,\infty) \to [0,\infty) which is also strictly increasing. In this case, we know that f−1(y)=yf^{-1}(y) = \sqrt{y} is the unique inverse of ff, since y=x2y = x^2 has only one non-negative solution.
Proposition 2.16 (Monotonicity and derivatives): Let a,b∈Ra,b \in \R and f:(a,b)→Rf: (a,b) \to \R be a function that is differentiable on (a,b)(a,b). That is, the derivative dfdx\dv{f}{x} of ff exists on (a,b)(a,b). Then:
  • ∀x∈(a,b):df(x)dx≥0\forall x \in (a,b) : \dv{f(x)}{x} \geq 0 implies f∣(a,b)f \vert_{(a,b)} is increasing
  • ∀x∈(a,b):df(x)dx>0\forall x \in (a,b) : \dv{f(x)}{x} > 0 implies f∣(a,b)f \vert_{(a,b)} is strictly increasing
  • ∀x∈(a,b):df(x)dx≤0\forall x \in (a,b) : \dv{f(x)}{x} \leq 0 implies f∣(a,b)f \vert_{(a,b)} is decreasing
  • ∀x∈(a,b):df(x)dx<0\forall x \in (a,b) : \dv{f(x)}{x} < 0 implies f∣(a,b)f \vert_{(a,b)} is strictly decreasing

2.2 Cardinality of Sets

2.2.1 Cardinality

Definition 2.17 (Finite and infinte sets): Let A\setA be a set. A\setA is said to be finite if it contains a finite number of elements. Otherwise, if the number of elements A\setA is not finite, A\setA is referred to as infinite.
Example (Infinite sets): The sets N\N, Z\Z, Q\Q, R\R and C\C are all infinite.
Definition 2.18 (Cardinality): Let A\setA be a set. We call #A\# \setA the cardinality of A\setA.
Definition 2.19 (Cardinality equality): Let A\setA and B\setB be two arbitrary sets. A\setA and B\setB are said to have the same cardinality, #A=#B\# \setA = \# \setB, if and only if there exists a bijection f:A→Bf: \setA \to \setB.
Example (Cardinality of finite sets): If A\setA and B\setB are finite, then #A=#B\# \setA = \# \setB precisely means that A\setA and B\setB have the same number of elements. In particular #∅=0\# \varnothing = 0.
Definition 2.20 (Cardinality order): Let A\setA and B\setB be two sets and C⊂B\setC \subset \setB. If there exists a bijection g:A→Cg: \setA \to \setC we write #A≤#B\# \setA \leq \# \setB. If there exists a bijection g:A→Cg: \setA \to \setC but no bijection f:A→Bf : \setA \to \setB, we write #A<#B\# \setA < \# \setB.
Example (Cardinality of subsets): Let A\setA and B\setB with A⊂B\setA \subset \setB, then #A≤#B\# \setA \leq \# \setB. This is because the identity map g:A→Ag: \setA \to \setA, g(a)=ag(a) = a, is a bijection.
Proposition 2.21 (Cardinality relations): We have
  • #N=#Z=#Q\#\N = \#\Z = \#\Q
  • #R>#N\#\R > \#\N
  • any interval A⊂R\setA \subset \R is such that #A>#N\#\setA > \#\N

2.2.2 Countability

Definition 2.22 (Countable and uncountable sets): Let A\setA be a set. If #A≤#N\#\setA \leq \#\N, then A\setA is countable, otherwise it is uncountable.
Proposition 2.23 (Countably infinite sets): Let A\setA be a set. If A\setA is countable but not finite, then #A=#N\#\setA = \#\N and A\setA is said to be countably infinite.

2.2.3 Cardinality of Set Operations

Proposition 2.24 (Union of countable sets): Let {Ai | i∈N}\set{\setA_i \mid i \in \N } be a collection of sets such that for any i∈Ni \in \N, Ai\setA_i is countable. Then the union ⋃i∈NAi\bigcup_{i \in \N} \setA_i is countable as well.
Proposition 2.25 (Cartesian product of countable sets): Let A1,…,An\setA_1, \ldots, \setA_n be countable sets. Then, their Cartesian product ⨂i=1nAi\bigtimes_{i=1}^n A_i is countable.

2.2.4 Heine-Borel Theorem

Theorem 2.26 (Heine-Borel theorem for intervals): Let [a,b]⊂R[a,b] \subset \R be any closed non-empty interval. Let I\setI be some countable set and assume that there exists a family of open intervals {(ai,bi)⊂R | i∈I}\set{ (a_i, b_i) \subset \R \mid i \in \setI} s.t. [a,b]⊂⋃i∈I(ai,bi)[a,b] \subset \bigcup_{i \in \setI} (a_i, b_i). Then, there exists an n∈Nn \in \N and i1,…,in∈Ii_1, \ldots, i_n \in \setI s.t. [a,b]⊂⋃j=1n(aij,bij)[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.27 (Euclidean norm): Let x∈Rk\dvec x \in \R^k, x=(x1,…,xk)\dvec x = (x_1, \ldots, x_k). The Euclidean norm of x\dvec x is given by ∥x∥=x12+…+xk2\norm{\dvec x} = \sqrt{x_1^2 + \ldots + x_k^2}.

∥x−y∥\norm{ \dvec x - \dvec y } gives the Euclidean distance between two points x,y∈Rk\dvec x, \dvec y \in \mathbb{R}^k.

Example (Euclidean norm in one dimension): If k=1k = 1, then we write ∥x∥=∣x∣\norm{x} = \abs{x}, where the function x↦∣x∣x \mapsto \abs{x} maps x∈Rx \in \mathbb{R} to its absolute value x2=∣x∣∈[0,∞)\sqrt{x^2} = \abs{x} \in [0, \infty).

For the next proposition, we use the notation 0\dvec 0 for the vector in Rk\mathbb{R}^k, k∈Nk \in \N, with all of its coordinates equal to zero.

Proposition 2.28 (Properties of the Euclidean norm): For any x,y∈Rk\dvec x, \dvec y \in \R^k, the Euclidean norm satisfies:
  1. ∥x∥≥0\norm{\dvec x} \geq 0
  2. ∥x∥=0  ⟺  x=0\norm{\dvec x} = 0 \iff \dvec x = \dvec 0
  3. ∥λx∥=λ∥x∥\norm{\lambda \dvec x} = \lambda \norm{\dvec x} for any λ∈R\lambda \in \R
  4. ∥x−y∥=∥y−x∥\norm{\dvec x - \dvec y} = \norm{\dvec y - \dvec x}
  5. ∥x+y∥≤∥x∥+∥y∥\norm{\dvec x + \dvec y} \leq \norm{\dvec x} + \norm{\dvec y}, the triangular inequality
  6. ∥x−y∥≥∣∥x∥−∥y∥∣\norm{\dvec x - \dvec y} \geq \abs{\norm{\dvec x} - \norm{\dvec y}}, the reverse triangular inequality

2.3.2 Open and Closed Balls and Boundedness

Definition 2.29 (Open ball): The open ball of radius r>0r > 0 with center y∈Rk\dvec y \in \R^k is Br ⁣(y)={x∈Rk | ∥y−x∥<r} \ball{r}{\dvec y} = \set{\dvec x \in \R^k \mid \norm{\dvec y - \dvec x} < r}
Definition 2.30 (Closed ball): The closed ball of radius r>0r > 0 with center y∈Rk\dvec y \in \R^k is B‾r ⁣(y)={x∈Rk | ∥y−x∥≤r} \cball{r}{\dvec y}= \set{\dvec x \in \R^k \mid \norm{\dvec y - \dvec x} \leq r}
Definition 2.31 (Open set): A set U⊂Rk\setU \subset \R^k is called open if for any point x∈U\dvec x \in \setU there exists an ε>0\epsilon > 0 s.t. Bε ⁣(x)⊂U\ball{\epsilon}{\dvec x} \subset \setU.
Example (Intersection of open sets is open): Let U1\setU_1, U2\setU_2 be two open subsets of Rk\R^k. By definition, for an arbitrary x∈U1∩U2x \in \setU_1 \cap \setU_2 there exist Bε1 ⁣(x)\ball{\epsilon_1}{\dvec x} and Bε2 ⁣(x)\ball{\epsilon_2}{\dvec x} s.t. Bε1 ⁣(x)⊂U1\ball{\epsilon_1}{\dvec x} \subset \setU_1 and Bε2 ⁣(x)⊂U2\ball{\epsilon_2}{\dvec x} \subset \setU_2. Set ε=min⁡{ε1,ε2}\epsilon = \min\set{\epsilon_1, \epsilon_2} and we obtain Bε ⁣(x)⊂U1∩U2\ball{\epsilon}{\dvec x} \subset \setU_1 \cap \setU_2. Hence, U1∩U2\setU_1 \cap \setU_2 is open.
Example (Open interval is an open set): Let a,b∈Ra,b \in \R, a<ba < b s.t. (a,b)(a,b) is an open interval. Let x∈(a,b)x \in (a,b). Note that ∣x−a∣=x−a\abs{x-a} = x-a and ∣x−b∣=b−x\abs{x-b} = b-x. Let ε<min⁡{x−a,b−x}\epsilon < \min\set{x-a, b-x} and take any y∈(x−ε,x+ε)=Bε ⁣(x)y \in (x-\epsilon, x+\epsilon) = \ball{\epsilon}{x}. We have ∣x−y∣<ε\abs{x-y} < \epsilon and thus x−y≤∣x−y∣<ε<x−ax-y \leq \abs{x-y} < \epsilon < x-a and y−x≤∣x−y∣<ε<b−xy-x \leq \abs{x-y} < \epsilon < b-x. Hence a<y<ba < y < b, y∈(a,b)y \in (a,b) and Bε ⁣(x)⊂(a,b)\ball{\epsilon}{x} \subset (a,b).
Example (Open ball is an open set): Let Br ⁣(y)⊂Rk\ball{r}{\dvec y} \subset \R^k and x∈Br ⁣(y)\dvec x \in \ball{r}{\dvec y} be an arbitrary point. Set δ=∥x−y∥\delta = \norm{\dvec x - \dvec y}. By definition of Br ⁣(y)\ball{r}{\dvec y} we have δ<r\delta < r. Let ε=r−δ\epsilon = r-\delta. For any z∈Bε ⁣(x)\dvec z \in \ball{\epsilon}{\dvec x} we have by the triangle inequality ∥z−y∥≤∥z−x∥+∥x−y∥<ε+δ=r\norm{ \dvec z - \dvec y } \leq \norm{ \dvec z - \dvec x } + \norm{ \dvec x - \dvec y } < \epsilon + \delta = r. Hence Bε ⁣(x)⊂Br ⁣(y)\ball{\epsilon}{\dvec x} \subset \ball{r}{\dvec y}.
Definition 2.32 (Closed set): A set V⊂Rk\setV \subset \R^k is said to be closed if Vc\setV^c is open.
Definition 2.33 (Bounded set): A set A⊂Rk\setA \subset \R^k is said to be bounded if there exists an r>0r>0 and y∈A\dvec y \in \setA s.t. A⊂Br ⁣(y)\setA \subset \ball{r}{\dvec y}.
Definition 2.34 (Bounded function): Let f:A→R‾f: \setA \to \Rext and C⊂A\setC \subset \setA. The function ff is said to be bounded on C\setC if thre exists a 0≤M<∞0 \leq M < \infty s.t. ∣f(a)∣≤M\abs{f(a)} \leq M for any a∈Ca \in \setC.

2.3.3 Open Set Characterization of Continuity

Continuous functions on Euclidean spaces are characterized in terms of open sets.

Definition 2.35 (Continuous function on Euclidean spaces): A function f:Rm→Rkf: \R^m \to \R^k is continuous if for any open set U⊂Rk\setU \subset \R^k the preimage f−1(U)f^{-1}(\setU) is open in Rm\R^m.
Example (Continuity of the identity function): Let f:R→Rf : \R \to \R, f(x)=xf(x) = x. Take any open set U⊂R\setU \subset \R. Then f−1(U)=Uf^{-1}(\setU) = \setU. Hence, f−1(U)f^{-1}(\setU) is an open subset of R\R and ff is continuous.

In terms of functions defined on subsets of Euclidean spaces Rm\R^m, continuity is characterized as follows.

Proposition 2.36 (Generalized notion of continuity): Let C⊂Rm\setC \subset \R^m, C≠∅\setC \neq \varnothing. A function f:C→Rkf : \setC \to \R^k is continuous if and only if for any open set U⊂Rk\setU \subset \R^k we have f−1(U)∈{E∩C | E open in Rm} f^{-1}(\setU) \in \set{\setE \cap \setC \mid \setE \text{ open in } \R^m}

Another characterization of continuity, known as the sequence criterion for continuous functions, will be introduced in the next chapter.