Subsets and Equality of Sets

# Subsets and Equality of Sets

Consider two sets $A$ and $B$. Suppose that every element $x \in B$ is also contained in $A$, that is $x \in B$ implies that $x \in A$. For example, consider the set $A = \{1, 2, 3, 4, 5\}$ and the set $B = \{ 1, 2, 3 \}$. Clearly every element in $B$ is contained in $A$.

 Definition: If $A$ and $B$ are sets such that every element of $B$ is contained in $A$ then we say that $B$ is a Subset of $A$ denoted $B \subseteq A$. If $B$ is not a subset of $A$ then we write $B \not \subseteq A$.

By definition every set has itself as a subset, called the "Whole Subset", that is, for every set $A$ we have $A \subseteq A$ regardless of what elements are in $A$. Furthermore, the empty set $\emptyset$ is conventionally defined to be a subset of all sets. These sets are both considered to be trivial subsets.

Of course, sometimes we are interested in subsets which are not the whole subset or empty set which we defined below.

 Definition: If $A$ and $B$ are sets such that every element of $B$ is contained in $A$ and such that there exists an element $x \in A$ where $x \not \in B$ and $B \neq \emptyset$ then $B$ is said to be a Proper Subset of $A$ denoted $B \subset A$. If $B$ is not a proper subset of $B$ we write $B \not \subset A$.

The set $B = \{ 1, 2, 3 \}$ is a proper subset of $A = \{ 1, 2, 3, 4, 5 \}$. Note that if $C = \{1, 2, 6 \}$ then $C \not \subset A$ since $6 \in C$ but $6 \not \in A$.

We are now ready to look at another result on nonempty finite sets which tells us that the elements in a nonempty finite set can be ordered from smallest to largest.

 Lemma 1: A nonempty finite set of real numbers can be ordered from the smallest element to the largest element.
• Proof: Let $A$ be a nonempty finite set of real numbers. If $\lvert A \rvert = 1$ then clearly the elements in $A = \{ x_1 \}$ can be ordered from smallest to largest. Assume that $\lvert A \rvert = m > 1$. Since $A$ is a finite set, we have that there exists a minimum value, say $x_1 \in C$, and a maximum value, say $x_m \in C$. Consider the subset $A_1 \subset A$ defined as $A_1 = \{ x_2, x_3, ..., x_{m-1} \}$. This set is also a finite set with $m - 2$ elements and so there exists a minimum value, say $x_2 \in A_1$, and a maximum value, say $x_{m-1} \in A_1$. We continue to consider $A_2 \subset \subset A_1 \subset A$ where $A_2$ is defined analogously in this manner and this process must eventually terminate with the size of each successive subset approaching zero. We can therefore order the elements of $C$ as desired:
(1)
\begin{align} x_1 < x_2 < ... < x_m \quad \blacksquare \end{align}

With the lemma above, we can now show that the set $C = \{ x \in \mathbb{R} : 0 \leq x \leq 1 \}$ is an infinite set.

 Lemma 2: The set $C = \{ x \in \mathbb{R} : 0 \leq x \leq 1 \}$ is an infinite set.
• Proof: Assume that $C$ is actually a finite set. Clearly this set is nonempty since $0 \in C$, so there exists a positive integer $m$ such that $\lvert A \rvert = m$. Since $C$ is a nonempty finite set of real numbers we have that the elements of $C$ can be ordered as:
(2)
\begin{align} \quad 0 = x_1 < x_2 < ... < x_m = 1 \end{align}
• Now consider the element $y = \frac{x_2 - x_1}{2}$, i.e, the number that is in between $x_1$ and $x_2$. This number is a real number and clearly $0 = x_1 < y < x_2 < ... < x_m = 1$ so $y \in C$. However, $y \neq x_n$ for each $n = 1, 2, ..., m$ so $C$ contains at least $m+1$ elements which is a contradiction. Therefore our assumption that $C$ is a finite set is wrong. $\blacksquare$
 Lemma 3: Let $B \subseteq A$. Then: a) If $A$ is a finite set then $B$ is a finite set. b) If $B$ is an infinite set then $A$ is an infinite set.
• Proof of a): Let $A$ be a finite set. If $A$ is the empty set then $B$ must also be the empty set and so $B$ is also finite. If $A$ is nonempty then there exists a positive integer $m$ such that $\lvert A \rvert = m$. Now suppose that $B$ is instead an infinite set. Consider any $m+1$ elements in $B$. These elements must all be in $A$ since $B \subseteq A$ but then $A$ has at least $m + 1$ elements which is a contradiction. Therefore the assumption that $B$ is an infinite set is false and so $B$ is a finite set.
• Proof of b) This follows immediately as the contrapositive of a). $\blacksquare$

We are now ready to prove that the set of real numbers is an infinite set - a somewhat obvious statement though.

 Theorem 1: The set of real numbers $\mathbb{R}$ is an infinite set.
• Proof: Define $C = \{ x \in \mathbb{R} : 0 \leq x \leq 1 \}$. In Lemma 2 we saw that $C$ is an infinite set. Furthermore, it's clear that $C \subseteq \mathbb{R}$ and so by Lemma 3 we have that $\mathbb{R}$ must also be an infinite set. $\blacksquare$

Another important thing that we should discuss is the equality of two sets which we define below.

 Definition: The sets $A$ and $B$ are said to be equal if $A \subseteq B$ and $B \subseteq A$ denoted by $A = B$.

It is very important to note that to prove that two sets are equal we must show that both sets are subsets of each other. For all of the sets we have looked at thus far - it has been intuitively clear whether or not the sets are equal. However, two sets may be equal despite it not being clear whether they are or not at first site.

Consider the following real-valued function:

(3)
\begin{align} \quad f(x) = \frac{x^2 + 2x + 1}{x^2 - 9} \end{align}

Define $D(f)$ to be the domain of the function $f$ which in itself is the set:

(4)
\begin{align} \quad D(f) = \{ x \in \mathbb{R} : f(x) \in \mathbb{R} \} \end{align}

Now consider the following set:

(5)
\begin{align} \quad A = \{ x : x \in \mathbb{R} \: \mathrm{and} \: x \neq \pm 3 \} \end{align}

Is it true that $D(f) = A$? Indeed it is. Note that $f$ is defined on all of $\mathbb{R}$ except when $x = \pm 3$ since $f(3)$ and $f(-3)$ are undefined in making the denominator of $f$ equal to $0$. Therefore $D(f)$ is the set of all real numbers excluding $3$ and $-3$ which is precisely $A$, i.e, $D(f) = A$.