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,…1, 2, 3, \ldots is denoted with N\N. If n∈Nn \in \N, then so is n+1n+1.

Note that it is a matter of convention whether 0∈N0 \in \N or not. For us, 0∈N0 \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∈Qq \in \Q such that q2=2q^2 = 2 showing that 2∉Q\sqrt{2} \notin \Q. The same is true for π\pi and ee. These numbers belong to the set of real numbers R\R.

Definition 1.2 (Cartesian product): Let A1,…,AnA_1, \ldots, A_n, n∈Nn \in \N, be a family of sets. The Cartesian product of A1,…,AnA_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 A1×⋯×AnA_1 \times \cdots \times A_n is referred to as a vector with coordinates ωi∈Ai\omega_i \in A_i, i=1,…,ni = 1, \ldots, n. If Ai=AA_i = A, i=1,…,ni = 1, \ldots, n, we write ⨂i=1nAi=An\bigtimes_{i=1}^{n} A_i = A^n. The space Rk\R^k is reffered to as the real coordinate space of dimension kk.

Definition 1.3 (Set operations): Let AA and BB be two sets, then we define the following set operations:
  • Equality: A=BA = B iff AA and BB contain the same elements
  • Inclusion: A⊂BA \subset B iff ω∈A\omega \in A implies ω∈B\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 AiA_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 AiA_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 AA, BB and CC be some sets. Properties of inclusion:
  1. A⊂AA \subset A
  2. ∅⊂A\varnothing \subset A
  3. A⊂BandB⊂A  ⟺  A=BA \subset B \qand B \subset A \iff A = B
  4. A⊂BandB⊂C  ⟹  A⊂CA \subset B \qand B \subset C \implies A \subset C
Associativity:
  1. (A∪B)∪C=A∪(B∪C)(A \cup B) \cup C = A \cup (B \cup C)
  2. (A∩B)∩C=A∩(B∩C)(A \cap B) \cap C = A \cap (B \cap C)
Commutativity:
  1. A∪B=B∪AA \cup B = B \cup A
  2. A∩B=B∩AA \cap B = B \cap A
Distributive law:
  1. A∩(B∪C)=(A∩B)∪(A∩C)A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
  2. A∪(B∩C)=(A∪B)∩(A∪C)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 AA, ∅⊂A\varnothing \subset A.

Further, ∅∩A=∅\varnothing \cap A = \varnothing and ∅∪A=A\varnothing \cup A = A.

Definition 1.7 (Disjoint sets): Let AA and BB be two sets. AA and BB are said to be disjoint if A∩B=∅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 Ai∩Aj=∅A_i \cap A_j = \varnothing for all i≠ji \neq j.

1.1.4 Results on Set Differences

Proposition 1.8 (Properties of set differences): Let AA, BB and CC be some sets.
  1. C∖(A∩B)=(C∖A)∪(C∖B)C \setminus (A \cap B) = (C \setminus A) \cup (C \setminus B)
  2. C∖(A∪B)=(C∖A)∩(C∖B)C \setminus (A \cup B) = (C \setminus A) \cap (C \setminus B)
  3. (B∖A)∩C=(B∩C)∖A(B \setminus A) \cap C = (B \cap C) \setminus A
  4. (B∖A)∪C=(B∪C)∖(A∖C)(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⊂ΩA \subset \Omega.

Definition 1.9 (Complement): Let A⊂ΩA \subset \Omega, then the complement of AA is Ac=Ω∖AA^{c} = \Omega \setminus A.
Proposition 1.10 (Properties of complements): Let AA and BB be subsets of Ω\Omega.
  1. A∪Ac=ΩA \cup A^{c} = \Omega
  2. A∩Ac=∅A \cap A^{c} = \varnothing
  3. A∖B=A∩BcA \setminus B = A \cap B^{c}
  4. ∅c=Ω\varnothing^{c} = \Omega
  5. Ωc=∅\Omega^{c} = \varnothing
  6. (A⊂B)  ⟹  (Bc⊂Ac)(A \subset B) \implies (B^{c} \subset A^{c})
  7. (Ac)c=A(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 AA and BB be subsets of Ω\Omega.
  1. (A∩B)c=Ac∪Bc(A \cap B)^{c} = A^{c} \cup B^{c}
  2. (A∪B)c=Ac∩Bc(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⊂RA \subset \R. An element s∈Rs \in \R is called an upper (resp. lower) bound of AA, if x≤sx \leq s (resp. x≥sx \geq s) for all x∈Ax \in A.

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

Definition 1.13 (Intervals): Let a<ba < b, a,b∈Ra,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⊂RI \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⊂RA \subset \R be a set. An element s∈Rs \in \R is called supremum of AA and we write s=sup⁡As = \sup A if ss is the smallest upper bound of AA, i.e.:
  1. ss is an upper bound of AA
  2. every s′<ss' \lt s is not an upper bound of AA
Example (Supremum): Let A=[0,1)A = [0,1). We can prove that 11 is the smallest upper bound for AA and hence sup⁡A=1\sup A = 1. Note that sup⁡A∉A\sup A \notin A, i.e. the supremum must not be an element of the set itself.
Definition 1.15 (Infimum): Let A⊂RA \subset \R be a set. An element s∈Rs \in \R is called infimum of AA and we write s=inf⁡As = \inf A if ss is the greatest lower bound of AA, i.e.:
  1. ss is a lower bound of AA
  2. every s′>ss' \gt s is not an lower bound of AA
Example (Infimum): Let A=[0,1)A = [0,1), then 00 is the minimum for AA and hence inf⁡A=0\inf A = 0.
Definition 1.16 (Maximum and minimum): Let A⊂RA \subset \R. If s=sup⁡A∈As = \sup A \in A (resp. s=inf⁡A∈As = \inf A \in A) we call ss the maximum (resp. the minimum) of AA.

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

Proposition 1.17 (Existence of supremum, infimum): Let A⊂RA \subset \R s.t. A≠∅A \neq \varnothing. Suppose that there exists an upper (resp. lower) bound for AA. Then, sup⁡A∈R\sup A \in \R (resp. inf⁡A∈R\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\Q are helpful.

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

1.2.3 Infima and Suprema of Unbounded Sets

Definition 1.19 (Infinity): Let A⊂RA \subset \R such that A≠∅A \neq \varnothing. We define
  • sup⁡A=∞\sup A = \infty if AA has no upper bound
  • inf⁡A=−∞\inf A = -\infty if AA has no lower bound
Definition 1.20 (Unbounded intervals): Let a,b∈Ra,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⊂RA, B \subset \R be non-empty sets such that A⊂BA \subset B, then inf⁡A≥inf⁡B\inf A \geq \inf B and sup⁡A≤sup⁡B\sup A \leq \sup B.
Proposition 1.22 (Property of infimum, supremum): Let A⊂RA \subset \R be a nonempty set. Then, if AA is
  • bounded from below, for any δ>0\delta \gt 0 we have ∃x∈A:x<inf⁡A+δ\exists x \in A : x \lt \inf A + \delta
  • bounded from above, for any δ>0\delta \gt 0 we have ∃x∈A:x<sup⁡A−δ\exists x \in A : x \lt \sup A - \delta

1.2.5 On the Completion of the Real Numbers

R\R is not bounded and hence inf⁡R=−∞\inf \R = - \infty and sup⁡R=∞\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, −∞,∞∉R-\infty, \infty \not\in \R, i.e. these objects are not numbers.

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

For future reference, we also write

\overline{\R}_{+} = [0, \infty) \cup \qty{\infty}

.