Probability/Set Theory


IntroductionEdit

The overview of set theory contained herein adopts a naive point of view. 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.

SetsEdit

Definition.

 
A set.

(Set)

  • A set is a well-defined collection of distinct object(s), which are called element(s).
  • We say that an element belongs to the set.
  • If   belongs to a set   , we write  .
  • If   does not belong to the set   , we write  .

Remark.

  • When   and   are (not) equal, denoted by   ,   and   are different symbols denoting the same (different) object(s).

Example. (Collection that is not well-defined)

  • The collection of easy school subjects is not a set.

We have different ways to describe a set, e.g.

  • word description: e.g., a set   is the set containing the 12 months in a year;
  • listing: elements in a set are listed within a pair of braces, e.g.,  ;
the ordering of the elements is not important, i.e. even if the elements are listed in different order, the set is still the same. E.g.,   is still referring to the same set.
  • set-builder notation:
     
in which the closing brace must also be written. E.g.,  .
  • In particular, since a set contains distinct objects, the months contained in this set are distinct, and therefore there are only 12 elements in this set.

Example. (Empty set) The set   is called an empty set, and it contains no element. It is commonly denoted by   also.

Exercise.

Is   an empty set?

Yes.
No.



Example.

  •  ;
  •  ;
  •  .

Exercise.

Select all element(s) belonging to the set  .

 
 
 
 
 



Definition. (Set equality) When two sets are equal, they contain the same elements.

Remark.

  • Equivalently, two sets   and   are equal if each element of   is also element of   and each element of   is also element of  .
  • We use   to denote sets   and   are (not) equal.

Example.

  •  ,  , and the set that contains only an empty set are pairwise equal.
  •  .
  •  

Definition. (Universal set) Universal set, denoted by  , is the set that contains all objects being considered in a particular context.

Remark.

  • In the context of probability, a universal set, which is usually denoted by   instead, is the set containing all outcomes of a particular random experiment, and is also called a sample space.

Definition. (Cardinality) Cardinality of a finite set, which is a set containing finite number of elements, is the number of its elements.

Remark.

  • Cardinality of set   can be denoted by   (or  )
  • We do not use the   notation to avoid ambiguity.
  • Infinite set is a set containing infinite number of elements.
  • We will leave the cardinality of infinite set undefined in this book, but it can be defined, in a more complicated way.

Example.

  •  .
  •  .
  •   (the set containing each positive number) is an infinite set.

Exercise.

Calculate  .

0
1
2
3
None of the above.




SubsetsEdit

We introduce a relationship between sets in this section.

Definition. (Subset)

  • If each element of set   is an element of set  , then   is a subset of  , denoted by  .
  • If   is not a subset of  , then we write  .

Remark.

  • By referring to the definitions of subsets and set equality, we can see that   is equivalent to (or if and only if)   and  .
  • The notation   means that   is a superset of  , which means that   is a subset of  .
  • This notation and terminology are seldom used.

Definition. (Venn diagram) A Venn diagram is a diagram that shows all possible logical relations between finitely many sets.

Remark.

  • It is quite useful for illustrating some simple relationships between sets, and making the relationships clear.
  • We may also add various annotations in the Venn digram, e.g. cardinality of each set, and the element(s) contained by each set.

Illustration of subset by Venn diagram:

A ⊆ B (A ≠ B):

*-----------------------*
|                       |
|                       |
|   *----------*        | <---- B
|   |          |        |
|   |    A     |        |
|   |          |        |
|   *----------*        |
*-----------------------*

Example.

  •  ;

Venn digram:

*-----------------------*
|                       |
|                       |
|   *----------*  2     | 
|   |          |        |
|   |    1  3  |        |
|   |          |        |
|   *----------*        |
*-----------------------*
  •  ;

Venn diagram:

*-----------------------*
|                       |
|                       |
|   *----------*  {1}   | 
|   |          |        |
|   |  1 2  3  |        |
|   |          |        |
|   *----------*        |
*-----------------------*
  •   for each set   ;
  •   for each set  .

Example. (Intervals) Intervals are commonly encountered subsets of  . If   and   are (extended) real numbers [1]such that  , then

 
In particular,  , and   is the set containing all extended real numbers.

