Probability/Set Theory

The review of set theory contained herein adopts a naive point of view. We assume that the meaning of a set as a collection of objects is intuitively clear. A rigorous analysis of the concept belongs to the foundations of mathematics and mathematical logic. Although we shall not initiate a study of these fields, the rules we follow in dealing with sets are derived from them. A set is a collection of objects, which are the elements of the set.

If an element $x$ belongs to a set $S$ , we express this fact by writing $x\in S$. If $x$ does not belong to $S$ , we write $x\notin S$ . We use the equality symbol to denote logical identity. For instance, $x=y$ means that $x,y$ are symbols denoting the same object. Similarly, the equation $S=T$ states that $S,T$ are two symbols for the same set. In particular, the sets $S,T$ contain precisely the same elements. If $x,y$ are different objects then we write $x\neq y$ . Also, we can express the fact that $S,T$ are different sets by writing $S\neq T$ .

A set $S$ is a subset of $T$ if every element of $S$ is also contained in $T$ . We express this relation by writing $S\subset T$ . Note that this definition does not require $S$ to be different from $T$ . In fact, $S=T$ if and only if $S\subset T$ and $T\subset S$ . If $S\subset T$ and $S$ is different from $T$ , then $S$ is a proper subset of $T$ and we write $S\subsetneq T$ .

There are many ways to specify a set. If the set contains only a few elements, one can simply list the objects in the set;

$S=\{x_{1},x_{2},x_{3}\}$

The content of a set can also be enumerated whenever $S$ has a countable number of elements,

$S=\{x_{1},x_{2},\dots \}$

Usually, the way to specify a set is to take some collection $S$ of objects and some property that elements of $S$ may or may not possess, and to form the set consisting of all elements of $S$ having that property. For example, starting with the integers $\mathbb {Z}$ , we can form the subset of S consisting of all even numbers

$S=\{x\in \mathbb {Z} |x{\text{ is an even number}}\}$

More generally, we denote the set of all elements that have a certain property $P$ by

$S=\{x|x{\text{ satisfies }}P\}$

The braces are to be read as the words "the set of" whereas the symbol | stands for the words "such that." It is convenient to introduce two special sets. The empty set, denoted by $\varnothing$ , is a set that contains no elements. The universal set is the collection of all objects of interest in a particular context, and it is denoted by $\Omega$ . Once a universal set $\Omega$ is specified, we need only consider sets that are subsets of $\Omega$ . In the context of probability, $\Omega$ is often called the sample space.

The complement of a set $S$ , with respect to the universal set $\Omega$ , is the collection of all objects in $\Omega$ that do not belong to $S$ ,

$S^{c}={\bar {S}}=\{x\in \Omega |x\notin S\}$

We note that $\Omega ^{c}=\varnothing$ .

Elementary Set Operations

Probability theory makes extensive use of elementary set operations. Below, we review the ideas of set theory, and establish the basic terminology and notation. Consider two sets $S,T$ .

The union of sets $S,T$ is the collection of all elements that belong to $S$ or $T$ (or both), and it is denoted by $S\cup T$ . Formally, we define the union of these two sets by

$S\cup T=\{x|x\in S{\text{ or }}x\in T\}$

The intersection of sets $S,T$ is the collection of all elements that are common to both $S$ and $T$ . It is denoted by $S\cap T$, and it can be expressed mathematically as

$S\cap T=\{x|x\in S{\text{ and }}x\in T\}$

When $S,T$ have no elements in common, we write $S\cap T=\varnothing$ . We also express this fact by saying that $S,T$ are disjoint. More generally, a collection of sets is said to be disjoint if no two sets have a common element. A collection of sets is said to form a partition of $S$ if the sets in the collection are disjoint and their union is $S$ .

The difference of two sets, denoted by $S-T$ or $S\setminus T$ , is defined as the set consisting of those elements of $S$ that are not in $T$ ,

$S-T=S\setminus T=\{x|x\in S{\text{ and }}x\notin T\}$

This set is sometimes called the complement of $T$ relative to $T$ , or the complement of $T$ in $S$ .

We have already looked at the definition of the union and the intersection of two sets. We can also form the union or the intersection of arbitrarily many sets. This is defined in the obvious way,

$\bigcup _{\alpha \in I}S_{\alpha }=\{x|x\in S_{\alpha }{\text{ for some }}\alpha \in I\}$

$\bigcap _{\alpha \in I}S_{\alpha }=\{x|x\in S_{\alpha }{\text{ for all }}\alpha \in I\}$

The index set I can be finite or even infinite.

Rules of Set Theory

Given a collection of sets, it is possible to form new ones by applying elementary set operations to them. As in algebra, one uses parentheses to indicate precedence. For instance, $R\cup (S\cap T)$ denotes the union of two sets $R,S\cap T$ , while $(R\cup S)\cap T$ represents the intersection of two sets $R\cup S,T$ .The sets thus formed are quite different.

Sometimes different combinations of operations lead to the same set. For instance, we have the two distributive laws

$R\cap (S\cup T)=(R\cap S)\cup (R\cap T)$

