Naive Set Theory: Definitions

Subsets and Power Sets


subset is a set whose elements are all elements of another set. For example, the set $X = \{a, b, c\}$ is a subset of the set $Y = \{a, b, c, d, e, f\}$, because each element in $X$ is also in $Y$. $X$ and $Y$ are in turn both subsets of the set $Z = \{a, b, c, d, e, f, x, y, z \}$. If a set $A$ is a subset of a set $B$, we express this as $A \subseteq B$, and we call $B$ a superset of $A$.

It is important not to confuse elements and subsets. Symbolically, $A \subseteq B$ is not the same as $A \in B$. Of all the tricky concepts in math, this one the one that, for some reason, every math resource feels the almost metaphysical urge to warn everyone about not screwing up. Not polynomial time reductions, triple integrals, or even when you're supposed to include the negative solution in a square root problem. No, it's not confusing elements and subsets. So, there you go, you've been delivered the obligatory pre-flight instructions to not confuse elements and subsets.

Two sets are equal if each is a subset of another. If $A \subseteq B$ and $B \subseteq A$, then $A = B$. Think about it - if all the elements in $A$ are also in $B$, and all the elements in $B$ are also in $A$, then the two sets have the same elements.

A set $A$ is a proper subset of a set $B$ if $A$ is a subset of $B$ but $A \neq B$. Formally, if $A$ is a proper subset of $B$, we write this as $A \subset B$. Improper subsets are subsets that can be equal to the other set in question, although this is the default meaning of "subset," so specifying a subset as an improper subset is only done in the context of explicitly contrasting it with a proper subset.

Note: The notation for subsets and proper subsets is a bit of a pain point in mathematics. The plain $\subset$ symbol has historically meant any subset, rather than a proper subset. Even the LaTeX macro for it is "\subset". However, the less than and less than or equal to signs, < and $\leq$, are even more well known (since everyone who even gets to set theory knows the less than sign). Having $\subset$ include equality while < precludes it, and having $\subseteq$ preclude equality while $\leq$ allows it is inconsistent and confusing. Therefore, by order of the realm, Mathmatique, the council of elders, the UN Security Council, and the Peaky Blinders, $\subset$ shall stand for proper subset, and $\subseteq$ shall stand for improper subset.

The complement of a subset $B$ of a set $A$ is the set of all elements in $A$ that are not in $B$, and is denoted by annotating the subset with a $c$ "exponent". Formally, if $B \subset A$, then

$$B^c = \{ x : x \in A \land x\notin B \}$$

Note that the complement of a set is only well defined in the context of a superset. For example, what is the complement of the set $A = \{1, 2, 3\}$? A simple definition might be "everything not in $A$," but this means that every possible thing and idea in the world (except $1$, $2$, and $3$) is in $A^c$, including all kinds of paradoxical mumbo jumbo. Thus one must insist on stating the intended superset of a set in order to have any meaningful discussion about its complement.

The power set of a set $A$ is the collection $\mathcal{P}(A)$ whose members are all of the possible subsets of $A$. Formally, $\mathcal{P}(A) = \{ x : x \subseteq A \}$.

For example, if $A = \{1, 2\}$, then $\mathcal{P}(A) = \{ \varnothing, \{1\}, \{2\}, \{1, 2\} \}$. Note that $\varnothing$ and $A$ are always elements of $\mathcal{P}(A)$, because $\varnothing$ is a subset of every set, and $A$ is always a subset of itself.

Power sets are useful for proving and understanding all kinds of meaningful relationships between sets. For example, a power set always has "more" elements in it than the set it's generated from. The word "more" is put in scare quotes here because the very notions of "more" and "less" turn out to be surprisingly tricky concepts that will be rigorously defined later on. Our intuitive notions of more and less work well for sets whose elements we can count, but break down when we consider more exotic, "bigger" sets.


