Intro to Probability 2025-02-24

2. Functions, Cardinality and Distance

2.1 Functions

2.1.1 Elementary Conventions

Definition 2.1 (Function): Let

𝐴

and

𝐵

be two sets. A function

𝑓 : 𝐴 \to 𝐵

is a rule which assigns to each element

𝑎 \in 𝐴

exactly one element

𝑓 (𝑎) \in 𝐵

Definition 2.2 (Image, Preimage): Let

𝑓 : 𝐴 \to 𝐵

be a function. We define the following sets:

Image: The image of $𝑓$ under $𝐶 \subset 𝐴$ is the set $𝑓 (𝐶) = {𝑓 (𝑎) : 𝑎 \in 𝐶}$ .

Preimage: The preimage of $𝑓$ under $𝐷$ is the set $𝑓 - 1 (𝐷) = {𝑎 : 𝑓 (𝑎) \in 𝐷}$ .

Example (Image): Let

𝑓 : ℝ \to ℝ

𝑓 (𝑥) = 𝑥 2

. We have that

𝑓 (ℝ) = [0, \infty)

. To see it, it is clear that

𝑓 (ℝ) \subset [0, \infty)

. For the other inclusion, take any

𝑦 \in [0, \infty)

. If we set

𝑥 = \sqrt 𝑦

, then

𝑥 2 = 𝑦

. Thus,

𝑦 \in 𝑓 (ℝ)

and

[0, \infty) \subset 𝑓 (ℝ)

Example (Vector valued function): A function

𝑓 : 𝐴 \to ℝ 𝑘

assigns to each element

𝑎 \in 𝐴

a vector

𝑓 (𝑎) \in ℝ 𝑘

. We use the notation

𝑓 (𝑎) = (𝑓 1 (𝑎), \dots, 𝑓 𝑘 (𝑎))

for the value of

𝑓

𝑎

, where

𝑓 𝑖 (𝑎)

𝑖 = 1, \dots, 𝑘

, are referred to as the coordinate functions of

𝑓

To indicate that an element $𝑎$ is assigned to an element $𝑓 (𝑎)$ we often use the notation $𝑎 \mapsto 𝑓 (𝑎)$ 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

𝑓, 𝑔 : 𝐴 \to ℝ

be two real-valued functions.

Sum: $𝑓 + 𝑔$ is the function $𝑎 \mapsto (𝑓 + 𝑔) (𝑎) = 𝑓 (𝑎) + 𝑔 (𝑎)$ .

Product: $𝑓 𝑔$ is the function $𝑎 \mapsto (𝑓 𝑔) (𝑎) = 𝑓 (𝑎) 𝑔 (𝑎)$ .

Quotient: If $𝑔 (𝑎) \neq 0$ $\forall 𝑎 \in 𝐴$ , then $𝑓 / 𝑔$ is the function $𝑎 \mapsto (𝑓 / 𝑔) (𝑎) = 𝑓 (𝑎) / 𝑔 (𝑎)$ .

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

𝑓 : 𝐴 \to - ℝ

be a function and

𝐸 \subset 𝐴

. For the image

𝑓 (𝐸)

we use the notation

i n f 𝑓 (𝐸) = i n f {𝑓 (𝑒) : 𝑒 \in 𝐸} = i n f 𝑒 \in 𝐸 𝑓 (𝑒)

and

s u p 𝑓 (𝐸) = s u p {𝑓 (𝑒) : 𝑒 \in 𝐸} = s u p 𝑒 \in 𝐸 𝑓 (𝑒)

2.1.2 Invertible Mappings

Definition 2.5 (Surjective, injective, bijective): Let

𝑓 : 𝐴 \to 𝐵

be a function.

Surjective: $𝑓$ is called surjective, if $𝑓 (𝐴) = 𝐵$ .

Injective: $𝑓$ is called injective, if $𝑎 \neq 𝑎 2 ⟹ 𝑓 (𝑎 1) \neq 𝑓 (𝑎 2)$ .

Bijective: $𝑓$ is called bijective if it is surjective and injective.

