Set Theory

Set theory is the study of sets or collections of items. This includes concepts and terms like sample space, mutually exclusive, disjoint, unions, events, intersections, etc…  and related symbols like $\cup$ or $\in$. Set theory is relevant in helping you understand probabilities, and specifically how to set up your problem so you can calculate the correct probability of an event.  This can be useful, especially during interviews, as a lot of brain teasers involve probability calculations. Set theory can also enlighten some concepts in other areas of statistics when we start to divide things into partitions. Finally, the notations used in set theory are prevalent throughout math and statistics.

With that said, set theory is pretty theoretical and can be hard to understand initially. Additionally, a lot of set theory just seems like a bunch of semantics. Because of this, in the grand scheme of things, outside of learning the symbols, set theory is not that important of a concept and you could potentially skip it.

The bulk of this page will cover symbols and terminology.  The terminology is a bit less important than the symbols. Note that within set theory, we make the distinction between a set and an event.  Depending on if something is viewed as a set or an event, the interpretation will slightly differ.  Interpreting things as events will be more relevant when we talk about probabilities.

Terminology

Experiment: In statistics, an experiment, is a process in which outcomes can be determined ahead of time.  For example, an experiment could be flipping a coin and the outcomes could be heads or tails.


Event: An event is a set of possible outcomes of an experiment.  For example, different events when rolling a single die could be, rolling a 1, rolling an even number, rolling 5 or 6, etc…  The difference between an outcome and an event is that an event usually is a collection set of outcomes.

As mentioned before, there also is a difference between events and sets.  While both sets and events contain outcomes, an event usually implies that something can occur (and often has an associated probability), and a set is purely a list of outcomes. Note that events can contain sets and sets can contain events.


Sample Space: A sample space is all the possible outcomes of an experiment.  For example, the sample space for tossing 2 coins is: $S = [HH, HT, TH, TT]$.  By definition, a sample space is also either a set or an event. Note: Don’t let the word sample confuse you as it is not really related to “sample” when we talk about sample versus population.  


Empty Set: An empty set is more of a theoretical concept and exists for conceptual reasons.  Similar to philosophy, where if there is being, then there is nothingness, in math, if there are sets, then there are empty sets. Previously, we talked about a set or space containing items, outcomes, or elements. An empty set is just a set that does not contain any elements or members and is denoted as $\emptyset$.  If we view an empty set as an even rather than a set, an empty set represents an event that is impossible or cannot occur. You may sometimes see an empty set referred to as a null set.

By definition $\emptyset \subset A$ where $A$ is any arbitrary event. 

Complement: A complement of set, $A$,  is another set that contains all the elements that are not in the set $A$.  The notation for a complement of set $A$ is usually a superscript c, and thus the complement is $A^c$.  Just like most terms here, the interpretation for complement changes depending on if you view it as a set or an event.  When it comes to events, $A^c$ can be thought of as the event that $A$ does not occur.  When it comes to sets, as mentioned already, $A^c$ can be thought of as a set that includes all the items not in $A$.

For example, if we are talking about rolling a die, and we define $A$ as the event where we roll a 1 or 2, then $A^c$ is the event of rolling a 3, 4, 5, or 6.

It also goes without saying that the following properties hold:

$(A^c)^c) = A$

$\emptyset^c = S$ where $S$ is the sample space

$S^c = \emptyset$

$(A_1 \cup A_2)^c = A_1^c \cap A_2^c$

$(A_1 \cap A_2)^c = A_1^c \cup A_2^c$


Union: A union of two sets or events is denoted as $\cup$.  If $A_1$ and $A_2$ are sets, we can think of $A_1 \cup A_2$ as the combination of the items within the two sets (without any repeats – i.e. we eliminate double counting).  For example if:

$A_1 = [1, 2, 3, 4]$

$A_2 = [3, 4, 5]$

$A_1 \cup A_2$ = [1, 2, 3, 4, 5]$  Note how we don’t include 3 and 4 twice.

