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={ω1,ω2,…,ωn}\setA = \set{\omega_1, \omega_2, \ldots, \omega_n} or upon a certain property A={ω | ω has property P}\setA = \set{\omega \mid \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={−n | n∈N}∩0∩N\Z = \set{-n \mid n \in \N} \cap {0} \cap \N is the set of integers.
Example (Rational numbers): Q={q=nm |  n,m∈Z, m≠0}\Q = \set{q= \frac{n}{m} \mid \ 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,…,An\setA_1, \ldots, \setA_n, n∈Nn \in \N, be a family of sets. The Cartesian product of A1,…,An\setA_1, \ldots, \setA_n is given by ⨂i=1nAi=A1×⋯×An={ω=(ω1,…,ωn) | ∀i∈{1,…,n}:ωi∈Ai} \bigtimes_{i=1}^{n} \setA_i = \setA_1 \times \cdots \times \setA_n = \set{\gvec \omega = (\omega_1, \ldots , \omega_n) \mid \forall i \in \set{1, \ldots, n} : \omega_i \in \setA_i}

An element ω\gvec \omega of A1×⋯×An\setA_1 \times \cdots \times \setA_n is referred to as a vector with coordinates ωi∈Ai\omega_i \in \setA_i, i=1,…,ni = 1, \ldots, n. If ∀i∈{1,…,n}:Ai=A\forall i \in \set{1, \ldots, n} : \setA_i = \setA, we write ⨂i=1nAi=An\bigtimes_{i=1}^{n} \setA_i = \setA^n. The space Rk\R^k is reffered to as the real coordinate space of dimension kk.

Definition 1.3 (Set operations): Let A\setA and B\setB be two sets, then we define the following set operations:
  • Equality: A=B\setA = \setB if and only if A\setA and B\setB contain the same elements
  • Inclusion: A⊆B\setA \subset \setB if and only if ω∈A\omega \in \setA implies ω∈B\omega \in \setB
  • Intersection: A∩B={ω | ω∈A and ω∈B}\setA \cap \setB = \set{\omega \mid \omega \in \setA \text{ and } \omega \in \setB}
  • Union: A∪B={ω | ω∈A or ω∈B}\setA \cup \setB = \set{\omega \mid \omega \in \setA \text{ or } \omega \in \setB}
  • Set difference: A∖B={ω | ω∈A and ω∉B}\setA \setminus \setB = \set{\omega \mid \omega \in \setA \text{ and } \omega \notin \setB}

Let {Ai | i∈I}\set{\setA_i \mid i \in \setI} be a family of sets, then the intersection of all Ai\setA_i is the set ⋂i∈IAi={ω | ∀i∈I:ω∈Ai} \bigcap_{i\in\setI} \setA_i = \set{\omega \mid \forall i \in \setI : \omega \in \setA_i} and the union of all Ai\setA_i is the set ⋃i∈IAi={ω | ∃i∈I:ω∈Ai} \bigcup_{i\in \setI} \setA_i = \set{\omega \mid \exists i \in \setI : \omega \in \setA_i}

1.1.2 Elementary Properties

Let A\setA, B\setB and C\setC be some sets.

Proposition 1.4 (Properties of inclusion):
  1. A⊆A\setA \subset \setA
  2. ∅⊆A\varnothing \subset \setA
  3. A⊆B and B⊆A  ⟺  A=B\setA \subset \setB \text{ and } \setB \subset \setA \iff \setA = \setB
  4. A⊆B and B⊆C  ⟹  A⊆C\setA \subset \setB \text{ and } \setB \subset \setC \implies \setA \subset \setC
Proposition 1.5 (Associativity):
  1. (A∪B)∪C=A∪(B∪C)(\setA \cup \setB) \cup \setC = \setA \cup (\setB \cup \setC)
  2. (A∩B)∩C=A∩(B∩C)(\setA \cap \setB) \cap \setC = \setA \cap (\setB \cap \setC)
Proposition 1.6 (Commutativity):
  1. A∪B=B∪A\setA \cup \setB = \setB \cup \setA
  2. A∩B=B∩A\setA \cap \setB = \setB \cap \setA
Proposition 1.7 (Distributive law):
  1. A∩(B∪C)=(A∩B)∪(A∩C)\setA \cap (\setB \cup \setC) = (\setA \cap \setB) \cup (\setA \cap \setC)
  2. A∪(B∩C)=(A∪B)∩(A∪C)\setA \cup (\setB \cap \setC) = (\setA \cup \setB) \cap (\setA \cup \setC)
Proposition 1.8 (Properties of set difference):
  1. C∖(A∩B)=(C∖A)∪(C∖B)\setC \setminus (\setA \cap \setB) = (\setC \setminus \setA) \cup (\setC \setminus \setB)
  2. C∖(A∪B)=(C∖A)∩(C∖B)\setC \setminus (\setA \cup \setB) = (\setC \setminus \setA) \cap (\setC \setminus \setB)
  3. (B∖A)∩C=(B∩C)∖A(\setB \setminus \setA) \cap \setC = (\setB \cap \setC) \setminus \setA
  4. (B∖A)∪C=(B∪C)∖(A∖C)(\setB \setminus \setA) \cup \setC = (\setB \cup \setC) \setminus (\setA \setminus \setC)

1.1.3 The Empty Set

Definition 1.9 (Empty set): The set which has no elements is called the empty set and denoted with ∅\varnothing.
Proposition 1.10: Given any set A\setA, it always holds that ∅⊆A\varnothing \subset \setA.

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

Definition 1.11 (Disjoint sets): Let A\setA and B\setB be two sets. A\setA and B\setB are said to be disjoint if A∩B=∅\setA \cap \setB = \varnothing.

More generally, let {Ai | i∈I}\set{\setA_i \mid i \in \setI} be any family of sets. {Ai | i∈I}\set{\setA_i \mid i \in \setI} is said to be disjoint if ∀i≠j:Ai∩Aj=∅\forall i \neq j : \setA_i \cap \setA_j = \varnothing.

1.1.4 On Families of Subsets

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

Definition 1.12 (Complement): Let A⊆Ω\setA \subset \Omega, then the complement of A\setA is Ac=Ω∖A\setA^{c} = \Omega \setminus \setA.
Proposition 1.13 (Properties of complements): Let A\setA and B\setB be subsets of Ω\Omega.
  1. A∪Ac=Ω\setA \cup \setA^{c} = \Omega
  2. A∩Ac=∅\setA \cap \setA^{c} = \varnothing
  3. A∖B=A∩Bc\setA \setminus \setB = \setA \cap \setB^{c}
  4. ∅c=Ω\varnothing^{c} = \Omega
  5. Ωc=∅\Omega^{c} = \varnothing
  6. (A⊆B)  ⟹  (Bc⊆Ac)(\setA \subset \setB) \implies (\setB^{c} \subset \setA^{c})
  7. (Ac)c=A(\setA^{c})^{c} = \setA

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

Proposition 1.14 (De Morgan's laws): Let {Ai | Ai⊆Ω, i∈I}\set{\setA_i \mid \setA_i \subset \Omega, \ i \in \setI} bet an arbitrary family of subsets. We have:
  1. (⋂i∈IAi)c=⋃i∈IAic\pa{\bigcap_{i \in \setI} \setA_i}^{c} = \bigcup_{i \in \setI} \setA_i^{c}
  2. (⋃i∈IAi)c=⋂i∈IAic\pa{\bigcup_{i \in \setI} \setA_i}^{c} = \bigcap_{i \in \setI} \setA_i^{c}

Specifically, if A\setA and B\setB are subsets of Ω\Omega then (A∩B)c=Ac∪Bc(\setA \cap \setB)^{c} = \setA^{c} \cup \setB^{c} and (A∪B)c=Ac∩Bc(\setA \cup \setB)^{c} = \setA^{c} \cap \setB^{c}.

1.2 Order Structure of the Real Numbers

1.2.1 Supremum and Infimum

Definition 1.15 (Upper and lower bound): Let A⊆R\setA \subset \R. An element s∈Rs \in \R is called an upper (respectively lower) bound of A\setA, if x≤sx \leq s (respectively x≥sx \geq s) for all x∈Ax \in \setA.

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

Definition 1.16 (Intervals): Let a,b∈Ra,b \in \R and a<ba < b.
  • [a,b]={x∈R | a≤x≤b}[a,b] = \set{x \in \R \mid a \leq x \leq b} is a closed interval
  • (a,b)={x∈R | a<x<b}(a,b) = \set{x \in \R \mid a < x < b} is an open interval
  • [a,b)={x∈R | a≤x<b}[a,b) = \set{x \in \R \mid a \leq x < b} is a right-open interval
  • (a,b]={x∈R | a<x≤b}(a,b] = \set{x \in \R \mid a < x \leq b} is a left-open interval

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

Definition 1.17 (Supremum): Let A⊆R\setA \subset \R be a set. An element s∈Rs \in \R is called supremum of A\setA and we write s=sup⁡As = \sup \setA if
  1. ss is an upper bound of A\setA
  2. every s′<ss' \lt s is not an upper bound of A\setA
Example (Supremum): Let A=[0,1)\setA = [0,1). We can prove that 11 is the smallest upper bound for A\setA and hence sup⁡A=1\sup \setA = 1. Note that sup⁡A∉A\sup \setA \notin \setA, i.e. the supremum must not be an element of the set itself.
Definition 1.18 (Infimum): Let A⊆R\setA \subset \R be a set. An element s∈Rs \in \R is called infimum of A\setA and we write s=inf⁡As = \inf \setA if
  1. ss is a lower bound of A\setA
  2. every s′>ss' \gt s is not an lower bound of A\setA
Example (Infimum): Let A=[0,1)\setA = [0,1), then 00 is the minimum for A\setA and hence inf⁡A=0\inf \setA = 0.
Definition 1.19 (Maximum and minimum): Let A⊆R\setA \subset \R. If s=sup⁡A∈As = \sup \setA \in \setA (respectively s=inf⁡A∈As = \inf \setA \in \setA) we call ss the maximum (respectively the minimum) of A\setA.

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

Proposition 1.20 (Existence of supremum, infimum): Let A⊆R\setA \subset \R s.t. A≠∅\setA \neq \varnothing. Suppose that there exists an upper (respectively lower) bound for A\setA. Then, sup⁡A∈R\sup \setA \in \R (respectively inf⁡A∈R\inf \setA \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.21 (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 Proposition 1.21 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.
Proposition 1.22 (Infimum, supremum of subsets): Let A,B⊆R\setA, \setB \subset \R be non-empty sets such that A⊆B\setA \subset \setB, then inf⁡A≥inf⁡B\inf \setA \geq \inf \setB and sup⁡A≤sup⁡B\sup \setA \leq \sup \setB.
Proposition 1.23: Let A⊆RA \subset \R be a nonempty set. Then, if AA is bounded from below (respectively above), for any δ>0\delta \gt 0 we have ∃x∈A:x<inf⁡A+δ\exists x \in A : x \lt \inf A + \delta (respectively ∃x∈A:x<sup⁡A−δ\exists x \in A : x \lt \sup A - \delta).

1.2.3 Infima and Suprema of Unbounded Sets

Definition 1.24 (Infinity): Let A⊆R\setA \subset \R such that A≠∅\setA \neq \varnothing. We define
  • sup⁡A=∞\sup \setA = \infty if A\setA has no upper bound
  • inf⁡A=−∞\inf \setA = -\infty if A\setA has no lower bound
Definition 1.25 (Unbounded intervals): Let a,b∈Ra,b \in \R. The unbounded real intervals are given by the sets
  • [a,∞)={x∈R:a≤x<∞}[a, \infty) = \set{x \in \R : a \leq x \lt \infty}
  • (a,∞)={x∈R:a<x<∞}(a, \infty) = \set{x \in \R : a \lt x \lt \infty}
  • (∞,b]={x∈R:∞<x≤b}(\infty, b] = \set{x \in \R : \infty \lt x \leq b}
  • (∞,b)={x∈R:∞<x<b}(\infty, b) = \set{x \in \R : \infty \lt x \lt b}

1.2.4 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.26 (Extended real numbers): The set R‾=R∪{−∞,∞}=[−∞,∞]\Rext = \R \cup \set{-\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 \Rext. 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 R‾+=[0,∞)∪{∞}\Rext_{+} = [0, \infty) \cup \set{\infty}.