Example (Surjection): Let

𝑓 : ℝ \to [0, \infty)

𝑓 (𝑥) = 𝑥 2

. We already know that

𝑓

is surjective. However, it is not injective, since for

𝑥 1 = - 1

and

𝑥 2 = 1

𝑓 (𝑥 1) = 𝑓 (𝑥 2) = 1

. This shows that

𝑥 \mapsto 𝑥 2

is not bijective.

Definition 2.6 (Restriction): Let

𝑓 : 𝐴 \to 𝐵

be a function and

𝐸 \subset 𝐴

. The restriction of

𝑓

𝐸

is the function

𝑓 | 𝐸 : 𝐸 \to 𝐵

given by

𝑓 | 𝐸 (𝑎) = 𝑓 (𝑎)

for any

𝑎 \in 𝐸

Example (Restriction): The function

𝑓 : ℝ \to [0, \infty)

𝑓 (𝑥) = 𝑥 2

is not bijective. However, its restriction to

[0, \infty)

is.

Definition 2.7 (Composition): Let

𝑓 : 𝐴 \to 𝐵

and

𝑔 : 𝐵 \to 𝐶

be two functions. The composition

𝑔 \circ 𝑓

𝑔 (𝑓)

is defined pointwise, i.e.

(𝑔 \circ 𝑓) (𝑎) = 𝑔 (𝑓) (𝑎) = 𝑔 (𝑓 (𝑎))

. Thus,

𝑔 \circ 𝑓 : 𝐴 \to 𝐶

Definition 2.8 (Inverse): Let

𝑓 : 𝐴 \to 𝐵

be a function. A function

𝑔 : 𝐵 \to 𝐴

is called an inverse of

𝑓

𝑔 (𝑓 (𝑎)) = 𝑎

\forall 𝑎 \in 𝐴

and

𝑓 (𝑔 (𝑏)) = 𝑏

\forall 𝑏 \in 𝐵

. If

𝑓

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

𝑓 : 𝐴 \to 𝐵

be a function. Then

𝑓

is bijective if and only if it is invertible.

Example (Exponential function): Let

𝑓 (𝑥) = 𝑒 𝑥

𝑥 \in ℝ

, i.e.

𝑓

is the natural exponential function. One can show that

𝑓 : ℝ \to (0, \infty)

is bijective where the inverse is given by the natural logarithm

l o g (𝑦) : (0, \infty) \to ℝ

Example (Trigonometric functions): The trigonometric functions

s i n : ℝ \to ℝ

and

c o s : ℝ \to ℝ

are clearly not bijective. However,

s i n | [- 𝜋 / 2, 𝜋 / 2] : [- 𝜋 / 2, 𝜋 / 2] \to [- 1, 1]

and

c o s | [0, 𝜋] : [0, 𝜋] \to [- 1, 1]

are bijective with inverse

a r c s i n : [- 1, 1] \to [- 𝜋 / 2, 𝜋 / 2]

and

a r c c o s : [- 1, 1] \to [0, 𝜋]

, respectively. As a further example, the cotangent

c o t : (0, 𝜋) \to ℝ

c o t (𝜃) = c o s (𝜃) s i n (𝜃)

, is bijective with inverse

a r c c o t : ℝ \to (0, 𝜋)

2.1.3 Set Operations for Image and Preimage

Proposition 2.10 (Set operations for image and preimage): Let

𝑓 : 𝐴 \to 𝐵

be a function. Let

𝐵 * \subset 𝐵

. Then

𝑓 - 1 (𝐵 𝑐 *) = 𝑓 - 1 (𝐵 *) 𝑐

Let $𝐼$ and $𝐽$ be some sets and $𝐴 𝑖 \subset 𝐴$ , $𝑖 \in 𝐼$ , and $𝐵 𝑗 \subset 𝐵$ , $𝑗 \in 𝐽$ , be collections of sets from $𝐴$ and $𝐵$ respectively. Then