Definition. (Proper subset)

  • Set   is a proper subset of set   if   and  ;. We write   in this case.
  • If set   is not a proper subset of  , then we write   (but we rarely write this).

Remark.

  • The notation   means that   is a proper superset of  , which means that   is a proper subset of  .
  • This notation and terminology are seldom used.

Example.

  •  .

Definition. (Complement) Let   be a subset of universal set  . The (absolute) complement of  , denoted by  , is the set  .

Example. If   and  , then  .

Venn diagram:

*-----------------------*
|                       |
|                4  5   |
|   *----------*        | 
|   |          |        | <---- U
|   |  1 2  3  |        |
|   |          |        |
|   *----------*        |
*--------^--------------*
         |
         A

Exercise.

Find  .

 
 
 
 
None of the above.




Set operationsEdit

Probability theory makes extensive use of some set operations, and we will discuss them in this section.

Definition.

 
Union of two sets is indicated by the red region.

(Union of sets) Union of set   and set  , denoted by  , is the set  .

Remark.

  •   is read 'A cup B'.
  • We can denote   by   (if the sequence of unions stops at  ), or   (if the sequence of unions does not stop).

Example.

  •  .

Venn diagram:

*----------------*
|                |
|  red   *-------*--------*
|        | orange|        |
*--------*-------*        |
         |       apple    |
         *----------------*

Proposition. (Properties of union of sets) Let  ,  and   be sets. Then, the following statements hold.

(a)  ;
(b)   (commutative law);
(c)   (associative law);
(d)   and  ;
(e)  ;
(f)   if and only if  .

Proof. Informally, consider the following Venn diagrams:

(a)
*----*
|    | <---- A ∪ A (a set overlaps itself completely)
|    | <--- A
*----*
(b)
*----------------*
|////////////////| <---- A 
|////////*-------*--------*               
|////////|///////|////////| 
*--------*-------*////////| <--- B
         |////////////////|
         *----------------*
(shaded region refers to both A ∪ B and B ∪ A)
(c)
*----------*
|//////////| <--- A
|//////////| 
|/////*----|----*
|/////|////|////| <---- C
*-----*----*----*------------*
|/////|////|////|////////////| <--- B
|/////*----|----*////////////|
*----------*-----------------*
(shaded region refers to both A∪(B∪C) and (A∪B)∪C)
(d)
*----------------*
|                | <---- A 
|        *-------*--------*               
|        |       |        | 
*--------*-------*        | <--- B
         |                |
         *----------------*
  and   are both inside the whole region, which represents  .
(e)
*----*
|    |
|    | .
*----*
(f)
*-----------------------*
|                       |
|                       |
|   *----------*        | <---- B
|   |          |        |
|   |    A     |        |
|   |          |        |
|   *----------*        |
*-----------------------*
(the whole region is both A u B and B)
We use a dot, which has zero area, to represent  . Then, we can see that the union of the region and the dot is the region itself.

 

Remark.

  • Formal proofs of propositions and theorems about sets will not be emphasized in this book.
  • Instead, we will usually prove the propositions and theorems informally, e.g. using Venn diagram.

Definition. (Intersection of sets)

 
Intersection of two sets.

Intersection of set   and set  , denoted by  , is the set  .

Remark.

  •   is read 'A cap B'.
  • We can denote   by   (if the sequence of intersections stops at  ), or   (if the sequence of intersection does not stop).

Example.

  •  ;
  •  .

Definition. (Disjoint sets) Set   and set   are disjoint (or mutually exclusive) if  .

Remark.

  • I.e.,   and   are disjoint if they have no element in common.
  • More than two events are disjoint if they are pairwise disjoint.

Venn diagram

*-----*       *-----*       *-----*       
|     |       |     |       |     |
|  A  |       |  B  |       |  C  |
*-----*       *-----*       *-----*

(A, B and C are disjoint)
      
*----------------*
|                | <---- D 
| *--*   *-------*--------*               
| |  |   |       |        | 
*-*--*---*-------*        | <--- E
  |  |   |                |
  *--*   *----------------*
   ^
   |
   F

(D, E and F are not disjoint, but E and F are disjoint)

Definition. (Partition of a set) A collection of sets form a partition of a set   if the sets in the collection are disjoint and their union is  .

Venn diagram

