Sets and Algebra of Sets

Set

Sample Space

sample space

a set describing all possible outcomes of a random experiment

I use $S$ to denote a sample space, but $\Omega$ is another common choice. I draw a sample space $S$ as a rectangle, where you are to believe that there are all possible outcomes contained within the rectangle.

Sample Space

subset

$A$ is a subset of $B$ if all elements of $A$ are also elements of $B$

We write $A \subset B$ and read this as $A$ is a subset of $B$. The set $B$ is referred to as a superset of $A$.

For the picture above, $A \subset B \subset S$, which is to say that $A \subset B$ and further $B \subset S$. If $A$ might be equal to its superset $B$, the symbol $\subseteq$ could be used. This symbol is analogous to $\leq$; for two numbers $x \leq y$, it might be the case that $x=y$.

Sometimes there is no benefit from referencing the sample space, $S$, and so pictures may exclude the sample space altogether.

Subset

intersection

TODO do better: the set of elements in both the first set and the second set

Example.

Let $A = \{ 1, 2, 3 \}$ and $B = \{2, 4, 6 \}$. Then $A \cap B = \{ 2 \}$.

The symbol used for intersection is $\cap$, sometimes called cap.

Intersection is a binary operation, much like addition $+$. Intersection is a binary set operation, meaning it operates on two sets. One set written on the left of $\cap$ and one set written on the right.

Example.

Let $A = \{ a, e, i, o, u \}$ and $B = \{g, u, i, t, a, r \}$. Then $A \cap B = \{ a, u, i \}$.

One can take the intersection of more than two sets, even though the operation technically works two sets at a time. The notation is $$\bigcap_{n=1}^N A_n = A_1 \cap A_2 \cap \ldots \cap A_N$$ for sets $A_1, A_2, \ldots, A_N$.

Intersection

A set doesn't necessarily contain any elements. In relation to intersection, two sets need not have any elements in common.

empty set

the set that contains no elements

One symbol used for the empty set is $\emptyset$, which is distinct from the Greek letter $\phi$. Another way to write the empty set is with two curly braces and nothing between them $\{ \}$.

Example.

Let $A = \{ a, e, i, o, u \}$ and $B = \{l, y, n, x \}$. Then $A \cap B = \{ \}$.

Intersection

union

TODO do better: the set of elements in either the first set or the second set

The symbol for union is $\cup$, sometimes called cup.

Example.

Let $A = \{ e, o, w, n \}$ and $B = \{ y, r, k \}$. Then the union of $A$ and $B$ might be written $A \cup B = \{n, e, w, y, o, r, k \}$.

Notice the keyword or in the definition union. What do you think is the keyword in the definition of intersection, separating the definitions of union and intersection?

Empty Set

subset

a set where every element in the smaller set is contained in a larger set

The symbol for subset is $\subset$.

Example.

Let $S$ represent all letters of the English alphabet. The vowels $V = \{a, e, i, o, u \}$ are a subset of $S$, $V \subset S$.

Example.

Let $\mathbb{N}$ represent the natural numbers. The even numbers $E = \{2 * n : n \in \mathbb{N} \}$ are a subset of $\mathbb{N}$, $E \subset \mathbb{N}$.

Note that the word subset generally refers to the smaller of two sets. The word superset generally refers to the bigger.

If the subset is possibly equal to the superset, then the symbol $\subseteq$ is sometimes used.

Union

complement

TODO do better, what base set? the set of elements not in the base set

Many different symbols are used for the set complement. If $A$ is the base set, then the complement of $A$ might be written as $A^c$, $A^{\complement}$ $A'$, or $S \setminus A$. The last can be more specifically called the relative complement or the set difference and is important when reference to a superset, say $S$, contributes useful information. Think of the set difference as starting with the superset $S$ and then removing or subtracting out all of the elements of $A$.

Example.

Let $S$ represent all the letters of the English alphabet. Let $V$ represent all the vowels. The set $V^c$ then represents all the consonants.

Complement

A partition is easy to see, but takes a few definitions to write down rigorously.

Example.

TODO insert picture

We state two definitions before giving the definition of partition.

disjoint

two sets are disjoint when their intersection is the empty set

exhaustive

a collection of sets whose union equals the complete space

partition

a collection of sets which are non-empty, (mutually) disjoint, and exhaustive of a superset

Example.

Let $S = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$. A partition of $S$ is $$\Bigl \{ \{0, 1 \}, \{2 \}, \{3, 4, 5, 6, 7 \}, \{8, 9 \} \Bigr \}$$

Partition

Complement (set theory). Wikipedia: The Free Encyclopedia. Wikimedia Foundation, Inc. Accessed 2023-09-08.

Intersection. Wikipedia: The Free Encyclopedia. Wikimedia Foundation, Inc. Accessed 2023-09-08.