$𝑓 (⋃ 𝑖 \in 𝐼 𝐴 𝑖) = ⋃ 𝑖 \in 𝐼 𝑓 (𝐴 𝑖)$
$𝑓 - 1 (⋃ 𝑗 \in 𝐽 𝐵 𝑗) = ⋃ 𝑗 \in 𝐽 𝑓 - 1 (𝐵 𝑗)$
$𝑓 - 1 (⋂ 𝑗 \in 𝐽 𝐵 𝑗) = ⋂ 𝑗 \in 𝐽 𝑓 - 1 (𝐵 𝑗)$

2.1.4 Polar Coordinate Representation

Introduce the set $𝑈 = {(𝜌, 𝜃) \in ℝ 2 : 𝜌 > 0, 0 < 𝜃 < 2 𝜋} = (0, \infty) \times (0, 2 𝜋)$ . Define the function $𝑇 (𝜌, 𝜃) = (𝜌 c o s (𝜃), 𝜌 s i n (𝜃))$ , $(𝜌, 𝜃) \in 𝑈$ . Clearly, $𝑇 (𝑈) \subset ℝ 2$ . The identification $𝑥 = 𝜌 c o s (𝜃)$ and $𝑦 = 𝜌 s i n (𝜃)$ is known as a polar coordinate representation of the point $(𝑥, 𝑦) \in ℝ 2$ . Define $𝑉 = 𝑅 2 ([0, \infty) \times 0)$ .

Proposition 2.11 (Bijection of polar coordinates): The mapping

𝑇 : 𝑈 \to 𝑉

is bijective.

Notice that for any point $𝑠 = (𝑥, 0)$ , $𝑥 \geq 0$ , $𝑠 \notin 𝑇 (𝑈)$ . In particular, $𝑇 : 𝑈 \to ℝ 2$ can not be bijective.

2.1.5 Monotonic Function

Definition 2.12 (Increasing, decreasing, monotonic): Let

𝑓 : 𝐼 \to ℝ

𝐼 \subset ℝ

be a function.

Increasing, decreasing: $𝑓$ is called increasing, resp. decreasing, if $𝑥 1 \leq 𝑥 2 ⟹ 𝑓 (𝑥 1) \leq 𝑓 (𝑥 2)$ , resp. $𝑥 1 \leq 𝑥 2 ⟹ 𝑓 (𝑥 1) \geq 𝑓 (𝑥 2)$ .

Strictly increasing, decreasing: $𝑓$ is called strictly increasing, resp. strictly decreasing, if $𝑥 1 < 𝑥 2 ⟹ 𝑓 (𝑥 1) < 𝑓 (𝑥 2)$ , resp. $𝑥 1 < 𝑥 2 ⟹ 𝑓 (𝑥 1) > 𝑓 (𝑥 2)$ .

Monotonic: $𝑓$ 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

𝑓 : 𝐼 \to ℝ

𝐼 \subset ℝ

be a strictly monotonic function. Then,

𝑓 : 𝐼 \to 𝑓 (𝐼)

is a bijection. Further, if

𝑓

is strictly increasing, resp. strictly decreasing, on

𝐼

, then an inverse of

𝑓

is strictly increasing, resp. strictly decreasing, on

𝑓 (𝐼)

Example (Strict monotonicity and inverse): Let

𝑓 : [0, \infty) \to [0, \infty)

𝑓 (𝑥) = 𝑥 2

. We know that

𝑓 ([0, \infty)) = [0, \infty)

. Further, if

𝑥 1 < 𝑥 2

, then

𝑓 (𝑥 1) < 𝑥 21 < 𝑥 22 = 𝑓 (𝑥 2)

. Thus,

𝑓

is strictly increasing and therefore we know that

𝑓

has an inverse

𝑓 - 1 : [0, \infty) \to [0, \infty)

which is also strictly increasing. In this case, we know that

𝑓 - 1 (𝑦) = \sqrt 𝑦

is the unique inverse of

𝑓

, since

𝑦 = 𝑥 2

has only one non-negative solution.

Proposition 2.14 (Monotonicity and derivatives): Let

