Naive Set Theory: Definitions

Set Algebra

Given two or more sets, we can combine them in different ways in order to create new sets. The three most important methods of doing so are the union, intersection, and set difference operations. These three operations form the basis of set algebra and are ubiquitous in nearly every other field of mathematics.

Unions

The union of two sets is the set that contains all of the elements in both sets and is denoted with the $\cup$ symbol. For example, if $A=\{1, 2, 3\}$ and $B=\{4, 5, 6\}$, then the union of $A$ and $B$ is $A \cup B = \{1, 2, 3, 4, 5, 6\}$. Formally,

$$A \cup B = \{ x : x \in A \text{ or } x \in B \}.$$

Since sets only have one instance of each element, the union of sets that share elements in common only retain a single instance of the shared elements. For example, if $C=\{i, \pi\}$ and $D=\{\pi, 7, 11\}$, then $C \cup D = \{i, \pi, 7, 11\}$; the $\pi$ element common to both sets is only included once in the union.

Set union
Set union of A and B

The union a collection $S$ of sets is the set that contains all the elements of the sets of $S$. Formally,

$$\bigcup S = \{ x : x \in y \text{ for some } y \in S \}.$$

Note that the union of two sets can be redefined in terms of the union of a collection. Namely, $A \cup B = \bigcup \{A, B\}$.

Intersections

The intersection of two sets is the set that contains only those elements that are common to both sets and is denoted with the $\cap$ symbol. For example, $C \cap D = \{\pi\}$. Two sets are said to be disjoint if their intersection is empty (i.e. they share no elements in common). Formally,

$$A \cap B = \{ x: x \in A \text{ and } x \in B \}$$

Set intersection
Set intersection of A and B

The intersection of a single nonempty collection $S$ of sets is the set that contains only those elements that are members of all the sets of $S$. Formally,

$$\bigcap S = \{ x : x \in y \text{ for all } y \in S \}.$$

Note that the intersection of the empty set is intentionally left undefined. The reason for this is a bit philosophical. It is vacuously true that every conceivable object $x$ belongs to each element of $\varnothing$ because there is no element  in $\varnothing$ to which it does not belong. This means that the intersection of the empty set would, weirdly enough, be the set of all possible sets. However, the set of all sets is in fact a paradox. The set of all sets would, by definition, contain those sets that are not members of themselves, which forms Russell's paradox that was noted in the overview. The set of all sets implies many other contradictions as well, but we leave such beard-stroking discussions for another day. The good news is that we can proceed perfectly well by leaving the intersection of the empty set undefined.

Set Difference

The difference of two sets $A$ and $B$ is the set of an elements in $A$ which are also not in $B$, and is denoted with either the $\setminus$ symbol or the $-$ symbol. For example, $C \setminus D = C - D = \{i\}$. Note that the second set does not have to be a subset of the first set. Formally,

$$A \setminus B = A - B = \{ x : x \in A \text{ and } x \notin B \}$$

Set difference
Set difference between A and B