If we think in terms of events, the interpretation of $\cup$ is similar.  If $A_3$ and $A_4$ are events, we can think of $A_3 \cup A_4$ as the event that either one or both of the events occur.  In other words, we can also think of $A_3 \cup A_4$ as the event that at least one event occurs.  This includes the event that both $A_3$ and $A_4$ occur. The difference between treating $A$ as an event as opposed to a set becomes more clear when we assign probabilities to the events.  For example, let’s consider a die roll again.  

$A_3 = rolling\, a\, 1,\, 2,\, 3,\, or\, 4$

$A_4 = rolling\, a\, 3,\, 4,\, or\, 5$

$A_3 \cup A_4 = rolling\, a\, 1,\, 2,\, 3,\, 4,\, or\, 5$

If we associate probabilities with each event, then $Pr(A_3 \cup A_4)$ is the probability of rolling a 1, 2, 3, 4, or 5.

By definition, the following hold for all sets and events:

$A_1 \cup A_2 = A_2 \cup A_1$

$A_1 \cup A_1 = A_1$

$A_1 \cup A_1^c = S$ where $S$ is the sample space

$A_1 \cup \emptyset = A_1$

$A_1 \cup S = S$ where $S$ is the sample space

$A_1 \subset A_2 = A_2$, this says that $A_1$ is a subset of $A_2$

$A_1 \cup A_2 \cup A_3 = (A_1 \cup A_2) \cup A_3 = A_1 \cup (A_2 \cup A_3)$, this is the associative property


Intersection: The intersection of two sets or events is donated by $\cap$. Like with unions, depending on if $A$ is an event or set, the interpretation differs. When it comes to sets, $A_1 \cap A_2$ means the common items in both sets.  In other words $A_1 \cap A_2$ is a set that contains items that show up in both $A_1$ and $A_2$.

For example, if $A_1$ and $A_2$ are sets:

$A_1: [blue,\, red,\, green]$

$A_2: [green,\, pink,\, purple]$

$A_1 \cap A_2: [green]$

When it comes to events, $A_1$ and $A_2$ means the situation where both events occur.  When we start looking at probabilities, Pr($A_1$ and $A_2$) will mean the probability that both events occur.  This is also known as the joint probability.

By definition, we have the following properties:

$A_1 \cap A_2 = A_2 \cap A_1$

$A_1 \cap A_1 = A_2$

$A_1 \cap A_1^c = \emptyset$

$A_1 \cap \emptyset = \emptyset$

$A_1 \cap S = A_1$, where S is the sample space

If $A_1 \subset A_2$ then $A_1 \cap A_2 = A_1$

$A_1 \cup A_2 = A_2 \cup (A_1 \cap A_2^c)$

$A_1 \cap A_2 \cap A_3 = (A_1 \cap A_2) \cap A_3 = A_1 \cap (A_2 \cap A_3)$, per the associative property

$A_1 \cap (A_2 \cup A_3) = (A_1 \cap A_2) \cup (A_1 \cap A_3)$, per the distributive property

$A_1 \cup (A_2 \cap A_3) = (A_1 \cup A_2) \cap (A_1 \cup A_3)$, per the distributive property

There are also some formulas for joint probabilities, which I will introduce in the probabilities section.


Disjoint:  In some texts, this is the same thing as mutually exclusive.  When it comes to sets, two disjoint sets means there are no common elements between the two.  You can think of it as there is no overlap. When it comes to events, two disjoint events means that it is impossible for the two events to occur at the same time.  There does not seem to be symbol for disjoint and so the most common way to notate two disjoint events or sets is $A_1 \cap A_2 = \emptyset$


Partitioning:  Partitioning is where we split a set or sample space into 2 or more disjoint sets where the union of all the sets equals the original set or sample space.  For example, let $S$ be a sample space. We can partition $S$ into n disjoint subsets so that:

$S = (A_1 \cap S) \cup (A_2 \cap S) \cup \dots \cup (A_n \cap S)$  

If we partition a set into only two partitions, we can think of it in terms of complements since the two partitions must be disjoint by definition of complements.  That is:  

$A_1 = (A_1 \cap A_2) \cup (A_1 \cap A_2^c)$

Symbols

