Intro to Probability

1. Sets and Order Structure

1.1 Sets

1.1.1 Elementary Operations

Definition 1.1 (Set): Sets are defined by their elements $A = \qty{\omega_1, \omega_2, \ldots, \omega_n}$ or upon a certain property $A = \qty{\omega : \omega \text{ has property } \mathcal{P} }$.
Example (Natural numbers): The set which contains the strictly positive integers $1, 2, 3, \ldots$ is denoted with $\N$. If $n \in \N$, then so is $n+1$.

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

Example (Integers): $\Z = \qty{-n : n \in \N} \cap {0} \cap \N$ is the set of integers.
Example (Rational numbers): $\Q = \qty{q= \frac{n}{m} : \ n,m \in \Z, \ m \neq 0 }$ is the set of rational numbers.

It can be shown that there does not exists $q \in \Q$ such that $q^2 = 2$ showing that $\sqrt{2} \notin \Q$. The same is true for $\pi$ and $e$. These numbers belong to the set of real numbers $\R$.

Definition 1.2 (Cartesian product): Let $A_1, \ldots, A_n$, $n \in \N$, be a family of sets. The Cartesian product of $A_1, \ldots, A_n$ is given by $$ \bigtimes_{i=1}^{n} A_i = A_1 \times \cdots \times A_n = \qty{\omega : \omega = (\omega_1, \ldots , \omega_n), \ \omega_i \in A_i, \ i = 1, \ldots, n} $$

An element $\omega$ of $A_1 \times \cdots \times A_n$ is referred to as a vector with coordinates $\omega_i \in A_i$, $i = 1, \ldots, n$. If $A_i = A$, $i = 1, \ldots, n$, we write $\bigtimes_{i=1}^{n} A_i = A^n$. The space $\R^k$ is reffered to as the real coordinate space of dimension $k$.

Definition 1.3 (Set operations): Let $A$ and $B$ be two sets, then we define the following set operations:

Equality: $A = B$ iff $A$ and $B$ contain the same elements

Inclusion: $A \subset B$ iff $\omega \in A$ implies $\omega \in B$

Intersection: $A \cap B = \qty{\omega : \omega \in A \text{ and } \omega \in B}$

Union: $A \cup B = \qty{\omega : \omega \in A \text{ or } \omega \in B}$

Set difference: $A \setminus B = \qty{\omega : \omega \in A \text{ and } \omega \notin B}$

Let $\qty{A_i : i \in I}$ be a family of sets, then the intersection of all $A_i$ is the set

$$ \bigcap_{i\in I} A_i = \qty{\omega : \qty(\forall i \in I : \omega \in A_i)} $$

and the union of all $A_i$ is the set

$$ \bigcup_{i\in I} A_i = \qty{\omega : \qty(\exists i \in I : \omega \in A_i)} $$

1.1.2 Elementary Properties

Proposition 1.4 (Properties of set operations): Let $A$, $B$ and $C$ be some sets.

Properties of inclusion:

  1. $A \subset A$
  2. $\varnothing \subset A$
  3. $A \subset B \qand B \subset A \iff A = B$
  4. $A \subset B \qand B \subset C \implies A \subset C$

Associativity:

  1. $(A \cup B) \cup C = A \cup (B \cup C)$
  2. $(A \cap B) \cap C = A \cap (B \cap C)$

Commutativity:

  1. $A \cup B = B \cup A$
  2. $A \cap B = B \cap A$

Distributive law:

  1. $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
  2. $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

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 $\varnothing$.
Proposition 1.6: Given any set $A$, $\varnothing \subset A$.

Further, $\varnothing \cap A = \varnothing$ and $\varnothing \cup A = A$.

Definition 1.7 (Disjoint sets): Let $A$ and $B$ be two sets. $A$ and $B$ are said to be disjoint if $A \cap B = \varnothing$.

More generally, let $\qty{A_i : i \in I}$ be any family of sets. $\qty{A_i : i \in I}$ is said to be disjoint if $A_i \cap A_j = \varnothing$ for all $i \neq j$.

1.1.4 Results on Set Differences

Proposition 1.8 (Properties of set differences): Let $A$, $B$ and $C$ be some sets.
  1. $C \setminus (A \cap B) = (C \setminus A) \cup (C \setminus B)$
  2. $C \setminus (A \cup B) = (C \setminus A) \cap (C \setminus B)$
  3. $(B \setminus A) \cap C = (B \cap C) \setminus A$
  4. $(B \setminus A) \cup C = (B \cup C) \setminus (A \setminus C)$

1.1.5 On Families of Subsets

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

Definition 1.9 (Complement): Let $A \subset \Omega$, then the complement of $A$ is $A^{c} = \Omega \setminus A$.
Proposition 1.10 (Properties of complements): Let $A$ and $B$ be subsets of $\Omega$.
  1. $A \cup A^{c} = \Omega$
  2. $A \cap A^{c} = \varnothing$
  3. $A \setminus B = A \cap B^{c}$
  4. $\varnothing^{c} = \Omega$
  5. $\Omega^{c} = \varnothing$
  6. $(A \subset B) \implies (B^{c} \subset A^{c})$
  7. $(A^{c})^{c} = A$

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

