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
Meaning of the used symbols
| Symbol | Meaning |
|---|---|
| \(\subseteq\) | is a subset of |
| \(\Longleftrightarrow\) | if and only if (iff) |
| \(\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
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\):
- \(\{\}\)
- \(\{\alpha\}\)
- \(\{\beta\}\)
- \(\{\{\bigstar\}\}\)
- \(\{\alpha, \beta\}\)
- \(\{\alpha, \{\bigstar\}\}\)
- \(\{\beta, \{\bigstar\}\}\)
- \(\{\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
Meaning of the used symbols
| Symbol | Meaning |
|---|---|
| \(\nsubseteq\) | is not a subset of |
| \(\Longleftrightarrow\) | if and only if (iff) |
| \(\exists\) | there 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.