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

 
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.

 

Exercise.

Is   an empty set?

Yes.
No.



Example.

  •  ;
  •  ;
  •  .
 

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

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  .

 

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.
 

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  .

 

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

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  ?

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

Exercise.

Find  .

 
 
 
 
None of the above.




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  .

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

 

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

 

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,

 
 

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,

  •  .
  •  .
  •  .
 

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  .