Proposition 1.11 (De Morgan's laws): Let $A$ and $B$ be subsets of $\Omega$.
  1. $(A \cap B)^{c} = A^{c} \cup B^{c}$
  2. $(A \cup B)^{c} = A^{c} \cap B^{c}$

More generally, for an arbitrary family of subsets $\qty{A_i : A_i \subset \Omega, \ i \in I}$ we have:

\begin{align} \qty(\bigcap_{i \in I} A_i)^{c} = \bigcup_{i \in I} A_i^{c} \\ \qty(\bigcup_{i \in I} A_i)^{c} = \bigcap_{i \in I} A_i^{c} \end{align}

1.2 Order Structure of the Real Numbers

1.2.1 Infima and Suprema

Definition 1.12 (Upper and lower bound): Let $A \subset \R$. An element $s \in \R$ is called an upper (resp. lower) bound of $A$, if $x \leq s$ (resp. $x \geq s$) for all $x \in A$.

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

Definition 1.13 (Intervals): Let $a < b$, $a,b \in \R$.
  • $[a,b] = \qty{x \in \R : a \leq x \leq b}$ is a closed interval
  • $(a,b) = \qty{x \in \R: a < x < b}$ is an open interval
  • $[a,b) = \qty{x \in \R: a \leq x < b}$ is a right-open interval
  • $(a,b] = \qty{x \in \R: a < x \leq b}$ is a left-open interval

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

Definition 1.14 (Supremum): Let $A \subset \R$ be a set. An element $s \in \R$ is called supremum of $A$ and we write $s = \sup A$ if $s$ is the smallest upper bound of $A$, i.e.:
  1. $s$ is an upper bound of $A$
  2. every $s' \lt s$ is not an upper bound of $A$
Example (Supremum): Let $A = [0,1)$. We can prove that $1$ is the smallest upper bound for $A$ and hence $\sup A = 1$. Note that $\sup A \notin A$, i.e. the supremum must not be an element of the set itself.
Definition 1.15 (Infimum): Let $A \subset \R$ be a set. An element $s \in \R$ is called infimum of $A$ and we write $s = \inf A$ if $s$ is the greatest lower bound of $A$, i.e.:
  1. $s$ is a lower bound of $A$
  2. every $s' \gt s$ is not an lower bound of $A$
Example (Infimum): Let $A = [0,1)$, then $0$ is the minimum for $A$ and hence $\inf A = 0$.
Definition 1.16 (Maximum and minimum): Let $A \subset \R$. If $s = \sup A \in A$ (resp. $s = \inf A \in A$) we call $s$ the maximum (resp. the minimum) of $A$.

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 $\R$.

Proposition 1.17 (Existence of supremum, infimum): Let $A \subset \R$ s.t. $A \neq \varnothing$. Suppose that there exists an upper (resp. lower) bound for $A$. Then, $\sup A \in \R$ (resp. $\inf A \in \R$).

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 $\Q$ are helpful.

Proposition 1.18 ($\Q$ is dense in $\R$): For any two real numbers $x_1, x_2 \in \R$, say $x_1 \lt x_2$, there exists a rational number $q \in \Q$ such that $x_1 \lt q \lt x_2$.
Example (Proof of $\sup [0,1) = 1$): Suppose there exists a smaller upper bound $s' < 1$. Note that $[0,1) \cap (s',1) = (s',1)$ is not empty as per the aforementioned proposition we can find a $q \in \Q \subset \R$ such that $q \in (s',1)$, hence $s'$ is no upper bound.

1.2.3 Infima and Suprema of Unbounded Sets

Definition 1.19 (Infinity): Let $A \subset \R$ such that $A \neq \varnothing$. We define
  • $\sup A = \infty$ if $A$ has no upper bound
  • $\inf A = -\infty$ if $A$ has no lower bound
Definition 1.20 (Unbounded intervals): Let $a,b \in \R$. The unbounded real intervals are given by the sets
  • $[a, \infty) = \qty{x \in \R : a \leq x \lt \infty}$
  • $(a, \infty) = \qty{x \in \R : a \lt x \lt \infty}$
  • $(\infty, b] = \qty{x \in \R : \infty \lt x \leq b}$
  • $(\infty, b) = \qty{x \in \R : \infty \lt x \lt b}$

1.2.4 On Properties of Infima and Suprema

Proposition 1.21 (Infimum, supremum of subsets): Let $A, B \subset \R$ be non-empty sets such that $A \subset B$, then $\inf A \geq \inf B$ and $\sup A \leq \sup B$.
Proposition 1.22 (Property of infimum, supremum): Let $A \subset \R$ be a nonempty set. Then, if $A$ is
  • bounded from below, for any $\delta \gt 0$ we have $\exists x \in A : x \lt \inf A + \delta$
  • bounded from above, for any $\delta \gt 0$ we have $\exists x \in A : x \lt \sup A - \delta$

1.2.5 On the Completion of the Real Numbers

$\R$ is not bounded and hence $\inf \R = - \infty$ and $\sup \R = \infty$.

Definition 1.23 (Extended real numbers): The set $\overline{\R} = \R \cup \qty{-\infty, \infty} = [-\infty, \infty]$ are the extended real numbers.

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

Note: Let $x \in \R$. Regarding algebraic operations, we rely on the following conventions regarding infinity:
  1. $x + \infty = \infty + x = \infty$
  2. $x - \infty = -\infty + x = -\infty$
  3. $x \cdot \infty = \infty \cdot x = \infty$ for $x > 0$
  4. $x \cdot (-\infty) = (-\infty) \cdot x = - \infty$ for $x > 0$
  5. $-(-\infty) = \infty$
  6. $0 \cdot \infty = \infty \cdot 0 = 0$
  7. $\infty \cdot \infty = \infty$
Example (Order of extended real numbers): The statement $a \leq b$ if for any $\epsilon > 0$, $a \leq b + \epsilon$, remains valid for $a,b \in \overline{\R}$. If $a = \infty$, then $b = \infty$ and hence $a = b$. If $b = \infty$, then either $a = b$ or $a < b$.

For future reference, we also write $\overline{\R}_{+} = [0, \infty) \cup \qty{\infty}$.