:Sets and their representation
In any investigation involving set theory, one usually postulates some basic set, or universal set, which consists of all elements to be considered for that problem. This may be the set R of all real numbers, or it may be an abstract set of elements (finite or infinite in number). As a general model, we consider
A basic set S of elements :
Set membership is indicated by ∈ S (this is read, “ belongs to S,” “ is a member of S,” or “ is in S”).
Various subsets of the basic space are represented by:
Capital letters, usually near the beginning of the alphabet (A, B, C, etc.).
Bracket notation with a list of elements in the set; e.g., {1, 2, 3, 4} indicates the set whose members are the elements listed.
Bracket notation with a defining proposition: if π(·) is a proposition which for any is either true or false, the set {: π()} is the set of such that π() is a true statement.
The empty set 
is the set which has no elements.
It is necessary to make a clear distinction between an element and a set of elements. In particular, one must distinguish between the single element and the set {}, which has as member only the single element . In developing the basic probability model in Chap. 2, we let the element represent one of the possible outcomes of a trial or experiment; an event is then a set of such elements. The reader should be warned, however, of an unfortunate anomaly in terminology found in much of the literature. In his fundamental work, Kolmogorov [1933, 1956] used the term elementary event for the elementary outcome ; he uses no specific term for the event {}. Although he does not confuse logically the elementary outcome with the event {}, his terminology is inconsistent at this point. We shall attempt to be consistent in our usage. A little care will prevent confusion in reading the literature which follows Kolmogorov’s usage.
Basic set operations
From given sets, new sets may be obtained by several basic operations.
The union of two or more sets. A ∪ B indicates the set formed by taking all elements that are in A or in B (or both). The idea of the union of sets may be extended to several sets in a straightforward manner.
The intersection of two or more sets. A ∩ B, or AB, indicates the set formed by taking all elements that are in both A and B. The idea of intersection may be extended to several sets.
The complement of a set. Ac indicates the set of those elements of S which are not in A.
In addition to the three operations taken as basic, we add two others which are commonly employed.
The difference of two sets A – B is the set formed by taking all those elements in A which are not in B. Thus A – B = ABc.
The disjunctive union or symmetric difference A ⊕ B of two sets is the set of all elements which are in A but not in B or in B but not in A.
We have A ⊕ B = ABc ∪ AcB = (A – B) ∪ (B – A). Properties of this combination are most readily studied with the aid of the indicator function for sets, introduced in Sec. 2-7.
Fig. B-1 Venn diagrams illustrating basic set relations of union, intersection, and complement.
It is often helpful to make a geometrical representation of sets and their combinations by use of the Venn diagram (also called the Euler diagram, or the Euler-Venn diagram). The basic set S is represented as a region on the plane (or as a discrete set of points located on a given region of the plane). Subsets of the basic space are represented by subregions (or the discrete sets of points located in the subregions). Figure B-1 shows several Venn diagrams. The shaded area in Fig. B-1a represents A ∪ B; that in Fig. B-1b represents AB; the shaded area in Fig. B-1c indicates Ac. Venn diagrams are used in figures throughout the text. A special form of the Venn diagram referred to as a minterm map is developed in Sec. 2-7 (see Figs. 2-7-2 and 2-7-3 for examples).
Basic set relationships
Three types of relationship between sets are useful in developing a theory of sets and set operations.
1. Inclusion. A set A is included in (or contained in) set B (written A ⊂ B or B ⊃ A) iffi each element of set A is also an element of set B. It should be noted that the relation ⊂ is always a relation between sets. It is never correct (or even meaningful) to write 1 ⊂ 2 (where 1 and 2 are elements) or ⊂ A. In the last case we have {} ⊂ A iffi ∈ A.
2. Equality. Sets A and B are equal iffi both A ⊂ B and B ⊂ A. In this case we write A = B.
3. Disjointedness. Two sets A and B are disjoint iffi they have no elements in common; this is equivalent to the condition that the intersection is empty (AB = ). In the case of the union of disjoint sets, it is convenient to have a special symbol. In this book we use the symbol A 
B to indicate the union of two sets, with the further stipulation that the sets are disjoint.
Again, we may use the Venn diagram to give a simple geometrical representation of the basic relationships. In Fig. B-2, we have A ⊂ B, AB = A, AC = , and BC = .
The characterization of sets in terms of propositions implies the following important set relations:
Fig. B-2 Venn diagram illustrating relations of inclusion and disjointedness.
To say that proposition π1(·) implies proposition π2(·) means that if π1() is true for any given , the proposition π2() is also true. From this it is apparent that
A clear grasp of these connections between set relations and logical relations among propositions is an important aid to understanding many relations among events (as sets of elementary outcomes).
Algebra of set operations
A series of simple theorems may be proved which make it possible to construct an algebra of set operations. A basic list is given below. Unless special sets S or are designated or unless there are restrictive conditions, the relations are set identities, in the sense that they hold for any subsets of the basic set S.
(Note that use of the symbol indicates the assertion “the Bk are disjoint.”)
Most of these rules can be given simple geometrical interpretations which are an aid to visualizing and remembering the rules. On the other hand, utilization of these rules makes it possible to modify set expressions by “algebraic” manipulation of the symbols according to these and other rules derived therefrom.
One peculiarity of notational usage in utilizing the symbolic rules of algebra should be pointed out. We use A ∩ B or AB alternatively to indicate set intersection, just as we use a · b or ab alternatively to indicate multiplication of numbers. In writing sums of products, some problems of grouping may arise. The expression a · b · c + d · e is ambiguous. It could mean (a · b · c) + (d · e). It could just as well mean a · (b · c + d · e) or one of the other possible expressions derived by a different grouping of characters. When we write abc + de, however, common usage reads this as (abc) + (de). Adjacent placing of several factors without the multiplication sign is intended to indicate a grouping of the factors which are juxtaposed. In a similar manner we shall deal with set intersection. Whereas the expression A ∩ B ∩ C ∪D ∩ E is ambiguous, the expression ABC ∪ DE is read with the following grouping: (A ∩ B ∩ C) ∪ (D ∩ E). Ordinarily, there is no difficulty in utilizing this scheme. Where there is danger of misinterpretation, use should be made of parentheses, brackets, or braces as grouping symbols in the manner familiar from ordinary algebra.
Cartesian product of sets
Consider two basic sets S and U with ∈ S and 
∈ U. A new type of set may be constructed by considering all ordered pairs (, ), where ∈ S and ∈ U. Each such pair is considered an element in the (cartesian) product set S × U. The fundamental model for this construction is the plane, considered as the cartesian product of two real lines. Real numbers are represented as points on the real lines (coordinate axes). Pairs of real numbers may then be considered as points on the plane. If R1 represents one coordinate axis (i.e., one coordinate of a point on the plane is a number represented by a point on this line) and R2 represents the other coordinate axis, the plane then becomes the cartesian product space R1 × R2. In keeping with this geometrical model, the sets S and U in the abstract case are called coordinate sets (or spaces). The concept of a cartesian product may be extended in a natural way to the product of several coordinate sets. If S, U, and V are such sets, one may make several constructions. One may take the cartesian product S × U to form a new space. Then this new space may be combined with V to form (S × U) × V. Or U and V could be combined to form U × V, and then a second combination S × (U × V) could be made. Or one could simply take S × U × V, in which case each element is a triple consisting of one element each from S, U, and V in that order. For most purposes, it is convenient and useful to identify the three spaces in a natural way. If ∈ S, ∈ U, and ζ ∈ V, then points from the three product spaces are [(, ), ζ] [, (, ζ)], and (, , ζ), respectively. It is apparent now that these can be considered identical.
A wide variety of subsets can be described by conditions on the coordinates of the points in a cartesian product space. One of the simplest is the rectangle set. Suppose the two basic spaces are S1 and S2 and that subsets in these sets are indicated by corresponding subscripts. The set A1 × A2 is the set of all pairs (, ) such that ∈ A1 and ∈ A2. The sets A1 and A2 may be quite complicated subsets of the coordinate spaces. These are not the most general subsets of the product space, however. For example, the union of two or more rectangle sets is not necessarily a rectangle set. Examples of rectangle sets on the plane are found in Figs. 3-5-2, 3-7-1, and 3-7-2.
A number of rules of combination for rectangle sets are easily proved and are often useful in dealing with these sets. Some of the more useful are
These may be interpreted in terms of sets on the plane. The coordinate sets A1, B1 are sets on one of the coordinate axes, and the coordinate sets A2, B2 are sets on the other coordinate axis. The validity may be argued from definitions, without regard to geometrical interpretations, however.
Classes of sets
The basic concept of a set is that of a collection of elements. It is desirable to deal also with collections of sets, that is, sets of sets. In order to prevent verbal confusion, it is customary to use the term class of sets (or perhaps family of sets) to indicate such a collection. If A, B, C are members of a given class 
, we say A ∈ , B ∈ , and C ∈ . The sets A and B may stand in the relationship A ⊂ B. We do not say A ∈ B or A ⊂ . It is, however, correct to say ⊂ 
, when is a class such that every set in is also in .
The term countable class may refer to either a finite class or a countably infinite class. A class is countably infinite iffi its members can be put into a one-one correspondence with the positive integers (natural numbers). A class is countable iffi its index set J is countable; it is finite iffi its index set J is finite.
A convenient notation for classes of sets uses subscripts to identify various sets in the class and a bracket notation as follows:
This is read, “ is the class of all those sets Ai such that i is a member of the index set J.” Subclasses of the set may be indicated by the choice of suitable subsets of the index set J. Thus
The first statement means that every set in class 0 is also in class ; the second statement means that every index i in J0 is also in J.
The concepts of union and intersection may be extended to general classes, as follows:
Ai is the set of all elements in at least one of the sets Ai in the class 
Ai is the set of all elements in every set of the class {Ai: i ∈ J}.
It is apparent that if the class contains only two sets, these definitions coincide with those for the union and intersection of two sets.
The rules on complements under (8) in the list of set operations above may be extended to general classes as follows:
An alternative notation is frequently useful. If = {Ai: i ∈ J} is any class of sets, we may denonte 
Ai by 
and 
by 
. Other variations may be used. These are generally described when used or are clear from the context.
These basic rules are known as DeMorgan’s rules.
A class is said to be a disjoint class if no two sets in the class have any point in common. This implies that the intersection of every subclass of sets must be empty. In the case of disjoint classes, we may use a special symbol for the union, as follows:
implies the stipulation that the class is disjoint
It is not incorrect to use the ordinary symbol for the union of a disjoint class. The use of the special symbol, however, indicates the union plus the assertion that the class is disjoint. An example of this usage is given (somewhat prematurely) in proposition (12) among the theorems on Algebra of Set Operations.
Sequences of sets
Sequences of sets are countable classes which are indexed by the integers or by some subset of the integers such as the positive integers or by the integers {1, 2, …, n} for some finite n. The members of a sequence can be put in natural order, according to the ordering of the integers in the index set. We speak of infinite sequences and finite sequences of sets in an obvious way. It is often convenient to designate sequences by one of the following notational schemes, according to the situation:
In the case of a sequence, the concept of a limit can be introduced in a natural and useful manner. Suppose = {Ai: 1 ≤ i < ∞}. The superior limit of the sequence, written lim sup Ai, is the set of all those elements which belong to Ai for an infinite number of the i in the index set. The inferior limit, written lim inf Ai, is the set of all those elements which belong to all but a finite number of the Ai. It should be apparent that any in A* = lim inf Ai must also be in A* = lim sup Ai; that is, A* ⊂ A*.
If belongs to an infinity of the Ai, for every n it must belong to the union of all those Ai for which i ≥ n. If it belongs to such a union for every n, it must clearly belong to an infinity of the Ai. Hence
If belongs to all but a finite number of the Ai, there must be some n such that belongs to Ai for all i ≥ n; that is, there must be some n such that belongs to the intersection of all the Ai for which i ≥ n. On the other hand, if belongs to such an intersection, it must belong to all but a finite number of the Ai. Thus
If the superior limit and the inferior limit are the same set, the common set is called the limit of the sequence, written lim Ai. If the sequence is monotone, that is, either monotone-increasing (Ai ⊂ Ai+1, all i) or monotone-decreasing (Ai ⊃ Ai+1, all i), the limit always exists and is given by the following formulas:
Monotone-increasing: 
Monotone-decreasing: 
These formulas can be derived from the formulas for lim sup Ai and lim inf Ai by the use of the special conditions, with their implications for the unions and intersections.
Fields and sigma fields
Various operations on sets (notably the formation of unions, of intersections, and of complements) have been introduced. These operations produce resultant sets which are usually different sets, although in some cases they may be the same set. In the diccussion of events as sets in Chap. 2, it is shown that the union or intersection of countable classes of events or the complement of an event must be an event for the model to be satisfactory. This means that the class 
of events, as a class of sets, must have the property that the formation of unions or intersections of countable subclasses and the formation of complements of individual sets must produce resultant sets within the class of events.
Definition.
A class of subsets of the basic space S is said to be closed under an operation on sets iffi the application of this operation to appropriate sets or subclasses of sets always yields a set in .
Thus, the class of events must be closed under the operations of forming countable unions, countable intersections, and complements (three distinct operations). Various types of classes may be defined by specifying closure under certain collections of operations.
We consider two such types of class. First we make the
Definition.
A nonempty class of sets is called a field of sets iffi it is closed under i) finite unions and ii) complements.
This means that if A1, A2, …, An are all members of so is the set 
. Also, Aic is a member of for any i. Since 
, it follows that a field is closed under finite intersections. It is clear that the empty set and the basic space S always belong to a field. Other names for a field are an algebra of sets or an additive class of sets.
If we have a whole family of fields of sets, the intersection of these classes will be nonempty and will form a field. If we begin with any nonempty class 
of sets and consider all the fields which include , their intersection will be the minimal field which contains .
The minimal field 
which includes a nonempty class is called the field generated by .
If is itself a field, then it is identical with its generated field.
Fields play an important role in developing basic probability theory. One often begins by assigning probabilities to members of a field, then extending the definition to a more general class of events. We consider, next, such classes.
Definition.
A nonempty class of sets is called a sigma field iffi it is closed under i) countable unions and ii) complements.
Just as in the case of a field, it follows that a sigma field is closed under the formation of countable intersections. These are the properties needed for a class of events. In a formal development of probability theory, the class of events is taken to be a sigma field of subsets of the basic space S. Again, we have for any nonempty class a minimal sigma field of sets which contains , called the sigma field generated by . Alternate terms found in the literature for sigma fields are Borel fields and completely additive classes.
Borel sets
The discussion above considers sigma fields on any abstract space. In dealing with real-valued or vector-valued random variables, we are concerned with sets of numbers viewed as points on the real line, or with sets of points on euclidean spaces of various dimensions. The Borel sets on the line appear as the sigma field generated by the intervals on the real line. Actually, any one of several classes of intervals may be taken as the generating class. One may begin with a class composed of all finite intervals of any specified one of the types (a, b), (a, b], [a, b), or [a, b], where a and b are any two real numbers with a ≤ b. One may also begin with the class of semi-infinite intervals (– ∞, a], or with the class consisting of intervals (– ∞, a).
Suppose one of the classes of intervals is taken as a starting point. The generated class then contains all intervals in any of the other classes, since an interval of any one type can be obtained by a countable number of operations of union, intersection, and complementation upon sets of any one of the other kinds (see Example 3-1-5 for an illustration of this conversion). Simple arguments show that the generated classes for each of the interval types must be identical.
Extensions to sets in euclidean spaces of higher dimension are straightforward. A variety of types of intervals may serve as the basis for the generating class, but they lead to the same generated completely additive class. It is apparent, in the case of Borel sets in the plane, that this class contains all rectangle sets whose coordinate sets are Borel sets on the real line. Also, the class of Borel sets in the plane has as members all sets obtained by performing a countable number of operations of taking unions, intersections, and complements of rectangle sets of the kind just described.
