The basic flow of the probability pages goes like this:
- Probability Definitions
- Set operations (this page)
- Probability axioms
- Counting: Permutations & combinations
- Conditional probability
- Independence of events
- Bayesian probability
Sets
In our work in probability theory, we'll be using a lot of sets, so it's prudent to know as much as we can about them, their properties and how to combine and compare them.
A set is a collection of distinct elements. In probability, those elements will usually be outcomes of some probability experiment, like the numbers that can turn up when rolling dice. Here are some examples of sets in different notations:
$\{a, \, b, \, c, \, d\}$ is a set with a finite number of elements, four in this case.
$\mathbb{R}$ or $\{ \mathbb{R} \}$ is the infinite set of all real numbers. Its members are uncountable. The infinite set of integers can be written as $\{1, 2, 3, \dots \}.$
$\{ x \in \mathbb{R}: \, cos(x) \gt \frac{1}{2} \}$ is the set of all real numbers with cosines larger than ½. The proper way to read this statement is "The set of all numbers that are elements of the set of real numbers, such that the cosine of the number is greater than ½."
Finally, we can represent sets with diagrams. The set S of elements x2, x2, and so on, can be represented like this:
We'll use the Greek capital letter omega, Ω, to represent a universal set to which all other sets belong. Thus our set S lies within Ω like this:
In the set S, we say that element x1 is an element of S like this:
$$x \in S$$
We can use a similar notation to show that an element is not an element of a set. Our set S is $\{x_1, x_2, x_3, \dots , x_{10} \},$ which does not contain an element labeled a, so we write
$$a \notin S$$
We will later write the probability of obtaining outcome x1 from set S as $P(x_1).$
Disjoint sets, like sets A and B in the Venn diagram below, share no elements.
Conjugate sets (!S) and the empty set
Sticking with our set S from above, we can also generate a set
$$!S \phantom{0000} \text{or} \phantom{0000} S^C$$
which represent everything not in set S. The notation $!S$ can be read as "not S", and $S^C$ means "the conjugate of set S." In terms of a diagram, the set $\{ !S \}$ is the gray area outside of set S and inside of Ω
Now using this notation, we can make some important statements. First, let's note that we use the symbol $\in$ to mean "is in" or "is an element of". Likewise, the symbol $\notin$ means "is not in" or "is not an element of." Then a set element xn is a member of the set $!S,$ if it is in the set Ω, and it is not in the set S, or
$$x \in !S \phantom{00} \text{if} \phantom{00} x \in \Omega \phantom{00} \text{and} \phantom{00} x \notin S.$$
Second, in keeping with our notion that a double negative is a positive [such as -(-3) = 3], we have
$$!(!S) = S.$$
The empty set, a set with no elements, is denoted $\{ \phantom{00} \}$ or $\emptyset$, and we note that:
$$\Omega^C = \emptyset \phantom{00} \text{or} \phantom{00} !\Omega = \emptyset , $$
which is to say that everything is in the universal set, Ω, and nothing is outside of it.
Subsets
A subset is a set entirely contained within another. For example, the set $\{a, b, c \}$ is a subset of the set of all lower-case letters, or a subset of $\{a, b, c, d, e, f \}.$ We write
$$\{a, b, c \} \subset \{a, b, c, d, e, f \}.$$
Later, the question of how many different n-element subsets can be made out of an m-element set will be a central one in our exploration of probability. (In the example above, n = 3 and m = 6.)
In the Venn diagram
we have $B \subset A,$ and we note that
$$\text{If} \; x \in B, \; \text{then} \; x \in A.$$
Also, a set is always a subset of itself: $B \subset B.$
Unions and intersections
A union of two sets is the set formed when the two are combined. In set notation, the union of sets $\{a, b, c\}$ and $\{d, e, f \}$ is the new set $\{a, b, c, d, e, f \}.$ We generally write a union like this:
$$\{a, b, c\} \cup \{d, e, f \} = \{a, b, c, d, e, f \}.$$
In Venn diagrams, two sets, A and B look like this:
The union of these sets is just the set made of the two combined:
Notice that x is an element of the union of sets A and B, if and only if x is an element of set A or x is an element of set B. Here is a more compact version of that statement:
$$x \in (A \cup B) \phantom{0} \text{iff} \phantom{0} x \in A \phantom{0} \text{or} \phantom{0} x \in B.$$
The symbol $\cup$ means "union." The notation iff is just a mathematical abbreviation for the phrase "if, and only if."
The intersection of two sets, A and B, is the set that is formed from elements that are in both sets. For example, the intersection of sets $\{a, b, c\}$ and $\{a, b, d, e\}$ is the set $\{a, b\}$ because elements a and b are in both sets. We write
$$\{a, b, c\} \cap \{a, b, d, e\} = \{a, b\},$$
where the symbol $\cap$ means "intersection."
Here is the Venn diagram picture:
Notice that if set element x can be an element of sets A and B if and only if x is an element of A and x is an element of B. In mathematical language, that is
$$x \in (A \cap B) \phantom{0} \text{iff} \phantom{0} x \in A \phantom{0} \text{and} \phantom{0} x \in B.$$
Some properties of sets
Unions
When we're using unions of sets, order of the expression $A \cup B$ doesn't matter.
$$A \cup B = B \cup A$$
Multiple unions
$$A \cup (B \cup C) = (A \cup B) \cup C$$
Here is a Venn diagram explanation of that property:
This kind of rule can be extended to any number of sets.
Intersections
The intersection of a set with the union of two other sets can be written as
$$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$
This looks like the distributive property of multiplication. Let's illustrate this property with an example. Take the sets $A = \{a, b, c\},$ $B = \{a, b, e\}$ and $C = \{c, d, f\}.$ Now:
$$ \begin{align} \{a,b,c\} &\cap (\{a,b,e \} \cup \{c,d,f\}) \\[5pt] &= \{a,b,c\} \cap \{a,b,c,d,e,f\} \\[5pt] &= \{a,b,c\} \end{align}$$
AND
$$ \begin{align} \{a,b,c\} &\cap (\{a,b,e \} \cup \{c,d,f\}) \\[5pt] &= (\{a,b,c\} \cap \{a,b,e\}) \cup (\{a,b,c\} \cap \{c,d,f\}) \\[5pt] &= \{a,b\} \cup \{c\} \\[5pt] &= \{a,b,c\} \end{align}$$
Other properties
Double negation: $!(!A) = A.$
The union of any set that is a subset of the universal set, Ω, and the universal set is just the universal set: $S \cup \Omega = \Omega.$
The intersection between a set and its complement is the empty set: $S \cap !S = \emptyset,$ or $S \cap S^C = \emptyset.$
The intersection of a set contained within the universal set with the universal set is just that set: $S \cap \Omega = S.$
DeMorgan's laws
DeMorgan's laws relate intersections and unions of sets. First let's see what they are, then we'll prove each of them pictorially below.
$$ \begin{align} !(A \cup B) &= \; !A \cap !B \\[5pt] !(A \cap B) &= \; !A \cup !B \end{align}$$
DeMorgan's laws are sometimes stated like this:
- The complement (the "not") of the union of two sets is the same as the intersection of their complements.
- The complement of the intersection of two sets is the same as the union of their complements.
These important laws link unions and intersections of sets. This will be crucial later on in probability theory, and we will refer back to DeMorgan's laws when we get there.
Below are two visual illustrations of DeMorgan's laws using Venn diagrams. They're worth staring at a bit. Further down you'll find a full algebraic proof of one of them.
$!(A \cup B) = \; !A \cap !B$
In the Venn diagrams above, the left hand side of Demorgan's law, $!(A \cup B) = !A \cap !B$ is illustrated. The blue oval is set A, the green set B. Their complements, !A and !B are also shown. The blue-green blob is the union, $A \cup B.$ The dark gray space in the third diagram is the set $!(A \cup B).$
In this set of Venn diagrams, we focus on the right side of this version of DeMorgan's first law, $!A \cap !B.$ The sets !A and !B are shown in light gray. If we stack them on top of one another, the dark-gray area in the right-hand diagram shows the overlap or intersection. Notice that this is the same as the dark-gray area in the set of figures above.
$!(A \cap B) = \; !A \cup !B$
In the Venn diagrams to the left, we show the intersection of sets A and B $(A \cap B),$ in blue-green. All other parts of the set Ω are shown in gray in the right-had panel.
In the set of Venn diagrams below, we superimpose the sets !A and !B. The resulting dark gray area, the set $!A \cup !B$ is the same as the gray area above, so this shows that $!(A \cap B) = \; !A \cup !B.$
Algebraic proof of $!(A \cap B) = !A \cup !B$
First, consider any x that is in the set !(A ∩ B). We then realize, by the definition of the complement ( ! ), that x is not in the set (A ∩ B):
Let $x \in !(A \cap B),$ then $x \notin (A \cap B).$
Now because (A ∩ B) is the set of all elements that are in both A and B (x ∈ A and x ∈ B) it must be true that x is either in set A or set B:
Because $A \cap B, \; x \notin A \text{ or } x \notin B.$
Then if x ∉ A, then x ∈ !A, so x ∈ [!A ∪ !B] because the set {!A ∪ !B} includes !A.
If $x \notin A,$ then $x \in !A,$ so $x \in {!A \cup !B}$
Similarly, if x ∉ B, then x ∈ !B, so x ∈ {!A ∪ !B}.
This means that for every x that is in {!A ∩ !B}, x ∈ !A ∪ !B. That is,
$$!(A \cap B) \subset \{!A \cup !B\}.$$
Well, now that's not enough to prove our assertion, because proving that one thing is a subset of another does not show equality. We can prove the reverse assertion by contradiction. First, let x ∈ {!A ∪ !B}, and assume that x ∉ !(A ∩ B). If that is true, then
$$x \in \{A \cap B \}$$
Then it follows that x ∈ A and x ∈ B, thus
$$x \notin !A \text{ and } x \notin !B.$$
However, that means that
$$x \notin \{!A \cup !B\},$$
which is a contradiction to our assumption that x ∈ {!A ∪ !B}. Therefore it is not true that x ∈ !(A ∩ B). Therefore
$$x \in !(A \cap B).$$
Therefore we find that for all x that are in the set {!A ∪ !B}, x ∈ {!(A ∩ B)}. That is:
$$!A \cup !B \subset !(A \cap B)$$
Finally, if
$$!A \cup !B \subset !(A \cap B) \text{ and } !(A \cap B) \subset {!A \cup !B},$$
then $!(A \cap B) = !(A \cup B).$
The other DeMorgan's equation can be proved in a similar way.
DeMorgan's laws: Compact notation
DeMorgan's laws can be extended to unions and intersections of more than one set. For this we often use a more compact notation, akin to summation notation. For example, the union
$$A_1 \cup A_2 \cup A_3$$
can be written as
$$\bigcup_{i=1}^3 \, A_i.$$
The large ∪ symbol means to repeatedly take the union of sets labeled Ai as the index i runs from 1 to 3, inclusive, in integer steps.
If we leave off the indices (the n = 1 and 3 parts), the open union just means to sum over all of the sets being considered.
Now we can write one of DeMorgan's laws as
$$!\left( \bigcap_i A_i \right) = \bigcup_i \, A_i$$
Likewise, the other law can be written
$$!\left( \bigcup_i A_i \right) = \bigcap_i \, A_i.$$
Practice problems
| 1. |
A universal set, Ω, is $\Omega = \{ 1,2,3,4,5,6,7 \}.$ Given that $A = \{1,2\},$ $B = \{2,4,5\},$ and $C = \{1,5,6,7\},$ write the following sets:
SolutionHere is a Venn diagram of this scenario. Notice that while the element 3 is in the universal set, it is not in any of its subsets.
From the diagram, we can easily see:
Now to prove DeMorgan's law: $$(A \cup B) = 2, \; \text{ so } !(A \cup B) = \{3,6,7 \}$$ $$ \begin{align} !A &= \{3,4,5,6,7 \} \\[5pt] !B &= \{1,3,6,7 \} \\[5pt] !A \cap !B &= \{3,6,7\} \end{align}$$ These are the same, so the law is verified for this case. |
| 2. |
Define these sets:
Write these sets:
Solutionsa. $A \cap B = \{11,17\}$ b. $!A = \{10,12,14,16,18,20\}$ c. $A \cup B = \{11,13,14,15,17,19,20\}$ d. $!B = \{10,12,13,15,16,18,19\}$ |
| 3. |
Let $A = \{\text{red}, \text{orange}, \text{yellow}, \text{green}, \text{blue}, \text{indigo}, \text{violet} \},$ $B = \{\text{violet}, \text{blue}, \text{green}, \text{yellow}, \text{orange}, \text{red}\},$ and $C = \{\text{white}, \text{black}, \text{red}\}.$ Write:
Solutiona. $(A \cap A) = \{\text{red}, \text{orange}, \text{yellow}, \text{green}, \text{blue}, \text{indigo}, \text{violet} \}$ b. $(A \cup B) = A \; \text{ because } \; B \subset A$ c. $(A \cap C) = \{ \text{red}\}$ d. $(A \cup C) = \{\text{red}, \text{orange}, \text{yellow}, \text{green}, \text{blue}, \text{indigo}, \text{violet}, \text{white}, \text{black}\} $ e. $(B \cap C) = \{\text{red}\}$ f. $(B \cup C) = \{\text{violet}, \text{blue}, \text{green}, \text{yellow}, \text{orange}, \text{red}, \text{white}, \text{black}\}$ |
| 4. |
Which of these are true?
Solutionsa (and b). If A is a subset of B, then $A \cup B = B.$ That means that (b) is true. This Venn diagram might help:
c. If $A \subset B$ and $B \subset C$ then $(A \cup B) \subset C$ To prove statements like these it's often useful to consider elements of the sets. Let $x \in (A \cup B),$ then either $x \in A$ or $x \in B.$ Now If $x \in A,$ then because $A \subset C, \; x \in C.$ If $x \in B,$ then because $B \subset C, \; x \in C.$ If $x \in C$ then we've proved (c) to be true. If $A \subset B$ and $B \subset C,$ then $A \subset C$ d. Let $x \in A.$ Then because $A \subset B,$ we know that $x \in B.$ We can follow a similar set of steps to show that $x \in C.$ This Venn diagram might help:
e. If $(A \cup B) = A,$ then $B \subset A$ Notice that if $x \in A,$ then $x \in (A \cup B),$ therefore the fact that $x \in A$ means that $B \subset A$ because all of the elements of B are in A. f. If $A \cap B = \{ \}$ and $B \cap C = \{ \},$ then $A \cap C = \{ \}.$ $A \cap B = \{ \}$ means that sets A and B don't intersect. The same is true for sets B and C because $B \cap C = \{ \}.$ But this doesn't guarantee that sets A and C don't intersect. Consider this Venn diagram, which shows that it's possible:
|
Axiom
An axiom is a statement that is self-evidently true, accepted or long-established, but which can't necessarily be proven so. A famous axiom is Euclid's first postulate, also known as the transitive property: "Things that are equal to the same thing are equal to each other," or If a = b and c = b, then a = c.
Induction
When we reason inductively, or use induction to reason, we extend a pattern. The sun has risen every day of my life, so I'm reasonably confident it will rise again tomorrow. That's induction. To extend a series like 2, 4, 6, 8, x, by concluding that x = 10 is also induction.
Axiom
An axiom is a statement that is regarded as being true or established, or self-evidently true. Axioms cannot be proven.
A fundamental axiom is the transcendental property: Things that are equal to the same thing are equal to each other, or if a = b and c = b, then a = c.
Theorem
A theorem is a general proposition in mathematics or other forms of reasoning that may not be self-evident, but can be proved by a chain of reasoning based on things that are already known to be true.
xaktly.com by Dr. Jeff Cruzan is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. © 2012, Jeff Cruzan. All text and images on this website not specifically attributed to another source were created by me and I reserve all rights as to their use. Any opinions expressed on this website are entirely mine, and do not necessarily reflect the views of any of my employers. Please feel free to send any questions or comments to jeff.cruzan@verizon.net.