# Probability/Set Theory

## Introduction

editThe 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 **Definition.**
(Set)
A *set* is a well-defined collection of *distinct* object(s), which are called *element(s)*.

**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.

**Exercise.**

**Example.**

- ;
- ;
- .

**Exercise.**

**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".

**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?

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 .

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

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.

- We will leave the cardinality of infinite set undefined in this book, but it

**Example.**

- .
- .
- (the set containing each
*positive*integer) is an infinite set.

**Exercise.**

**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 .

**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 .

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

## Subsets

editWe 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, .

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

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 | | | | | | | *----------* | *-----------------------*

**Exercise.**

## Set operations

editProbability 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 .

**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 .

**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, .

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

First, . On the other hand, .

**Definition.**
(Relative complement)
The *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 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, .

**Exercise.**
Verify that for these three sets .

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.

- See the chapter about combinatorics for a proof of this statement.

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

**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 .

(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,

- .
- .
- .

**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 ?

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