0.2. Subsets

https://giphy.com/gifs/infinite-boxes-vG1Dgq3JRXLMc

Consider a set $A = \{2, 3, 7\} \text{ and } B = \{2, 3, 4, 5, 6, 7\}.$ Note that every element in set A is also found in set B, however, the reverse is not true (B contains elements 4, 5 and 6 which are not in A)

Consider another case, $A = \{2n: n \in \mathbb{ N }\} = \{ 0, 2, 4, 6, ... \} \text { and } B = \mathbb{Z} = \{ ..., -2, -1, 0, 1, 2, ... \}.$ Again, we can see that every element in set A is also found in set B and similarly, everything in B cannot be found in set A. B contains negative and odd integers, which are not in A.

To describe this phenomena, mathematicians defined subsets:

$def^n$ Suppose A and B are sets. If every element in A is an element of B, then A is a subset of B and we denote this as $A \subseteq B$

If B is not a subset of A, as in the above cases, then there exists at least one element, say $x \in B \text{ such that } x \notin A. \text{ We denote this as } B \subsetneq A$

e.g.1. $\{2, 3, 5, 7, ... \} \subseteq \mathbb{ N }$ but $\{\frac{1}{3}, 2, 5, 7, ... \} \subsetneq \mathbb{ N }$ since $\frac{1}{3} \in \mathbb{ Q }$

e.g.2. $\mathbb { N } \subseteq \mathbb { Z } \subseteq \mathbb{ Q } \subseteq \mathbb{ R }$

e.g.3. $(\mathbb{ R } \times \mathbb{ N }) \subseteq (\mathbb{ R } \times \mathbb{ R })$ since $(\mathbb{ R } \times \mathbb{ N }) = \{(x, y): x \in \mathbb{ R }, y \in \mathbb{ N }\}$ and $( \mathbb{ R } \times \mathbb{ R }) = \{ (x, y): x \in \mathbb{ R }, y \in \mathbb{ R } \}$ Hint: look at what sets y is in

Every set is a subset of itself :

e.g.1. $A = \{ x, y, z, \} \subseteq B \text{ if and only if } B = \{ x, y, z, \}$

e.g.2. $B = \{ 4, 7, 8, P, Z \} \subseteq B =\{ 4, 7, 8, P, Z \}$

e.g.3. $\mathbb{ N } \subseteq \mathbb{ N }$

Likewise, the empty set ( $\{\} \text{ or } \varnothing$ ) is a subset of every set (i.e. $\varnothing \subseteq B$ , where B is any set). To understand this, let’s look at the following case:

Set A = { 1, 2, …., 10} has the numbers 1 to 10 as elements. We can remove 10 from set A and the remaining set will be A = { 1, 2, …, 9}. Again, we can remove element 9 from the set and we’ll have A = {1, 2, …, 8}. We can continue doing this until we have set A = { 1 }. When we remove the last element, 1, from the set, we will be left with A = {}. This is the empty set.

Hence every element that contains at least one element (i.e. a non-empty set), can have all its elements removed until only the empty set is left. In this sense, we can think of the empty set as reaching the “simplest possible form” for the set.

If we start with the empty set, there is nothing to remove. So we are at “simplest form” for our set.

We can also imagine that we start with the empty set before we add elements into a set. Thus we say every set has a the empty set as a subset.

To determine the subsets of a set, we know two already: the empty set and the set itself. To determine the additional subsets, let’s look at some examples:

e.g.1. List the all the subsets of $C = \{ 1, 2, \{1, 3\} \}$

Since C has three elements, namely 1, 2 and {0,3} then the subsets of C are:

$\varnothing, \{1\}, \{2\}, \{\{1, 3\}\}, \{1, \{1, 3\} \}, \{2, \{1, 3\}\}, \{1, 2, \{1, 3\}\}$

So the additional subsets are made by taking each element and forming single subsets, then combining the elements with all possible combinations.

e.g.2 List the all the subsets of $D = \{ \mathbb { Q }, 2, \varnothing \}$

D has three elements: Q, 2, and { }. So we know we can make single subsets out of each element, then we can match the elements in different combinations to make the other subsets:

$\varnothing, \{ \mathbb { Q }\}, \{2\}, \{\varnothing\}, \{ \mathbb { Q }, 2\}, \{ \mathbb { Q }, \varnothing \}, \{2, \varnothing \}, \{ \mathbb { Q }, 2, \varnothing\}$

Note: In both of the above examples, we had 3 elements in the sets C and D. This resulted in 8 subsets (i.e. $2^3 = 8$ )

e.g.3. List the all the subsets of $E = \{ \{ \mathbb{R } \} \}$

Since E has 1 element, $\{ \mathbb{ R } \}$ , so the possible subsets are:

$\varnothing \text{ and } \{ \mathbb{ R } \}$

e.g.4. $F = \{ \varnothing \}$

Since set F has one element, the empty set, hence has subsets:

$\varnothing \text{ and } \{ \varnothing \}$

Note: Again, in the above examples, we had one element in sets E and F which resulted in 2 subsets: the empty set and the set containing the one element (i.e. $2^1 = 2$ )

We can see that there is a common method of determining how many subsets a finite set will have:

$2^n = 2, \text{ where n is the number of elements in a set }$

Look at the following examples to understand the difference between a subsets and the elements of a set:

e.g.1. For $G =\{2, \{1\}\}$ , we can conclude the following:

$2 \in \{2, \{1\} \}$ Since 2 is an element of set G (2 is listed as the first element of set G)
$\{1\} \in \{2, \{1\}\}$ Since set { 1 } is an element of G ({ 1 } is listed as the second element of set G)
$\{1\} \subseteq \{2, \{1 \}\}$ Since set { 1 } is a subset of G
${2} \subsetneq \{2, \{1 \} \}$ Since 2 is not a set, hence cannot be a subset
$\varnothing \subseteq G$ Since the empty set is a subset of every set
$G \subseteq G$ Since every finite set is a subset of itself
G has 4 subsets. We know we have 4 subsets, namely $\varnothing, \{2 \}, \{\{ 1 \} \} \text{ and } \{2, \{1\}\}$ because $2^2 = 4,$

e.g.2. For $\text{ H } =\{\varnothing, \mathbb{ N } \}$ , we can conclude the following:

$\varnothing \in H$ Since { } is an element of H (namely, the first element of set H)
$\varnothing \subseteq H$ Since { } is the empty set and we know the empty set is the subset of every set. Furthermore, { } is explicitly a subset of H
$H \subseteq H$ Since Every set is a subset of itself
$\mathbb{ N } \in H$ Since $\mathbb{ N }$ is an element of H (namely, the second element of set H)
$\{ \mathbb{ N } \} \notin H$ Since $\{ \mathbb{ N } \}$ is not an element of H. However, $\mathbb{ N }$ is an element of $\{ \mathbb{ N } \}$ which is still not in H.
$\{ \mathbb{ N } \} \subsetneq H$ Since $\{ \mathbb{ N } \}$ is not a subset of H, however $\mathbb{ N } \subset H$