The mathematics of probability is expressed most naturally in terms of sets. This chapter lays out the basic terminology and reviews naive set theory: how to define and manipulate sets of things, operations on sets that yield other sets, special relationships among sets, and so on. Translating word problems into the language of set theory is crucial in solving logic and probability problems. Venn diagrams are useful for visualizing the relationships among sets. In addition to its crucial role in probability, discussed in set theory is intimately connected to categorical logic, discussed in and to propositional logic, discussed in
A set is a collection of things (called the elements of the set or the members of the set) without regard to their order. We often define sets by listing their contents within curly braces {}. For example, {1, 2, 3} is the set whose elements are the numbers 1, 2, and 3. Another way to define a set is to characterize its elements. For example {x : P(x)} is the set of all values of x for which P(x) is true. (The function P(x) is called the predicate function or membership function. For more discussion, see
Sets usually are defined with respect to a universe of things that contains everything of interest. The symbol S denotes the universe.
Venn diagrams represent sets and the relationships among sets pictorially. A Venn diagram represents the universe S by a two-dimensional region (usually a rectangle or a circle). Sets within S are denoted by closed regions within S. Shading or highlighting is used in Venn diagrams to draw attention to special relationships or sets. Here is a Venn diagram for S.
If x is in the set A we write x∈A, pronounced "x is an element of A" or "x is a member of A." Equivalently, we write A∋x, pronounced "A contains x." If x is not an element of A we write x∉A. Here is a Venn diagram showing S, a set A within S, and a point x∈A.
·x
If the sets A and B have exactly the same elements, we say that the sets are equal and we write A = B. Remember that order does not matter: the set {a, b, c} is equal to the set {c, a, b}, but not to the set {a, b, d} nor to the set {a, b, c, d}.
The complement of the set A (with respect to the universe S), denoted Ac, is the set of all things in S that are not in A. The complement of the set A is pronounced "A complement" or "not A." For instance, if the universe S is the set of living people and A comprises all living people who are over 6' tall, then Ac comprises all living people who are no more than 6' tall. If S is the set of all ravens and A comprises all black ravens, then Ac is the set of all ravens that are not black. The complement of the complement of a set is the original set: (Ac)c = A. The set of all ravens that are not (not black) is the set of all ravens that are black. Here is a Venn diagram illustrating the set Ac. The yellow region is A and the blue region is Ac.
Ac
The set that has no elements is called the empty set. It is denoted {} or φ. The empty set is the complement of the universal set S, and vice versa: Sc = {} and {}c = S. Nothing in S is not in S.
Suppose we have two sets, A and B. If every element of A is also an element of B, we say that A is a subset of B and we write A⊂B or B⊃A. For instance, {1, 2} is a subset of {1, 2, 3}, but {1, 4} is not a subset of {1, 2, 3}. With respect to the universe S of animals, the set of ravens is a subset of the set of birds, but the set of ravens is not a subset of the set of fish. Nor is the set of black birds a subset of the set of ravens, because some black birds are not ravens. Here is a Venn diagram illustrating A⊂B.
Every set is a subset of itself, and the empty set {} is a subset of every set. If A⊂B and B⊂A then A = B: every element of A is an element of B and vice versa. The subset relation is transitive: if A⊂B and B⊂C then A⊂C. For example, all ravens are birds and all birds are animals, so all ravens are animals. The subset relation is reversed by taking complements: if A⊂B then Bc⊂Ac. For example, all ravens are birds, so all non-birds are non-ravens. If something is not a bird it is not a raven.
If A is not a subset of B, we write A⊄B. The not-subset relation is also reversed under complements: if A⊄B then Bc⊄Ac. For example, if some birds are not ravens, then some non-ravens are birds (i.e., not non-birds). Here is a Venn diagram illustrating A⊄B.
Be careful not to confuse a set with its elements. For instance, A ≠ {A}—the former is the thing A while {A} is a set with one element, namely, A. Similarly, while A ∈ {A}, A ⊄ {A}.
The intersection of two or more sets is the collection of elements they all have in common, that is, the set of things contained in each and every one of the sets. For instance, the intersection of the set {0, 1, 2, 3} and the set {1, 3, 5} is the set {1, 3}. The intersection of the set {0, 1, 2, 3} and the set {4, 5, 6} is the empty set, {}. The intersection of the set A and the set B is sometimes written A∩B or AB, and is pronounced "AB", "A and B," "A intersect B" or "A meet B." Here is a Venn diagram illustrating A∩B. The set A is shaded yellow and the set B is shaded blue. The overlap between the two sets, A∩B, is shaded green.
A∩B
The intersection of the empty set and any other set is the empty set: {}∩A = {}. The intersection of the universe S and any other set is that set: S∩A=A. Intersections are associative (A∩(B∩C) = (A∩B)∩C = A∩B∩C) and commutative (A∩B = B∩A). If A⊂B then A∩B = A.
The union of two or more sets is the collection of things that are in at least one of the sets. For instance, the union of the set {0, 1, 2, 3} and the set {1, 3, 5} is the set {0, 1, 2, 3, 5}. The union of the sets {0, 1}, {0, 1, 2}, {0, 1, 2, 3}, and {4, 5, 6} is {0, 1, 2, 3, 4, 5, 6}. The union of the sets A and B is sometimes written A∪B, A+B, or (A or B), and is pronounced "A union B" or "A or B." Here is a Venn diagram for A∪B (shaded blue).
A∪B
The union of the empty set and any other set is that same set: {}∪A = A. The union of the universe S and any other set is the universe: S∪A=S. Unions are associative (A∪(B∪C) = (A∪B)∪C = A∪B∪C) and commutative (A∪B = B∪A). If A⊂B then A∪B = B.
de Morgan's rules are very helpful in untangling complicated relationships among sets. They characterize complements of unions and intersections:
(A∩B)c = Ac∪Bc.
(A∪B)c = Ac∩Bc.
Unions and intersections are associative and commutative with themselves, but not with each other. For instance, A∩(B∪C) is not generally equal to (A∩B)∪C. However, there are rules for combining (distributing) unions and intersections:
A∩(B∪C) = (A∩B) ∪ (A∩C).
A∪(B∩C) = (A∪B) ∩ (A∪C).
Two sets are disjoint or mutually exclusive if their intersection is the empty set; that is, if the two sets have no elements in common. For instance, the sets {1, 2, 3} and {0, 4} are disjoint. In symbols, A and B are disjoint if A∩B = {}. Here is a Venn diagram illustrating that the sets A and B are disjoint:
A collection of sets {A1, A2, A3, … } is disjoint if every pair of sets in the collection is disjoint; that is, the collection is disjoint if AiAj = {} whenever i≠j (i≠j means i is not equal to j). For instance, the sets {1, 2, 3}, {0, 4}, {5}, and {-1, -2, -3, -4} are disjoint, but the sets {1, 2, 3}, {1, 4}, {5}, and {-1, -2, -3, -4} are not. The set of black ravens and the set of white ravens are mutually exclusive. The empty set and any other set are mutually exclusive, because the intersection of the empty set and any other set is the empty set.
Sometimes we need to ensure that every element of some set is in at least one set in a collection of sets. This issue arises in counting and in probability when we want to break a complicated set into smaller pieces and know that we have not lost anything. The corresponding technical term is exhaust. A collection of sets {A1, A2, A3, … } exhausts a set A (the collection is exhaustive of A) if every element of A is in at least one of the sets A1, A2, A3, …; that is, if A is a subset of A1 ∪ A2 ∪ A3 ∪ … . For instance, the sets {1, 2, 3}, {1, 4} {3, 5} and {-1, -2, -3, -4} exhaust the set {2, 3, 4, 5}, but they do not exhaust the set {0, 1, 2}. The set of men, the set of women, and the set of children exhaust the set of people. The set of black ravens and the set of non-black ravens exhaust the set of ravens.
Sometimes we need to ensure that every element of some set is in exactly one set in a collection of sets—and that nothing but members of that set are in the collection. This issue arises in counting and in probability when we want to break a complicated set into smaller parts while avoiding double-counting or counting anything extra. The corresponding technical term is partition. A collection of sets {A1, A2, A3, … } partitions a set A (the collection is a partition of A) if the collection is disjoint, each element Ai of the collection is a subset of A, and the collection exhausts A; that is, if each element of A is in exactly one of the sets A1, A2, A3, … and A = A1 ∪ A2 ∪ A3 ∪ … . For instance, the sets {a}, {b, d}, and {c} partition the set {a, b, c, d}. The set of black ravens and the set of non-black ravens partition the set of ravens.
Useful Properties of Subsets, Complements, Unions and Intersections
If A⊂B and B⊂A then A = B. (If two sets are subsets of each other, they are the same set.)
{}⊂A. (The empty set is a subset of every set.)
{}∪A = A. (The union of the empty set and any other set is that set.)
{}∩A = {}. (The intersection of the empty set and any other set is empty.)
If A⊂B and B⊂C then A⊂C. (The subset relation is transitive.)
If A⊂B then Bc⊂Ac. (Complementation reverses the subset relation.)
A∩B ⊂ A. Moreover, A∩B = A if and only if A⊂B.
A ⊂ A∪B. Moreover, A = A∪B if and only if B⊂A.
(A∩B)c = Ac∪Bc. (de Morgan)
(A∪B)c = Ac∩Bc. (de Morgan)
A∩B = B∩A. (Intersection is commutative.)
A∪B = B∪A. (Union is commutative.)
A∩(B∩C) = (A∩B)∩C. (Intersection is associative.)
A∪(B∪C) = (A∪B)∪C. (Union is associative.)
A∩(B∪C) = (A∩B)∪(A∩C). (Distribution of intersection over union.)
A∪(B∩C) = (A∪B)∩(A∪C). (Distribution of union over intersection.)
The following exercises check your understanding of set membership, equality of sets, complements, unions, intersections, what it means for two sets to be disjoint, for a one set to be a subset of another, and for a collection of sets to exhaust or partition another set.
Examples of Exercises 14-1 to 14-5 (Reminder: Examples and exercises may vary when the page is reloaded; the video shows only one version.)
A random experiment or random trial is basically any situation whose outcome is not perfectly predictable, but for which we can specify all possible outcomes, and that shows long-term regularities. For example, when we toss a coin, we do not know how it will land, but it certainly must land heads, tails, on its edge, or not land at all. There is no other possibility. The set of all possible outcomes of a random experiment is called the outcome space. The letter S will denote outcome space. We are free to choose the outcome space to correspond to what we deem relevant for the experiment, as long as it is essentially inevitable that the random experiment will result in some outcome in the outcome space. For example, the outcome space we just described was {heads, tails, edge, doesn't land}. It might be adequate for our purposes for the outcome space to be {heads, not heads}.
Often we shall tailor outcome spaces for specific problems. Here is an example: Imagine a box containing tickets that are indistinguishable except that each has written upon it a unique number between 1 and the number of tickets, n. We shake the box, draw a ticket from the box without looking, and record the number written on the ticket we happened to draw. The natural outcome space of this experiment is the set of numbers {1, 2, … , n}. However, suppose we are interested only in whether the number on the ticket we draw is even. The outcome space then could be reduced to {even number on ticket, odd number on ticket}, or coded even more abstractly as {0, 1}, where the outcome is the number of even-numbered tickets drawn.
An event is a subset of outcome space: a collection of outcomes in the outcome space. A is an event if A⊂S. For example, in the experiment of drawing a numbered ticket from the box, suppose there are 10 tickets in all, and that we choose the outcome space S to be the numbers {1, 2, 3, … , 9, 10}. Then "we draw the number 1" is the event {1}, and "we draw an even number" is the event {2, 4, 6, 8, 10}, both of which are subsets of the set of possible outcomes, the outcome space S.
Two events are disjoint or mutually exclusive if the occurrence of one is incompatible with the occurrence of the other; that is, if they have no outcome in common. This is equivalent to the definition of disjoint sets, viewing events as sets. The event A implies the event B if A⊂B: then if A occurs, B must also occur (if the outcome that occurs is in A, the outcome that occurs is also in B, because every element of A is an element of B).
contains a Venn diagram that displays the universe S and two subsets of S, A and B. The figure has check boxes on the right side. Checking a box highlights the corresponding set; the options are as follows:
You can click and drag A and B to change the amount by which they intersect. Scrollbars at the bottom of the figure let you change the sizes of A and B. Usually, Venn diagrams do not have a scale, but because this figure is intended to represent the outcome space S, it represents the probability of an event by the area of the event. Probability is never greater than 100%, so the area of S in the diagram is 100%. The area of the subsets of S represents their probability, so the areas of A and of B are between 0% and 100%; these are denoted P(A) and P(B) at the bottom of the figure. The areas of the events A∩B and A∪B are listed in the figure as P(AB) and P(A or B), respectively.
The following exercises check your ability to translate word problems into the language of set theory.
Sets are collections of things without regard to their order. Sets can be specified by listing their elements (the things in the set, also called members) or by giving a property satisfied by their members (and nothing else). The empty set, the set with no members, is {}. Set operations turn sets into other sets. If x is in the set A we write x∈A or A∋x. The complement of a set A, Ac, relative to a "universe" of elements S, is the set of members of the reference universe S that are not in A. The set A is a subset of the set B (A⊂B) if every element of A is also an element of B. If A is not a subset of B, we write A⊄B.
The empty set is a subset of every set. Thus, the statement A⊂B can be true even if neither A nor B has any members. But for A⊄B to be true, A must have at least one member, as must Bc. If A⊂B then Bc⊂Ac and if A⊄B then Bc⊄Ac.
The intersection of the set A and the set B, A∩B (also written A∩B), is the set of things that are in both A and B. If A∩B = A then A⊂B.
The union of the set A and the set B, A∪B, contains every element of A, every element of B, and nothing else. If A∪B = A then B⊂A.
The sets A and B are disjoint or mutually exclusive if they have no elements in common, that is, if A∩B = {}. The collection {A1, A2, A3, … } exhausts A if every element of A is in at least one of the sets in the collection; that is, if A ⊂ A1 ∪ A2 ∪ A3∪ … . The collection {A1, A2, A3, … } is disjoint if AiAj = {} when i ≠ j. The collection {A1, A2, A3, … } is a partition of A if every element of A is in exactly one of the sets in the collection and nothing else is; that is, if the collection is disjoint and A = A1 ∪ A2 ∪ A3∪ … .
Outcome space S is the set of all things that could possibly happen in an experiment. Events are subsets of S. The event A occurs if the outcome of the experiment is an element of A; otherwise, A does not occur. Two events are disjoint or mutually exclusive if they have no outcomes in common—if they are disjoint subsets of S. Disjoint events cannot occur simultaneously. For example, if a coin is tossed, the event that the coin lands "heads" and the event that the coin lands "tails" are disjoint.
Set theory forms the basis of the mathematical study of probability, which we begin in