*-----------------------*
| \        A            |
|  \                    |
|B  *-------------------*
|   /                   |
|  /       C            |
| /         *-----------*  <----- S
|/         /            |
*\        /             |
| *------*              |
|        |    E         |
|  D     |              |
*--------*--------------*

(A,B,C,D and E form a partition of S)

Proposition. (Properties of intersection of sets) Let  ,  and   be sets. Then, the following statements hold.

(a)  ;
(b)   (commutative law);
(c)   (associative law);
(d)   and  ;
(e)  ;
(f)   if and only if  .

Proof. Informally, consider the following Venn diagrams:

(a)
*----*
|    | <---- A ∩ A (a set overlaps itself completely)
|    | <--- A
*----*
(b)
*----------------*
|                | <---- A 
|        *-------*--------*               
|        |A∩B=B∩A|        | 
*--------*-------*        | <--- B
         |                |
         *----------------*
(c)
*----------*
|          | <--- A
|          | 
|     *----*----*
|     |    |    | <---- C
*-----*----*----*------------*
|     |////|    |            | <--- B
|     *----*----*            |
|          |                 |
*----------*-----------------*

*----*
|////| : A∩(B∩C)=(A∩B)∩C
*----*
(d)
*----------------*
|                | <---- A 
|        *-------*--------*               
|        | A ∩ B |        | 
*--------*-------*        | <--- B
         |                |
         *----------------*
(A ∩ B is inside A, and A ∩ B is inside B)
(e)
*----*
|    |
| .  |  
*----*
We use a dot, which has zero area, to represent  . Then, we can see that the intersection of the region and the dot is the dot.

 

Proposition. (Distributive law) Let  ,  and   be sets. Then, the following statements hold.

(a)  ;
(b)  .

Proof.

(a)
*----------*
|          | <--- A
|          | 
|     *----*----*
|     |    |    | <---- C
*-----*----*----*------------*
|/////|////|    |            | <--- B
|/////*----*----*            |
|//////////|                 |
*----------*-----------------*

*----*
|////| : AnB
*----*

*----------*
|          | <--- A
|          | 
|     *----*----*
|     |////|    | <---- C
*-----*----*----*------------*
|     |////|    |            | <--- B
|     *----*----*            |
|          |                 |
*----------*-----------------*

*----*
|////| : AnC
*----*

*----------*
|          | <--- A
|          | 
|     *----*----*
|     |////|    | <---- C
*-----*----*----*------------*
|/////|////|    |            | <--- B
|/////*----*----*            |
|//////////|                 |
*----------*-----------------*

*----*
|////| : (AnB)u(AnC)
*----*

*----------*
|          | <--- A
|          | 
|     *----*----*
|     |////|////| <---- C
*-----*----*----*------------*
|/////|////|////|////////////| <--- B
|/////*----*----*////////////|
|//////////|/////////////////|
*----------*-----------------*

*----*
|////| : BuC
*----*

*----------*
|          | <--- A
|          | 
|     *----*----*
|     |////|    | <---- C
*-----*----*----*------------*
|/////|////|    |            | <--- B
|/////*----*----*            |
|//////////|                 |
*----------*-----------------*

*----*
|////| : An(BuC)
*----*
(b)
*----------*
|//////////| <--- A
|//////////| 
|/////*----*----*
|/////|////|    | <---- C
*-----*----*----*------------*
|/////|////|////|////////////| <--- B
|/////*----*----*////////////|
|//////////|/////////////////|
*----------*-----------------*

*----*
|////| : AuB
*----*

*----------*
|//////////| <--- A
|//////////| 
|/////*----*----*
|/////|////|////| <---- C
*-----*----*----*------------*
|/////|////|////|            | <--- B
|/////*----*----*            |
|//////////|                 |
*----------*-----------------*

*----*
|////| : AuC
*----*

*----------*
|//////////| <--- A
|//////////| 
|/////*----*----*
|/////|////|    | <---- C
*-----*----*----*------------*
|/////|////|////|            | <--- B
|/////*----*----*            |
|//////////|                 |
*----------*-----------------*

*----*
|////| : (AuB)n(AuC)
*----*

*----------*
|          | <--- A
|          | 
|     *----*----*
|     |    |    | <---- C
*-----*----*----*------------*
|     |////|////|            | <--- B
|     *----*----*            |
|          |                 |
*----------*-----------------*