𝑎, 𝑏 \in ℝ

and

𝑓 : (𝑎, 𝑏) \to ℝ

be a function that is differentiable on

(𝑎, 𝑏)

. That is, the derivative

𝑓'

𝑓

exists on

(𝑎, 𝑏)

. Then:

$𝑓' (𝑥) \geq 0$ $\forall 𝑥 \in (𝑎, 𝑏)$ implies $𝑓 | (𝑎, 𝑏)$ is increasing
$𝑓' (𝑥) > 0$ $\forall 𝑥 \in (𝑎, 𝑏)$ implies $𝑓 | (𝑎, 𝑏)$ is strictly increasing
$𝑓' (𝑥) \leq 0$ $\forall 𝑥 \in (𝑎, 𝑏)$ implies $𝑓 | (𝑎, 𝑏)$ is decreasing
$𝑓' (𝑥) < 0$ $\forall 𝑥 \in (𝑎, 𝑏)$ implies $𝑓 | (𝑎, 𝑏)$ is strictly decreasing

2.2 Cardinality of Sets

2.2.1 Cardinality

Definition 2.15 (Finite and infinte sets): Let

𝐴

be a set.

𝐴

is said to be finite if it contains a finite number of elements. Otherwise, if the number of elements

𝐴

is not finite,

𝐴

is referred to as infinite.

Example (Infinite sets): The sets

ℕ

ℤ

ℚ

ℝ

and

ℂ

are all infinite.

Definition 2.16 (Cardinality equality): Let

𝐴

and

𝐵

be two arbitrary sets.

𝐴

and

𝐵

are said to have the same cardinality,

# 𝐴 = # 𝐵

, if and only if there exists a bijection

𝑓 : 𝐴 \to 𝐵

Example (Cardinality of finite sets): If

𝐴

and

𝐵

are finite, then

# 𝐴 = # 𝐵

precisely means that

𝐴

and

𝐵

have the same number of elements. In particular

# \emptyset = 0

Definition 2.17 (Cardinality order): Let

𝐴

and

𝐵

be two sets and

𝐶 \subset 𝐵

. If there exists a bijection

𝑔 : 𝐴 \to 𝐶

we write

# 𝐴 \leq # 𝐵

. If there exists a bijection

𝑔 : 𝐴 \to 𝐶

but no bijection

𝑓 : 𝐴 \to 𝐵

, we write

# 𝐴 < # 𝐵

Example (Cardinality of subsets): Let

𝐴

and

𝐵

with

𝐴 \subset 𝐵

, then

# 𝐴 \leq # 𝐵

. This is because the identity map

𝑔 : 𝐴 \to 𝐴

𝑔 (𝑎) = 𝑎

, is a bijection.

Proposition 2.18 (Cardinality relations): We have that

# ℕ = # ℤ = # ℚ

# ℝ > # ℕ

and that any interval

𝐼 \subset ℝ

is s.t.

# 𝐼 > # ℕ

2.2.2 Countability

Definition 2.19 (Countable and uncountable sets): Let

𝐴

be a set. If

# 𝐴 \leq # ℕ

, then

𝐴

is countable, otherwise it is uncountable.

Proposition 2.20 (Countably infinite sets): Let

𝐴

be a set. If

𝐴

is countable but not finite, then

# 𝐴 = # ℕ

and

𝐴

is said to be countably infinite.

2.2.3 Cardinality of Set Operations

Proposition 2.21 (Union of countable sets): Let

{𝐴 𝑖 : 𝑖 \in ℕ}

be a collection of sets s.t. for any

𝑖 \in ℕ

𝐴 𝑖

is countable. Then the union

⋃ 𝑖 \in ℕ 𝐴 𝑖

is countable as well.

Proposition 2.22 (Cartesian product of countable sets): Let

𝐴 𝑖

𝑖 = 1, \dots, 𝑛

, be countable sets. Then, their Cartesian product

\times 𝑛 𝑖 = 1 𝐴 𝑖

is countable.

2.2.4 Heine-Borel Theorem