Problems

  1. Consider the set $X=\left\{e,i,\pi\right\}$. Determine whether the following statements are true:

    1. $e \in X$
    2. $\{e,i\} \in X$
    3. $\{e\} \in X$
    4. $\{\pi\} \subset X$
    5. $\{\pi, i\} \subset X$
    6. $\varnothing \in X$
    7. $\{\varnothing\} \in X$
    1. True: $e$ is an element of $X$

    2. False: The set containing $e$ and $i$ is not in $X$. But $\{e,i\}$ is a subset of $X$.

    3. False: The set containing $e$ is not an element of $X$. Note that the set containing $\{e\}$ is not the same as $e$ itself.

    4. True: The set containing $\pi$ is a subset of $X$.

    5. True: The set containing both $\pi$ and $i$ is a subset of $X$.

    6. False: The empty set is not an element of $X$. It is, however, a subset of $X$.

    7. False: The set containing the empty set is not an element of $X$.

    Show Answer
  2. Let $A = \{ 2, 3, 5\}$. List out all of the possible subsets of $A$.

    • $\varnothing$
    • $\{2\}$
    • $\{3\}$
    • $\{5\}$
    • $\{2,3\}$
    • $\{2,5\}$
    • $\{3,5\}$
    • A
    Show Answer
  3. Show that the empty set, $\varnothing$, is a subset of every set.

    Proof 1: Let $S$ be an arbitrary set. The empty set $\varnothing$ is a subset of $S$ if all of its members belong to $S$. Since there are no elements in $\varnothing$, it is vacuously true that $\varnothing \subset S$.

    Proof 2: This proof requires knowing a bit about set subtraction. Let $A$ be a set and let $B$ be a subset of $A$. It holds that $(A \setminus B) \subset A$. Therefore $(A \setminus A) = \varnothing \subset A$.

    Show Answer
  4. Transitivity of Subsets: Let $A, B, \text{ and } C$ be sets such that $A \subseteq B$ and $B \subseteq C$. Show that $A \subseteq C$.

    Let $a \in A$. Because $A \subseteq B$, it follows that $a \in B$. Because $B \subseteq C$, it follows that $a \in C$. Therefore $A \subseteq C$.

    Show Answer
  5. Determine if the following statements are true or false:

    1. $\mathbb{Z} \subset \mathbb{R}$
    2. $\mathbb{R} \subset \mathbb{C}$
    3. $\mathbb{R} \subset \mathbb{R}^2$
    4. $\mathbb{R}^2 \subset \mathbb{R}^3$
    5. $\mathbb{R}^2 \subset \mathbb{C}$
    1. True: Every integer is also a real number.

    2. True: Every real number is also a complex number.

    3. False: $\mathbb{R}^2$ consists of ordered pairs of real numbers, which are not the same as real numbers.

    4. False: Likewise, pairs of real numbers are not the same as triplets of real numbers.

    5. False: Continuing the trend, ordered pairs of real numbers are not the same as complex numbers.

    Show Answer
  6. Let $A=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$. Calculate the set complements for the following subsets of $A$:

    1. $\{3, 5, 7\}^c$
    2. $\{1, 2, 3, 4, 5\}^c$
    3. $\{x \in A : x \text{ is even} \}^c$
    4. $A^c$
    5. $\varnothing^c$
    1. $\{3, 5, 7\}^c = \{1, 2, 4, 6, 8, 9, 10\}$
    2. $\{1, 2, 3, 4, 5\}^c = \{6, 7, 8, 9, 10\}$
    3. $\{x \in A : x \text{ is even} \}^c = \{1, 3, 5, 7, 9\}$
    4. $A^c = \varnothing$
    5. $\varnothing^c = A$
    Show Answer
  7. Provide a counterexample to this incorrect statement: Because the power set of a set contains both the empty set and the set itself, power sets always have at least two elements.

    The empty set has no elements, so the only subset of the empty set is the empty set itself. Thus the power set $\mathcal{P}(\varnothing) = \{\varnothing\}$ has only one element.

    Show Answer
  8. Trichotomy Law: Prove that for any two sets $A$ and $B$, at most one of the following holds:

    • $A \subset B$

    • $A = B$

    • $B \subset A$

    To prove that at most one condition holds, we must show that the truth of one necessarily precludes the truth of the others.

    First assume $A \subset B$. Then there is some element $x \in B$ such that $x \notin A$. Therefore $B \not\subseteq A$, and therefore $A \neq B$ and $B \not\subset A$. Next, assume $A = B$. Then $A \not\subset B$, as otherwise there would be an element in $B$ that was not in $A$, which would mean $B \not\subseteq A$, contradicting $A = B$. Last, assume $B \subset A$. Then as in the first case, there is some element $x \in A$ such that $x \notin B$. Therefore $A \not\subseteq B$, and therefore $A \neq B$ and $A \not\subset B$.

    Show Answer