Probability/Set Theory

From Wikibooks, open books for an open world
Jump to navigation Jump to search


Introduction[edit | edit source]

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.

Sets[edit | edit source]

Definition. (Set) A set is a well-defined collection of distinct object(s), which are called element(s).

A set.

Remark.

  • If belongs to (or is contained in) a set , we write .
  • If does not belong to the set , we write .
  • When and are equal, denoted by , and are different symbols denoting the same object(s). (When and are not equal, we write , and they are different things.)
  • Because of the vagueness of the term "well-defined", some may not accept this "definition" as a definition of set. Sometimes, a set may be left as a primitive notion, i.e., an undefined term.

Example. (Collection that is not "well-defined")

  • The collection of easy school subjects is not a set, since "easy" is not well-defined.

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:
(the closing brace must also be written.)
For example, .

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

Clipboard

Exercise.

Is an empty set?

Yes.
No.



Example.

  • ;
  • ;
  • .
Clipboard

Exercise.

Select all element(s) belonging to the set .



Example.

  • Let be the set containing all outcomes from rolling a six-faced dice. Then, we can express the set as .
  • Let be the set containing all outcomes from tossing a coin. Then, we can express the set as where stands for "heads" and stands for "tails".
Clipboard

Exercise. Amy participates in a lucky draw where the grand prize is a car. Suppose we say that the outcome is 1 if Amy gets the grand prize, and 0 otherwise, what is the set containing all outcomes?

Solution

The set is .

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 equal ( is used to denote and are not equal).

Example.

  • .
  • .

Example. Let be the set containing all odd outcomes from rolling a six-faced dice. Also, let be the set containing all outcomes that are not even from rolling a six-faced dice. Then, .

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.

Example. The sample space of rolling a six-faced dice is .

Clipboard

Exercise. What is the sample space of tossing a coin? (Use to stand for the outcome "heads" and to stand for the outcome "tails".)

Solution

The sample space is .

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

Remark.

  • A set is said to be finite if it is empty set or it contains elements ( is the set containing all positive integers).
  • Cardinality of set can be denoted by (or ).
  • 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 integer) is an infinite set.
Clipboard

Exercise.

Calculate .

0
1
2
3
None of the above.



Example. Let be the sample space of rolling a six-faced dice and be the set containing all odd outcomes from rolling a six-faced dice. Then, and .

Clipboard

Exercise. A student is asked to show that two sets and are equal in a question of his assignment. In that question, one of the given condition is that . The student then makes the following argument:

Since , it follows that .

Is his argument correct? If not, provides an example of sets and such that but .

Solution

The argument is wrong. We can take, for example, and . Then, but .

Subsets[edit | edit source]

We introduce a relationship between sets in this section.

Definition. (Subset) is a subset of , denoted by if each element of set is an element of set .

Remark.

  • If is not a subset of , then we write .
  • 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  |     |
|   *----------*     |
*--------------------*
  • ().
  • It can be proved that for each set .

Example. Let be the sample space of rolling a six-faced dice and be the set containing all odd outcomes from rolling a six-faced dice. Then, .

Clipboard

Exercise. Let be the set containing all prime outcomes from rolling a six-faced dice. Is a subset of ?

Solution

No, since but .


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

In particular, .

We also have , which is the set containing all extended real numbers, i.e., . Such notation is occasionally used. (Extended real number system is obtained by adding and to the real number system.)

Definition. (Proper subset) A set is a proper subset of set if and ;. We write in this case.

Remark.

  • If a set is not a proper subset of , then we write (but we rarely write this).
  • 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.

  • The set is not a proper subset of itself, i.e., .
  • .

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

Example. If and , then .

Venn diagram:

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

Exercise.

Find .

None of the above.




Set operations[edit | edit source]

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

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

Union of two sets is indicated by the red region.

Remark.

  • is read 'A cup B'.

Example.

  • .

Venn diagram:

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

In the following, some basic properties possessed by the union operation: commutative law and associative law, are introduced.

Proposition. (Properties of union of sets) Let and be sets. Then, we have

(a) (commutative law);
(b) (associative law).

Remark.

  • Because of the associative law, we can write the union of three or more sets without ambiguity. For instance, we can write directly, since .

Example. Let and . Then,

  • .

( means (), and means .)

Definition. (Intersection of sets) The intersection of set and set , denoted by , is the set .

Intersection of two sets.

Remark.

  • is read 'A cap B'.

Example.

  • .
  • .

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

Example. The sets and are disjoint.

Remark.

  • I.e., and are disjoint if they have no element in common.
  • More than two sets are said to be 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)

Proposition. (Properties of intersection of sets) Let , and be sets. Then, we have

(a) (commutative law);
(b) (associative law);

Remark.

  • Likewise, we denote by ().
  • Also, we denote (never ends) by .
  • For (a), the equation can be interpreted as "distributing" into the bracket.
  • For (b), the equation can be interpreted as "distributing" into the bracket.

Example. For every positive integer , defines . Then,

The following result combines the union operation and intersection operation.

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

(a) ;
(b) .

Example. Let and . Verify that the distributive law (a) holds for these three sets, i.e., show that

for these three sets .

Solution. First, . On the other hand, .

Clipboard

Exercise. Verify that the distributive law (b) holds for these three sets.

Solution

First, . On the other hand, .


Definition. (Relative complement) The relative complement of set in set , denoted by , is the set .

The relative complement of (left) in (right) (), given by the red region.

Remark.

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

Example.

  • ;
  • ;
  • .

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

Remark.

  • Special case: If , then the equations become .

Example. Let , and let the universal set be . For these three sets ,

(a) Verify that .

(b) Verify that .

Solution.

(a) First, . On the other hand, . So, we have the desired equality.

(b) First, . On the other hand, .

Clipboard

Exercise. Verify that for these three sets .

Solution

First, . On the other hand, .


Definition. (Power set) The power set of a set , denoted by , 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.

Example. Let be the sample space of tossing a coin ( and stand for "heads" and "tails" respectively). Then,

Clipboard

Exercise. Suppose we toss a coin twice. Then, the sample space of this random experiment is

where means "heads" followed by "heads", means "heads" followed by "tails", etc. Notice that the order matters, and hence is different from .

(a) Find the power set . (Suggestion: check whether your power set contains elements.)

(b) Define the set to be the set containing subsets of that includes the outcome . That is, . Find .


Solution

(a) The power set is

(b) By observing the power set in (a), we can see that 8 subsets (green one) of contains the outcome . So, .

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

Remark.

  • It can be proved that .
  • is ordered, i.e., the order matters for the things inside it.
  • When , is called an ordered pair.
  • It is common to use to denote .

Example. Let and . Then,

  • .
  • .
  • .
Clipboard

Exercise. A restaurant offers a set lunch where the customer can choose one food/drink from each of group A,B,C:

  • group A: egg, beacon
  • group B: steak, salmon
  • group C: tea, milk, water

We define the sets , corresponding to these three groups A,B,C:

(a) Find the set , which contains every possible combination of choices made by the customer.

(b) Suppose the tea in the restaurant is out of stock, so the customer cannot choose tea in group C now. Suppose the set now contains every possible combination of choices made by the customer. What should be the set ? What is the cardinality of the set ?

Solution

(a) The set is given by

(b) The set should be . The cardinality of the set is .