*----*
|////| : B∩C
*----*

*----------*
|//////////| <--- A
|//////////| 
|/////*----*----*
|/////|////|    | <---- C
*-----*----*----*------------*
|/////|////|////|            | <--- B
|/////*----*----*            |
|//////////|                 |
*----------*-----------------*

*----*
|////| : Au(B∩C)
*----*

 

Definition. (Relative complement)

 
Relative complement of   (left) in   (right).

Relative complement of set   in set  , denoted by  , is the set  .

Remark.

  • If   is the universal set and   is a subset of  , then  .
  •   is read 'B minus A'.

Example.

  •  ;
  •  ;
  •  .

Proposition. (Properties of relative complement) Let   and   be sets. Then, the following statements hold.

(a)  ;
(b)  ;
(c)  ;
(d)   if and only if  ;
(e)  ;
(f)  .

Proof.

  •   can be viewed as 'removing' the region of   from the region of  .
(a)
*--*
|A |  removing the whole region <=> empty region left
*--*
(b)
*--*
|A |  removing empty region <=> whole region left
*--*
(c)
.  removing anything from an empty region <=> still an empty region
(d)
*----*
|    | <-- B
*--* |
|A | |    removing B from A becomes empty region <=> region B is not smaller than A
*--*-*
(e)
*-----*
| A\B | 
*-----*-----*
|     | B\A | <--- B
*-----*-----*
   ^
   |
   A
(A\B and B\A are always disjoint)  
(f)
*-----*
|     |
*-----*-----*
|     | B\A | <--- B
*-----*-----*
   ^
   |
   A

(A and B\A are always disjoint)  

 

Theorem. (De Morgan's laws) Let   be sets. Then,

 

Proof.

(only 3 sets involved)
*-------------------------------*
|                    IV         |
|   *---------*                 |
|   |    I    | <--- A_1        | <--- B
|   *---------*-------*         |
|   |    II   | III   |<--- A_2 |
|   *---------*-------*         |
*-------------------------------* 
B\(A_1uA_2)=IV
(B\A_1)=III u IV \
                  ----> intersection: IV
(B\A_2)=I u IV   /

B\(A_1nA_2)=I u III u IV
(B\A_1)=III u IV \
                  ----> union: I u III u IV
(B\A_2)=I u IV   /

 

Remark.

  • If  , then the equations become  .

Example. Let   and  . Then,

  •  ;
  •  ;
*--------------------------*
|   *-------------------*  |
| 5 |///////////////////|  |
|   |/4/*------------*//|  |
|   |///|//////2/////|//|  |
|   |///|/*-------*//|//|  |
|   |///|/| 1    3|//|//|  |
|   |///|/|  AnB  |//|//| <-------- C
|   |///|/*-------*//|//|  |
|   |///|////////////|//|  |
|   |///*------------*//|  |
|   |///////////////////|  |
|   *-------------------*  |
*--------------------------*

*---*
|///| : C\(AnB)
*---*

*--------------------------*
|   *-------------------*  |
| 5 |\.\.\.\.\.\.\.\.\.\|  |
|   |\4\*------------*\.|  |
|   |\.\|.A\B..2.....|\.|  |
|   |\.\|.*-------*..|\.|  |
|   |\.\|.| 1    3|..|\.|  |
|   |\.\|.|   B   |..|\.| <-------- C
|   |\.\|.*-------*..|\.|  |
|   |\.\|............|\.|  |
|   |\.\*------------*\.|  |
|   |\.\\.\.\.\.\.\.\.\.|  |
|   *-------------------*  |
*--------------------------*

*---*
|...| : C\B
*---*
*---*
|\\\| : C\A
*---*
  •  .

Definition. (Power set) Power set   (or  ) of set   is the set of all subsets of  , i.e.,  .

Example.

  •  ;
  •   (power set of an empty set is not an empty set).

Remark.

  • Power set of a set containing   elements contains   elements.

Definition. ( -ary Cartesian product) The  -ary Cartesian product over   sets  , denoted by  , is

 

Example. Let   and  . Then,

  •  ;
  •  ;
  •  .


  1. Extended real number system is obtained by adding   and   to the real number system