Intro to Probability 2025-02-24

2. Functions, Cardinality and Distance

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

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

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

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

g(f(a)) = a

\forall a \in A

and

f(g(b)) = b

\forall b \in B

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'

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

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.