1.1 Sets
Definition 1.1.1. A set is a well defined collection of objects, called the elements or members of the set. We write \(x\in X\) to say that \(x\) is an element of \(X\), and \(x\notin X\) to say that it is not.
The standard sets of numbers
Five sets of numbers occur throughout the course, and it is worth being clear from the start about what separates them, because the differences are easy to blur.
- \(\mathbb {N}\)
- Natural numbers — the counting numbers \(1,2,3,\dots \) There is a first one and no last one.
- \(\mathbb {Z}\)
- Integers — the natural numbers together with zero and the negatives: \(\dots ,-2,-1,0,1,2,\dots \) What \(\mathbb {Z}\) adds to \(\mathbb {N}\) is the ability to subtract freely: \(3-5\) is an integer but not a natural number.
- \(\mathbb {Q}\)
- Rational numbers — all fractions \(\frac {p}{q}\) with \(p,q\in \mathbb {Z}\) and \(q\neq 0\), for example \(\frac {1}{2}\), \(-\frac {3}{4}\), \(\frac {7}{1}=7\). What \(\mathbb {Q}\) adds is division: \(1\div 2\) is rational but not an integer. Note that every integer is rational, taking \(q=1\).
- \(\mathbb {R}\)
- Real numbers — every point on the number line. This adds the irrational numbers, those that cannot be written as a fraction at all, such as \(\sqrt {2}\), \(\pi \) and \(e\). This is the distinction learners most often lose: \(\sqrt {2}\) is a perfectly good real number, but no fraction equals it.
- \(\mathbb {C}\)
- Complex numbers — all numbers \(a+bi\) with \(a,b\in \mathbb {R}\) and \(i^2=-1\). This adds square roots of negative numbers: \(\sqrt {-1}\) is complex but not real.
Each set contains the one before it, a fact recorded as Example 1.1.3 below.
Definition 1.1.2. Let \(X\) and \(Y\) be two sets. If every element of \(X\) is also an element of \(Y\), then \(X\) is said to be a subset of \(Y\) \((X\subset Y)\).
Example 1.1.3. We have \(\mathbb {N}\subset \mathbb {Z}\subset \mathbb {Q}\subset \mathbb {R}\subset \mathbb {C}\).
Definition 1.1.4. Let \(X\) and \(Y\) be two sets. Then
- i.
- \(X\cup Y=\{x: x\in X \ \text { or }\ x\in Y\}\), the union of \(X\) and \(Y\);
- ii.
- \(X\cap Y=\{x: x\in X \ \text { and }\ x\in Y\}\), the intersection of \(X\) and \(Y\);
- iii.
- \(X-Y=\{x: x\in X \ \text { and }\ x\notin Y\}\), the difference of \(X\) and \(Y\);
- iv.
- \(X\bigtriangledown Y=\{x: x\in X-Y \ \text { or }\ x\in Y-X\}\), the symmetric difference of \(X\) and \(Y\).
Read the connectives carefully: the union asks for “or”, the intersection for “and”, and the difference for “in the first but not the second”. The symmetric difference collects what lies in exactly one of the two — it is the union with the intersection removed.
Example 1.1.5. Let \(X=\{1,3,5,7\}\) and \(Y=\{1,2,4,6\}\). Then all four operations of Definition 1.1.4 can be read off the same two lists: \begin {align*} X\cup Y &=\{1,2,3,4,5,6,7\} &&\text {everything appearing in either list}\\ X\cap Y &=\{1\} &&\text {the only element in both}\\ X-Y &=\{3,5,7\} &&\text {in }X\text {, absent from }Y\\ Y-X &=\{2,4,6\} &&\text {in }Y\text {, absent from }X\\ X\bigtriangledown Y &=\{2,3,4,5,6,7\} &&(X-Y)\cup (Y-X) \end {align*}
Notice the check available at the end: \(X\bigtriangledown Y\) is \(X\cup Y\) with the single shared element \(1\) removed, which is what the last line says.
Definition 1.1.7. The Cartesian product of two sets \(X\) and \(Y\) is the set of ordered pairs defined by \[X\times Y=\{(x,y):x\in X\qquad \text {and}\qquad y\in Y\}\]
Example 1.1.8. If \(X=\{0,2\}\), \(Y=\{1,3\}\) are subsets of \(U=\{0,1,2,3,4,5\}\) then \(X^c=\{1,3,4,5\}\) and \(X\times Y=\{(0,1),(0,3),(2,1),(2,3)\}\) \[\mathbb {R}\times \mathbb {R}=\{(x,y):x,y\in \mathbb {R}\}=\mathbb {R}^2\]
The next theorem provides some of the properties of the sets.
Theorem 1.1.9. If \(X, Y\) and \(Z\) are sets, then:
- i.
- \((X\cup Y)\cup Z=X\cup (Y\cup Z)\)
- ii.
- \((X\cap Y)\cap Z=X\cap (Y\cap Z)\)
- iii.
- \(X\cap (Y\cup Z)=(X\cap Y)\cup (X\cap Z)\)
- iv.
- \(X\cup (Y\cap Z)=(X\cup Y)\cap (X\cup Z)\)
Proof. Each part is proved by taking an arbitrary element and rewriting the condition for membership. Every step is an equivalence, so the two sets have exactly the same elements and are therefore equal.
- i.
- For any \(x\), \begin {align*} x\in (X\cup Y)\cup Z &\iff x\in X\cup Y \ \text { or }\ x\in Z\\ &\iff (x\in X \ \text { or }\ x\in Y) \ \text { or }\ x\in Z\\ &\iff x\in X \ \text { or }\ (x\in Y \ \text { or }\ x\in Z)\\ &\iff x\in X \ \text { or }\ x\in Y\cup Z\\ &\iff x\in X\cup (Y\cup Z). \end {align*}
The middle step is the fact that “or” is associative.
- ii.
- For any \(x\), \begin {align*} x\in (X\cap Y)\cap Z &\iff x\in X\cap Y \ \text { and }\ x\in Z\\ &\iff (x\in X \ \text { and }\ x\in Y) \ \text { and }\ x\in Z\\ &\iff x\in X \ \text { and }\ (x\in Y \ \text { and }\ x\in Z)\\ &\iff x\in X \ \text { and }\ x\in Y\cap Z\\ &\iff x\in X\cap (Y\cap Z). \end {align*}
- iii.
- For any \(x\), \begin {align*} x\in X\cap (Y\cup Z) &\iff x\in X \ \text { and }\ x\in Y\cup Z\\ &\iff x\in X \ \text { and }\ (x\in Y \ \text { or }\ x\in Z)\\ &\iff (x\in X \ \text { and }\ x\in Y) \ \text { or }\ (x\in X \ \text { and }\ x\in Z)\\ &\iff x\in X\cap Y \ \text { or }\ x\in X\cap Z\\ &\iff x\in (X\cap Y)\cup (X\cap Z). \end {align*}
The third step is the one doing the work: it is the distribution of “and” over “or”. The brackets matter, and are the reason the statement is not merely a rearrangement.
- iv.
- For any \(x\), \begin {align*} x\in X\cup (Y\cap Z) &\iff x\in X \ \text { or }\ x\in Y\cap Z\\ &\iff x\in X \ \text { or }\ (x\in Y \ \text { and }\ x\in Z)\\ &\iff (x\in X \ \text { or }\ x\in Y) \ \text { and }\ (x\in X \ \text { or }\ x\in Z)\\ &\iff x\in X\cup Y \ \text { and }\ x\in X\cup Z\\ &\iff x\in (X\cup Y)\cap (X\cup Z). \end {align*}
This is the mirror image of (iii), with the roles of \(\cup \) and \(\cap \) exchanged — “or” distributes over “and” just as “and” distributes over “or”.
This theorem gives more properties of sets.
Theorem 1.1.10 (De Morgan’s theorem). If \(X\) and \(Y\) are any two sets, then
- 1.
- \((X\cup Y)^c=X^c\cap Y^c\)
- 2.
- \((X\cap Y)^c=X^c\cup Y^c\)
Proof.
- 1.
- For any \(x\), \begin {align*} x\in (X\cup Y)^c &\iff x\notin X\cup Y\\ &\iff x\notin X \ \text { and }\ x\notin Y\\ &\iff x\in X^c \ \text { and }\ x\in Y^c\\ &\iff x\in X^c\cap Y^c. \end {align*}
The second step is the point: to fail to be in \(X\cup Y\) is to be in neither of them, so the “or” in the union becomes an “and”.
- 2.
- For any \(x\), \begin {align*} x\in (X\cap Y)^c &\iff x\notin X\cap Y\\ &\iff x\notin X \ \text { or }\ x\notin Y\\ &\iff x\in X^c \ \text { or }\ x\in Y^c\\ &\iff x\in X^c\cup Y^c. \end {align*}
Here the “and” becomes an “or”: to fail to be in both is to fail to be in at least one.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.