The review of set theory contained herein adopts a naive point of view. We assume that the meaning of a set as a collection of objects is intuitively clear. 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. A set is a collection of objects, which are the elements of the set.
If an element belongs to a set , we express this fact by writing . If does not belong to , we write . We use the equality symbol to denote logical identity. For instance, means that are symbols denoting the same object. Similarly, the equation states that are two symbols for the same set. In particular, the sets contain precisely the same elements. If are different objects then we write . Also, we can express the fact that are different sets by writing .
A set is a subset of if every element of is also contained in . We express this relation by writing . Note that this definition does not require to be different from . In fact, if and only if and . If and is different from , then is a proper subset of and we write .
There are many ways to specify a set. If the set contains only a few elements, one can simply list the objects in the set;
The content of a set can also be enumerated whenever has a countable number of elements,
Usually, the way to specify a set is to take some collection of objects and some property that elements of may or may not possess, and to form the set consisting of all elements of having that property. For example, starting with the integers , we can form the subset of S consisting of all even numbers
More generally, we denote the set of all elements that have a certain property by
The braces are to be read as the words "the set of" whereas the symbol | stands for the words "such that." It is convenient to introduce two special sets. The empty set, denoted by , is a set that contains no elements. The universal set is the collection of all objects of interest in a particular context, and it is denoted by . Once a universal set is specified, we need only consider sets that are subsets of . In the context of probability, is often called the sample space.
The complement of a set , with respect to the universal set , is the collection of all objects in that do not belong to ,
Probability theory makes extensive use of elementary set operations. Below, we review the ideas of set theory, and establish the basic terminology and notation. Consider two sets .
The union of sets is the collection of all elements that belong to or (or both), and it is denoted by . Formally, we define the union of these two sets by
The intersection of sets is the collection of all elements that are common to both and . It is denoted by , and it can be expressed mathematically as
When have no elements in common, we write . We also express this fact by saying that are disjoint. More generally, a collection of sets is said to be disjoint if no two sets have a common element. A collection of sets is said to form a partition of if the sets in the collection are disjoint and their union is .
The difference of two sets, denoted by or , is defined as the set consisting of those elements of that are not in ,
This set is sometimes called the complement of relative to , or the complement of in .
We have already looked at the definition of the union and the intersection of two sets. We can also form the union or the intersection of arbitrarily many sets. This is defined in the obvious way,
Given a collection of sets, it is possible to form new ones by applying elementary set operations to them. As in algebra, one uses parentheses to indicate precedence. For instance, denotes the union of two sets , while represents the intersection of two sets .The sets thus formed are quite different.
Sometimes different combinations of operations lead to the same set. For instance, we have the two distributive laws
Two particularly useful equivalent combinations of operations are given by De Morgan's laws, which state that
These two laws can be generalized to
when multiple sets are involved. To establish the first equality, suppose that belongs to . Then is not contained in . That is, is not an element of for any . This implies that belongs to for all , and therefore . We have shown that . The converse inclusion is obtained by reversing the above argument. The second law can be obtained in a similar fashion.
There is yet another way to create new sets form existing ones. It involves the notion of an ordered pair of objects. Given sets , the cartesian product is the set of all ordered pairs for which is an element of and is an element of ,