$\in$: This symbol translates to “an element of” or “a member of” or “belongs to”.  If we have $A \in S$, this means A is a member of or an element of S. For example, if $A = rolling\, a\, 1$, then $A \in S$ where $S$ is the sample space of rolling a die.  This symbol along with $\notin$ and variations of the symbols pop up quite frequently in statistics.


$\notin$: This is just like the above except it translates to “not an element of” or “not a member of” or “does not belong to”.


$\subset$: This symbol translates to “a subset of”.  Some texts may say “is contained in” but that can be somewhat misleading.  The difference between $\subset$ and $\in$ is important. I will provide an example so that it may be more clear.  Let’s define the following where [] denotes a set of items:

$A_1 = [2, 3]$

$A_2 = [2, 3, 4, 5]$

$A_3 = [2, [3, 4], 5]$

$A_4 = [[2, 3], [3, 4], 2, 3, 4, 5]$

In the above, $A_1 \subset A_2$ since $A_1$ is a subset of $A_2$.  However, $A_1 \notin A_2$ since while $A_1$ is composed of values in $A_2$, $A_1$ is strictly not a member of $A_2$.  Also, $A_1 \notin A_3$. However, $A_1 \in A_4$ since it is a member of $A_4$. Also note that $A_2 \in A_4$, but $A_2 \notin A_3$ and $A_2 \not\subset A_3$.

Finally, note that $A_1 \notin A_1$ but $A_1 \subset A_1$.  This is by definition.

Some additional properties of $\subset$ include:

Given event or set $A_5$ and $A_6$, if $A_5 \subset A_6$ and $A_6 \subset A_5$, then $A_5 = A_6$

$A_5 \in A_6 = A_6 \ni A_5$, the symbol $\ni$ means the same thing as $\in$ just backwards.


$\not\subset$: You can probably guess that this means “not a subset of”.


$\emptyset$: This symbol means an empty set.


$^c$: This is the symbol used for a complement of something.  For example, the complement of event $A$ is denoted as $A^c$.


$\cup$: This is used to indicate the union of two events or sets.   If $A_1$ and $A_2$ are events, then $A_1 \cup A_2$ is the event that either one or both of the events occur.  If $A_1$ and $A_2$ are sets, then $A_1 \cup A_2$ is the combination of both sets not including repetitions.


$\bigcup$: This represents the union of many sets or events.  For example:

$\bigcup_{i = 1}^5 A_i = A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5$

In the above i ranges from 1 to 5, and thus expanding the expression on the left out leads to the right hand side.  The notation is just like $\sum$, which you have likely seen before. For these large symbols, at the bottom of the symbol we usually have something like ${i = 1}$. This tells you two things. First, $i$ is the value that will be changing. Second, the lowest value $i$ will take on is 1. At the top of a large symbol, we will usually have another number, which in this case is 5. This is the highest number $i$ will take on. That is, $i$ counts from from 1 to 5 in increments of 1 (increments of 1 is standard). For example:

$\bigcup_{i = 5}^10 A_i$ means we start at $A_5$ and end at $A_10$

$\bigcup_{i = 1}^n A_i$ means we start at $A_1$ and end at $A_n$

Interpreting $\bigcup$ is just like interpreting $\cup$.  For sets, we combine all items within each set without repetition.  For events, it is the event that either one or some combination of the events occur.  Another way to think of this is the event that at least one of the events occur.


$\cap$: This is used to indicate the intersection of sets or events.

For example, if $A_1$ and $A_2$ are sets, then $A_1 \cap A_2$ means the common elements in both sets.  If $A_1$ and $A_2$ are events, then $A_1 \cap A_2$ means the situation where both events occur.


$\bigcap$: This represents the intersection of many sets or events.  Like before, the value at the bottom is the start of the range and the value at the top is the end of the range.  We usually increase by integers. For example:

$\bigcap_{i = 1}^5 A_i = A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5$

Thus, if $A_i$ are sets, then $\bigcap_{i = 1}^5 A_i$ can be interpreted as the common elements across all 5 of the sets.  If $A_i$ are events, then $\bigcap_{i = 1}^5 A_i$ can be interpreted as the situation where all 5 events occur.

GO BACK | CONTINUE

No comment yet, add your voice below!


Have a suggestion, question, or found an error?