Theorem 2.23 (Heine-Borel theorem for intervals): Let

[𝑎, 𝑏]

𝑎, 𝑏 \in 𝑅

𝑎 < 𝑏

, be any closed interval. Let

𝐼

be some countable set and assume that there exists a family of open intervals

(𝑎 𝑖, 𝑏 𝑖)

𝑎 𝑖, 𝑏 𝑖 \in ℝ

𝑖 \in 𝐼

, s.t.

[𝑎, 𝑏] \subset ⋃ 𝑖 \in 𝐼 (𝑎 𝑖, 𝑏 𝑖)

. Then, there exists

𝑁 \in ℕ

and

𝑖 1, \dots, 𝑖 𝑁 \in 𝐼

s.t.

[𝑎, 𝑏] \subset ⋃ 𝑁 𝑗 = 1 (𝑎 𝑖 𝑗, 𝑏 𝑖 𝑗)

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

𝐱 \in ℝ 𝑘

𝐱 = (𝑥 1, \dots, 𝑥 𝑘)

. The Euclidean norm of

𝐱

is given by

‖ 𝐱 ‖ = \sqrt 𝑥 21 + \dots + 𝑥 2 𝑘

$‖ 𝐱 - 𝐲 ‖$ gives the Euclidean distance between two points $𝐱, 𝐲 \in ℝ 𝑘$ .

Example (Euclidean norm in one dimension): If

𝑘 = 1

, then we write

‖ 𝑥 ‖ = | 𝑥 |

, where the function

𝑥 \mapsto | 𝑥 |

maps

𝑥 \in ℝ

to its absolute value

\sqrt 𝑥 2 = | 𝑥 | \in [0, \infty)

For the next proposition, we use the notation $𝟎$ for the vector in $ℝ 𝑘$ , $𝑘 \in ℕ$ , with all of its coordinates equal to zero.

Proposition 2.25 (Properties of the Euclidean norm): For any

𝐱, 𝐲 \in ℝ 𝑘

, the Euclidean norm satisfies:

$‖ 𝐱 ‖ \geq 0$
$‖ 𝐱 ‖ = 0 ⟺ 𝐱 = 𝟎$
$‖ 𝜆 𝐱 ‖ = 𝜆 ‖ 𝐱 ‖$ for any $𝜆 \in ℝ$
$‖ 𝐱 - 𝐲 ‖ = ‖ 𝐲 - 𝐱 ‖$
$‖ 𝐱 + 𝐲 ‖ \leq ‖ 𝐱 ‖ + ‖ 𝐲 ‖$ , the triangular inequality
$‖ 𝐱 - 𝐲 ‖ \geq | ‖ 𝐱 ‖ - ‖ 𝐲 ‖ |$ , 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

𝑟 > 0

with center

𝐲 \in ℝ 𝑘

𝐵 𝑟 (𝐲) = {𝐱 \in ℝ 𝑘 : ‖ 𝐲 - 𝐱 ‖ < 𝑟}

, resp.

𝐵 𝑟 [𝐲] = {𝐱 \in ℝ 𝑘 : ‖ 𝐲 - 𝐱 ‖ \leq 𝑟}

Definition 2.27 (Open set): A set

𝑈 \subset ℝ 𝑘

is called open if for any point

𝐱 \in 𝑈

there exists an

𝜀 > 0

s.t.

𝐵 𝜀 (𝐱) \subset 𝑈

Example (Intersection of open sets is open): Let

𝑈 1

𝑈 2

be two open subsets of

ℝ 𝑘

. By definition, for an arbitrary

𝑥 \in 𝑈 1 \cap 𝑈 2

there exist

𝐵 𝜀 1 (𝐱)

and

𝐵 𝜀 2 (𝐱)

s.t.

𝐵 𝜀 1 (𝐱) \subset 𝑈 1

and

𝐵 𝜀 2 (𝐱)

. Set

𝜀 = m i n {𝜀 1, 𝜀 2}

and we obtain

𝐵 𝜀 (𝐱) \subset 𝑈 1 \cap 𝑈 2

