Set theory in a nutshell

Set theory is an elegant framework often used in probability theory. So here is a small refresher.

Consider $m$ different objects $o_1,..., o_m$, of which we select some. To be concrete, assume that the $m$ objects are the numbers $1$ to $10$, and the selected objects are the numbers from $1$ to $6$. The set $A$ with the elements $1,2,...,6$ is denoted by

Equality of sets

The order of occurrence is not important, and identical objects count only as one, so we have

In other words, to sets are equal, if the contain the same elements, no matter how often they occur.

Special sets

• The empty set is the set that contains no element, and is denoted by

  $$\{ \}$$

• The set $S$ containing all the $m$ elements, $S=\{1,2,3,...,10\}$ is called the universal set.

Magnitude

The magnitude of $A$ is the number of different elements in $A$, and is denoted by $\vert A\vert$, so we have

Set relations

• The number $5$ is an element of $A$, written

  $$5\in A$$

  while the element $7$ is not an element of $A$, written

  $$7\not\in A$$

• Any selection of elements of $A$, such as $1,2,4$, is a set as well, and is called a subset of $A$, written

  $$\{1,2,4\} \subset A$$

  But

  $$\{1,4,2,7\} \not\subset A$$

  Note that every set is its own subset, $A\subset A$, and the empty set is always a the empty set is always a subset, $\{ \} \subset A$. The set $A$ is also a subset of $S$.

Set operations

Given two subsets $A$ and $B$ of $S$, we can form a new set, which correspond to the logical statements NOT, AND, and OR:

• The complement of $A$, written

  $$A^c\,\text{or }A^\prime\text{ or }\overline{A}$$

  is the set of elements in $S$ that are NOT in $A$. In a Venn-diagram, this is set is represented by the region outside of circle $A$.

• The intersection of $A$ and $B$, written

  $$A\cap B$$

  is the set of elements that is in $A$ AND in $B$. In a Venn-diagram this set is represented by the intersection of the two circles $A$ and $B$.

• The union of $A$ and $B$, written

  $$A\cup B$$

  is the set of elements that is in $A$ OR in $B$. In a Venn-diagram this set is represented by the union of the two circles $A$ and $B$.

  

Disjoint subsets

We say that two sets $E$ and $F$ are disjoint if they do not intersect, that is, if

We say that the subsets $E, F$ and $G$ are pairwise disjoint if each pair is disjoint, that is, $E \cap F=\{\}$, $E \cap G=\{\}$, $F \cap G=\{\}$. Clearly, disjoint and pairwise disjoint subsets do not have elements in common (see figure below).

It is straightforward to generalise this to an arbitrary number of events.

Partitions

Consider $m$ subsets $A_1, A_2, ... A_m$ of $S$. We say that these subsets form a partition of $S$, if the subsets are pairwise disjoint:

and the union of these subsets is $S$:

The Venn-diagram looks like a puzzle.

Here are two partitions of $S=\{1,2,3,4,5,6\}$:

• $\{1\},\{2\},\{3\},\{4\},\{5\},\{6\}$
• $\{1\},\{2,3,4,5\},\{6\}$

Exercise 1

Q1

$S=\{1,2,3,4,5,6,7,8,9,10\}$, $A=\{1,3,5,8\}$, and $B=\{2,5,10\}$.

1. Determine the sets $A\cap B$, $A\cup B$, $A^\prime$, $A\cap B^\prime$ and $A \cup B^\prime$.
2. Is $3\in B$?
3. Is $B\subset A$?

Q2

$A$ is a subset of the universal set $S$. Determine $\{ \}^\prime$, $S^\prime$, $A\cup A^\prime$, $A\cap A^\prime$, and $(A^\prime)^\prime$.

Q3

Consider two sets $A$ and $B$ with $A\subset B$. Determine $A\cap B$ and $A\cup B$.

Q4

Consider the universal set $S$ and two subsets $A$ and $B$ of $S$. Do the following subsets form a partition of $S$?

1. $A$ and $A^\prime$
2. $A\cap B, A^\prime\cap B, A\cap B^\prime$ and $A^\prime\cap B^\prime$

Hint: draw the Venn-Diagram.

Q5

Show that for any two subsets $A$ and $B$ in $S$ the following is true:

$$\vert A\cup B\vert = \vert A\vert +\vert B\vert -\vert A\cap B\vert$$

Simplify the formula for the case where $A$ and $B$ are disjoint.

Hint: draw the Venn-Diagram.

Q6

Assume that $A_1,...,A_m$ is a partition of $S$. Show that

$$|A_1|+|A_2|+...+|A_m|=|S|$$

Q7

Show that

1. $(A\cup B)^\prime = A^\prime \cap B^\prime$

2. $(A\cap B)^\prime = A^\prime \cup B^\prime$

Solution

A1

1. $A\cap B=\{ 5\}$, $A\cup B=\{1,2,3,5,8,10 \}$, $A^\prime=\{2,4,6,7,9,10\}$, $A\cap B^\prime=\{ 1,3,8\}$ and $A \cup B^\prime=\{ 1,3,4,5,6,7,8,9\}$
2. $3\not\in B$
3. $B\not\subset A$.

A2

$\{ \}^\prime=S$, $S^\prime=\{ \}$, $A\cup A^\prime=S$, $A\cap A^\prime=\{ \}$, and $(A^\prime)^\prime=A$

A3

$A\cap B=A$ and $A\cup B=B$

A4

See figure below.

1. Yes
2. Yes

A5

See figure below.

If $A$ and $B$ are disjoint, it is $\vert A\cap B\vert =0$, and therefore

$$\vert A\cup B\vert = \vert A\vert +\vert B\vert$$

A6

It is a generalisation of A5. Because $A_1$, ..., $A_m$ do not overlap, it is

$$|\underbrace{A_1 \cup A_2 \cup ... \cup A_m}_{=S}| = |A_1|+|A_2|+...+|A_m|$$

But the union of these sets is $S$. Thus, it is

$$|A_1|+|A_2|+...+|A_m|=|S|$$

A7

See figure below.