Naive Set Theory: Definitions

Set Operations

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\}$.

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.

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 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

  7. 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

  8. 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