Intro to Probability 2025-02-17

1. Sets and Order Structure

1.1 Sets

1.1.1 Elementary Operations

Definition 1.1 (Set): Sets are defined by their elements

𝐴 = {𝜔 1, 𝜔 2, \dots, 𝜔 𝑛}

or upon a certain property

𝐴 = {𝜔 : 𝜔 h a s p r o p e r t y P}

Example (Natural numbers): The set which contains the strictly positive integers

1, 2, 3, \dots

is denoted with

ℕ

. If

𝑛 \in ℕ

, then so is

𝑛 + 1

Note that it is a matter of convention whether $0 \in ℕ$ or not. For us, $0 \in ℕ$ .

Example (Integers):

ℤ = {- 𝑛 : 𝑛 \in ℕ} \cap 0 \cap ℕ

is the set of integers.

Example (Rational numbers):

ℚ = {𝑞 = 𝑛 𝑚 : 𝑛, 𝑚 \in ℤ, 𝑚 \neq 0}

is the set of rational numbers.

It can be shown that there does not exists $𝑞 \in ℚ$ such that $𝑞 2 = 2$ showing that $\sqrt 2 \notin ℚ$ . The same is true for $𝜋$ and $𝑒$ . These numbers belong to the set of real numbers $ℝ$ .

Definition 1.2 (Cartesian product): Let

𝐴 1, \dots, 𝐴 𝑛

𝑛 \in ℕ

, be a family of sets. The Cartesian product of

𝐴 1, \dots, 𝐴 𝑛

is given by

𝑛 \times 𝑖 = 1 𝐴 𝑖 = 𝐴 1 \times \dots \times 𝐴 𝑛 = {𝜔 : 𝜔 = (𝜔 1, \dots, 𝜔 𝑛), 𝜔 𝑖 \in 𝐴 𝑖, 𝑖 = 1, \dots, 𝑛}

An element $𝜔$ of $𝐴 1 \times \dots \times 𝐴 𝑛$ is referred to as a vector with coordinates $𝜔 𝑖 \in 𝐴 𝑖$ , $𝑖 = 1, \dots, 𝑛$ . If $𝐴 𝑖 = 𝐴$ , $𝑖 = 1, \dots, 𝑛$ , we write $\times 𝑛 𝑖 = 1 𝐴 𝑖 = 𝐴 𝑛$ . The space $ℝ 𝑘$ is reffered to as the real coordinate space of dimension $𝑘$ .

Definition 1.3 (Set operations): Let

𝐴

and

𝐵

be two sets, then we define the following set operations:

Equality: $𝐴 = 𝐵$ iff $𝐴$ and $𝐵$ contain the same elements

Inclusion: $𝐴 \subset 𝐵$ iff $𝜔 \in 𝐴$ implies $𝜔 \in 𝐵$

Intersection: $𝐴 \cap 𝐵 = {𝜔 : 𝜔 \in 𝐴 a n d 𝜔 \in 𝐵}$

Union: $𝐴 \cup 𝐵 = {𝜔 : 𝜔 \in 𝐴 o r 𝜔 \in 𝐵}$

Set difference: $𝐴 ∖ 𝐵 = {𝜔 : 𝜔 \in 𝐴 a n d 𝜔 \notin 𝐵}$

Let ${𝐴 𝑖 : 𝑖 \in 𝐼}$ be a family of sets, then the intersection of all $𝐴 𝑖$ is the set

⋂ 𝑖 \in 𝐼 𝐴 𝑖 = {𝜔 : (\forall 𝑖 \in 𝐼 : 𝜔 \in 𝐴 𝑖)}

and the union of all $𝐴 𝑖$ is the set

⋃ 𝑖 \in 𝐼 𝐴 𝑖 = {𝜔 : (\exists 𝑖 \in 𝐼 : 𝜔 \in 𝐴 𝑖)}

1.1.2 Elementary Properties

Proposition 1.4 (Properties of set operations): Let

𝐴

𝐵

and

𝐶

be some sets.

Properties of inclusion:

$𝐴 \subset 𝐴$
$\emptyset \subset 𝐴$
$𝐴 \subset 𝐵 a n d 𝐵 \subset 𝐴 ⟺ 𝐴 = 𝐵$
$𝐴 \subset 𝐵 a n d 𝐵 \subset 𝐶 ⟹ 𝐴 \subset 𝐶$

Associativity:

$(𝐴 \cup 𝐵) \cup 𝐶 = 𝐴 \cup (𝐵 \cup 𝐶)$
$(𝐴 \cap 𝐵) \cap 𝐶 = 𝐴 \cap (𝐵 \cap 𝐶)$

Commutativity:

$𝐴 \cup 𝐵 = 𝐵 \cup 𝐴$
$𝐴 \cap 𝐵 = 𝐵 \cap 𝐴$

Distributive law:

$𝐴 \cap (𝐵 \cup 𝐶) = (𝐴 \cap 𝐵) \cup (𝐴 \cap 𝐶)$
$𝐴 \cup (𝐵 \cap 𝐶) = (𝐴 \cup 𝐵) \cap (𝐴 \cup 𝐶)$

1.1.3 The Empty Set

Definition 1.5 (Empty set): The set which has no elements is called the empty set and denoted with

\emptyset

Proposition 1.6: Given any set

𝐴

\emptyset \subset 𝐴

Further, $\emptyset \cap 𝐴 = \emptyset$ and $\emptyset \cup 𝐴 = 𝐴$ .

Definition 1.7 (Disjoint sets): Let

𝐴

and

𝐵

be two sets.

𝐴

and

𝐵

are said to be disjoint if

𝐴 \cap 𝐵 = \emptyset

More generally, let ${𝐴 𝑖 : 𝑖 \in 𝐼}$ be any family of sets. ${𝐴 𝑖 : 𝑖 \in 𝐼}$ is said to be disjoint if $𝐴 𝑖 \cap 𝐴 𝑗 = \emptyset$ for all $𝑖 \neq 𝑗$ .

1.1.4 Results on Set Differences

Proposition 1.8 (Properties of set differences): Let

𝐴

𝐵

and

𝐶

be some sets.

$𝐶 ∖ (𝐴 \cap 𝐵) = (𝐶 ∖ 𝐴) \cup (𝐶 ∖ 𝐵)$
$𝐶 ∖ (𝐴 \cup 𝐵) = (𝐶 ∖ 𝐴) \cap (𝐶 ∖ 𝐵)$
$(𝐵 ∖ 𝐴) \cap 𝐶 = (𝐵 \cap 𝐶) ∖ 𝐴$
$(𝐵 ∖ 𝐴) \cup 𝐶 = (𝐵 \cup 𝐶) ∖ (𝐴 ∖ 𝐶)$

1.1.5 On Families of Subsets

It is often the case that a particular set $Ω$ is given and one only considers subsets $𝐴 \subset Ω$ .

Definition 1.9 (Complement): Let

𝐴 \subset Ω

, then the complement of

𝐴

𝐴 𝑐 = Ω ∖ 𝐴

Proposition 1.10 (Properties of complements): Let

𝐴

and

𝐵

be subsets of

Ω

$𝐴 \cup 𝐴 𝑐 = Ω$
$𝐴 \cap 𝐴 𝑐 = \emptyset$
$𝐴 ∖ 𝐵 = 𝐴 \cap 𝐵 𝑐$
$\emptyset 𝑐 = Ω$
$Ω 𝑐 = \emptyset$
$(𝐴 \subset 𝐵) ⟹ (𝐵 𝑐 \subset 𝐴 𝑐)$
$(𝐴 𝑐) 𝑐 = 𝐴$

Further, we have the following properties for the complement of intersections and unions.

