Defined Piece by Piece - Subset
Definition
If $A$ and $B$ are sets, then $A$ is called a subset of $B$, if, and only if, every element of $A$ is also an element of $B$.
Notation
\[A \subseteq B \Longleftrightarrow \forall \; x\; (x \in A \Longrightarrow x \in B).\]Meaning of the used symbols
| Symbol | Meaning |
|---|---|
| $ \subseteq $ | is a subset of |
| $ \Longleftrightarrow $ | if, and only if |
| $ \forall $ | for all (universal quantifier) |
| $ \in $ | is an element of |
| $ \Longrightarrow $ | if, then |
Example
Let $A$ and $B$ be the following (finite) sets: $A = \{1, 3, 5, \{6\}\}$, $B = \{1, 2, 3, 4, 5, \{6\}\}$. All elements of $A$ are the four elments 1, 3, 5, and $\{6\}$. All four elements are in $B$. Therefore, $A$ is indeed a subset of $B$. We can therefore write $A \subseteq B$.
Enumerating all the subsets of a set
Let’s say that we want to enumerate all the possible subsets of a finite set. The question arises as to how we can do this without running the risk of forgetting a possible subset. Actually, there is a useful method: For the sake of simplicity, let’s imagine that the set $C$ has only one element: $ C = \{ \alpha \} $. Now, by definition of subset, $C = \{\alpha\} $ itself is a possible subset of $C$. We could also remove the element $\alpha$ from it. And now, also $ C = \{\}$ is a possible subset. So basically, for each element in a set, either the element is included in the subset or it’s not. Therefore, the possible subsets of $C$ are actually two.
Now, let $D$ be the following (finite) set: $ D = \{\alpha, \beta, \{\bigstar\}\}$. As we have seen in the previuous example, each of the three elements is either contained in the subset or not, so $\alpha$ is in $\boxdot$ or out $\square$ (two possibilities), $\beta$ is in $\boxdot$ or out $\square$ (two possibilities), and finally $\{\bigstar\}$ is in $\boxdot$ or out $\square$ (two possibilities), which we can also denote as $2 \times 2 \times 2 = 2^{3} = 8$. If we generalize this, we get the following formula for calculating all the subsets of a set, that is
\[2^{n}\]where $n$ is the number of elements in the (finite) set at hand. As we have seen, by using the method described, the total number of subsets of set $D$ is $8$:
| 1. | $ \{\} $ |
| 2. | $ \{\alpha\}$ |
| 3. | $ \{\beta\}$ |
| 4. | $ \{ \{ \bigstar \} \}$ |
| 5. | $ \{ \alpha, \beta \}$ |
| 6. | $ \{ \alpha, \{ \bigstar \} \}$ |
| 7. | $ \{ \beta, \{ \bigstar \} \}$ |
| 8. | $ \{ \alpha, \beta, \{ \bigstar \} \}$ |
Negation of the definition of subset
Starting from he formal definition of a subset, a set $A$ is not a subset of another set $B$, if not every element of $A$ is also contained in set $B$. That is, if there is at least one element in set $A$, that is not contained in set $B$.
Notation of the negation
\[A \nsubseteq B \Longleftrightarrow \exists \; x\; (x \in A \wedge x \notin B).\]Meaning of the used symbols
| Symbol | Meaning |
|---|---|
| $ \nsubseteq $ | is not a subset of |
| $ \Longleftrightarrow $ | if, and only if |
| $ \exists $ | it exists (existential quantifier) |
| $ \in $ | is an element of |
| $ \wedge $ | and |
| $ \notin $ | is not an element of |
Non-example of a subset
Let A and B be the following sets: $A = \{1, 3, 5, 6\}$, $B = \{1, 2, 3, 4, 5\}$. All elements of $A$ are the four elments 1, 3, 5, and 6. But there is at least one element of A, that is not containted in set B: the element 6 in our example. Therefore, A is not a subset of B ($A \nsubseteq B$).
Jargon-free explanation
Given two boxes, if all the objects of the first box are contained within the second box, the first box is said to be a subset of the second box. The second box may - but doesn’t need to - contain supplementary objects which are not contained within the first box. That’s why the symbol that expresses “is a subset of” $\subseteq$ contains also some sort of equals sign.
If we imagine the sets as boxes and the subsets as possible configurations of boxes, then it is clear that a box can of course also be empty.