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