Proposition 1.11 (De Morgan's laws): Let

𝐴

and

𝐵

be subsets of

Ω

$(𝐴 \cap 𝐵) 𝑐 = 𝐴 𝑐 \cup 𝐵 𝑐$
$(𝐴 \cup 𝐵) 𝑐 = 𝐴 𝑐 \cap 𝐵 𝑐$

More generally, for an arbitrary family of subsets ${𝐴 𝑖 : 𝐴 𝑖 \subset Ω, 𝑖 \in 𝐼}$ we have:

(⋂ 𝑖 \in 𝐼 𝐴 𝑖) 𝑐 = ⋃ 𝑖 \in 𝐼 𝐴 𝑐 𝑖 (⋃ 𝑖 \in 𝐼 𝐴 𝑖) 𝑐 = ⋂ 𝑖 \in 𝐼 𝐴 𝑐 𝑖 (0.1) (0.2)

1.2 Order Structure of the Real Numbers

1.2.1 Infima and Suprema

Definition 1.12 (Upper and lower bound): Let

𝐴 \subset ℝ

. An element

𝑠 \in ℝ

is called an upper (resp. lower) bound of

𝐴

, if

𝑥 \leq 𝑠

(resp.

𝑥 \geq 𝑠

) for all

𝑥 \in 𝐴

If $𝐴$ has an upper (resp. lower) bound then we say that $𝐴$ is bounded from above (resp. below). If $𝐴$ is bounded from below and above, $𝐴$ is called bounded.

Definition 1.13 (Intervals): Let

𝑎 < 𝑏

𝑎, 𝑏 \in ℝ

$[𝑎, 𝑏] = {𝑥 \in ℝ : 𝑎 \leq 𝑥 \leq 𝑏}$ is a closed interval
$(𝑎, 𝑏) = {𝑥 \in ℝ : 𝑎 < 𝑥 < 𝑏}$ is an open interval
$[𝑎, 𝑏) = {𝑥 \in ℝ : 𝑎 \leq 𝑥 < 𝑏}$ is a right-open interval
$(𝑎, 𝑏] = {𝑥 \in ℝ : 𝑎 < 𝑥 \leq 𝑏}$ is a left-open interval

A set $𝐼 \subset ℝ$ is said to be an interval if it is either closed, open, right-open or left-open.

Definition 1.14 (Supremum): Let

𝐴 \subset ℝ

be a set. An element

𝑠 \in ℝ

is called supremum of

𝐴

and we write

𝑠 = s u p 𝐴

𝑠

is the smallest upper bound of

𝐴

, i.e.:

$𝑠$ is an upper bound of $𝐴$
every $𝑠' < 𝑠$ is not an upper bound of $𝐴$

Example (Supremum): Let

𝐴 = [0, 1)

. We can prove that

1

is the smallest upper bound for

𝐴

and hence

s u p 𝐴 = 1

. Note that

s u p 𝐴 \notin 𝐴

, i.e. the supremum must not be an element of the set itself.

Definition 1.15 (Infimum): Let

𝐴 \subset ℝ

be a set. An element

𝑠 \in ℝ

is called infimum of

𝐴

and we write

𝑠 = i n f 𝐴

𝑠

is the greatest lower bound of

𝐴

, i.e.:

$𝑠$ is a lower bound of $𝐴$
every $𝑠' > 𝑠$ is not an lower bound of $𝐴$

Example (Infimum): Let

𝐴 = [0, 1)

, then

0

is the minimum for

𝐴

and hence

i n f 𝐴 = 0

Definition 1.16 (Maximum and minimum): Let

𝐴 \subset ℝ

. If

𝑠 = s u p 𝐴 \in 𝐴

(resp.

𝑠 = i n f 𝐴 \in 𝐴

) we call

𝑠

the maximum (resp. the minimum) of

𝐴

The following result shows that for each nonempty subset of the real line which has an upper (resp. lower) bound, the supremum (resp. infimum) exists as an element of $ℝ$ .

Proposition 1.17 (Existence of supremum, infimum): Let

𝐴 \subset ℝ

s.t.

𝐴 \neq \emptyset

. Suppose that there exists an upper (resp. lower) bound for

𝐴

. Then,

s u p 𝐴 \in ℝ

(resp.

i n f 𝐴 \in ℝ

1.2.2 The Rational Numbers as Approximation of the Real Numbers

In order to show that there exists a number in between any two distinct real numbers, the rational numbers $ℚ$ are helpful.

Proposition 1.18 (

ℚ

is dense in

ℝ

): For any two real numbers

𝑥 1, 𝑥 2 \in ℝ

, say

𝑥 1 < 𝑥 2

, there exists a rational number

𝑞 \in ℚ

such that

𝑥 1 < 𝑞 < 𝑥 2

Example (Proof of

s u p [0, 1) = 1

): Suppose there exists a smaller upper bound

𝑠' < 1

. Note that

[0, 1) \cap (𝑠', 1) = (𝑠', 1)

is not empty as per the aforementioned proposition we can find a

𝑞 \in ℚ \subset ℝ

such that

𝑞 \in (𝑠', 1)

, hence

𝑠'

is no upper bound.

1.2.3 Infima and Suprema of Unbounded Sets

Definition 1.19 (Infinity): Let

𝐴 \subset ℝ

such that

𝐴 \neq \emptyset

. We define

$s u p 𝐴 = \infty$ if $𝐴$ has no upper bound
$i n f 𝐴 = - \infty$ if $𝐴$ has no lower bound

Definition 1.20 (Unbounded intervals): Let

𝑎, 𝑏 \in ℝ

. The unbounded real intervals are given by the sets

$[𝑎, \infty) = {𝑥 \in ℝ : 𝑎 \leq 𝑥 < \infty}$
$(𝑎, \infty) = {𝑥 \in ℝ : 𝑎 < 𝑥 < \infty}$
$(\infty, 𝑏] = {𝑥 \in ℝ : \infty < 𝑥 \leq 𝑏}$
$(\infty, 𝑏) = {𝑥 \in ℝ : \infty < 𝑥 < 𝑏}$

1.2.4 On Properties of Infima and Suprema

Proposition 1.21 (Infimum, supremum of subsets): Let

𝐴, 𝐵 \subset ℝ

be non-empty sets such that

𝐴 \subset 𝐵

, then

i n f 𝐴 \geq i n f 𝐵

and

s u p 𝐴 \leq s u p 𝐵

Proposition 1.22 (Property of infimum, supremum): Let

𝐴 \subset ℝ

be a nonempty set. Then, if

𝐴

bounded from below, for any $𝛿 > 0$ we have $\exists 𝑥 \in 𝐴 : 𝑥 < i n f 𝐴 + 𝛿$
bounded from above, for any $𝛿 > 0$ we have $\exists 𝑥 \in 𝐴 : 𝑥 < s u p 𝐴 - 𝛿$

1.2.5 On the Completion of the Real Numbers

$ℝ$ is not bounded and hence $i n f ℝ = - \infty$ and $s u p ℝ = \infty$ .

Definition 1.23 (Extended real numbers): The set

- ℝ = ℝ \cup {- \infty, \infty} = [- \infty, \infty]

are the extended real numbers.

It is important to note that by definition, $- \infty, \infty \notin ℝ$ , i.e. these objects are not numbers.

Note: Let

𝑥 \in ℝ

. Regarding algebraic operations, we rely on the following conventions regarding infinity:

$𝑥 + \infty = \infty + 𝑥 = \infty$
$𝑥 - \infty = - \infty + 𝑥 = - \infty$
$𝑥 \cdot \infty = \infty \cdot 𝑥 = \infty$ for $𝑥 > 0$
$𝑥 \cdot (- \infty) = (- \infty) \cdot 𝑥 = - \infty$ for $𝑥 > 0$
$- (- \infty) = \infty$
$0 \cdot \infty = \infty \cdot 0 = 0$
$\infty \cdot \infty = \infty$

Example (Order of extended real numbers): The statement

𝑎 \leq 𝑏

if for any

𝜀 > 0

𝑎 \leq 𝑏 + 𝜀

, remains valid for

𝑎, 𝑏 \in - ℝ

. If

𝑎 = \infty

, then

𝑏 = \infty

and hence

𝑎 = 𝑏

. If

𝑏 = \infty

, then either

𝑎 = 𝑏

𝑎 < 𝑏

For future reference, we also write $- ℝ + = [0, \infty) \cup {\infty}$ .