. Hence,

𝑈 1 \cap 𝑈 2

is open.

Example (Open interval is an open set): Let

𝑎, 𝑏 \in ℝ

𝑎 < 𝑏

s.t.

(𝑎, 𝑏)

is an open interval. Let

𝑥 \in (𝑎, 𝑏)

. Note that

| 𝑥 - 𝑎 | = 𝑥 - 𝑎

and

| 𝑥 - 𝑏 | = 𝑏 - 𝑥

. Let

𝜀 < m i n {𝑥 - 𝑎, 𝑏 - 𝑥}

and take any

𝑦 \in (𝑥 - 𝜀, 𝑥 + 𝜀) = 𝐵 𝜀 (𝑥)

. We have

| 𝑥 - 𝑦 | < 𝜀

and thus

𝑥 - 𝑦 \leq | 𝑥 - 𝑦 | < 𝜀 < 𝑥 - 𝑎

and

𝑦 - 𝑥 \leq | 𝑥 - 𝑦 | < 𝜀 < 𝑏 - 𝑥

. Hence

𝑎 < 𝑦 < 𝑏

and

𝑦 \in (𝑎, 𝑏)

and

𝐵 𝜀 (𝑥) \subset (𝑎, 𝑏)

Example (Open ball is an open set): Let

𝐵 𝑟 (𝐲) \subset ℝ 𝑘

and

𝐱 \in 𝐵 𝑟 (𝐲)

be an arbitrary point. Set

𝛿 = ‖ 𝐱 - 𝐲 ‖

. By definition of

𝐵 𝑟 (𝐲)

we have

𝛿 < 𝑟

. Let

𝜀 = 𝑟 - 𝛿

. For any

𝐳 \in 𝐵 𝜀 (𝐱)

we have by the triangle inequality

‖ 𝐳 - 𝐲 ‖ \leq ‖ 𝐳 - 𝐱 ‖ + ‖ 𝐱 - 𝐲 ‖ < 𝜀 + 𝛿 = 𝑟

. Hence

𝐵 𝜀 (𝐱) \subset 𝐵 𝑟 (𝐲)

Definition 2.28 (Closed set): A set

𝑉 \subset ℝ 𝑘

is said to be closed if

𝑉 𝑐

is open.

Definition 2.29 (Bounded set): A set

𝐴 \subset ℝ 𝑘

is said to be bounded if there exists an

𝑟 > 0

and

𝐲 \in 𝐴

s.t.

𝐴 \subset 𝐵 𝑟 [𝐲]

Definition 2.30 (Bounded function): Let

𝑓 : 𝐴 \to - ℝ

and

𝐸 \subset 𝐴

. THe function

𝑓

is said to be bounded on

𝐸

if thre exists a

0 \leq 𝑀 < \infty

s.t.

| 𝑓 (𝑎) | \leq 𝑀

for any

𝑎 \in 𝐸

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

𝑓 : ℝ 𝑚 \to ℝ 𝑘

is continuous if for any open set

𝑈 \subset ℝ 𝑘

the preimage

𝑓 - 1 (𝑈)

is open in

ℝ 𝑚

Example (Continuity of the identity function): Let

𝑓 : ℝ \to ℝ

𝑓 (𝑥) = 𝑥

. Take any open set

𝑈 \subset ℝ

. Then

𝑓 - 1 (𝑈) = 𝑈

. Hence,

𝑓 - 1 (𝑈)

is an open subset of

ℝ

and

𝑓

is continuous.

In terms of functions defined on subsets of Euclidean spaces $ℝ 𝑚$ , continuity is characterized as follows.

Proposition 2.32 (Generalized notion of continuity): Let

𝐸 \subset ℝ 𝑚

𝐸 \neq \emptyset

. A function

𝑓 : 𝐸 \to ℝ 𝑘

is continuous iff for any open set

𝑈 \subset ℝ 𝑘

we have

𝑓 - 1 (𝑈) \in {𝐺 \cap 𝐸 : 𝐺 o p e n i n ℝ 𝑚}

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