# Probability/Set Theory

## Introduction edit

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

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

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

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

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 edit

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 .

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

*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

(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

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