$R\cup (S\cap T)=(R\cup S)\cap (R\cup T)$

Two particularly useful equivalent combinations of operations are given by De Morgan's laws, which state that

$R-(S\cup T)=(R-S)\cap (R-T)$

$R-(S\cap T)=(R-S)\cup (R-T)$

These two laws can be generalized to

$\left(\bigcup _{\alpha \in I}S_{\alpha }\right)^{c}=\bigcap _{\alpha \in I}S_{\alpha }^{c}$

$\left(\bigcap _{\alpha \in I}S_{\alpha }\right)^{c}=\bigcup _{\alpha \in I}S_{\alpha }^{c}$

when multiple sets are involved. To establish the first equality, suppose that $x$ belongs to $\left(\bigcup _{\alpha \in I}S_{\alpha }\right)^{c}$ . Then $x$ is not contained in $\bigcup _{\alpha \in I}S_{\alpha }$ . That is, $x$ is not an element of $S_{\alpha }$ for any $\alpha \in I$ . This implies that $x$ belongs to $S_{\alpha }^{c}$ for all $\alpha \in I$ , and therefore $x\in \bigcap _{\alpha \in I}S_{\alpha }^{c}$ . We have shown that $\left(\bigcup _{\alpha \in I}S_{\alpha }\right)^{c}\subset \bigcap _{\alpha \in I}S_{\alpha }^{c}$ . The converse inclusion is obtained by reversing the above argument. The second law can be obtained in a similar fashion.

Cartesian Products

There is yet another way to create new sets form existing ones. It involves the notion of an ordered pair of objects. Given sets $S,T$ , the cartesian product $S\times T$ is the set of all ordered pairs $x,y$ for which $x$ is an element of $S$ and $y$ is an element of $T$ ,

$S\times T=\{(x,y)|x\in S{\text{ and }}y\in T\}$

Summary of Probability & Set Theory

• $A=P(A)\cdot \sum [0,1]$
• ${\text{not }}A=P({\bar {A}})=P(A^{c})=1-P(A)$
• $A{\text{ or }}B=P(A\cup B)=P(A)+P(B)-P(A\cap B)=P(A)+P(B)$ [*if and only if $A$ and $B$ are mutually exclusive]
• $A{\text{ and }}B=P(A\cap B)=P(A\setminus B)\cdot P(B)=P(A)\cdot P(B)$ [*if and only if $A$ and $B$ are independent]
• $A{\text{ given }}B=P(A|B)={\frac {P(A\cap B)}{P(B)}}$ [*conditional]

Basic Set Theory

UNION: combined area of set $A,B$ , known as $A\cup B$ . The set of all items which are members of either $A$ or $B$

• Union of $A,B$ are added together
• Some basic properties of unions:
• $A\cup B=B\cup A$
• $A\cup (B\cup C)=(A\cup B)\cup C$
• $A\subset (A\cup B)$
• $A\cup A=A$
• $A\cup \varnothing =A$ , where $\varnothing ={\text{empty set}}$
• $A\subset B$ , if and only if $A\cup B=B$

INTERSECTION: area where both $A,B$ overlap, known as $A\cap B$ . It represents which elements the two sets $A,B$ have in common

• If $A\cap B=\varnothing$ , then A and B are said to be DISJOINT.
• Some basic properties of intersections:
• $A\cap B=B\cap A$
• $A\cap (B\cap C)=(A\cap B)\cap C$
• $(A\cap B)\subset A$
• $A\cap A=A$
• $A\cap \varnothing =\varnothing$
• $A\subset B$ , if and only if $A\cap B=A$
• UNIVERSAL SET: space of all things possible, which contains ALL of the elements or elementary events.
• $U\setminus A$ is called the absolute complement of $A$

Complement (set): 2 sets can be subtracted. The relative complement (set theoretic difference of $B$ and $A$). Denoted by $B\setminus A$ (or $B-A$) is the set of all elements which are members of $B$ , but not members of $A$

Some basic properties of complements (${\overline {A}}\ ,\ A^{c}\ ,\ ~A\ ,\ A'$):

• $A\cup {\overline {A}}=U$
• $A\cap {\overline {A}}=\varnothing$
• ${\overline {({\overline {A}})}}=A$
• $A\setminus A=\varnothing$
• ${\overline {U}}=\varnothing$ , and ${\overline {\varnothing }}=U$
• $A\setminus B=A\cap {\overline {B}}$

Summary

• Intersection $A\cap B$ --> AND – both events occur together at the same time
• Union $A\cup B$ --> OR – everything about both events, $A,B$
• Complement ${\overline {A}}$ --> NOT $A$ – everything else except $A$ (or the event in question)
• $A\cup {\overline {A}}=S$ (sample space)
• $A\cap {\overline {A}}=\varnothing$ (impossible event)

Union and Intersection are:

Commutative

• $A\cup B=B\cup A$
• $A\cap B=B\cap A$

Associative

• $A\cup (B\cup C)=(A\cup B)\cup C$
• $A\cap (B\cap C)=(A\cap B)\cap C$

Distributive

• $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
• $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$