1 Sets
A set is a collection of objects, and the objects in it are its elements. That is all the word means: a set is decided entirely by which objects belong to it, not by how they are listed, how often, or in what order. So \(\{1,2,3\}\), \(\{3,2,1\}\) and \(\{1,2,2,3\}\) are the same set.
If \(A\) is a set and \(x\) an object, we write \(x\in A\) to mean that \(x\) belongs to \(A\), and \(x\notin A\) to mean that it does not.
Sets are described in two ways. Roster notation lists the elements between braces, as above. Set-builder notation states the property that the elements share: \[A=\{x: x \text { is an even integer and } 2\leq x\leq 10\}.\] The colon is read “such that”, and some texts use a vertical bar for it. Roster notation is only available when the elements can actually be listed; set-builder notation always works, and is the only option for infinite sets.
Definition 1.2 (Subset). If \(A\) and \(B\) are sets, \(A\) is a subset of \(B\), written \(A\subset B\), if every element of \(A\) is an element of \(B\): \[A\subset B \iff \left (x\in A \implies x\in B\right ).\]
Definition 1.3 (Equality of sets). Two sets \(A\) and \(B\) are equal if both inclusions hold, \(A\subset B\) and \(B\subset A\).
Note 1.4. This is the standard way to prove two sets equal, and it is worth stating plainly because almost every proof in this chapter uses it: to show \(A=B\), take an arbitrary \(x\in A\) and show \(x\in B\), then take an arbitrary \(x\in B\) and show \(x\in A\). Two inclusions, two halves of the argument.
Note 1.5. On the symbol. These notes write \(A\subset B\) for “\(A\) is a subset of \(B\)”, allowing \(A=B\). Many books write \(A\subseteq B\) for that and reserve \(A\subset B\) for a proper subset, one where \(A\neq B\). Both conventions are in use, so check which a book means before relying on it. Here \(A\subset A\) is true for every set \(A\).
Definition 1.6 (Empty set). The empty set, or null set, is the set with no elements, written \(\emptyset \).
Note 1.7. \(\emptyset \) is a subset of every set. This surprises people, so here is why. To fail to be a subset of \(B\), a set would need an element that is not in \(B\). The empty set has no elements at all, so it has no such element, and the condition \(x\in \emptyset \implies x\in B\) is never put to the test — there is no \(x\) to test it on. A statement that cannot be broken is true, and this one is said to hold vacuously.
Note also that \(\emptyset \) and \(\{\emptyset \}\) are different. The first has no elements; the second has exactly one element, which happens to be the empty set.
Definition 1.8 (Universal set). The universal set is the set containing every element under discussion in a given problem, written \(E\).
Note 1.9. The universal set is not fixed once and for all — it is chosen to suit the problem. For a question about digits, \(E=\{0,1,\dots ,9\}\); for one about people in a village, \(E\) is that village. Some books write \(U\) for it. Do not write \(\bigcup \), which is the symbol for taking the union of a family of sets and is an operator, not a set.
Definition 1.10 (Complement). Let \(E\) be the universal set and \(A\subset E\). The complement of \(A\), written \(A'\), is the set of elements of \(E\) not in \(A\): \[A'=\{x\in E : x\notin A\}.\]
Example 1.11. Let \(E=\{1,2,3,4,5,6,7\}\) and \(A=\{3,4,5,7\}\). The elements of \(E\) that are not in \(A\) are \(1\), \(2\) and \(6\), so \[A'=\{1,2,6\}.\] Check the count: \(A\) has \(4\) elements, \(A'\) has \(3\), and together they make the \(7\) elements of \(E\) with none repeated. Every element of \(E\) is in exactly one of \(A\) and \(A'\).
Definition 1.12 (Difference). Let \(A\) and \(B\) be sets. The difference \(B-A\) is \[B-A=\{x : x\in B \text { and } x\notin A\}.\]
Example 1.13. Let \(A=\{2,3,4,5,6,7,8\}\) and \(B=\{0,1,2,3,4,5\}\). The elements of \(B\) that avoid \(A\) are \(0\) and \(1\), so \(B-A=\{0,1\}\).
Note that \(A-B=\{6,7,8\}\), which is a different set. Unlike addition, the difference of sets depends on the order.
Note 1.14. Complement and difference are the same operation. Taking \(B=E\) gives \(E-A=A'\), so the complement is just the difference from the universal set. This is why \(A-B=A\cap B'\), an identity used constantly in simplification.
Definition 1.15 (Cardinality). The cardinality of a finite set \(A\), written \(n(A)\) or \(\left |A\right |\), is the number of elements it contains. Thus \(n(\{2,4,6\})=3\) and \(n(\emptyset )=0\).
Definition 1.16 (Power set). The power set of \(A\), written \(\mathcal {P}(A)\), is the set of all subsets of \(A\).
Example 1.17. Let \(A=\{a,b\}\). Its subsets are \(\emptyset \), \(\{a\}\), \(\{b\}\) and \(\{a,b\}\), so \[\mathcal {P}(A)=\left \{\emptyset ,\{a\},\{b\},\{a,b\}\right \}, \quad n\left (\mathcal {P}(A)\right )=4 .\] In general a set with \(n\) elements has \(2^{n}\) subsets, since each element is either in a given subset or not, independently of the others — \(n\) choices with two options each.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.