Problems

  1. Calculate the following unions:

    1. $\{ 1, 3, 5 \} \cup \{2, 4, -6\}$
    2. $\{ -3.2, 17, 9 \} \cup \{0, 9, 17\}$
    3. $\{ 1, 10, 100, 1000, 10000 \} \cup \{0, 1, 10, 100, 1000, 10000, 100000\}$
    4. $\{ a, b, q\} \cup \{q, a, b\}$
    5. $\{ 100, 101 \} \cup \varnothing$
    6. $\varnothing \cup \varnothing$
    7. $\{\varnothing\} \cup \varnothing \cup \{1, 4\}$
    1. $\{ 1, 3, 5 \} \cup \{2, 4, -6\} = \{1, 2, 3, 4, 5, -6\}$
    2. $\{ -3.2, 17, 9 \} \cup \{0, 9, 17\} = \{-3.2, 0, 9, 17\}$
    3. $\{ 1, 10, 100, 1000, 10000 \} \cup \{0, 1, 10, 100, 1000, 10000, 100000\} = \{0, 1, 10, 100, 1000, 10000, 100000\}$
    4. $\{ a, b, q\} \cup \{q, a, b\} = \{ a, b, q \}$
    5. $\{ 100, 101 \} \cup \varnothing = \{100, 101\}$
    6. $\varnothing \cup \varnothing = \varnothing$
    7. $\{\varnothing\} \cup \varnothing \cup \{1, 4\} = \{\varnothing, 1, 4\}$
    Show Answer

  2. Calculate the following unions:

    1. $\bigcup \{ \{1, 5 \}, \{\alpha, 7 \}, \{4, \pi, 100\} \}$

    2. $\bigcup \{ \varnothing, \{\varnothing\}, \{\{\varnothing\}\} \}$

    3. $\bigcup \{ \mathbb{N}, \{1\} \}$

    1. $\bigcup \{ \{1, 5 \}, \{\alpha, 7 \}, \{4, \pi, 100\} \} = \{ 1, 4, 5, 7, 100, \pi, \alpha \}$.

    2. $\bigcup \{ \varnothing, \{\varnothing\}, \{\{\varnothing\}\} \} = \{ \varnothing, \{\varnothing\} \}$.

    3. $\bigcup \{ \mathbb{N}, \{1\} \} = \mathbb{N}$.

    Show Answer

  3. Show that $\bigcup (A \cup B) = \bigcup A \cup \bigcup B$

    $ \bigcup (A \cup B) = \{ x : x \in y \text{ and } y \in A \cup B \} \\ \bigcup (A \cup B) = \{ x : x \in y \text{ and } (y \in A \text{ or } y \in B) \} \\ \bigcup (A \cup B) = \{ x : (x \in y \text{ and } y \in A ) \text{ or } (x \in y \text{ and } y \in B) \} \\ \bigcup (A \cup B) = \{ x : x \in y \text{ and } y \in A \} \cup \{ x : x \in y \text{ and } y \in B \} \\ \bigcup (A \cup B) = \bigcup A \cup \bigcup B \\ $

    Show Answer

  4. Calculate the following intersections:

    1. $\{4, 7\} \cap \{7, 9, 3\}$
    2. $\{-2, 2\} \cap \{2, 4\}$
    3. $\{e, \pi\} \cap \{i, 0\}$
    4. $\{a, g, 4, 17e, p\} \cap \{n, q, p, 4, 17f, 9, a\}$
    5. $\mathbb{Z} \cap \varnothing$
    1. $\{4, 7\} \cap \{7, 9, 3\} = \{7\}$
    2. $\{-2, 2\} \cap \{2, 4\} = \{2\}$
    3. $\{e, \pi\} \cap \{i, 0\} = \varnothing$
    4. $\{a, g, 4, 17e, p\} \cap \{n, q, p, 4, 17f, 9, a\} = \{a, 4, p\}$
    5. $\mathbb{Z} \cap \varnothing = \varnothing$
    Show Answer

  5. Calculate the following set differences:

    1. $\{200, 400, 600\} \setminus \{400\}$
    2. $\{1, 50, 100, 250\} \setminus \{50, 100\}$
    3. $\{9000, 4, e\} \setminus \{100, 4\}$
    4. $\{a, b, c\} \setminus \{a, b, g\}$
    5. $\{e, f, g\} \setminus \{, 1, 2, 3\}$
    1. $\{200, 400, 600\} \setminus \{400\} = \{200, 600\}$
    2. $\{1, 50, 100, 250\} \setminus \{50, 100\} = \{1, 250\}$
    3. $\{9000, 4, e\} \setminus \{100, 4\} = \{9000, e\}$
    4. $\{a, b, c\} \setminus \{a, b, g\} = \{ c \}$
    5. $\{e, f, g\} \setminus \{0, 1, 2, 3\} = \{e, f, g\}$
    Show Answer

  6. Show that $A - B = A \cap B^c.$

    $ A - B = \{ x : x \in A \text{ and } x \notin B \} \\ A - B = \{ x : x \in A \text{ and } x \in B^c \} \\ A - B = A \cap B^c $

    Show Answer

  7. Show that for any sets $A$, $B$, and $C$ that $A = (A \cap B) \cup (A - B)$.

    $ (A \cap B) \cup (A - B) = \{ x : (x \in A \text{ and } x \in B) \text{ or } (x \in A \text{ and } x \notin B) \} \\ (A \cap B) \cup (A - B) = \{ x : x \in A \text{ and } (x \in B \text{ or } x \notin B) \} \\ (A \cap B) \cup (A - B) = \{ x : x \in A \} \\ (A \cap B) \cup (A - B) = A \\ $

    Show Answer

  8. De Morgan's Laws: Prove the following:

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

    Remember that to prove $A=B$, we must show that $A \subset B$ and $B \subset A$.

    1. If $x \in (A \cup B)^c$, then $x \not\in (A \cup B)$. Therefore $x \not\in A$ and $x \not\in B$, which means that $x \in A^c$ and $x \in B^c$. Then $x \in A^c \cap B^c$, and thus $(A \cup B)^c \subset A^c \cap B^c$.

      If $x \in (A^c \cap B^c)$, then $x \in A^c$ and $x \in B^c$. It follows that $x \notin A$ and $x \notin B$. Then $x \notin (A \cup B)$, and thus $x \in (A \cup B)^c$. Therefore $(A^c \cap B^c) \subset (A \cup B)^c$.

    2. Let $x \in (A \cap B)^c$, then $x \notin (A \cap B)$. If $x \notin A$, then $x \in A^c$, and therefore $x \in (A^c \cup B^c)$. Alternatively, if $x \notin B$, then $x \in B^c$, and therefore $x \in (A^c \cup B^c)$. In both cases, $x \in A^c \cup B^c$, and therefore $(A \cap B)^c \subset A^c \cup B^c$.

      Let $x \in (A^c \cup B^c)$. Then either $x \in A^c$ or $x \in B^c$. If $x \in A^c$, then $x \notin A$, and therefore $x \notin (A \cap B)$. Alternatively, if $x \in B^c$, then $x \notin B$, and $x \notin (A \cap B)$. In general, then, $x \notin A \cap B$, so $x \in (A \cap B)^c$ and therefore $(A^c \cup B^c)$ \subset $(A \cap B)^c$.

    Show Answer

  9. De Morgan's Laws: Prove the following generalized versions of De Morgan's Laws:

    1. $\left(\bigcap\limits_{C \in \mathcal{C}} C\right)^{c} = \bigcup\limits_{C \in \mathcal{C}} C^c$.

    2. $\left(\bigcup\limits_{C \in \mathcal{C}} C\right)^{c} = \bigcap\limits_{C \in \mathcal{C}} C^c$.

    The $\bigcap\limits_{C \in C}$ and $\bigcup\limits_{C \in C}$ notation is equivalent to $\bigcap \mathcal{C}$ and $\bigcup \mathcal{C}$, respectively, but they let us refer to any given element of $\mathcal{C}$ directly as $C$. This notation is useful for when we want to take the intersection or union of arbitrarily many sets.

    1. Let $x \in \left(\bigcap\limits_{C \in \mathcal{C}} C \right)^c$. Then $x \notin \bigcap\limits_{C \in \mathcal{C}} C$. Therefore there is at least one $C$ such that $x \notin C$. Therefore $x \in C^c$. Since $C^c \subseteq \bigcup\limits_{C \in \mathcal{C}} C^c$, it follows that $x \in \bigcup\limits_{C \in \mathcal{C}} C^c$, so $\left(\bigcap\limits_{C \in \mathcal{C}} C \right)^c \subseteq \bigcup\limits_{C \in \mathcal{C}} C^c$.
      Conversely, let $x \in \bigcup\limits_{C \in \mathcal{C}} C^c$. Then $x \in C^c$ for at least one $C \in \mathcal{C}$. Therefore $x \notin C$. Therefore $x \notin \bigcap\limits_{C \in \mathcal{C}} C$, and thus $x \in \left(\bigcap\limits_{C \in \mathcal{C}} C \right)^c$. Therefore $\bigcup\limits_{C \in \mathcal{C}} C^c \subseteq \left(\bigcap\limits_{C \in \mathcal{C}} C\right)^{c}$. Therefore $\left(\bigcap\limits_{C \in \mathcal{C}} C\right)^{c} = \bigcup\limits_{C \in \mathcal{C}} C^c$.

    2. Let $x \in \left(\bigcup\limits_{C \in \mathcal{C}} C\right)^{c}$. Then $x \notin \bigcup\limits_{C \in \mathcal{C}} C$. Then there is no $C \in \mathcal{C}$ such that $x \in C$. Therefore $x \in C^c$ for all $C \in \mathcal{C}$, so $x \in \bigcap\limits_{C \in \mathcal{C}} C^c$, so $\left(\bigcup\limits_{C \in \mathcal{C}} C\right)^{c} \subseteq \bigcap\limits_{C \in \mathcal{C}} C^c$.
      Conversely, let $x \in \bigcap\limits_{C \in \mathcal{C}} C^c$. Then $x \in C^c$ for all $C \in \mathcal{C}$, which means there is no $C$ such that $x \in C$. Therefore $x \notin \bigcup\limits_{C \in \mathcal{C}} C$, so $x \in \left(\bigcup\limits_{C \in \mathcal{C}} C\right)^{c}$. Thus $\left(\bigcup\limits_{C \in \mathcal{C}} C\right)^{c} \subseteq \bigcap\limits_{C \in \mathcal{C}} C^c$. Therefore $\left(\bigcup\limits_{C \in \mathcal{C}} C\right)^{c} = \bigcap\limits_{C \in \mathcal{C}} C^c$.

    Show Answer

  10. Distributive Laws: Let $A$, $B$, and $C$ all be sets. Prove the following:

    1. $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
    2. $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

    To aid in clarity, we will write these as two column proofs.

    1. First show we show that $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$. Let $x \in A \cup (B \cap C)$.

    $x \in A \lor (x \in (B \cap C))$ Definition of union
    $x \in A \lor (x \in B \land x \in C)$ Definition of intersection
    $(x \in A \lor x \in B) \land (x \in A \lor x \in C)$ Logical distributive property
    $(x \in A \cup B) \land (x \in A \cup C)$ Definition of union
    $x \in (A \cup B) \cap (A \cup C)$ Definition of intersection

    Now we show that $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$. Let $x \in (A \cup B) \cap (A \cup C)$

    $x \in (A \cup B) \land x \in (A \cup C)$ Definition of intersection
    $(x \in A \lor x \in B) \land (x \in A \lor x \in C)$ Definition of union
    $x \in A \lor (x \in B \land x \in C)$ Logical distributive property
    $x \in A \lor (x \in B \cap C)$ Definition of intersection
    $x \in A \cup (x \in B \cap C)$ Definition of union

    2. First show we show that $A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$. Let $x \in A \cap (B \cup C)$.

    $x \in A \land (x \in (B \cup C))$ Definition of intersection
    $x \in A \land (x \in B \lor x \in C)$ Definition of union
    $(x \in A \land x \in B) \lor (x \in A \land x \in C)$ Logical distributive property
    $(x \in A \cap B) \lor (x \in A \cap C)$ Definition of intersection
    $x \in (A \cup B) \cup (A \cup C)$ Definition of union

    Now we show that $(A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)$. Let $x \in (A \cap B) \cup (A \cap C)$

    $x \in (A \cap B) \lor x \in (A \cap C)$ Definition of union
    $(x \in A \land x \in B) \lor (x \in A \land x \in C)$ Definition of intersection
    $x \in A \land (x \in B \lor x \in C)$ Logical distributive property
    $x \in A \land (x \in B \cup C)$ Definition of union
    $x \in A \cap (x \in B \cap C)$ Definition of intersection
    Show Answer